Skip to main content

Chapter 21 Permutations and Combinations

Here are the formulas to count sublists and subsets of the set \([n] = \{1,2,\ldots, n\}\text{.}\)

  • A permutation of \([n]\) is an ordered list of its elements. The number of permutations of \([n]\) is

    \begin{equation*} n! = n (n-1) (n-2) \cdots 2 \cdot 1. \end{equation*}

  • A \(k\)-list of \([n]\) (also called a \(k\)-permutation) is an ordered list of \(k\) elements of \([n]\text{.}\) The number of \(k\)-lists of \([n]\) is

    \begin{equation*} P(n,k) = (n)_k = n (n-1) \cdots (n-k+1) = \frac{n!}{(n-k)!}. \end{equation*}

  • A \(k\)-set of \([n]\) (also called a \(k\)-combination) is a subset containing \(k\) elements of \([n]\text{.}\) The number of \(k\)-sets of \([n]\) is

    \begin{equation*} C(n,k) = {n \choose k} = \frac{n!}{k! (n-k)!}. \end{equation*}

Exercises Practice Problems

1. Bus Stop.

Four adults and seven children are waiting at a bus stop.

  1. How many ways can they sit in a row?

  2. How many ways can they sit in a row if the adults must sit together and the children must sit together?

  3. How many ways can they sit in a row if the the children must sit together?

  4. How many ways can they sit in a row if just the children are sitting together (and the adults must not sit together)?

2. In the Queue.

How many ways can 10 adults and 5 children stand in a line so that no two children are standing next to each other? (Hint: place the adults first, and then the children.)

3. Forming a Circle.

In how many ways can \(n\) people stand in a circle? (How is this problem different from standing in a line?)

4. Five Digits, No Zeros.

  1. How many 5-digit numbers are there where no digit repeats and only the digits 1-9 appear?

  2. Use inclusion-exclusion to determine how many numbers in part (a) contain a 3 and a 6. (Hint: you will need to use "good = all - bad.")

5. Coin Toss.

A coin is tossed 10 times and a sequence of heads and tails is observed.

  1. How many different sequences are possible?

  2. In how how many of these sequences are there exactly 4 heads?

6. Dinner Party.

A woman has 9 close friends.

  1. In how many ways can she invite 6 of them to dinner?

  2. Repeat (a) if two of her friends don't get along and will not attend together.

  3. Repeat (a) if her friends consist of 3 single people and 3 married couples, so that she must invite both spouses, or neither of them.

7. 10 Points.

Ten points in a plane, no three colinear, are given.

  1. Every pair of points determines a unique line. So how many different lines are formed by joining pairs of these points?

  2. Assume that none of the lines in part (a) are parallel and no three lines intersect at a single point. How many different triangles are formed by these lines? (Note that the corners of many of these triangles are at points other than the original 10 points!)

8. Executive Board.

How many ways can a club with 20 members choose an executive board consisting of a president, a secretary, a treasurer, and two other members?