Combinatorics
Basic Counting Principles
Multiplication Principle
The Fundamental Counting Principle (or the Multiplication Principle) states that if an event can occur in $m$ ways, and another independent event is able to occur in $n$ ways, then the total number of unique ways both events can occur is:
\[m \cdot n\]For example, if there are $m$ Formula 1 drivers, and $n$ Formula 1 cars, each driver can be paired with any car. Therefore there are a total of $mn$ different driver–car combinations that can be made.
This principle can be generalised to any number of events. If there are $k$ independent events, where the $i^{\text{th}}$ event can occur in $n_i$ ways, then the total number of unique ways all of the events can occur is:
\[\boxed{\prod_{i=1}^k n_i}\]Addition Principle
The Addition Principle states that given an event can occur in $m$ ways, and another mutually exclusive event (recall mutual exclusivity from Chapter [[5. Sets]]) can occur in $n$ ways, then the total number of ways either event can occur is:
\[m + n\]Which can be generalised in the same way. If there are $k$ mutually exclusive events, where the the $i^{\text{th}}$ event can occur in $n_i$ ways, then the total number of possible outcomes is:
\[\boxed{\sum_{i=1}^k n_i}\]Factorials
The factorial of a positive integer $n$ is written as $n!$, and defined as the product of all positive integers from 1 to $n$:
\[\boxed{n! = \prod_{i=1}^n i, \quad n \geq 1}\]By convention, $0! = 1$.
Permutations
A permutation is a unique ordering of a set of objects. For example $ABC$, and $CBA$ are both permutations of three letters $A$, $B$, and $C$.
Note: If you take $AAB$, swapping the position of the two $A$s is still considered the same permutation, since the result is still $AAB$.
The number of permutations of $n$ distinct objects taken in groups of $r$ at a time, is written as $nPr$, is given by:
\[\boxed{nPr = \dfrac{n!}{(n-r)!} \quad \text{(Assuming no identical objects)}}\]From here we can see that if all $r$ objects are used ($r=n$):
\[nPr = \dfrac{n!}{(n-n)!} = \dfrac{n!}{(0)!} = \dfrac{n!}{1} = n!\]So the special case where all objects are used ($r=n$):
\[\boxed{ nPr = n! \quad \text{when } r = n }\]Permutations with Identical Objects
The formula for the number of permutations given earlier assumes all objects are distinct. In situations where some objects are identical (e.g. the example given earlier with $AAB$), there are fewer distinct permutations, as some are repeated.
The general formula is:
\[\boxed{ \dfrac{n!}{ \displaystyle \prod_{i=1}^r n_i! } }\]where $n$ is the total number of objects, $n_1, n_2, \dots, n_r$ are the counts for each group of identical objects.
| Worked Example 6A |
|---|
| Find the number of permutations of the letters in the word: $\text{MISSISSIPPI}$. |
| We use the general formula for permutations with identical objects: |
| \(\dfrac{n!}{ \displaystyle \prod_{i=1}^r n_i! }\) |
| $\text{MISSISSIPPI}$ has $n=11$ letters, with 4 ‘I’s, 4 ‘S’s, 2 ‘P’s, and 1 ‘M’. So the number of permutations is: |
| \(\dfrac{11!}{4! \cdot 4! \cdot 2! \cdot 1!}\) |
| \(=\dfrac{11 \cdot 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4!}{4! \cdot 4! \cdot 2}\) |
| \(=\dfrac{11 \cdot 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5}{4! \cdot 2}\) |
| \(=\dfrac{11 \cdot 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5}{24 \cdot 2}\) |
| Simplifying the denominator: $24 \cdot 2 = 48 = 6 \cdot 8$, which can be cancelled from the numerator: |
| \(=11 \cdot 10 \cdot 9 \cdot 7 \cdot 5\) |
| \(=990 \cdot 7 \cdot 5\) |
| \(=34\,650 \text{ permutations}\) |
Combinations
A combination is a set of objects, meaning that order does not matter. For example ${A, B, C}$ and ${C, B, A}$ are the same combination of three letters, irrespective of the fact they are different permutations.
Since each group of $r$ objects can be arranged in $r!$ different orders, all representing the same combination, the number of combinations of $n$ distinct objects in groups of $r$, written as $nCr$ or $\binom{n}{r}$ (“n choose r”), is given by:
\[\boxed{nCr = \binom{n}{r} = \dfrac{nPr}{r!} = \dfrac{n!}{r!(n-r)!}}\]We also define that $nC0 = 1$ (there is one way to choose nothing), and $nCn=1$ (there is one way to choose all objects):
\[\boxed{\binom{n}{0} = 1 \quad \text{and} \quad \binom{n}{n} = 1}\]Partitions of Sets
A partition of a set is a way to group its elements into non-empty subsets, where each element belongs to exactly one subset.
For example, the set ${A, B, C}$ has the following partitions:
- ${{A, B, C}}$
- ${{A} {B, C}}$
- ${{B}{A, C}}$
- ${{C}{A, B}}$
- ${{A}{B}{C}}$
Therefore there are 5 different ways to partition the set ${A, B, C}$ in total.
Partitions of Objects (Stars and Bars)
| The stars and bars method is a way to count the number of ways $n$ identical objects can be distributed into $r$ distinct groups. The method involves representing the $n$ objects as “stars” ( $\star$ ), and the partitions between the groups as “bars” ( $ | $ ). |
So taking another example of $5$ objects and $3$ groups, may look like:
\[\star \, \star \; | \; \star \; | \; \star \, \star\]This represents the grouping of $(2, 1, 2)$.
Since $r-1$ bars are required to create $r$ groups, there are a total of $n + r - 1$ slots (positions). The number of ways to do this is:
\[\boxed{ \binom{n + r - 1}{r - 1} }\]Binomial Expansion
The binomial theorem gives a formula allowing us to expand powers of a binomial expression of the form $(a + b)^n$, without having to multiply out each term by hand. It states that (for any non-negative integer $n$):
\[\boxed{ (a + b)^n = \displaystyle \sum_{r=0}^n \binom{n}{r} a^{n-r} b^r }\]For example, the binomial expansion for $n = 3$ is:
\[(a + b)^3 = \binom{3}{0} a^3 + \binom{3}{1} a^2b + \binom{3}{2} ab^2 + \binom{3}{3} b^3 = a^3 + 3a^2b + 3ab^2 + b^3\]Pascal’s Triangle
The coefficients of $\binom{n}{r}$ which appear in the expansion can also be found through Pascal’s triangle, where each number is the sum of the two numbers directly above it:
\[\begin{array}{ccccccc} 1 \\ 1 & 1 \\ 1 & 2 & 1 \\ 1 & 3 & 3 & 1 \\ 1 & 4 & 6 & 4 & 1 \\ 1 & 5 & 10 & 10 & 5 & 1 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \\ \end{array}\]Multinomial Theorem
The multinomial theorem is a generalisation of the binomial theorem to allow for the expansion of powers of a sum with more than two terms. This allows it to be applied to expressions such as $(a + b + c + \dots)^n$. It is formally defined as:
\[\boxed{ \left(\displaystyle \sum_{i=1}^m x_i \right)^n = \sum_{\substack{k_1+k_2+\cdots+k_m=n \\ k_1,k_2,\ldots,k_m \geq 0}} \dfrac{n!}{\prod_{j=1}^m k_j!}\, \prod_{r=1}^m x_r^{k_r} }\]Although this form is relatively cluttered, so typically, the multinomial coefficient is introduced:
\[\boxed{\binom{n}{k_1, k_2, \dots, k_m} = \dfrac{n!}{\prod_{i=1}^{m}k_i!}}, \, \text{where } k_1 + k_2 + \dots + k_m = n\]Notice that for $m = 2$, this becomes the binomial coefficient:
\[\binom{n}{k_1, k_2} = \dfrac{n!}{k_1!k_2!},\]Since $k_1 + k_2 = n$, we can write $k_2=n-k_1$, giving:
\[\binom{n}{k_1, k_2} = \dfrac{n!}{k_1!(n-k_1)!},\]Therefore, for $m=2$, the multinomial coefficient reduces to the binomial coefficient:
\[\binom{n}{k_1, k_2} = \binom{n}{k_1}, \quad (\text{since } k_2=n-k_1)\]