1. Use the
multiplication principle to show that the number of permutations of
length k from an n element set isVirtual Laboratories > Combinatorics > 1 [2] 3 4 5
Consider a set D with n elements. A permutation of length k from D is an ordered sequence
(x1, x2, ..., xk)
of k distinct elements of D (of course, k cannot be larger than n). Statistically, a permutation of length k from D corresponds to an ordered sample of size k chosen without replacement.
1. Use the
multiplication principle to show that the number of permutations of
length k from an n element set is
(n)k = n(n - 1) ··· (n - k + 1)
2. Show that the
number of permutations of length n from the n element set D
(these are called simply permutations of D) is
n! = (n)n = n(n - 1) ··· (1)
3. Show that
(n)k = n! / (n - k)!
4. In a race with
10 horses, the first, second, and third place finishers are noted. How many outcomes are
there?
5. Eight persons,
consisting of four married couples, are to be seated in a row of eight chairs. How many
seating arrangements are there if:
6. Suppose that n
people are to be seated at a round table. Show that there are (n - 1)! distinct
seating arrangements. Hint: the mathematical significance of a round table is
that there is no dedicated first chair.
7.
Twelve books,
consisting of 5 math books, 4 science books, and 3 history books are randomly arranged on a
bookshelf.
8. The birthday problem. Suppose that n persons are chosen
at random and their birthdays noted.
9. Run the
birthday experiment 1000 times for the following values of n.
In each case, compare the relative frequency of the event that the birthdays are distinct
with the theoretical values in Exercise 8.
10. Suppose that there are 5 duck
hunters, each a perfect shot. A flock of 10 ducks fly over, and each hunter
selects one duck at random and shoots. Find the probability that 5 ducks
are killed.
11. Show that the
number of permutations of the cards in a standard deck is
52! = 8.0658 × 1068.
The number in Exercise 10 is enormous. Indeed if you perform the experiment of dealing all 52 cards from a well-shuffled deck, you will probably generate a pattern of cards that has never been generated before.
12. Suppose that
8 rooks are randomly placed on a chessboard. Show that the probability that no
rook can capture another is
8! 8! / (64)8.
13. Suppose that
5 fair dice are rolled. Find the probability that the scores are all
different.
14.
A license tag consists of 2 letters and 5 digits. Find the probability that
the letters and digits are all different.
The formula for (n)k in Exercise 1 makes sense for any real number n and nonnegative integer k. The resulting expression is called the generalized permutation formula.
15.
Compute each of the following