Combination

From Maths
(Redirected from Combinations)
Jump to: navigation, search
See: Combinations and permutations for an informal (word/colloquial) definition and discussion of what a combination and indeed a permutation is.

Definition

A combination is the name given to any selection from none to possibly all of items from a pool of items. A combination is defined purely in terms of which items are selected from the pool not by what order they were selected in (in contrast to a permutation), and indeed itself provides no notion for "what order the items come in" for either the pool or the combination.


We usually speak about "choosing a subset (of a set)"[Note 1] with combinations.

Length

If asked "to choose a combination of [ilmath]n[/ilmath] items" this means we must choose exactly [ilmath]n[/ilmath] from some pool containing [ilmath]n[/ilmath] or more items. So all the combinations of length [ilmath]n[/ilmath] of a set [ilmath]A[/ilmath] correspond to all the items in [ilmath]\mathcal{P} [/ilmath][ilmath](A)[/ilmath] of cardinality (or length) [ilmath]n[/ilmath].

  • Thus we may write the set of combinations of length [ilmath]n[/ilmath] from [ilmath]A[/ilmath] as:
    • [ilmath]\{X\in\mathcal{P}(A)\ \vert \#(X)\eq n\} [/ilmath]

Caveat: Combination lock

Summary: "Combination" locks ought to be called permutation locks instead

A combination lock is the unfortunate term given to a device which has a finite and fixed number of wheels or dials with some number (usually the same for each wheel or dial) of distinct letters, numbers or symbols on them which will unlock if each dial or wheel is in its correct position.

For example a common bike lock might have 4 wheels (we'll call A, B, C and D) each with numbers [ilmath]0[/ilmath] to [ilmath]9[/ilmath] inclusive on them. The code might be [ilmath]1234[/ilmath], indicating A[ilmath]\eq 1[/ilmath], B[ilmath]\eq 2[/ilmath], C[ilmath]\eq 3[/ilmath] and D[ilmath]\eq 4[/ilmath] are the positions required to unlock the lock.

If the device was a true "combination" lock, it would not matter which wheel to which value, only that the values shown contained one wheel showing "[ilmath]1[/ilmath]", one wheel showing [ilmath]2[/ilmath], one wheel showing [ilmath]3[/ilmath] and one wheel showing [ilmath]4[/ilmath].

Requiring the values shown to be in a certain order makes the correct value to unlock the permutation [ilmath]1234[/ilmath]

The combination [ilmath]\{1,\ 2,\ 3,\ 4\} [/ilmath] being the unlock combination would mean any of the following permutations would open the lock:

[ilmath]1234[/ilmath], [ilmath]1243[/ilmath], [ilmath]1423[/ilmath], [ilmath]1432[/ilmath], [ilmath]4132[/ilmath], [ilmath]4312[/ilmath], [ilmath]4321[/ilmath], [ilmath]\ldots[/ilmath]

and several more.

In fact there are [ilmath]4\times 3\times 2\times 1\eq 24[/ilmath] different permutations that would open this lock if it were a true combination lock.

Notes

  1. It is important that we consider this for a set, not a multiset. That is to say a thing must occur either once or not at all in the set and the subset, in a multiset things may occur not at all, once, twice, so forth
Grade: B
This page requires some work to be carried out
Some aspect of this page is incomplete and work is required to finish it
The message provided is:
I'm not sure why but I don't like this. Same reason as Combinations page. Alec (talk) 16:32, 14 April 2018 (UTC)

Warning:That grade doesn't exist!