Permutations and combinations

The product rule of lesson 2 counts sequences of choices. Two special cases come up so often that they have their own names and notation. A permutation is an arrangement of objects in order; a combination is a selection in which order does not matter. Most counting problems ask for one or the other, sometimes with repetition allowed and sometimes not, and the first job in any problem is to decide which. This lesson derives the four basic formulas, shows how to tell them apart and applies them to committees, card hands, words with repeated letters and paths on a grid.

Permutations

A permutation of a set of \(n\) distinct objects is an ordering of all of them. There are \(n\) choices for the first position, \(n - 1\) for the second, and so on down to 1 for the last, so by the product rule there are \(n!\) permutations. The letters A, B, C can be arranged in \(3! = 6\) ways: ABC, ACB, BAC, BCA, CAB, CBA.

More generally, an \(r\)-permutation of \(n\) objects is an ordered list of \(r\) of them, with no repetition. The count is

\[ P(n, r) = n(n - 1)(n - 2) \cdots (n - r + 1) = \frac{n!}{(n - r)!}. \]

There are \(r\) factors, starting at \(n\) and going down by one each time. The second form is convenient for algebra; the first is better for calculation, since it avoids computing two huge factorials only to divide them. The number of ways to award gold, silver and bronze medals among 8 finalists is \(P(8, 3) = 8 \cdot 7 \cdot 6 = 336\). As special cases, \(P(n, n) = n!\) and \(P(n, 0) = 1\): there is exactly one way to choose nothing.

Combinations

A combination of \(r\) objects from \(n\) is a subset of size \(r\); order does not matter. The number of such subsets is written \(\binom{n}{r}\) and read n choose r. To find it, count the \(r\)-permutations in two ways. On one hand there are \(P(n, r)\) of them. On the other hand, each can be built by first choosing which \(r\) objects to use, in \(\binom{n}{r}\) ways, and then arranging them, in \(r!\) ways. So \(P(n, r) = \binom{n}{r} r!\), and

\[ \binom{n}{r} = \frac{P(n, r)}{r!} = \frac{n!}{r!\,(n - r)!}. \]

This derivation is the division principle in action: if every combination corresponds to exactly \(r!\) permutations, divide the number of permutations by \(r!\) to count combinations. A committee of 3 chosen from 8 people can be formed in \(\binom{8}{3} = 336 / 6 = 56\) ways. Each of those 56 committees corresponds to 6 of the 336 medal assignments, one for each way of handing out the three medals to its members.

Two simple facts follow from the formula and are worth knowing by heart. First, \(\binom{n}{0} = \binom{n}{n} = 1\): one way to choose nothing and one way to choose everything. Second, \(\binom{n}{r} = \binom{n}{n - r}\). The formula shows this at once, but there is a better reason: choosing the \(r\) objects to include is the same as choosing the \(n - r\) objects to leave out. Arguments of this kind, which explain an identity by describing two ways to make the same choice, are called combinatorial proofs.

Which formula?

Two questions decide which formula applies. Does order matter? Is repetition allowed? Selecting \(r\) items from \(n\) kinds gives four cases:

The bottom-right entry, combinations with repetition, is derived below. Deciding whether order matters is not always obvious from the wording. A hand of cards is a combination, because the same cards in a different order are the same hand. A PIN is a sequence, because 1234 and 4321 are different PINs. A word is a sequence. A committee is a combination, but a committee with a chair and a secretary is partly ordered: choose the chair, then the secretary, then the other members.

Arrangements with repeated objects

How many different words can be made by rearranging the letters of BANANA? If the six letters were all different the answer would be \(6! = 720\). But the three As are identical, so swapping them gives the same word; likewise the two Ns. Each distinct word corresponds to \(3! \cdot 2! = 12\) arrangements of labeled letters \(A_1 A_2 A_3 N_1 N_2 B\). By the division principle there are \(720 / 12 = 60\) words.

In general, the number of arrangements of \(n\) objects of which \(n_1\) are of one type, \(n_2\) of a second type, and so on up to \(n_k\), with \(n_1 + \cdots + n_k = n\), is the multinomial coefficient

\[ \binom{n}{n_1, n_2, \dots, n_k} = \frac{n!}{n_1!\, n_2! \cdots n_k!}. \]

Another way to see this: choose the \(n_1\) positions for the first type in \(\binom{n}{n_1}\) ways, then the \(n_2\) positions for the second type from the remaining \(n - n_1\), and so on. Multiplying these binomial coefficients and canceling gives the same formula. MISSISSIPPI, with one M, four Is, four Ss and two Ps, has \(\frac{11!}{1!\,4!\,4!\,2!} = 34\,650\) arrangements.

Combinations with repetition: stars and bars

A bakery sells 4 kinds of muffin. How many ways can you buy a box of 10 muffins? Order does not matter, and kinds may be repeated. Such a purchase is described by four non-negative integers, one per kind, adding up to 10. Encode it as a row of 10 stars and 3 bars: the stars before the first bar count the first kind, the stars between the first and second bars count the second kind, and so on. For example, ★★★|★|★★★★★★| means 3, 1, 6 and 0 muffins.

Every row of 10 stars and 3 bars gives a purchase, and every purchase gives exactly one row. So the purchases correspond one to one with ways of choosing which 3 of the 13 positions hold bars: \(\binom{13}{3} = 286\). In general, the number of ways to choose \(r\) items from \(n\) kinds with repetition allowed, which is also the number of solutions of \(x_1 + \cdots + x_n = r\) in non-negative integers, is

\[ \binom{n + r - 1}{r} = \binom{n + r - 1}{n - 1}. \]

If each kind must appear at least once, first put one of each into the box. That leaves \(r - n\) items to choose freely, giving \(\binom{r - 1}{n - 1}\) ways. With 10 muffins and at least one of each of 4 kinds there are \(\binom{9}{3} = 84\) boxes.

Lattice paths

A city street plan is a rectangular grid. How many shortest routes lead from the corner \((0, 0)\) to the corner \((m, n)\), moving only east or north along streets? Every shortest route consists of exactly \(m\) east steps and \(n\) north steps in some order, and any such order is a valid route. So a route is a word of length \(m + n\) with \(m\) Es and \(n\) Ns, and the number of routes is \(\binom{m + n}{m}\). From one corner of a 4 by 3 block grid to the opposite corner there are \(\binom{7}{3} = 35\) routes.

Routes that must pass through a particular corner are counted with the product rule: count the routes to that corner, then the routes from it to the end, and multiply. Routes that must avoid a corner are counted with the complement: all routes minus those through it. Lattice paths reappear in lesson 4, where they give a picture of Pascal's triangle.

A famous refinement asks for the routes from \((0, 0)\) to \((n, n)\) that never rise above the diagonal, so that at every point the number of east steps taken so far is at least the number of north steps. The answer is the Catalan number \(C_n = \frac{1}{n + 1}\binom{2n}{n}\), giving 1, 1, 2, 5, 14, 42 for \(n = 0, \dots, 5\). The proof is a neat use of the complement and a bijection, the reflection principle. Count the bad routes, those that touch the line one step above the diagonal. Reflect the part of a bad route before its first touch across that line, swapping east and north steps. The result is a route from \((-1, 1)\) to \((n, n)\), and every such route arises from exactly one bad route. There are \(\binom{2n}{n+1}\) of them, so the good routes number \(\binom{2n}{n} - \binom{2n}{n + 1}\), which simplifies to \(C_n\). Catalan numbers count an astonishing variety of objects: correctly matched strings of \(n\) pairs of parentheses, binary trees with \(n\) internal vertices, and the ways to cut a convex polygon with \(n + 2\) sides into triangles by diagonals. Reading an east step as an opening parenthesis and a north step as a closing one turns a good route into a matched string, since at no point may more parentheses be closed than opened.

Circular arrangements and distributions

Seating \(n\) people around a round table, where only the order around the table matters and not which seat is which, gives fewer arrangements than seating them in a row. Each circular seating corresponds to \(n\) row seatings, one for each place at which we could cut the circle open, so by the division principle there are \(n!/n = (n - 1)!\) circular seatings. Five people can sit around a table in \(4! = 24\) ways. If, in addition, a seating and its mirror image are considered the same, as for beads on a bracelet that can be turned over, we divide by 2 again when \(n \ge 3\). Counting necklaces whose beads may repeat colors is harder, because some necklaces look the same after fewer rotations than others; that problem needs the group-theoretic counting methods of MATH-460.

Distribution problems come in four varieties, depending on whether the objects and the boxes are distinguishable. Placing \(k\) distinct objects into \(n\) distinct boxes is a function from objects to boxes, so there are \(n^k\) ways. Placing \(k\) identical objects into \(n\) distinct boxes is stars and bars, \(\binom{n + k - 1}{k}\) ways. Requiring every box to be nonempty changes these counts: for identical objects it gives \(\binom{k - 1}{n - 1}\) as above, while for distinct objects it counts the functions onto the boxes, which needs inclusion–exclusion. When the boxes themselves are identical, as when people are split into unlabeled teams, the counts become the Stirling numbers and partition numbers, which have no simple closed form; MATH-460 treats them. Recognizing which of the varieties a word problem describes is half the work of solving it.

Checking formulas by computer

Every formula in this lesson can be checked for small cases by listing the objects with Python's itertools module, which provides permutations, combinations and combinations with replacement. The code below does this for each formula.

from itertools import permutations, combinations, combinations_with_replacement, product
from math import comb, perm, factorial

n, r = 6, 3
print("P(6,3):", sum(1 for _ in permutations(range(n), r)), "formula", perm(n, r))
print("C(6,3):", sum(1 for _ in combinations(range(n), r)), "formula", comb(n, r))
print("6^3   :", sum(1 for _ in product(range(n), repeat=r)), "formula", n**r)
print("multiset C(6+3-1,3):", sum(1 for _ in combinations_with_replacement(range(n), r)),
      "formula", comb(n + r - 1, r))

words = set(permutations("BANANA"))
print("BANANA arrangements:", len(words), "formula", factorial(6) // (factorial(3) * factorial(2)))

# muffins: solutions of x1+x2+x3+x4 = 10 in non-negative integers
boxes = sum(1 for xs in product(range(11), repeat=4) if sum(xs) == 10)
print("muffin boxes:", boxes, "formula", comb(13, 3))

# lattice paths from (0,0) to (4,3) avoiding the corner (2,1)
total = comb(7, 3)
through = comb(3, 1) * comb(4, 2)
print("routes:", total, "through (2,1):", through, "avoiding it:", total - through)

P(6,3): 120 formula 120
C(6,3): 20 formula 20
6^3   : 216 formula 216
multiset C(6+3-1,3): 56 formula 56
BANANA arrangements: 60 formula 60
muffin boxes: 286 formula 286
routes: 35 through (2,1): 18 avoiding it: 17