91Ó°ÊÓ

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?

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?

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?

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

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 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)

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.

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)