Permutations

Consider a set D with n elements. A permutation of length k from D is an ordered sequence

(x₁, x₂, ..., x_k)

of k distinct elements of D (of course, k cannot be larger than n). A permutation of length k from D is formed when k elements are chosen sequentially from D 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. Eight persons, consisting of four married couples, are to be seated in a row of eight chairs. How many seating arrangements are there if:

1. There are no other restrictions
2. The men must sit together and the women must sit together
3. The men must sit together
4. Each married couple must sit together

When sampling without replacement, the Ball and Urn Experiment has permutations as outcomes.

Combinatorics