5.7 Combinatorial Methods

5.7.1 Permutations

An ordered arrangement of k distinct objects from a total of n objects is called a permutation. The number of ways of ordering n distinct objects taken k at a time is distinguished by the symbol \(P_{k}^{n}\): \[P_k^n =n \cdot (n-1) \cdot (n-2) \cdot (n-3) \cdots (n-k+1)=\frac{n!}{(n-k)!}\] where the factorial \(n!\) is defined as \(n!=n \cdot (n - 1) \cdot (n - 2) \cdot (n - 3) \cdots (2) \cdot (1)\) with \(0! = 1\). With replacement of the objects, the number of possibilities is \(n^k\).

For example, consider a bowl containing six balls with the letters A, B, C, D,E , and F on the respective balls. Now consider an experiment where I draw one ball from the bowl and write down its letter and then draw a second ball and write down its letter. The outcome is then an ordered pair, i.e., \(BA \neq AB\). The number of distinct ways of doing this is given by \[P_{2}^{6}=\frac{6!}{4!}=\frac{6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{4\cdot 3 \cdot 2 \cdot 1} =6 \cdot 5=30\] What is number of ways to arrange objects if \(n=4\) and \(k=2\)? Without replacement, we have to calculate \(P^4_2\) and with replacement, we have to calculate \(n^k\).

5.7.2 Combinations

A arrangement of k distinct objects where ordering does not matter is called a combinations. The number of unordered subsets of size r chosen (without replacement) from n available objects is \[{n \choose k} = C^n_k = \frac{P^n_k}{k!}=\frac{n!}{k! \cdot (n-k)!}\] What is \(C_{6}^{6}\)? Consider a bowl containing six balls with the letters \(A\), \(B\), \(C\), \(D\), \(E\), \(F\) on the respective balls. Now consider an experiment where I draw two balls from the bowl and write down the letter on each of them, not paying any attention to the order in which I draw the balls so that \(AB\) is the same as \(BA\). The number of distinct ways of doing this is given by \[C_{2}^{6}=\frac{6!}{2! \cdot 4!}=\frac{6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1}{2\cdot 1\cdot 4\cdot 3 \cdot 2 \cdot 1} =\frac{6 \cdot 5}{2} =15\] The equation for a combination with repetition is as follows: \[{n+k-1 \choose k} = \frac{(n+k-1)!}{k! \cdot (n-1)!}=\frac{(n+k-1)!}{k! \cdot (n-k)!}\]