Permutations

Let A be any finite set. A permutation of A is a one-to-one mapping of A onto itself.

To specify a particular permutation, we list the elements of A and, under them, show where each element is sent by the one-to-one mapping. For example, if A = { a, b, c }, a possible permutation σ would be

$\sigma = \begin{pmatrix} a&b&c \\ c&a&b \end{pmatrix} .$

By the permutation σ, a is sent to c, b is sent to a, and c is sent to b. The condition that the mapping be one-to-one means that no two elements of A are sent, by the mapping, into the same element of A.

We can put the elements of our set in some order and rename them 1, 2, 3, ... , n. Then, a typical permutation of the set A = { a, b, c, d } can be written in the form

$\sigma = \begin{pmatrix} 1&2&3&4 \\ 3&1&4&2 \end{pmatrix} ,$

indicating that "1" went to "3", "2" to "1", "3" to "4", and "4" to "2".

If we always choose the top row to be 1, 2, 3, 4, then, to prescribe the permutation, we need only give the bottom row, with the understanding that this tells us where 1 goes, 2 goes, and so forth, under the mapping. When this is done, the permutation is often called a rearrangement of the n objects 1, 2, 3,...,n. For example, all possible permutations, or rearrangements, of the numbers A = { 1, 2, 3 } are

$123 \quad 132 \quad 213 \quad 231 \quad 312 \quad 321 .$

It is an easy matter to count the number of possible permutations of n objects. By our general counting principle, there are n ways to assign the first element, for each of these we have n-1 ways to assign the second object, n-2 for the third, and so forth. This proves the following theorem.

Theorem: The total number of permutations of a set of n elements is given by $n\cdot (n-1) \cdot (n-2) \cdots 2 \cdot 1 ,$ which is called the factorial and denoted by n!

It is sometimes helpful to consider orderings of subsets of a given set. This prompts the following definition.

Let A be an n-element set, and let k be an integer between 0 and n. Then a k-permutation of A is an ordered listing of a subset of A of size k.

Theorem: The total number of k-permutations of a set of n elements is given by k-th falling factorial: $n^{\underline{k}} = n\cdot (n-1) \cdot (n-2) \cdots (n-k+1) .$

Example: How many people do we need to have in a room to make it a favorable bet (probability of success greater than 1/2) that two people in the room will have the same birthday?

Assuming that there are 365 (in general, any integer n) possible birthdays (which isn't true 1/4 of the time), birthdays are independent (not true---twins), and that birthdays are uniformely distributed among the days of the year (not true again: September birthdays predominate), it is tempting to guess that we would need about 1/2 this number, or 183. You would surely win this bet. In fact, the number required for a favorable bet is only 23. In general, the problem can be answered by solving the equation

$\frac{365!}{\left( 365-r \right)! 365^r} = \frac{1}{2}\,\quad ( p_r ).$

To show this, we find the probability p_r that, in a room with r people, there is no duplication of birthdays; we will have a favorable bet if this probability is less than one half.

Assume that there are 365 possible birthdays for each person (we ignore leap years). Order the people from 1 to r. For a sample point ω, we choose a possible sequence of length r of birthdays each chosen as one of the 365 possible dates. There are 365 possibilities for the first element of the sequence, and for each of these choices there are 365 for the second, and so forth, making 365^r possible sequences of birthdays. We must Ønd the number of these sequences that have no duplication of birthdays. For such a sequence, we can choose any of the 365 days for the Ørst element, then any of the remaining 364 for the second, 363 for the third, and so forth, until we make r choices. For the r-th choice, there will be 365 - r + 1 possibilities. Hence, the total number of sequences with no duplications is

$365\cdot 364 \cdot 363 \cdot \cdots (365-r+1) .$

Thus, assuming that each sequence is equally likely,

$p_r = \frac{365\cdot 364 \cdot 363 \cdot \cdots (365-r+1)}{365^r} .$

It is a custom (following Donald Knuth) to denote the product in the numerator by

$n^{\underline{r}} = n\cdot (n-1)\cdot (n-2) \cdots (n-r+1) ,$

and call it k-th falling factorial. Then

$p_r = \frac{365^{\underline{r}}}{365^r} .$

We make a computational experioment and calculate for several values of r:

r	10	20	22	23	30	40	50	60
Pr[match]	0.1170	0.4114	0.4757	0.5073	0.7063	0.8912	0.9704	0.9941

Solving for r the above equation is not easy, and it is convenient to use Stirling's formula

$n! \sim \sqrt{2\pi\, n}\left( \frac{n}{e} \right)^n \qquad\mbox{as} \quad n \to \infty .$

Using Stirling's approximation, the probability p_r in the above equation

$365^{\underline{r}} / 365^r = 1/2 \quad (p_r ) ,$ the probability p can be given approximately by (we use n instead of 365)

$p_r \sim \left( \frac{n}{n-r} \right)^{n-r+1/2} e^{-r} .$

Taking the logarithm of both sides gives

$\ln p_r \sim \left( n-r+1/2 \right) \ln \left( 1 + \frac{r}{n-r} \right) -r .$

Our objective is to solve for r but it is not readily clear how to extract it. Expanding the logarithm in a taylor series, we get

$\ln p_r \sim - \frac{r^2}{2(n-r)} + \frac{r}{2(n-r)} + \frac{r^3}{3(n-r)^2} - \cdots .$

Solving

$\ln p_r = -(r^2 /2(n-r))$ for r, we obtain

$r \approx \sqrt{\ln^2 p_r - 2n \left( \ln p_r \right)} + \ln p_r .$

As a check on this formula, if p = 1/2 and n = 365, we get r ≈ 21.81. For comparison, the exact factorial expression gives r = 22.768. ■

Permutations that occur when objects are arranged in a circle are called circular permutations. Two circular permutations are not considered different (and are counted only once) if corresponding objects in the two arrangements have the same objects to their right and to their left. ▣

Abramson, M. and W. Moser W. O. J, More Birthday Surprises, The American Mathematical Monthly, 1978, Vol. 77, 856–858
Braza, P.A., The birthday problem anew, International Journal of Mathematical Education in Science and Technology, 2006, Vol. 37, No. 4, pp. 484--488; doi: 10.1080/00207390600578088
Mathis, F.H., A generalized bithday problem, SIAM Review, 1991, Vol. 33, No. 2, pp. 265--270; doi:10.1137/1033051
The birthday problem, Wikipedia.

Basics

Probability

Random Variables

Multivariable Distributions

Discrete Random Variables

Continuous Random Variables

Sampling Distributions

Statistical Inference I: Classical Methods

Statistical Inference II: Bayesian Inference

Intro to Random Processes

Some Important Random Processes

Intro to Simulation Using MATLAB

Intro to Simulation Using R

Glossary

Reference

Statistics