A count that is hard to do directly
How many ways are there to put 7 identical coins into 3 labeled jars, if a jar may be left empty? The coins are all alike, so a way of filling the jars is fixed by how many coins each jar gets: three whole numbers, in order, that add up to 7, such as 2, 3 and 2, or 0, 7 and 0.
Listing them by hand is slow, and it is easy to miss one or count one twice. A bijection replaces this collection with one that is easy to count and has the same size.
Stars and bars
Write each coin as a star, and put a bar for each wall between neighboring jars, all in one row. Three jars have 2 walls between them, so every row has 7 stars and 2 bars, 9 places in all.
The filling 2, 3, 2 becomes two stars, a bar, three stars, a bar, two stars. An empty jar shows up as a bar at one end of the row, or as two bars side by side: the filling 0, 7, 0 is a bar, seven stars and a bar, and 4, 0, 3 is four stars, two bars together, then three stars.
The filling 2, 3, 2 as one row of 9 places: the 7 stars are the coins and the 2 bars are the walls between the jars.
The filling 0, 7, 0: nothing before the first bar and nothing after the second, so the first and third jars are empty.
A match in both directions
This matching is a bijection: it is one-to-one and it is onto, and the count needs both.
One-to-one: different fillings give different rows. A row records how many coins are in each jar, so two fillings that give the same row have the same number of coins in every jar, and are the same filling.
Onto: every row comes from some filling. Take any row of 7 stars and 2 bars, and count the stars before the first bar, between the two bars, and after the second bar. Those are three whole numbers that add up to 7, so they are a filling, and writing that filling out gives back the same row.
So each filling gives exactly one row, and each row comes from exactly one filling. Neither collection can be the larger, so they have the same size. A match that was one-to-one but not onto would leave rows over, and would show only that there are at most as many fillings as rows.
The easy count
A row is fixed by choosing which 2 of its 9 places hold the bars; the other 7 hold stars. There are 9 × 8 = 72 ways to pick a first place and then a second, and each pair of places is picked twice that way, so the number of rows is . So there are 36 rows, and therefore 36 ways to fill the jars.
A smaller case can be checked by listing everything. With 3 coins in 3 jars, written as the coins in the first, second and third jar, the fillings are (3, 0, 0), (0, 3, 0) and (0, 0, 3); then (2, 1, 0), (2, 0, 1), (1, 2, 0), (0, 2, 1), (1, 0, 2) and (0, 1, 2); and (1, 1, 1). That is 10 fillings. The rows have 3 stars and 2 bars, 5 places, and .
In general, with k identical objects and j labeled boxes, empties allowed, the rows have k stars and j − 1 bars, and the count is the number of ways to choose which j − 1 of the k + j − 1 places hold bars.
Subsets and yes-or-no strings
A set of n elements has subsets. Match each subset with a string of n answers, one for each element, saying whether that element is in the subset.
One-to-one: two different subsets differ in some element, so their strings differ in that answer. Onto: any string of answers picks out a subset, the elements marked yes. So subsets and strings are equal in number, and each of the n answers has 2 choices, which makes strings. For the set {a, b, c} that is subsets, from the empty subset to the whole set.
The 8 subsets of a set of three elements a, b and c, each named on the left by the elements it holds, with its string of answers across the row. Every possible string appears exactly once.
Matches and the players they knock out
A bijection also counts things that are hard to track. In a knockout tournament every match has exactly one loser, and every player except the champion loses exactly once, so matches pair one to one with the players knocked out. In the first application below, 37 players play 36 matches, however the byes fall. In the second, boxes of donuts in four flavors are matched with rows of dots and dividers.
The usual mistakes
Using one bar per jar. Bars are walls between jars: 3 jars need 2 bars, and 4 jars need 3. A fourth bar would make a fifth jar.
Choosing from the stars only. The bars take places too, so the row has 7 + 2 = 9 places; 7C2 = 21 is not the count.
Treating the coins as different. lets each coin choose its own jar, which counts which coin went where, and the coins are alike.
Checking the match in one direction only. One-to-one without onto shows only “at most”.
Worked example: The Matches in a Knockout Tennis Tournament of 37 Players, Then in Double Elimination
Question A club's tennis tournament has 37 players. Every match has a winner and a loser, and the loser leaves the tournament; a player given a bye in a round goes through to the next round without playing. Play continues until one champion is left. (a) Pair each match with the player who loses it, and use this to find how many matches are played, without working out the byes. (b) The next year's tournament, again with 37 players, is double elimination: a player leaves after a second loss, and play continues until one player is left. The champion lost exactly one match. How many matches are played?
1.Every match has exactly one loser. In a knockout a player loses at most once, because a loss ends that player's tournament, so different matches are paired with different players.
Each match has one loser, and a loser leaves, so no player is paired with two matches. 2.Every player except the champion loses exactly once, because play goes on until only the champion is left. So the players paired with a match are exactly the 37 − 1 = 36 who are knocked out, and each of them is paired with exactly one match.
Everyone but the champion loses exactly once: 37 − 1 = 36 players are knocked out. 3.(a) The pairing is a bijection between the matches and the 36 players knocked out, so 36 matches are played, however the byes fall. Check: with 32 players and no byes the rounds have 16 + 8 + 4 + 2 + 1 = 31 matches, one fewer than the number of players.
(a) Matches and knocked-out players pair off one to one: 36 matches. 4.In the double-elimination tournament, pair each match with the loss it hands to its loser. Every match hands out exactly one loss, and every loss comes from exactly one match, so the number of matches equals the total number of losses.
In double elimination, each match hands out exactly one loss. 5.(b) The 36 players who leave have lost 2 matches each, and the champion lost 1. The total number of losses is 36 × 2 + 1 = 73, so 73 matches are played.
(b) 36 × 2 + 1 = 73 losses, so 73 matches.
Answer: (a) 36 matches; (b) 73 matches
Common mistakes
- Counting rounds as 18 + 9 + 4 + 2 + 1 = 34 by halving 37 and rounding down each time. The byes carry players into the next round, so after 18 matches there are 19 players left, not 18; the pairing with losers gives 36 without tracking them.
- Doubling the answer to (a) and giving 72 for (b). The champion's one loss also came from a match, so the count is 36 × 2 + 1 = 73.
Worked example: Boxes of 12 Donuts in Four Flavors, and How Many Different Boxes a Bakery Can Sell
Question A bakery sells boxes of 12 donuts. A customer fills a box with any mix of 4 flavors (glazed, chocolate, jam and cinnamon), and a box may leave out a flavor. Two boxes are the same when they hold the same number of each flavor. (a) Describe a way to match each box with a row of 12 dots and 3 dividers, explain why it is a bijection, and find the number of different boxes. (b) How many different boxes hold at least one donut of every flavor?
1.Write a box as a row: a dot for each glazed donut, a divider, a dot for each chocolate one, a divider, the jam, a divider, and the cinnamon. For example, 3 glazed, 0 chocolate, 5 jam and 4 cinnamon is 3 dots, two dividers side by side, 5 dots, a divider and 4 dots.
The box of 3 glazed, 0 chocolate, 5 jam and 4 cinnamon, as dots and dividers. 2.This is a bijection. Each box gives exactly one row, and each row of 12 dots and 3 dividers gives back exactly one box: count the dots before the first divider, between the first and second, between the second and third, and after the third. So the number of boxes equals the number of rows.
Each row gives back exactly one box, so boxes and rows pair off one to one. 3.A row has 12 + 3 = 15 places, and it is fixed by choosing which 3 of them hold the dividers. (a) The number of boxes is 153 = 15 × 14 × 133 × 2 × 1 = 455.
(a) Choose which 3 of the 15 places hold dividers: 153 = 455 boxes. 4.For a box with every flavor, put one donut of each flavor in first. That leaves 12 − 4 = 8 donuts to choose freely, so these boxes match one to one with boxes of 8 donuts that may leave out a flavor.
With one of each flavor in first, 8 donuts are left to choose freely. 5.(b) A row of 8 dots and 3 dividers has 11 places, so there are 113 = 11 × 10 × 93 × 2 × 1 = 165 boxes with every flavor. Check: these boxes also match cutting a line of 12 dots at 3 of the 11 gaps between them, which again gives 165.
(b) Choose 3 of the 11 places: 113 = 165 boxes.
Answer: (a) 455 boxes; (b) 165 boxes
Common mistakes
- Counting 412 boxes, as if each donut in turn chose a flavor. That counts the order in which the donuts are chosen, but two boxes with the same number of each flavor are the same box.
- Using 4 dividers, one for each flavor. Three dividers split a row into four groups, and a fourth divider would make five groups.