Section 2.2 - Permutations

How to count the outcomes in a sample space.

N distinct items sampled with replacement k times produces a sample space of size n^k. Ordered sampling without replacement is a permutation, and produces a sample space of size

P(n, k) = n(n - 1)(n - 2)· · ·(n - k + 1)^?The first item can be picked n ways, the second (n - 1), and so on. = (n)_k^?(n)_k is known as the falling factorial.

As a sanity check, P(n, 1) is n, and P(n, n + 1) is 0.

Multiplying the falling factorial (n)_k by (n - k)! turns it into the full factorial n! Multiplying P(n, k) by 1 in the form n!/n! gives an alternate formula for permutation counting:

P(n, k) = n!/(n - k)!

For more sanity P(n, n) = n!/(n - n)! = n!/0! = n!^?Because 0! = 1. and P(n, 0) = n!/(n - 0)! = n!/n! = 1.

Sampling with replacement is a cheap but not tight upper-bound for sampling without replacement:

P(n, k) ≤ n^k

Can n^k be tightened up? Multiply P(n, k) by 1 in the form of n^k/n^k:

P(n, k) = (n^k/n^k)(n(n - 1)(n - 2)· · ·(n - k + 1)))

Distribute 1/n^k among the other terms:

n^k(n/n(n - 1)/n(n - 2)/n)· · ·((n - (k - 1))/n)

Divide through:

n^k((1 - 1/n)(1 - 2/n))· · ·(1 - (k - 1)/n))

Now substitute the upper bound^?Appendix 1.B, shamefully skipped, derived this bound. 1 - x ≤ e^-x to get

n^ke^-1/ne^-2/n· · ·e^{-(k + 1)/n}

n^ke^{-(1/n + 2/n + · · · + (k + 1)/n)}

n^ke^{-k(k - 1)/2n}

Example 2.2-1 How many ways can 3 out of 10 distinct books be arranged?

P(10, 3) = 10(10 - 1)(10 - (3 - 1)) = 10×9×8 = 720

Example 2.2-2 How many ways can 6 out of 10 distinct books be arranged?

P(10, 6) = 10×9×8×7×6 ×5 = 151,200

Example 2.2-3 How many ways can 10 out of 10 distinct books be arranged?

P(10, 10) = 10! = 3,628,800

The number of possible permutations grows quickly.

Example 2.2-4 How many permutations are there of three books, two of them indistinguishable?

Using subscripts to distinguish the otherwise indistinguishable books, the naive sample space is

	permutations
books	a1	a2	a1	a2	b	b
	a2	a1	b	b	a1	a2
	b	b	a2	a1	a2	a1

Any permutation containing a₁ then a₂ is indistinguishable from the permutation with a₁ and a₂ swapped, which means the naive permutation count is two times larger than it should be.

	permutations
books	a	a	b
	a	b	a
	b	a	a

The naive permutations are reduced by the same amount for each permutation, which preserves symmetry in the reduced sample space.