1.3: Some Applications of Basic Counting Principles

1.3.1: Lattice Paths and Catalan Numbers

$\circ$ Exercise $47$

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? (Hint).

$\cdot$ Exercise $48$

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.

1. What is the length of a lattice path from $(0, 0)$ to $(m, n)$?
2. How many such lattice paths of that length are there? (Hint).
3. How many lattice paths are there from $(i, j)$ to $(m, n)$, assuming $i, j, m$, and $n$ are integers? (Hint).

$\cdot$ Exercise $49$

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

1. Describe which points are connected to $(0, 0)$ by diagonal lattice paths. (Hint).
2. What is the length of a diagonal lattice path from $(0, 0)$ to $(m, n)$?
3. Assuming that $(m, n)$ is a point you can get to from $(0, 0)$, how many diagonal lattice paths are there from $(0, 0)$ to $(m, n)$? (Hint).

$\circ$ Exercise $50$

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.

1. 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)$.
2. Describe a bijection between the set of sequences of tens and twenties that people give the teacher and the set of diagonal lattice paths between $(0, 0)$ and $(2n, 0)$.
3. In each of the previous parts, what is the geometric interpretation of a sequence that does not require the teacher to give any IOUs? (Hint).

$→ \; \cdot$ Exercise $51$

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$. 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$. Such lattice paths are called Catalan paths. 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$.

a. Explain why the number of lattice paths from $(0, 0)$ to $(n, n)$ that go outside the triangle described previously is the number of lattice paths from $(0, 0)$ to $(n, n)$ that either touch or cross the line $y = x + 1$.

b. 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)$. (Hint).

c. Find a formula for the number of lattice paths from $(0, 0)$ to $(n, n)$ that do not go above the line $y = x$. The number of such paths is called a Catalan Number and is usually denoted by $C_{n}$. (Hint).

Figure $\PageIndex{1}$: The Catalan paths from $(0, 0)$ to $(i, i)$ for $i = 0, 1, 2, 3, 4$. The number of paths to the point $(i, i)$ is shown just above that point. (Copyright; author via source)

$\rightarrow$ Exercise $52$

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 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 (diagonal) Catalan Path of length $2n$. Thus the number of (diagonal) Catalan Paths of length $2n$ is the Catalan Number $C_n$. We normally can decide from context whether the phrase Catalan Path refers to a diagonal path, so we normally leave out the word diagonal.

1. 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$?
2. 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. (Hint).
3. Let $D$ be the set of all diagonal lattice paths from $(0, 0)$ to $(2n, 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}$. (Hint).
4. How many upsteps are in a Catalan Path?
5. *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^{\text{th}}$ upstep in the Catalan path. The piece $U$ (for “up”) consists of the $i^{\text{th}}$ upstep. The piece $B$ (for “back”) is the portion of the path that follows the $i^{\text{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 U F$ can go below the $x$ axis.) (Hint).
6. Explain how you have just given another proof of the formula for the Catalan Numbers.

1.3.2: The Binomial Theorem

$\circ$ Exercise $53$

We know that $(x+y)^{2} = x^{2}+2xy+y^{2}$. Multiply both sides by $(x+y)$ to get a formula for $(x + y)^{3}$ and repeat to get a formula for $(x + y)^{4}$. 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}$.

$\bullet$ Exercise $54$

When we apply the distributive law $n$ times to $(x+y)^{n}$, we get a sum of terms of the form $x^{i}y^{n−i}$ for various values of the integer $i$.

1. If it is clear to you that each term of the form $x^{i}y^{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 this part of the problem and skip the next part. Otherwise, do the next part instead of this one. In how many ways can we choose an $x$ from $i$ terms and a $y$ from $n - i$ terms?
   1. Expand the product $(x_{1} + y_{1})(x_{2} + y_{2})(x_{3} + y_{3})$.
   2. What do you get when you substitute $x$ for each $x_{i}$ and $y$ for each $y_{i}$?
   3. Now imagine expanding
      $$(x_{1} + y_{1})(x_{2} + y_{2}) \dotsi (x_{n} + y_{n}).$$
      Once you apply the commutative law to the individual terms you get, you will have a sum of terms of the form
      $$x_{k_{1}}x_{k_{2}} \dotsi x_{k_{i}} \cdot y_{j_{1}}y_{j_{2}} \dotsi y_{j_{n−i}}.$$
      What is the set $\{k_{1}, k_{2}, \dotsc, k_{i}\} \bigcup \{j_{1}, j_{2}, \dotsc, j_{n−i}\}$?
   4. In how many ways can you choose the set $\{k_{1}, k_{2}, \dotsc, k_{i}\}$?
   5. Once you have chosen this set, how many choices do you have for $\{j_{1}, j_{2}, \dotsc, j_{n−i}\}$?
   6. If you substitute $x$ for each $x_i$ and $y$ for each $y_i$, how many terms of the form $x^iy^{n−i}$ will you have in the expanded product
      $$(x_{1} + y_{1})(x_{2} + y_{2}) \dotsc (x_{n} + y_{n}) = (x + y)^{n}?$$
   7. How many terms of the form $x^{n−i}y^{i}$ will you have?
2. Explain how you have just proved your conjecture from Problem. The theorem you have proved is called the Binomial Theorem.

Exercise $55$

What is $\Sigma^{10}_{i=1}\binom{10}{i}3^{i}$? (Hint).

Exercise $56$

What is $\binom{n}{0} - \binom{n}{1} + \binom{n}{2} - \dotsi \pm \binom{n}{n}$ if $n$ is an integer bigger than zero? (Hint).

$\rightarrow \bullet$ Exercise $57$

Explain why

$\sum^{k}_{i=0} \binom{m}{i} \binom{n}{k-i} = \binom{m+n}{k}$

Find two different explanations. (Hint).

$\rightarrow$ Exercise $58$

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, . . . , n\}$ of odd size equals the number of subsets of $\{1, 2, . . . , n\}$ of even size. Is it true that when $n$ is even the number of subsets of $\{1, 2, . . . , n\}$ of even size equals the number of subsets of odd size? Why or why not? (Hint).

$\rightarrow$ Exercise $59$

What is $\Sigma^{n}_{i=0} i \binom{n}{i}$? (Hint: think about how you might use calculus.) (Hint).

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.

1.3.3: The Pigeonhole Principle

$\circ$ Exercise $\PageIndex{1}$

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.”

Exercise $61$

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. (Hint).

$\bullet$ Exercise $62$

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. (Hint).

$\cdot$ Exercise $63$

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. (Hint).

Exercise $64$

All the powers of five end in a five, and all the powers of two are even. Show that for some integer $n$, if you take the first $n$ powers of a prime other than two or five, one must have “$01$” as the last two digits. (Hint).

$\rightarrow \; \cdot$ Exercise $65$

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.) (Hint).

$\cdot$ Exercise $66$

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?

1.3.4: Ramsey Numbers

Problems 65 and 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 six 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.¹ 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.

Figure $\PageIndex{2}$: Three ways to draw a complete graph on four vertices. (Copyright; author via source)

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 Km 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)$. 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 Kn all of whose edges have the same color.

$\cdot$ Exercise $67$

Since $R(3, 3) = 6$, an uneducated guess might be that $R(4, 4) = 8$. Show that this is not the case. (Hint).

$\cdot$ Exercise $68$

Show that among ten people, there are either four mutual acquaintances or three mutual strangers. What does this say about $R(4, 3)$? (Hint).

$\cdot$ Exercise $69$

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. (Hint).

$\cdot$ Exercise $70$

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}$. (Hint).

$\rightarrow \; \cdot$ Exercise $71$

Find $R(4, 3)$. (Hint).

As of this writing, relatively few Ramsey Numbers are known. $R(3, n)$ is known for $n < 10, R(4, 4) = 18$, and $R(5, 4) = R(4, 5) = 25$.

Notes

1. 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.