4  Permutation, Combination and Partition

4.1 Permutation

Suppose that we have \(n\) distinct objects. An arrangement of these objects is also called a permutation.

Proposition (First Counting Principle for Permutation): The number of permutations of \(n\) objects is \[n! = n(n−1)...1\](\(n!\) is read as n-factorial) Note: \(0! = 1\), the number of ways to arrange 0 objects.

Proposition (Second Counting Principle for Permutation): The number of permutation of \(n\) objects taken \(k\) at a time is denoted by \(P(n, k)\): \[P(n,k) = n(n−1)...(n−k+1)=\frac{n!}{k!}\] Example: There are \(5!\) permutations of the 5 letters of the word “exams.” In how many of them is h the second letter?

Solution: \(4\times 3 \times 2 \times 1=4!=24\)

Example: How many different letter arrangements can be formed from the letters “PEPPER”?

Solution: We first note that there are \(6!\) permutations of the letters \(P_1E_1P_2P_3E_2R_1\). Considering that there are 3 P’s and 2 E’s, the number of permutations of these letters amongst themselves are \(3! 2!\). Thus, total number of arrangements = \(\frac{6!}{3!2!} = 60\)

​Example: A city council has 8 members. The council has decided to set up a committee of three members to study a zoning issue. In how many ways can the committee be selected?

Solution: If we wanted to count all the ordered selections of 3 individuals from 8 council members, the answer would be \(P(8,3) = 336 =\) number of ordered selections. In the 336 ordered selections, each group of 3 individuals is counted \(3! = 6\) times. Thus, the number of unordered selections of 3 individuals is \(\frac{336}{6} = \frac{P(8,3)}{3!} = 56\) ## Combination A combination of \(n\) objects taken \(k\) at a lime is an \(k\)-element subset of the original n elements (or, equivalently, an unordered selection of \(k\) of the original \(n\) elements).

Proposition (Counting Principle for Combinations): The number of combinations of \(n\) elements taken \(k\) aI a time is denoted by \(n \choose k\) or \(C(n,k)\). We have \[{n \choose k} = C(n, k) = \frac{n!}{(n−k)!k!}\]

Theorem (Identities on Combination): \[\begin{align}{n \choose k} &= {n \choose n-k} = \frac{n!}{k!(n-k)!}\\ {n \choose k} &= {n \choose k-1} + {n-1 \choose -1}\end{align}\] The first identity shows that the number of ways to take \(k\) objects from \(n\) objects is equal to the number of ways to take \(n-k\) objects. The second identity is the Pascal’s Triangle identity.

Binomial Theorem: \[(x + y)^n = \sum_{k=0}^n {n\choose k}x^ky^{n-k}\] Remark: \(2^n = {n \choose 0} + {n \choose 1} + ... + {n \choose n}\)

Vandermonde Identity:\[\sum_{k=0}^m {N \choose k}{N-K \choose n-k} = {N \choose n}\] This can be proven combinatorially by noting that any combination of \(r\) objects from a group of \(m+n\) objects must have some \(0\le k\le r\) from group \(m\) and the remaining from group \(n\). ## Partition Partitioning refers to the process of breaking a large group into separate smaller groups. Combination is partition involving two groups.

Example: A company has 20 new employees to train. The company will select 6 employees to test a new computer-based training package, 4 for televised classes and 10 for traditional classes.
Solution: The partitioning requires the following two tasks - Task 1: select 6 of 20 for computer-based training - Task 2: select 4 of the remaining 14 for the televised class The total number of ways to partition the employees is: \[{20\choose 6}{14\choose 4} = \frac{20!}{6!14!} \frac{14!}{4!10!} = \frac{20!}{6!4!10!} = 39,798,760\]

The number of partitions of 20 objects into three groups of size 6,4, and 10 is denoted by \[{20 \choose 6,4,10}\] Proposition (Counting Principle for Partition): The number of ways that one can divide \(n\) objects into \(r\) distinct groups of size \(n_1,n_2,...,n_r\) where \(\sum n_j = n\) is given by \[\frac{n!}{n_1! n_2! ... n_r!} = {n \choose n_1, n_2, ..., n_r}\]

Multinomial Theorem: For any positive integer \(m\) and any non-negative integer \(n\), the multinomial formula describes how a sum with \(m\) terms expands when raised to an arbitrary power \(n\): \[(x_1 + ... + x_m)^n = \sum_{k_1 + ... k_m = n;\ k_1, ..., k_m \ge 0} {n \choose k_1,...,k_m} \prod_{t=1}^m x_t^{k_t}\] This is the special case of the binomial theorem.

Example: Ten children are to be divided into an A team and a B team of 5 each. The A team will play in one league and the B team in another. How many different divisions are possible?

Solution: There are \(\frac{10!}{5!5!}=252\) possible divisions

Example: In order to play a game of basketball, 10 children at a playground divide themselves into two teams of 5 each. How many different divisions are possible?

Solution: Note that this is a little bit different from the above example, since now we do not distinguish between the A team and B team. Thus there would be \(\frac{252}{2!} = 126\) possible divisions.

Example: A police department in a small city consists of 10 officers. If the department policy is to have 5 of the officers patrolling the streets, 2 of the officers working full time at the station, and 3 of the officers on reserve at the station, how many different divisions of the 10 officers into the 3 groups are possible?

Solution: The number of possible divisions is \(\frac{10!}{5!2!3!} = 2520\)

Example: Each week, a subcommittee of four individuals is formed from among the members of a committee comprising seven individuals. Two subcommittee members are then assigned to lead the subcommittee, one as chair and the other as secretary. Calculate the maximum number of consecutive weeks that can elapse without having the subcommittee contain four individuals who have previously served together with the same subcommittee chair.

Solution: The number of consecutive weeks is also the number of ways to choose 4 individuals then assign a subcommittee chair. This equals to \({7 \choose 4} * 4 = 140\)

4.1.1 The Euler’s Division Problem

The Euler’s Division problem can be state as such: How many ways there are to split \(n\) balls amongst \(m\) people, such that each child has at least one ball?

This problem is equivalent to the number of integer solutions to the equation: \[ x_1 + x_2 + ... + x_m = n, \qquad x_i \ge 1\] We could solve this problem by arranging n balls in a row and then find a way to insert \(m-1\) separators in-between the balls. There are \(n-1\) positions where one can put a separator, thus there are \(n-1 \choose m-1\) ways to divide the \(n\) balls \(m\)-way.

Example: How many ways there is to choose three numbers from the set \(\{1,2,...,20\}\) such that the difference between any two of those three is at least 2.

Solution: We can imagine that there are 17 blue balls. We are counting the number of ways to put the other 3 green balls in the 18 slots, each slot contains at most one ball to ensure that no two green balls are consecutive. The number of ways to choose is hence \({18 \choose 3} = 816\)