Discrete Math Home
Home Courses News Videos Contact
☰

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:

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

  2. 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.

  1. \(P(n,r)=\frac{n!}{(n-r)!}\) is still valid for \(r=0\) because \(P(n,0)=\frac{n!}{n!}=1\).

  2. \(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.

  1. How many ways are there to form a 5-member committee with 2 men and 3 women?

  2. How many ways are there to form a 5-member committee with at least 3 women?

  3. 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.

  1. 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.\]

  2. 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.\]

  3. 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}.\]

    4. 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