Arrangements and selections

Arrangements and selections are the structures counted most often, and the product rule reaches them only by rebuilding the same argument every time.

This lesson turns that argument into formulas. It starts from the two questions the previous lesson left open, how many orders ten runners can finish in and how many committees of three ten people can form, then goes further: words whose letters repeat, selections in which a kind may be taken more than once, and routes along a grid. Each needs the right set to count, reached by a bijection (a perfect pairing between two sets, which forces them to have the same size) to something the product rule already handles.

Arrangements

Ten runners cross the line. The winner is any of the $10$ ; whoever won, second place is any of the $9$ left; then $8$ for third, and so on down to $1$ . The product rule, which multiplies the number of options at each stage provided that number does not depend on earlier choices, gives $10 \times 9 \times \dots \times 1 = 3 628 800$ finishing orders. The product $n (n - 1) \dots 1$ is written $n!$ , read " $n$ factorial", and an ordering of $n$ distinct objects is a permutation of them. The convention $0! = 1$ , one way to arrange nothing, keeps the formulas below true at their edges.

If only the podium matters, the product stops after three stages: $10 \times 9 \times 8 = 720$ ways to award gold, silver and bronze. In general an ordered selection of $k$ objects from $n$ , nothing reused, can be made in

P (n, k) = n (n - 1) \dots (n - k + 1) = \frac{n!}{(n - k)!}

ways, the second form being the full factorial with the orders of the unused $n - k$ objects divided away. The probability course derives this and the next formula the same way and applies them to poker hands and the birthday problem.

Selections

A committee of three is a set, not a sequence. The $720$ podium lists count Ana, Ben, Chloe and Chloe, Ben, Ana separately, while as a committee they are one. The fix is the division rule: if a map from one set onto another sends exactly $d$ elements to each element of the target, the target has $1 / d$ as many elements. Send each ordered list of three people to the set of those three. Every committee is hit by exactly $3! = 6$ lists, one per ordering of its members, so there are $720 / 6 = 120$ committees.

The number of $k$ element subsets of an $n$ element set is written $(\binom{n}{k})$ , read " $n$ choose $k$ ", and the same argument gives

(\binom{n}{k}) = \frac{P (n, k)}{k!} = \frac{n!}{k! (n - k)!}

The formula is symmetric in $k$ and $n - k$ , and a bijection explains why without algebra: sending each subset to its complement pairs the $k$ element subsets perfectly with the $(n - k)$ element ones.

The previous lesson paired the subsets of an $n$ element set with bit strings of length $n$ , a $1$ marking each chosen element. Under that pairing a $k$ element subset becomes a string with exactly $k$ ones, so $(\binom{8}{3}) = 56$ bytes have exactly three bits set. This reading, $(\binom{n}{k})$ as the number of ways to choose which $k$ of $n$ positions receive a given symbol, is the one the rest of the lesson uses over and over.

Words with repeated letters

How many strings can be made by rearranging MISSISSIPPI? The probability course pretends the letters are distinct, giving $11!$ , then divides out the $4!$ orders of the S's, the $4!$ of the I's and the $2!$ of the P's that the pretence counted separately, reaching $34 650$ .

A second derivation builds the word instead of correcting an overcount, and it is the one that generalises. An arrangement is fixed once we know which positions hold each letter. Of the $11$ positions, choose the $1$ for M in $(\binom{11}{1}) = 11$ ways; of the $10$ left, the $4$ for the I's in $(\binom{10}{4}) = 210$ ways; of the $6$ still free, the $4$ for the S's in $(\binom{6}{4}) = 15$ ways; the last $2$ take the P's. The number of options at each stage does not depend on which positions were taken before, so the product rule gives $11 \times 210 \times 15 \times 1 = 34 650$ . Written out in factorials, everything cancels except $11!$ on top and $1! 4! 4! 2!$ below.

In general a word of length $n$ with $n_{1}$ copies of one letter, $n_{2}$ of another and so on up to $n_{r}$ has

\frac{n!}{n_{1}! n_{2}! \dots n_{r}!}

arrangements, a multinomial coefficient. With only two kinds of letter it is $(\binom{n}{k})$ itself: arranging $k$ ones and $n - k$ zeros is the bit string count again.

Example. How many distinct arrangements does BOOKKEEPER have?

Count the letters first, since everything rests on it: B once, O twice, K twice, E three times, P once and R once, all $10$ accounted for. Then

\frac{10!}{2! 2! 3!} = \frac{3 628 800}{24} = 151 200

omitting the factors $1! = 1$ . Checking by positions: $(\binom{10}{3}) = 120$ ways to place the E's, $(\binom{7}{2}) = 21$ for the O's, $(\binom{5}{2}) = 10$ for the K's, and $3! = 6$ for the three single letters, and $120 \times 21 \times 10 \times 6 = 151 200$ .

Now you. How many distinct arrangements does ABRACADABRA have, and in how many do the five A's stand together?

Answer

A five times, B twice, R twice, C and D once each, eleven in all: $11! / (5! 2! 2!) = 83 160$ arrangements. With the A's together, glue them into one block; the word becomes seven symbols, the block, B, B, R, R, C and D, with $7! / (2! 2!) = 1260$ arrangements.

Selections with repetition

A domino is an unordered pair of spot counts from $0$ to $6$ , repetition allowed, since the double six is a tile. Pairs of different values number $(\binom{7}{2}) = 21$ and doubles $7$ , so a full set has $28$ tiles, as a real set does. Splitting into cases works for pairs but soon becomes painful. Three identical dice show a multiset of size three from six values (a multiset being a collection where order does not matter but repetition is allowed), and the cases all different, two alike and all alike already need care. One idea handles every case at once.

Record a multiset of size $k$ from $n$ types as a row of $k$ stars and $n - 1$ bars. The bars cut the row into $n$ compartments, one per type in a fixed order, and the stars in each compartment say how many of that type were taken. For three dice, ${2, 2, 5}$ becomes |**|||*|: nothing before the first bar, so no $1$ ; two stars, so two $2$ s; two empty compartments for $3$ and $4$ ; one star for the $5$ ; nothing for $6$ . Any row of $3$ stars and $5$ bars reads back as exactly one multiset, so this is a bijection, and the rows are counted by choosing which of the $k + n - 1$ positions hold stars. The number of multisets of size $k$ from $n$ types is therefore

(\binom{n + k - 1}{k})

Three dice give $(\binom{8}{3}) = 56$ distinguishable outcomes, and dominoes $(\binom{8}{2}) = 28$ , agreeing with the case count. The method is called stars and bars, and its only difficulty is seeing that the thing to count is not the objects but the dividers between the types.

Equations and distributions

The same count wears two other disguises. A multiset of size $k$ from $n$ types is determined by how many of each type it holds, whole numbers $x_{1}, \dots, x_{n}$ , each at least $0$ , adding to $k$ . So $x_{1} + x_{2} + \dots + x_{n} = k$ has $(\binom{n + k - 1}{k})$ solutions in nonnegative integers. Handing $k$ identical objects to $n$ people is the same list of numbers again: ten identical sweets shared among four children, some perhaps getting none, can be shared in $(\binom{13}{3}) = 286$ ways.

Lower bounds are handled by handing out the guaranteed part first. If each child must get at least one sweet, give each one, then share the remaining six freely: $(\binom{9}{3}) = 84$ ways. As equations, $y_{i} = x_{i} - 1$ turns a positive solution of $x_{1} + \dots + x_{4} = 10$ into a nonnegative solution of $y_{1} + \dots + y_{4} = 6$ and back, a bijection. In general $x_{1} + \dots + x_{n} = k$ has $(\binom{k - 1}{n - 1})$ positive solutions.

Upper bounds are different. If no child may have more than four sweets, there is nothing to hand out first. One counts everything and removes the distributions where some child exceeds the limit, but several can exceed it at once, so the removed sets overlap. Correcting for that overlap is the job of inclusion and exclusion, in a later lesson.

Example. A bakery sells five kinds of doughnut. How many different boxes of a dozen are there, and how many contain at least one of each kind?

A box is a multiset of size $12$ from $5$ types, $12$ stars and $4$ bars: $(\binom{16}{4}) = 1820$ boxes. For at least one of each, place one of each kind first and choose the other $7$ freely: $(\binom{11}{4}) = 330$ boxes, which the positive solution formula confirms as $(\binom{12 - 1}{5 - 1})$ .

Now you. How many solutions does $a + b + c + d = 20$ have in integers with every variable at least $2$ ?

Answer

Set $a^{'} = a - 2$ and likewise for the others. Then $a^{'} + b^{'} + c^{'} + d^{'} = 12$ with every variable at least $0$ , which has $(\binom{15}{3}) = 455$ solutions.

Lattice paths

Most of Manhattan is a grid of streets and avenues, fixed by the Commissioners' Plan of 1811. A walker going $5$ blocks east and $3$ north, never doubling back, has many shortest routes. Model the grid as the points with integer coordinates and a route as a lattice path from $(0, 0)$ to $(5, 3)$ made of unit steps, each right, $R$ , or up, $U$ .

The thing to count is the sequence of steps. Every such path takes five $R$ s and three $U$ s in some order, so it is a word of length $8$ , and every such word traces exactly one path. Choosing which $3$ of the $8$ positions are $U$ gives $(\binom{8}{3}) = 56$ routes, and in general there are $(\binom{m + n}{n})$ lattice paths from $(0, 0)$ to $(m, n)$ .

Conditions yield to the product and sum rules. A path from $(0, 0)$ to $(6, 4)$ through $(2, 2)$ is a path to $(2, 2)$ followed by an independent path onwards, so the counts of the two legs multiply. A path that must avoid a point is counted by complement: all paths, minus those through it. Some conditions are harder. The paths from $(0, 0)$ to $(n, n)$ that never rise above the line $y = x$ cannot be split at one point, since the condition binds at every step; there are $5$ for $n = 3$ and $42$ for $n = 5$ , the Catalan numbers, which a later lesson counts with generating functions.

Example. How many lattice paths run from $(0, 0)$ to $(6, 4)$ , how many pass through $(2, 2)$ , and how many avoid it?

All paths: $(\binom{10}{4}) = 210$ . To $(2, 2)$ there are $(\binom{4}{2}) = 6$ paths, and from $(2, 2)$ the walker needs $4$ right and $2$ up, $(\binom{6}{2}) = 15$ paths. Through the point, $6 \times 15 = 90$ ; avoiding it, $210 - 90 = 120$ .

Now you. How many lattice paths from $(0, 0)$ to $(7, 5)$ avoid the point $(3, 2)$ ?

Answer

All paths: $(\binom{12}{5}) = 792$ . Through $(3, 2)$ : $(\binom{5}{2}) = 10$ paths to it and, with $4$ right and $3$ up remaining, $(\binom{7}{3}) = 35$ from it, so $350$ . Avoiding it: $792 - 350 = 442$ .

Choosing what to count

Selecting $k$ things from $n$ kinds now has four answers, set by two questions: does order matter, and may a kind repeat? Ordered with repetition, the product rule gives $n^{k}$ . Ordered without, $P (n, k)$ . Unordered without, $(\binom{n}{k})$ . Unordered with, $(\binom{n + k - 1}{k})$ . With $n = 5$ and $k = 3$ they are $125$ , $60$ , $10$ and $35$ , so choosing the wrong model is never a small error.

Most counting mistakes answer a different question from the one asked, and the question to settle first is whether swapping two objects produces a different outcome. Ten different sweets handed to four children is ten independent choices of recipient, $4^{10} = 1 048 576$ ways, not the $286$ of identical sweets. Three dice rolled by three different people give $6^{3} = 216$ sequences, while three identical dice rolled together show one of $56$ outcomes, and those outcomes are not equally likely: ${1, 2, 3}$ arises from $6$ sequences and ${1, 1, 1}$ from one. Stars and bars counts outcomes, not probabilities.

A reliable habit is to state the bijection in words, such as "a box of doughnuts is a row of $12$ stars and $4$ bars", and check it both ways before computing. When no single formula fits, split into cases that do not overlap and add, as the domino count did with its doubles.

Numbers that keep returning

The binomial coefficients have appeared in every section: as committees, bit strings, positions in a word, stars and bars, and routes. They also satisfy identities that look like accidents of algebra. Checking $(\binom{n}{k}) = (\binom{n - 1}{k - 1}) + (\binom{n - 1}{k})$ by expanding factorials takes a line of fractions and explains nothing, and $(\binom{n}{0}) + (\binom{n}{1}) + \dots + (\binom{n}{n}) = 2^{n}$ looks just as mysterious.

The lattice paths hint that neither is an accident. Every path to $(m, n)$ arrives by a last step, from $(m - 1, n)$ or from $(m, n - 1)$ , and the two kinds do not overlap, so the count to each point is the sum of the counts to the two points behind it. Written in binomial coefficients, that sentence is the first identity. The next lesson makes it a method: count one set in two ways, set the answers equal, and the identity arrives with its reason attached.