## Permutations and Combinations |

Consider three distinct objects \(a,b\), and \(c\). We can choose two distinct objects from \(a,b\), and \(c\) with two different approaches:

- Unordered selections: \(\{a,b\},\;\{a,c\},\;\{b,c\}\). These are called \(2\)-combinations of \(a,b,c\).
- Ordered selections: \((a,b),\;(b,a),\;(a,c),\;(c,a),\;(b,c),\;(c,b)\). These are called \(2\)-permutations of \(a,b,c\).

**Definition** (Permutation).
A *permutation* of \(n\) distinct objects is an ordered arrangement or selection of the objects. For a positive integer \(r\leq n\),
an *\(r\)-permutation* of \(n\) distinct objects is an ordered arrangement or selection of \(r\) distinct objects chosen from these
\(n\) distinct objects. The number of \(r\)-permutations of \(n\) distinct objects is denoted by \(P(n,r)\) or \(^nP_r\).

**Theorem.**
Let \(n\) and \(r\) be two positive integers and \(r\leq n\). Then
\[P(n,r)=\frac{n!}{(n-r)!}=n(n-1)(n-2)\cdots (n-r+1).\]

Consider \(n\) distinct objects \(a_1,a_2,\ldots,a_n\). An \(r\)-permutation of \(a_1,a_2,\ldots,a_n\) is of the form
\[(a_{i_1},a_{i_2},\ldots,a_{i_r}).\]
For \(i=1,2,\ldots,n\), there are \(n+1-i\) ways to choose the \(i\)th entry of an \(r\)-permutation of \(a_1,a_2,\ldots,a_n\).
By the product rule,
\[P(n,r)=\prod_{i=1}^r (n+1-i)=n(n-1)(n-2)\cdots (n-r+1)=\frac{n!}{(n-r)!}.\]

**Remark.**

- \(P(n,r)=\frac{n!}{(n-r)!}\) is still valid for \(r=0\) because \(P(n,0)=\frac{n!}{n!}=1\).
- \(P(n,n)=\frac{n!}{0!}=n!\) is the number of permutations of \(n\) distinct objects, i.e., there are \(n!\) ways to order \(n\) distinct objects.

**Example.**
Find the number of ways to select the first, second, and third prize winners from 10 contestants.

*Solution.*
The number of ways to select the first, second, and third prize winners from 10 contestants is
\[P(10,3)=\frac{10!}{(10-3)!}=\frac{10!}{7!}=10\cdot 9 \cdot 8=720.\]
The above answer is basically obtained by the product rule.

**Example.**
Find the number of permutations of the letters a, b, c, d, e, f, g containing (a) bad, (b) bad and gf.

*Solution.*

(a) The number of permutations of the letters a, b, c, d, e, f, g containing bad is the number of permutations of 5 objects bad, c, e, f, g which is
\(P(5,5)=5!=120\).

(b) The number of permutations of the letters a, b, c, d, e, f, g containing bad and gf is the number of permutations of 4 objects bad, gf, c, e
which is \(P(4,4)=4!=24\).

**Example.**
How many ways are there for \(8\) men and \(6\) women to stand in a line so that no two women stand next to each other.

*Solution.*
First \(8\) men can be ordered in a line in \(8!\) ways. For each of these \(8!\) ordering of men, there are \(9\) places of which \(6\)
would be filled by \(6\) women. This can be done in
\[P(9,6)=\frac{9!}{(9-6)!}=\frac{9!}{3!}\]
ways. By the product rule, the number of ways for \(8\) men and \(6\) women to stand in a line so that no two women stand next to each other is
\[8! \cdot \frac{9!}{3!}=2,438,553,600.\]

**Definition** (Combination).
For a positive integer \(r\leq n\), an *\(r\)-combination* of \(n\) distinct objects is an unordered arrangement or selection
of \(r\) distinct objects chosen from these \(n\) distinct objects. The number of \(r\)-combinations of \(n\) distinct objects is denoted by
\(C(n,r)\) or \(\displaystyle\binom{n}{r}\) (read as \(n\) choose \(r\)).

**Theorem.**
Let \(n\) and \(r\) be two integers and \(0\leq r\leq n\). Then
\[\binom{n}{r}=\frac{P(n,r)}{r!}=\frac{n!}{r!(n-r)!}.\]

\(P(n,r)\) \(r\)-permutations of \(n\) distinct objects can be obtained from \(\displaystyle\binom{n}{r}\) \(r\)-combinations of these objects
by ordering each of the \(\displaystyle\binom{n}{r}\) \(r\)-combinations in \(r!\) ways. By the product rule,
\[P(n,r)=\binom{n}{r} r!\]
which implies
\[\binom{n}{r}=\frac{P(n,r)}{r!}=\frac{n!}{r!(n-r)!}.\]

**Remark.**
For integers \(0\leq r\leq n\),
\[\binom{n}{r}=\binom{n}{n-r}.\]
In particular, \(\binom{n}{n}=\binom{n}{0}=1\).

**Example.**
Find the number of ways to select the top three prize winners from 10 contestants.

*Solution.*
The number of ways to select the top three prize winners from 10 contestants is
\[\binom{10}{3}=\frac{10!}{3!(10-3)!}=\frac{10!}{3!7!}=\frac{10\cdot 9 \cdot 8}{6}=120.\]

**Example.**
Suppose \(S\) is a set with 10 elements. Find the number of subsets of \(S\) with odd number of elements.

*Solution.*
The number of subsets of \(S\) with 1 element is \(\binom{10}{1}\). Similarly the numbers of subsets of \(S\) with 3, 5, 7, and 9 elements
are \(\binom{10}{3}\), \(\binom{10}{5}\), \(\binom{10}{7}\), and \(\binom{10}{9}\) respectively. Thus the number of subsets of \(S\)
with odd number of elements is
\[\binom{10}{1}+\binom{10}{3}+\binom{10}{5}+\binom{10}{7}+\binom{10}{9}=512.\]

**Example.**
Suppose a department has 5 men and 9 women.

- How many ways are there to form a 5-member committee with 2 men and 3 women?
- How many ways are there to form a 5-member committee with at least 3 women?
- How many ways are there to form a 5-member committee with 2 men and 3 women if there are one man and one woman who do not want work together in a committee?

*Solution.*

- There are \(\binom{5}{2}\) ways to choose 2 men from 5 men. For each choice of 2 men, there are \(\binom{9}{3}\) ways to choose 3 women from 9 women. By the product rule, the number of 5-member committees with 2 men and 3 women is \[\binom{5}{2}\binom{9}{3}=840.\]
- The number of 5-member committees with 2 men and 3 women is \(\binom{5}{2}\binom{9}{3}\). Similarly the number of 5-member committees with 1 men and 4 women is \(\binom{5}{1}\binom{9}{4}\) and that of 5-member committees with no man and 5 women is \(\binom{9}{5}\). Thus by the sum rule, the number of 5-member committees with at least 3 women is \[\binom{5}{2}\binom{9}{3}+\binom{5}{1}\binom{9}{4}+\binom{9}{5}=1596.\]
- First we count the number of 5-member committees with 2 men and 3 women including both of these particular man and woman. After choosing the particular man, there are \(\binom{4}{1}\) ways to choose 1 man from 4 men. After choosing the particular woman, there are \(\binom{8}{2}\) ways to choose 2 woman from 8 women. By the product rule, the number of 5-member committees with 2 men and 3 women including both of these particular man and woman is \[\binom{4}{1}\binom{8}{2}.\]

Since there are \(\binom{5}{2}\binom{9}{3}\) 5-member committees with 2 men and 3 women, the number of 5-member committees with 2 men and 3 women where no committee includes both of these particular man and woman is \[\binom{5}{2}\binom{9}{3}-\binom{4}{1}\binom{8}{2}=728.\]

Last edited