Combinatronics is the mathematics which enables you to calculate the number of different combinations you can get when you make a selection from a population. E.g. You have a bag of 10 uniquely balls. How many different ways are there of selecting 3 balls?

The number of unique types of balls in the bag (10) is called the population, denoted with 𝒏. If there were two balls considered β€˜the same’ in a bag of 10, the population 𝒏 would be 9. The number of items in the selection (3) is denoted by 𝒓.

It is very important to note that this has nothing to do with probability. The examples of bags and balls are also very often used for probability thought experiments.

The Four Relevant Factors

Four things you need to identify for any combinatorics question:

  1. Combination or Permutation: Combinations are unordered selections, permutations are ordered selections.
  2. With or Without Repetition: Can we have the same item type appear more than once in a resulting selection? I.e. Are we selecting from types of objects or individual object instances?
  3. Selection (𝒓): the number of instances of item in the resulting selection (a.k.a. the sample size)
  4. Population (𝒏): number of types of the item we are selecting from.

Combination vs Permutation

Each selection of size 𝒓 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 with three rollers where the permutations collectively count as 1 combination
    • I.e. πŸ‡πŸπŸŠ ≑ πŸπŸ‡πŸŠ ≑ πŸπŸŠπŸ‡.
  • 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 where the distinction between permutations is important.
    • I.e. 1️⃣2️⃣3️⃣ β‰  2️⃣3️⃣1️⃣ β‰  3️⃣1️⃣2️⃣

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.

Selection (𝒓)

  • 𝒓: A Sample a.k.a. β€˜Resulting selection’ , contains β€˜π’“β€™ item instances.

Population (𝒏)

  • 𝒏: 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)!}\]
With or without Repetition Combination
(𝒓 is Unordered)		 Permutation
(𝒓 is Ordered)
Without Repetition
(Instances of 𝒏)		 Combination \(\binom{n}{r}\) Permutation without repetition
\(r!\binom{n}{r}\)
With Repetition
(Types of 𝒏)		 Multiset \(\binom{n+r-1}{r}\) Permutation 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
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}\)		 Permutation without repetition
\(r!\binom{n}{r}\)		 Permutation with repetition
\(n^r\)
Selection (𝒓) \(𝒓=3\) E.g.
\(𝒓=3\) E.g.
\(r=3\) E.g.
\(𝒓 = 3\) E.g.
Population (𝒏) or blank
\(𝒏=10\)
\(𝒏=10\)
\(𝒏=10\)
\(𝒏=10\)
Count \(220\) \(120\) \(720\) \(1000\)

Examples

See Also