Combinatronics
Combinatronics
The Four Relevant Factors
Four things you need to identify for any combinatorics question:
- Combination or Permuation: Are we counting βresulting selectionβ with same items but differently ordered just once (combination) or for each different order (permuations)?
- With or Without Repetition: Are we selecting from types of objects or individual object instances? I.e. Can we have the same item type appear more than once in a resulting selection?
- Resulting Selection Size (π): the number of instances of item in the resulting selection (a.k.a. the sample size)
- Number of Object Types (π): number of types of the item we are selecting from (a.k.a. the number of objects).
Combination vs Permutation:
Each combination of π items has many ways of arranging the order, known as permutations. Assuming no repetition of object types, there are π! permutations for each combination. If there is repetition, there is a much more complicated equation for the ratio.
- In a βcombinationβ the order is irrelevant and we count each time the same item types appears in the resulting selection but ignore combinations with a different order. Each combination has a number of possible permutations, which we ignore. E.g. in a slot machine where πππ == πππ == πππ etc. Collectively, the 6 possible βpermutationsβ only represent 1 combination, and we only count the combinations. Another example of a combination is selecting people for a committee.
- In a βpermutationβ, the order is relevant and we count every order of object types that appears in the resulting selection. E.g. Numbers in a combination lock, or a committee with assigned roles.
With or Without Repetition
- With Repetitions: Allow and count the repeating object types in the resulting selection. This is when there is a pool of object types rather than actual object instances. E.g. numbers, categories of objects.
- Without repetitions: Donβt count or allow repeating objects types in the resulting selection. This is when there is a pool of individual instances of objects which can only be selected once E.g. physical objects or people.
Resulting Selection Size (π)
- π: A Sample a.k.a. βResulting selectionβ , contains βπβ item instances.
Number of Object Types (π)
- π: The pool of objects contains βπβ object types.
The Equations
All combinations (with or without repetition) and permutations (without repetition) are found using some version of the binomial coefficient equation:. This equation, often vocalised as βπ choose πβ or βπ choose πβ is expressed as either: $nCr$ or, $\binom{n}{r}$. \(\binom{n}{r} = \frac{n!}{r!(n-r)!}\)
-
Combination
(π is Unordered)Permutation
(π is Ordered)-
Without Repetition
(Instances of π)Combination \(\binom{n}{r}\) Permuation without repetition \(r!\binom{n}{r}\) With Repetition
(Types of π)Multiset \(\binom{n+r-1}{r}\) Permuation with repetition\(n^r\)
-
Scientific calculators often have the binomial coefficient function normally written as β$nCr$β or β$\binom{n}{r}$β as above. The Windows 10 calculator doesnβt have this function, so the easiest way for quick calculation is to find an online calculator such as this.
Examples
Lets take the examples of a slot machine, committee, role assignment and a combination lock. Each example has a result selection (π) of 3 and 10 object types or instances (π).
| Example | Slot machine Combinations | Committee Membership | Role Assignment | Combination Lock Code Permutations |
|---|---|---|---|---|
| Example of Resulting Selection | ![[Pasted image 20220831035806.png]] | ![[Pasted image 20220831050703.png]] | ![[Pasted image 20220831051434.png]] | ![[Pasted image 20220831055329.png]] |
| Object Types | ![[Pasted image 20220831041049.png]] or blank | ![[Pasted image 20220831055814.png]] | ![[Pasted image 20220831055814.png]] | ![[Pasted image 20220831041857.png]] |
| π | \(π=3\) | \(π=3\) | \(r=3\) | \(π = 3\) |
| π | \(π=10\) | \(π=10\) | \(π=10\) | \(π=10\) |
| Combination or Permuation | Combination (Unordered) | Combination (Unordered) | Permutation (Ordered) | Permutation (Ordered) |
| With or without Repetition | With Repetitions (types) | Without Repetitions (Instances) | Without Repetitions (Instances) | With repetitions (Types) |
| Equation | Multiset \(\binom{n+r-1}{r}\) | Combination \(\binom{n}{r}\) | Permuation without repetition\(r!\binom{n}{r}\) | Permuation with repetition \(n^r\) |
| Count | \(220\) | \(120\) | \(720\) | \(1000\) |