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?
Note that we must walk at least ten blocks, so ten is the smallest number of blocks possible. In how many of those ten blocks must we walk north?
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)\text{,}\) 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.
What is the length of a lattice path from \((0,0)\) to \((m,n)\text{?}\)
How many such lattice paths of that length are there?
In ProblemĀ 47 you saw that we had to make ten choices of north or east, choosing north four times.
How many lattice paths are there from \((i,j)\) to \((m,n)\text{,}\) assuming \(i\text{,}\) \(j\text{,}\) \(m\text{,}\) and \(n\) are integers?
This problem is actually a bit tricky. What happens to the answer if \(i \gt m\) or \(j \gt n\text{?}\) Remember that paths go up or to the right.
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.)
Describe which points are connected to \((0,0)\) by diagonal lattice paths.
Where can you go from (0,0) in one step? In two steps? In any of these cases, what can you say about the sum of the coordinates of a point you can get to? Can you find any other relationship between the x- and y-coordinates of a point you can get to? For example, can you get to the point (1, 3)?
What is the length of a diagonal lattice path from \((0,0)\) to \((m,n)\text{?}\)
Assuming that \((m,n)\) is such a point, how many diagonal lattice paths are there from \((0,0)\) to \((m,n)\text{?}\)
How many choices do you have to make in order to choose a path?
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 \(2n\) people come to the play, and exactly half of them pay with ten dollar bills.
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)\text{.}\)
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 \((2n,0)\text{.}\)
In each case, what is the geometric interpretation of a sequence that does not require the teacher to give any IOUs?
In each part, each such sequence corresponds to a path that can't cross over (but may touch) a certain line.
Notice that a lattice path from \((0,0)\) to \((n,n)\) stays inside (or on the edges of) the square whose sides are the \(x\)-axis, the \(y\)-axis, the line \(x=n\) and the line \(y=n\text{.}\) In this problem we will compute the number of lattice paths from (0,0) to \((n,n)\) that stay inside (or on the edges of) the triangle whose sides are the \(x\)-axis, the line \(x=n\) and the line \(y=x\text{.}\) For example, in FigureĀ 1.3.1 we show the grid of points with integer coordinates for the triangle whose sides are the \(x\)-axis, the line \(x=4\) and the line \(y=x\text{.}\)
Explain why the number of lattice paths from \((0,0)\) to \((n,n)\) that go outside the triangle is the number of lattice paths from \((0,0)\) to \((n,n)\) that either touch or cross the line \(y=x+1\text{.}\)
Find a bijection between lattice paths from \((0,0)\) to \((n,n)\) that touch (or cross) the line \(y=x+1\) and lattice paths from \((-1,1)\) to \((n,n)\text{.}\)
Given a path from \((0, 0)\) to \((n, n)\) which touches or crosses the line \(y = x + 1\text{,}\) how can you modify the part of the path from \((0, 0)\) to the first touch of \(y = x + 1\) so that the modified path starts instead at \((-1, 1)\text{?}\) The trick is to do this in a systematic way that will give you your bijection.
Find a formula for the number of lattice paths from \((0,0)\) to \((n,n)\) that do not go above the line \(y=x\text{.}\) The number of such paths is called a Catalan Number and is usually denoted by \(C_n\text{.}\)
A path either touches the line \(y = x + 1\) or it doesn't. This partitions the set of paths into two blocks.
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.ā3āThe result we will derive is called the Chung-Feller Theorem; this approach is based of a paper of Wen-jin Woan āUniform Partitions of Lattice Paths and Chung-Feller Generalizations,ā American Mathematics Monthly 58 June/July 2001, p556. 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 \((2n,0)\) a Catalan Path of length \(2n\text{.}\) Thus the number of Catalan Paths of length \(2n\) is the Catalan Number \(C_n\text{.}\)
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\le n\text{?}\)
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)\text{?}\) Explain why a Dyck Path whose rightmost absolute minimum point is its last point is a Catalan Path.
Look back at the definition of a Dyck Path and a Catalan Path.
Let \(D\) be the set of all diagonal lattice paths from \((0,0)\) to \((2n,0)\text{.}\) (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\text{.}\)
What makes this part difficult is understanding how we are partitioning the paths. As an example, \(B_0\) is the set of all paths that have no upsteps following the last absolute minimum. Can such a path have downsteps after the last absolute minimum? (The description we gave of \(B_0\) is not succinct enough to be the answer to the second question of this part.) As another example \(B_1\) is the set of all paths that have exactly one upstep and perhaps some downsteps after the last absolute minimum. Is it possible, though, for a path in \(B_1\) to have any downsteps after the last absolute minimum? A path in \(B_2\) has exactly two upsteps after its last absolute minimum. If is possible to have one downstep after the last absolute minimum, but it has to be in a special place. What place is that? Now to figure out how many parts our partition has, we need to know the maximum number of upsteps a path can have following its last absolute minimum. What is this maximum? It might help to draw some pictures with \(n = 5\) or \(6\text{.}\) In particular, is it possible that all upsteps occur after the last absolute minimum?
How many upsteps are in a Catalan Path?
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\text{.}\) For now, suppose the value of \(i\text{,}\) 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 \(FUB\text{.}\) Show that the function that takes \(FUB\) to \(BUF\) is a bijection from the set of Catalan Paths onto the block \(B_i\) of the partition. (Notice that \(BUF\) can go below the \(x\) axis.)
Using \(d\) for down and \(u\) for up, we could have \(uudduuddudud\) as our Catalan path. Suppose that \(i = 5\text{.}\) The fifth upstep is the \(u\) in position 9. Thus \(F = uudduudd\text{,}\) \(U = u\text{,}\) and \(B = dud\text{.}\) Now \(BU F\) is \(duduuudduudd\text{.}\) This is a Dyck path that begins by going below the \(x\)-axis. The \(d\)'s in positions 1 and 3 take the path to the \(y\)-coordinate \(-1\text{.}\) Then the \(y\) coordinate climbs to 2, goes back to 0, up to 2 again, and finally down to 0. So the absolute minimum is \(-1\text{,}\) and it occurs in the first and third position. There are five \(u\)'s after the third positon. So this Dyck path is in the block \(B_5\) of our partition. Now comes the crucial question. Why were there five u's after that last absolute minimum in position 3? Try with the same path and \(i = 3\text{.}\) Figure out why there are three u's after the last absolute minimum in the resulting path. All this discussion should explain why when \(i = 5\text{,}\) the set of all Catalan paths is mapped into the set \(B_5\text{.}\) Keeping \(i = 5\) for a while, try to see why this correspondence between Catalan paths and \(B_5\) is a bijection. Then, if you need to, do the same thing with \(i = 3\text{.}\) This should give you enough insight to do the general case.
Explain how you have just given another proof of the formula for the Catalan Numbers.
We know that \((x+y)^2 = x^2+2xy+y^2\text{.}\) Multiply both sides by \((x+y)\) to get a formula for \((x+y)^3\) and repeat to get a formula for \((x+y)^4\text{.}\) Do you see a pattern? If so, what is it? If not, repeat the process to get a formula for \((x+y)^5\) and look back at FigureĀ 1.2.4 to see the pattern. Conjecture a formula for \((x+y)^n\text{.}\)
When we apply the distributive law \(n\) times to \((x+y)^n\text{,}\) we get a sum of terms of the form \(x^iy^{n-i}\) for various values of the integer \(i\text{.}\) If it is clear to you that each term of the form \(x^iy^{n-i}\) that we get comes from choosing an \(x\) from \(i\) of the \((x+y)\) factors and a \(y\) from the remaining \(n-i\) of the factors and multiplying these choices together, then answer partĀ a of the problem and skip partĀ b. In either case, be sure to answer partĀ c.
In how many ways can we choose an \(x\) from \(i\) terms and a \(y\) from \(n-i\) terms?
We can take this step-by-step and consider a small case to get started.
Expand the product \((x_1 +y_1)(x_2 +y_2)(x_3+y_3)\text{.}\)
What do you get when you substitute \(x\) for each \(x_i\) and \(y\) for each \(y_i\text{?}\)
Now imagine expanding
Once you apply the commutative law to the individual terms you get, you will have a sum of terms of the form
What is the set \(\{k_1,k_2,\ldots, k_i\}\cup \{j_1,j_2,\ldots, j_{n-i}\}\text{?}\)
In how many ways can you choose the set \(\{k_1,k_2,\ldots, k_i\}\text{?}\)
Once you have chosen this set, how many choices do you have for \(\{j_1,j_2,\ldots, j_{n-i}\}\text{?}\)
If you substitute \(x\) for each \(x_i\) and \(y\) for each \(y_i\text{,}\) how many terms of the form \(x^iy^{n-i}\) will you have in the expanded product
How many terms of the form \(x^{n-i}y^i\) will you have?
Explain how you have just proved your conjecture from ProblemĀ 53. The theorem you have proved is called the Binomial Theorem.
What is \(\sum_{i=1}^{10} \binom{10}{i}3^i\text{?}\)
What would the lower limit of the sum have to be for this problem to be a routine application of the binomial theorem?
What is \(\binom{n}{0}-\binom{n}{1}+\binom{n}{2}-\cdots \pm \binom{n}{n}\) if \(n\) is an integer bigger than 0?
What does the binomial theorem give you for \((x - y)^n\text{?}\)
Explain why
Find two different explanations.
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?
For example when \(n = 3\text{,}\) we have \(\binom{3}{0} = \binom{3}{3}\) and \(\binom{3}{1} = \binom{3}{2}\text{.}\) The number of subsets of even size is \(\binom{3}{0}+\binom{3}{2}\) and the number of subsets of odd size is \(\binom{3}{1} + \binom{3}{3}\text{,}\) and the two sums can be paired off into equal terms. When we subtract the number of subsets of odd size from the number of subsets of even size, the pairing also gives us \(\binom{3}{0} - \binom{3}{1} + \binom{3}{2} - \binom{3}{3} = 0\text{.}\)
What is \(\sum_{i=0}^n i\binom{n}{i}\text{?}\) (Hint: think about how you might use calculus.)
Take the derivative of something interesting.
Notice how the proof you gave of the binomial theorem was a counting argument. It is interesting that an apparently algebraic theorem that tells us how to expand a power of a binomial is proved by an argument that amounts to counting the individual terms of the expansion. Part of the reason that combinatorial mathematics turns out to be so useful is that counting arguments often underlie important results of algebra. As the algebra becomes more sophisticated, so do the families of objects we have to count, but nonetheless we can develop a great deal of algebra on the basis of counting.
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.)
There are many ways in which you might explain your answer to ProblemĀ 60. For example, you can partition the coins according to the last digit of their date; that is, you put all the coins with a given last digit in a block together, and put no other coins in that block; repeating until all coins are in some block. Then you have a partition of your set of coins. If no two coins have the same last digit, then each block has exactly one coin. Since there are only ten digits, there are at most ten blocks and so by the sum principle there are at most ten coins. In fact with ten coins it is possible to have no two with the same last digit, but with 11 coins some block must have at least two coins in order for the sum of the sizes of at most ten blocks to be 11. This is one explanation of why we need 11 coins in ProblemĀ 60. This kind of situation arises often in combinatorial situations, and so rather than always using the sum principle to explain our reasoning , we enunciate another principle which we can think of as yet another variant of the sum principle. The pigeonhole principle states that
If we partition a set with more than \(n\) elements into \(n\) parts, then at least one part has more than one element.
The pigeonhole principle gets its name from the idea of a grid of little boxes that might be used, for example, to sort mail, or as mailboxes for a group of people in an office. The boxes in such grids are sometimes called pigeonholes in analogy with stacks of boxes used to house homing pigeons when homing pigeons were used to carry messages. People will sometimes state the principle in a more colorful way as āif we put more than \(n\) pigeons into \(n\) pigeonholes, then some pigeonhole has more than one pigeon.ā
Show that if we have a function from a set of size \(n\) to a set of size less than \(n\text{,}\) then \(f\) is not one-to-one.
To prove that each function from a set \(S\) of size \(n\) to a set of size less than \(n\) is not one-to-one, we must prove that regardless of the function \(f\) that we choose, there are always two elements, say \(x\) and \(y\text{,}\) such that \(f(x) = f(y)\text{.}\)
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.
There is a generalized pigeonhole principle which says that if we partition a set with more than \(kn\) elements into \(n\) blocks, then at least one block has at least \(k+1\) elements. Prove the generalized pigeonhole principle.
The statement of the generalized pigeonhole principle involves the number of elements in a block, so a counting principle is likely to help you.
All the powers of five end in a five, and all the powers of two are even. Show that for for some integer \(n\text{,}\) if you take the first \(n\) powers of a prime other than two or five, one must have ā01ā as the last two digits.
You may choose a specific number for \(n\) if you want to. Notice that the last two digits of the powers of a prime other than two cannot represent an even number.
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.)
While this sounds like a pigeonhole principle problem, the ordinary pigeonhole principle doesn't guarantee three of something.
Draw five circles labeled Al, Sue, Don, Pam, and Jo. Find a way to draw red and green lines between people so that every pair of people is joined by a line and there is neither a triangle consisting entirely of red lines or a triangle consisting of green lines. What does ProblemĀ 65 tell you about the possibility of doing this with six people's names? What does this problem say about the conclusion of ProblemĀ 65 holding when there are five people in our set rather than six?
ProblemsĀ 65ā66 together show that six is the smallest number \(R\) with the property that if we have \(R\) people in a room, then there is either a set of (at least) three mutual acquaintances or a set of (at least) three mutual strangers. Another way to say the same thing is to say that six is the smallest number so that no matter how we connect 6 points in the plane (no three on a line) with red and green lines, we can find either a red triangle or a green triangle. There is a name for this property. The Ramsey Number \(R(m,n)\) is the smallest number \(R\) so that if we have \(R\) people in a room, then there is a set of at least \(m\) mutual acquaintances or at least \(n\) mutual strangers. There is also a geometric description of Ramsey Numbers; it uses the idea of a complete graph on \(R\) vertices. A complete graph on \(R\) vertices consists of \(R\) points in the plane together with line segments (or curves) connecting each two of the \(R\) vertices.ā4āAs you may have guessed, a complete graph is a special case of something called a graph. The word graph will be defined in SubsectionĀ 2.3.1. The points are called vertices and the line segments are called edges. In FigureĀ 1.3.2 we show three different ways to draw a complete graph on four vertices. We use \(K_n\) to stand for a complete graph on \(n\) vertices.
Our geometric description of \(R(3,3)\) may be translated into the language of graph theory (which is the subject that includes complete graphs) by saying \(R(3,3)\) is the smallest number \(R\) so that if we color the edges of a \(K_R\) with two colors, then we can find in our picture a \(K_3\) all of whose edges have the same color. The graph theory description of \(R(m,n)\) is that \(R(m,n)\) is the smallest number \(R\) so that if we color the edges of a \(K_R\) with red and green, then we can find in our picture either a \(K_m\) all of whose edges are red or a \(K_n\) all of whose edges are green. Because we could have said our colors in the opposite order, we may conclude that \(R(m,n) = R(n,m)\text{.}\) In particular \(R(n,n)\) is the smallest number \(R\) such that if we color the edges of a \(K_R\) with two colors, then our picture contains a \(K_n\) all of whose edges have the same color.
Since \(R(3,3)=6\text{,}\) an uneducated guess might be that \(R(4,4)=8\text{.}\) Show that this is not the case.
What usually makes it hard for students to start this problem is the fact that we just defined what \(R(4, 4)\) is, and not what it means for a number not to be \(R(4, 4)\text{.}\) So to get started, try to write down what it means to say \(R(4, 4)\) is not 8. You will see that there are two things that can keep \(R(4, 4)\) from being 8. You need to figure out which one happens and explain why. One such explanation could involve the graph \(K_8\) .
Show that among ten people, there are either four mutual acquaintances or three mutual strangers. What does this say about \(R(4,3)\text{?}\)
Review ProblemĀ 65 and your solution of it.
Show that among an odd number of people there is at least one person who is an acquaintance of an even number of people and therefore also a stranger to an even number of people.
Let \(a_i\) be the number of acquaintances of person \(i\text{.}\) Can you explain why the sum of the numbers \(a_i\) is even?
Find a way to color the edges of a \(K_8\) with red and green so that there is no red \(K_4\) and no green \(K_3\text{.}\)
Often when there is a counter-example, there is one with a good deal of symmetry. (Caution: there is a difference between often and always!) One way to help yourself get a symmetric example, if there is one, is to put 8 vertices into a circle. Then, perhaps, you might draw green edges in some sort of regular fashion until it is impossible to draw another green edge between any two of the vertices without creating a green triangle.
Find \(R(4,3)\text{.}\)
In ProblemĀ 68 you showed that \(R(4, 3) \le 10\text{.}\) In ProblemĀ 70 you showed that \(R(4, 3) \gt 8\text{.}\) Thus \(R(4, 3)\) is either 9 or 10. Deciding which is the case is just plain hard. But there is a relevant problem we have done that we haven't used yet.
As of this writing, relatively few Ramsey Numbers are known. \(R(3,n)\) is known for \(n\lt 10\text{,}\) \(R(4,4) = 18\text{,}\) and \(R(5,4)=R(4,5)=25\text{.}\)
