Chapter 1

Five schools are going to send their baseball teams to a tournament, in which each team must play each other team exactly once. How many games are required?

Now some number \(n\) of schools are going to send their baseball teams to a tournament, and each team must play each other team exactly once. Let us think of the teams as numbered 1 through \(n\). (a) How many games does team 1 have to play in? (b) How many games, other than the one with team \(1,\) does team two have to play in? (c) How many games, other than those with the first \(i-1\) teams, does team \(i\) have to play in? (d) In terms of your answers to the previous parts of this problem, what is the total number of games that must be played?

One of the schools sending its team to the tournament has to send its players from some distance, and so it is making sandwiches for team members to eat along the way. There are three choices for the kind of bread and five choices for the kind of filling. How many different kinds of sandwiches are available? (b)

An ordered pair \((a, b)\) consists of two things we call \(a\) and \(b\). We say \(a\) is the first member of the pair and \(b\) is the second member of the pair. If \(M\) is an \(m\) element set and \(N\) is an \(n\) -element set, how many ordered pairs are there whose first member is in \(M\) and whose second member is in \(N\) ? Does this problem have anything to do with any of the previous problems?

Two sets are said to be disjoint if they have no elements in common. For example, \(\\{1,3,12\\}\) and \(\\{6,4,8,2\\}\) are disjoint, but \(\\{1,3,12\\}\) and \(\\{3,5,7\\}\) are not. Three or more sets are said to be mutually disjoint if no two of them have any elements in common. What can you say about the size of the union of a finite number of finite (mutually) disjoint sets? Does this have anything to do with any of the previous problems?

If we make a sequence of \(m\) choices for which \- there are \(k_{1}\) possible first choices, and \- for each way of making the first \(i-1\) choices, there are \(k_{i}\) ways to make the \(i\) th choice, then in how many ways may we make our sequence of choices? (You need not prove your answer correct at this time.)

A tennis club has \(2 n\) members. We want to pair up the members by twos for singles matches. (a) In how many ways may we pair up all the members of the club? (Hint: consider the cases of \(2,4,\) and 6 members.) (h) (b) Suppose that in addition to specifying who plays whom, for each pairing we say who serves first. Now in how many ways may we specify our pairs?

Now suppose we are thinking about a set \(S\) of functions \(f\) from \([m]\) to some set \(X\). (For example, in Problem 6 we were thinking of the set of functions from the three possible places for scoops in an ice-cream cone to 12 flavors of ice cream.) Suppose there are \(k_{1}\) choices for \(f(1)\). (In Problem 6 , \(k_{1}\) was \(12,\) because there were 12 ways to choose the first scoop.) Suppose that for each choice of \(f(1)\) there are \(k_{2}\) choices for \(f(2)\). (For example, in Problem \(6 k_{2}\) was 12 if the second flavor could be the same as the first, but \(k_{2}\) was 11 if the flavors had to be different.) In general, suppose that for each choice of \(f(1), f(2), \ldots f(i-1),\) there are \(k_{i}\) choices for \(f(i) .\) (For example, in Problem 6 , if the flavors have to be different, then for each choice of \(f(1)\) and \(f(2),\) there are 10 choices for \(f(3) .)\) What we have assumed so far about the functions in \(S\) may be summarized as \- There are \(k_{1}\) choices for \(f(1)\) \- For each choice of \(f(1), f(2), \ldots, f(i-1),\) there are \(k_{i}\) choices for \(f(i)\). How many functions are in the set \(S ?\) Is there any practical difference between the result of this problem and the general product principle?

A roller coaster car has \(n\) rows of seats, each of which has room for two people. If \(n\) men and \(n\) women get into the car with a man and a woman in each row, in how many ways may they choose their seats?

How many subsets does a set \(S\) with \(n\) elements have? (b)

Assuming \(k \leq n,\) in how many ways can we pass out \(k\) distinct pieces of fruit to \(n\) children if each child may get at most one? What is the number if \(k>n\) ? Assume for both questions that we pass out all the fruit.

Another name for a list, in a specific order, of \(k\) distinct things chosen from a set \(S\) is a \(k\) -element permutation of \(S .\) We can also think of a \(k\) -element permutation of \(S\) as a one-to-one function (or, in other words, injection) from \([k]=\\{1,2, \ldots, k\\}\) to \(S .\) How many \(k\) -element permutations does an \(n\) -element set have? (For this problem it is natural to assume \(k \leq n\). However the question makes sense even if \(k>n\). What is the number of \(k\) -element permutations of an \(n\) -element set if \(k>n ?\)

Draw the digraph of the function from the set \(\\{\) Alice, Bob, Dawn, Bill \(\\}\) to the set \(\\{\mathrm{A}, \mathrm{B}, \mathrm{C}, \mathrm{D}, \mathrm{E}\\}\) given by \(f(X)=\) the first letter of the name \(X\)

The word permutation is actually used in two different ways in mathematics. A permutation of a set \(S\) is one-to-one from \(S\) onto \(S\). How many permutations does an \(n\) -element set have?

The binary representation of a number \(m\) is a list, or string, \(a_{1} a_{2} \ldots a_{k}\) of zeros and ones such that \(m=a_{1} 2^{k-1}+a_{2} 2^{k-2}+\cdots+a_{k} 2^{0}\) Describe a bijection between the binary representations of the integers between 0 and \(2^{n}-1\) and the subsets of an \(n\) -element set. What does this tell you about the number of subsets of an \(n\) -element set?

Let \(C\) be the set of \(k\) -element subsets of \([n]\) that contain the number \(n,\) and let \(D\) be the set of \(k\) -element subsets of \([n]\) that don't contain \(n .\) (a) Let \(C^{\prime}\) be the set of \((k-1)\) -element subsets of \([n-1] .\) Describe a bijection from \(C\) to \(C^{\prime}\). (A verbal description is fine.) (b) Let \(D^{\prime}\) be the set of \(k\) -element subsets of \([n-1]=\\{1,2, \ldots n-1\\}\). Describe a bijection from \(D\) to \(D^{\prime} .\) (A verbal description is fine.) (c) Based on the two previous parts, express the sizes of \(C\) and \(D\) in terms of binomial coefficients involving \(n-1\) instead of \(n\). (d) Apply the sum principle to \(C\) and \(D\) and obtain a formula that expresses \(\left(\begin{array}{l}n \\ k\end{array}\right)\) in terms of two binomial coefficients involving \(n-1\). You have just derived the Pascal Equation that is the basis for the famous Pascal's Triangle.

As we noted in Problem \(29,\) the first question in Problem 8 asked us for the number of three-element subsets of a twelve-element set. We were able to use the Pascal Equation to get a numerical answer to that question. Had we had twenty or thirty flavors of ice cream to choose from, using the Pascal Equation to get our answer would have entailed a good bit more work. We have seen how the general product principle gives us an answer to Problem 6 . Thus we might think that the number of ways to choose a three element set from 12 elements is the number of ways to choose the first element times the number of ways to choose the second element times the number of ways to choose the third element, which is \(12 \cdot 11 \cdot 10=1320\). However, our result in Problem 29 shows that this is wrong. (a) What is it that is different between the number of ways to stack ice cream in a triple decker cone with three different flavors of ice cream and the number of ways to simply choose three different flavors of ice cream? (b) In particular, how many different triple decker cones use the same three flavors? (Of course any three distinct flavors could substitute for vanilla, chocolate and strawberry without changing the answer.) (c) Using your answer from part b, compute the number of ways to choose three different flavors of ice cream (out of twelve flavors) from the number of ways to choose a triple decker cone with three different flavors (out of twelve flavors).

In how many ways can we pass out \(k\) (identical) ping-pong balls to \(n\) children if each child may get at most one? (h)

In how many ways may \(n\) people sit around a round table? (Assume that when people are sitting around a round table, all that really matters is who is to each person's right. For example, if we can get one arrangement of people around the table from another by having everyone get up and move to the right one place and sit back down, we get an equivalent arrangement of people. Notice that you can get a list from a seating arrangement by marking a place at the table, and then listing the people at the table, starting at that place and moving around to the right.) There are at least two different ways of doing this problem. Try to find them both. (h)

A basketball team has 12 players. However, only five players play at any given time during a game. (a) In how may ways may the coach choose the five players? (b) To be more realistic, the five players playing a game normally consist of two guards, two forwards, and one center. If there are five guards, four forwards, and three centers on the team, in how many ways can the coach choose two guards, two forwards, and one center? (h) (c) What if one of the centers is equally skilled at playing forward? (h)

In how many ways may we string \(n\) distinct beads on a necklace without a clasp? (Perhaps we make the necklace by stringing the beads on a string, and then carefully gluing the two ends of the string together so that the joint can't be seen. Assume someone can pick up the necklace, move it around in space and put it back down, giving an apparently different way of stringing the beads that is equivalent to the first.) \((\mathrm{h})\)

(This becomes especially relevant in Chapter \(6,\) though it makes an important point here.) In how many ways may we attach two identical red beads and two identical blue beads to the corners of a square (with one bead per corner) free to move around in (three-dimensional) space? (n)

In a part of a city, all streets run either north-south or east-west, and there are no dead ends. Suppose we are standing on a street corner. In how many ways may we walk to a corner that is four blocks north and six blocks east, using as few blocks as possible? (h)

Problem 47 has a geometric interpretation in a coordinate plane. A lattice path in the plane is a "curve" made up of line segments that either go from a point \((i, j)\) to the point \((i+1, j)\) or from a point \((i, j)\) to the point \((i, j+1),\) where \(i\) and \(j\) are integers. (Thus lattice paths always move either up or to the right.) The length of the path is the number of such line segments. (a) What is the length of a lattice path from (0,0) to \((m, n) ?\) (b) How many such lattice paths of that length are there? (h) (c) How many lattice paths are there from \((i, j)\) to \((m, n),\) assuming \(i, j,\) \(m,\) and \(n\) are integers? (n)

Another kind of geometric path in the plane is a diagonal lattice path. Such a path is a path made up of line segments that go from a point \((i, j)\) to \((i+1, j+1)\) (this is often called an upstep) or \((i+1, j-1)\) (this is often called a downstep), again where \(i\) and \(j\) are integers. (Thus diagonal lattice paths always move towards the right but may move up or down.) (a) Describe which points are connected to (0,0) by diagonal lattice paths. (h) (b) What is the length of a diagonal lattice path from (0,0) to \((m, n) ?\) (c) Assuming that \((m, n)\) is such a point, how many diagonal lattice paths are there from (0,0) to \((m, n) ?(\mathrm{~h})\)

A school play requires a ten dollar donation per person; the donation goes into the student activity fund. Assume that each person who comes to the play pays with a ten dollar bill or a twenty dollar bill. The teacher who is collecting the money forgot to get change before the event. If there are always at least as many people who have paid with a ten as a twenty as they arrive the teacher won't have to give anyone an IOU for change. Suppose \(2 n\) people come to the play, and exactly half of them pay with ten dollar bills. (a) Describe a bijection between the set of sequences of tens and twenties people give the teacher and the set of lattice paths from (0,0) to \((n, n)\). (b) Describe a bijection between the set of sequences of tens and twenties that people give the teacher and the set of diagonal lattice paths from (0,0) and \((2 n, 0)\) (c) In each case, what is the geometric interpretation of a sequence that does not require the teacher to give any IOUs? (b)

Your formula for the Catalan Number can be expressed as a binomial coefficient divided by an integer. Whenever we have a formula that calls for division by an integer, an ideal combinatorial explanation of the formula is one that uses the quotient principle. The purpose of this problem is to find such an explanation using diagonal lattice paths. \({ }^{a}\) A diagonal lattice path that never goes below the \(y\) -coordinate of its first point is called a Dyck Path. We will call a Dyck Path from (0,0) to \((2 n, 0)\) a Catalan Path of length \(2 n\). Thus the number of Catalan Paths of length \(2 n\) is the Catalan Number \(C_{n}\) (a) If a Dyck Path has \(n\) steps (each an upstep or downstep), why do the first \(k\) steps form a Dyck Path for each nonnegative \(k \leq n ?\) (b) Thought of as a curve in the plane, a diagonal lattice path can have many local maxima and minima, and can have several absolute maxima and minima, that is, several highest points and several lowest points. What is the \(y\) -coordinate of an absolute minimum point of a Dyck Path starting at (0,0)\(?\) Explain why a Dyck Path whose rightmost absolute minimum point is its last point is a Catalan Path. (h) (c) Let \(D\) be the set of all diagonal lattice paths from (0,0) to \((2 n, 0)\). (Thus these paths can go below the \(x\) -axis.) Suppose we partition \(D\) by letting \(B_{i}\) be the set of lattice paths in \(D\) that have \(i\) upsteps (perhaps mixed with some downsteps) following the last absolute minimum. How many blocks does this partition have? Give a succinct description of the block \(B_{0} \cdot(\mathrm{h})\) (d) How many upsteps are in a Catalan Path? (e) We are going to give a bijection between the set of Catalan Paths and the block \(B_{i}\) for each \(i\) between 1 and \(n\). For now, suppose the value of \(i,\) while unknown, is fixed. We take a Catalan path and break it into three pieces. The piece \(F\) (for "front") consists of all steps before the \(i\) th upstep in the Catalan path. The piece \(U\) (for "up") consists of the \(i\) th upstep. The piece \(B\) (for "back") is the portion of the path that follows the \(i\) th upstep. Thus we can think of the path as \(F U B\). Show that the function that takes \(F U B\) to \(B U F\) is a bijection from the set of Catalan Paths onto the block \(B_{i}\) of the partition. (Notice that \(B\) UF can go below the \(x\) axis.) \((\mathrm{h})\) (f) Explain how you have just given another proof of the formula for the Catalan Numbers.

What is \(\left(\begin{array}{c}n \\\ 0\end{array}\right)-\left(\begin{array}{c}n \\\ 1\end{array}\right)+\left(\begin{array}{c}n \\ 2\end{array}\right)-\cdots \pm\left(\begin{array}{c}n \\ n\end{array}\right)\) if \(n\) is an integer bigger than \(0 ?(\mathrm{~h})\)

From the symmetry of the binomial coefficients, it is not too hard to see that when \(n\) is an odd number, the number of subsets of \(\\{1,2, \ldots, n\\}\) of odd size equals the number of subsets of \(\\{1,2, \ldots, n\\}\) of even size. Is it true that when \(n\) is even the number of subsets of \(\\{1,2, \ldots, n\\}\) of even size equals the number of subsets of odd size? Why or why not? (h)

What is \(\sum_{i=0}^{n} i\left(\begin{array}{c}n \\ i\end{array}\right) ?\) (Hint: think about how you might use calculus.)

American coins are all marked with the year in which they were made. How many coins do you need to have in your hand to guarantee that on two (at least) of them, the date has the same last digit? (When we say "to guarantee that on two (at least) of them,..." we mean that you can find two with the same last digit. You might be able to find three with that last digit, or you might be able to find one pair with the last digit 1 and one pair with the last digit \(9,\) or any combination of equal last digits, as long as there is at least one pair with the same last digit.)

Show that if we have a function from a set of size \(n\) to a set of size less than \(n,\) then \(f\) is not one-to-one. \((\mathrm{h})\)

Show that if \(S\) and \(T\) are finite sets of the same size, then a function \(f\) from \(S\) to \(T\) is one-to-one if and only if it is onto. (h)

There is a generalized pigeonhole principle which says that if we partition a set with more than \(k n\) elements into \(n\) blocks, then at least one block has at least \(k+1\) elements. Prove the generalized pigeonhole principle. (h)

Show that in a set of six people, there is a set of at least three people who all know each other, or a set of at least three people none of whom know each other. (We assume that if person 1 knows person 2 , then person 2 knows person \(1 .)\) (h)