1.E: Fundamentals (Exercises)

1.2: Examples

Exercise $\PageIndex{2.1}$

Explain why an $m\times n$ board can be covered if either $m$ or $n$ is even. Explain why it cannot be covered if both $m$ and $n$ are odd.

Exercise $\PageIndex{2.2}$

Suppose two diagonally opposite corners of an ordinary $8\times8$ board are removed. Can the resulting board be covered?

Exercise $\PageIndex{2.3}$

Suppose that $m$ and $n$ are both odd. On an $m\times n$ board, colored as usual, all four corners will be the same color, say white. Suppose one white square is removed from the board. Show that the resulting board can be covered.

Exercise $\PageIndex{2.4}$

Suppose that one corner of an $8\times 8$ board is removed. Can the remainder be covered by $1\times 3$ tiles? Show a tiling or prove that it cannot be done.

Exercise $\PageIndex{2.5}$

Suppose the square in row 3, column 3 of an $8\times8$ board is removed. Can the remainder be covered by $1\times 3$ tiles? Show a tiling or prove that it cannot be done.

Exercise $\PageIndex{2.6}$

Remove two diagonally opposite corners of an $m\times n$ board, where $m$ is odd and $n$ is even. Show that the remainder can be covered with dominoes.

Exercise $\PageIndex{2.7}$

Suppose one white and one black square are removed from an $n\times n$ board, $n$ even. Show that the remainder can be covered by dominoes.

Exercise $\PageIndex{2.8}$

Suppose an $n\times n$ board, $n$ even, is covered with dominoes. Show that the number of horizontal dominoes with a white square under the left end is equal to the number of horizontal dominoes with a black square under the left end.

Exercise $\PageIndex{2.9}$

In the complete graph on five vertices shown above, there are five pairs of edges that cross. Draw this graph so that only one pair of edges cross. Remember that "edges'' do not have to be straight lines.

Exercise $\PageIndex{2.10}$

The complete bipartite graph $K_{3,3}$ consists of two groups of three vertices each, with all possible edges between the groups and no other edges:

Figure $\PageIndex{1}$

Draw this graph with only one crossing.

1.3: Combinations and Permutations

Exercise $\PageIndex{3.1}$

How many positive factors does $2\cdot3^4\cdot7^3\cdot11^2\cdot47^5$ have? How many does $p_1^{e_1}p_2^{e_2}\cdots p_n^{e_n}$ have, where the $p_i$ are distinct primes?

Exercise $\PageIndex{3.2}$

A poker hand consists of five cards from a standard 52 card deck with four suits and thirteen values in each suit; the order of the cards in a hand is irrelevant. How many hands consist of 2 cards with one value and 3 cards of another value (a full house)? How many consist of 5 cards from the same suit (a flush)?

Exercise $\PageIndex{3.3}$

Six men and six women are to be seated around a table, with men and women alternating. The chairs don't matter, only who is next to whom, but right and left are different. How many seating arrangements are possible?

Exercise $\PageIndex{3.4}$

Eight people are to be seated around a table; the chairs don't matter, only who is next to whom, but right and left are different. Two people, X and Y, cannot be seated next to each other. How many seating arrangements are possible?

Exercise $\PageIndex{3.5}$

In chess, a rook attacks any piece in the same row or column as the rook, provided no other piece is between them. In how many ways can eight rooks be placed on a chess board so that no two attack each other? What about eight rooks on a $10\times 10$ board?

Exercise $\PageIndex{3.6}$

Suppose that we want to place 8 non-attacking rooks on a chessboard. In how many ways can we do this if the 16 most `northwest' squares must be empty? How about if only the 4 most `northwest' squares must be empty?

Exercise $\PageIndex{3.7}$

A "legal'' sequence of parentheses is one in which the parentheses can be properly matched, like $()(())$. It's not hard to see that this is possible precisely when the number of left and right parentheses is the same, and every initial segment of the sequence has at least as many left parentheses as right. For example, $())\ldots$ cannot possibly be extended to a legal sequence. Show that the number of legal sequences of length $2n$ is $C_n={2n\choose n}-{2n\choose n+1}$. The numbers $C_n$ are called the Catalan numbers.

1.4: Binomial Coefficients

Exercise $\PageIndex{4.1}$

Suppose a street grid starts at position $(0,0)$ and extends up and to the right:

Figure $\PageIndex{1}$

A shortest route along streets from $(0,0)$ to $(i,j)$ is $i+j$ blocks long, going $i$ blocks east and $j$ blocks north. How many such routes are there? Suppose that the block between $(k,l)$ and $(k+1,l)$ is closed, where $k< i$ and $l\le j$. How many shortest routes are there from $(0,0)$ to $(i,j)$?

Exercise $\PageIndex{4.2}$

Prove by induction that $\sum_{k=0}^n {k\choose i} = {n+1\choose i+1}$ for $n\ge 0$ and $i\ge 0$.

Exercise $\PageIndex{4.3}$

Use a combinatorial argument to prove that $\sum_{k=0}^n {k\choose i} = {n+1\choose i+1}$ for $n\ge 0$ and $i\ge 0$; that is, explain why the left-hand side counts the same thing as the right-hand side.

Exercise $\PageIndex{4.4}$

Use a combinatorial argument to prove that ${k \choose 2} + {n-k \choose 2}+k(n-k) = {n \choose 2}$.

Exercise $\PageIndex{4.5}$

Use a combinatorial argument to prove that ${2n\choose n}$ is even.

Exercise $\PageIndex{4.6}$

Suppose that $A$ is a non-empty finite set. Prove that $A$ has as many even-sized subsets as it does odd-sized subsets.

Exercise $\PageIndex{4.7}$

Prove that $\sum_{k=0}^n {k\choose i}k = {n+1\choose i+1}n-{n+1\choose i+2}$ for $n\ge 0$ and $i\ge 0$.

Exercise $\PageIndex{4.8}$

Verify that ${n+1\choose2}+{n\choose2}=n^2$. Use Exercise $\PageIndex{4.2}$ to find a simple expression for $\sum_{i=1}^n i^2$.

Exercise $\PageIndex{4.9}$

Make a conjecture about the sums of the upward diagonals in Pascal's Triangle as indicated. Prove your conjecture is true.

Figure $\PageIndex{2}$

Exercise $\PageIndex{4.10}$

Find the number of ways to write $n$ as an ordered sum of ones and twos, $n\ge 0$. For example, when $n=4$, there are five ways: $1+1+1+1$, $2+1+1$, $1+2+1$, $1+1+2$, and $2+2$.

Exercise $\PageIndex{4.11}$

Use $(x+1)^n=\sum_{i=0}^n{n\choose i}x^i$ to find a simple expression for $\sum_{i=0}^n{1\over i+1}{n\choose i}x^{i+1}$. Then find a simple expression for $\sum_{i=0}^n{1\over i+1}{n\choose i}$.

Exercise $\PageIndex{4.12}$

Use the previous exercise to find a simple expression for $\sum_{i=0}^n(-1)^i{1\over i+1}{n\choose i}$.

Exercise $\PageIndex{4.13}$

Give a combinatorial proof of $$\sum_{i=0}^k {m\choose i}{n\choose k-i}={m+n\choose k}.\nonumber$$ Rewrite this identity in simpler form if $m=n$, and when $k=m=n$.

Exercise $\PageIndex{4.14}$

Finish the proof of Theorem 1.4.3.

Exercise $\PageIndex{4.15}$

Give an alternate proof of Theorem 1.4.3 by characterizing those $i$ for which ${n\choose i}/{n\choose i-1} > 1$.

Exercise $\PageIndex{4.16}$

When is ${n\choose i}/{n\choose i-1}$ a maximum? When is ${n\choose i}/{n\choose i-1}=2$?

Exercise $\PageIndex{4.17}$

When is ${n\choose i}-{n\choose i-1}$ a maximum?

Exercise $\PageIndex{4.18}$

A Galton board is an upright flat surface with protruding horizontal pins arranged as shown below. At the bottom are a number of bins; if the number of rows is $n$, the number of bins is $n+1$. A ball is dropped directly above the top pin, and at each pin bounces left or right with equal probability. We assume that the ball next hits the pin below and immediately left or right of the pin it has struck, and this continues down the board, until the ball falls into a bin at the bottom. If we number the bins from 0 to $n$, how many paths can a ball travel to end up in bin $k$?

This may be interpreted in terms of probability, which was the intent of Sir Francis Galton when he designed it. Each path is equally likely to be taken by a ball. If many balls are dropped, the number of balls in bin $k$ corresponds to the probability of ending up in that bin. The more paths that end in a bin, the higher the probability. When a very large number of balls are dropped, the balls will form an approximation to the bell curve familiar from probability and statistics.

There is an animation of the process at http://www.math.uah.edu/stat/apps/GaltonBoardExperiment.html. There was once a very nice physical implementation at the Pacific Science Center in Seattle.

Figure $\PageIndex{3}$

1.5: Bell Numbers

Exercise $\PageIndex{5.1}$

Show that if $\{A_1,A_2,\ldots,A_k\}$ is a partition of $\{1,2,\ldots,n\}$, then there is a unique equivalence relation $\equiv$ whose equivalence classes are $\{A_1,A_2,\ldots,A_k\}$.

Exercise $\PageIndex{5.2}$

Suppose $n$ is a square-free number, that is, no number $m^2$ divides $n$; put another way, square-free numbers are products of distinct prime factors, that is, $n=p_1p_2\cdots p_k$, where each $p_i$ is prime and no two prime factors are equal. Find the number of factorizations of $n$. For example, $30=2\cdot 3\cdot 5$, and the factorizations of 30 are 30, $6\cdot 5$, $10\cdot 3$, $2\cdot 15$, and $2\cdot 3\cdot 5$. Note we count 30 alone as a factorization, though in some sense a trivial factorization.

Exercise $\PageIndex{5.3}$

The rhyme scheme of a stanza of poetry indicates which lines rhyme. This is usually expressed in the form ABAB, meaning the first and third lines of a four line stanza rhyme, as do the second and fourth, or ABCB, meaning only lines two and four rhyme, and so on. A limerick is a five line poem with rhyming scheme AABBA. How many different rhyme schemes are possible for an $n$ line stanza? To avoid duplicate patterns, we only allow a new letter into the pattern when all previous letters have been used to the left of the new one. For example, ACBA is not allowed, since when C is placed in position 2, B has not been used to the left. This is the same rhyme scheme as ABCA, which is allowed.

Exercise $\PageIndex{5.4}$

Another way to express the Bell numbers for $n>0$ is $$B_n=\sum_{k=1}^n S(n,k),\nonumber$$ where $S(n,k)$ is the number of partitions of $\{1,2,\ldots,n\}$ into exactly $k$ parts, $1\le k\le n$. The $S(n,k)$ are the Stirling numbers of the second kind . Find a recurrence relation for $S(n,k)$. Your recurrence should allow a fairly simple triangle construction containing the values $S(n,k)$, and then the Bell numbers may be computed by summing the rows of this triangle. Show the first five rows of the triangle, $n\in\{1,2,\ldots,5\}$.

Exercise $\PageIndex{5.5}$

Let $A_n$ be the number of partitions of $\{1,2,\ldots,n+1\}$ in which no consecutive integers are in the same part of the partition. For example, when $n=3$ these partitions are $\{\{1\},\{2\},\{3\},\{4\}\}$, $\{\{1\},\{2,4\},\{3\}\}$, $\{\{1,3\},\{2\},\{4\}\}$, $\{\{1,3\},\{2,4\}\}$, $\{\{1,4\},\{2\},\{3\}\}$, so $A_3=5$. Let $A(n,k)$ be the number of partitions of $\{1,2,\ldots,n+1\}$ into exactly $k$ parts, in which no consecutive integers are in the same part of the partition. Thus $$A_n=\sum_{k=2}^{n+1} A(n,k).\nonumber$$ Find a recurrence for $A(n,k)$ and then show that $A_n=B_n$.

1.6: Choice with Repetition

Exercise $\PageIndex{6.1}$

Suppose a box contains 18 balls numbered 1–6, three balls with each number. When 4 balls are drawn without replacement, how many outcomes are possible? Do this in two ways: assuming that the order in which the balls are drawn matters, and then assuming that order does not matter.

Exercise $\PageIndex{6.2}$

How many permutations are there of the letters in Mississippi?

Exercise $\PageIndex{6.3}$

How many permutations are there of the multiset $\{1\cdot a_1,1\cdot a_2,\ldots,1\cdot a_n\}$?

Exercise $\PageIndex{6.4}$

Let $M=\sum_{i=1}^n m_i$. If $k_i< 0$, let's say $${M\choose k_1\;k_2\;\ldots\; k_n}=0.\nonumber$$

Prove that $${M\choose m_1\;m_2\;\ldots\; m_n}= \sum_{i=1}^n {M-1\choose m_1\;m_2\;\ldots\;(m_i-1)\;\ldots\; m_n}. \nonumber$$

Note that when $n=2$ this becomes $${M\choose m_1\;m_2}= {M-1\choose (m_1-1)\;m_2}+{M-1\choose m_1\;(m_2-1)}.\nonumber$$

As noted above in Equation (1.6.1), when $n=2$ we are really seeing ordinary binomial coefficients, and this can be rewritten as $${M\choose m_1}={M-1\choose m_1-1}+{M-1\choose m_1},\nonumber$$ which of course we already know.

Exercise $\PageIndex{6.5}$

The Binomial Theorem 1.4.1 can be written $$(x+y)^n=\sum_{i+j=n} {n\choose i\;j}x^i\,y^j,\nonumber$$ where the sum is over all non-negative integers $i$ and $j$ that sum to $n$. Prove that for $m\ge 2$, $$(x_1+x_2+\cdots+x_m)^n= \sum {n\choose i_1\;i_2\;\ldots\;i_m}x_1^{i_1}\,x_2^{i_2}\ldots x_m^{i_m}.\nonumber$$ where the sum is over all $i_1,\ldots,i_m$ such that $i_1+\cdots+i_m=n$.

1.7: The Pigeonhole Principle

Exercise $\PageIndex{7.1}$

Assume that the relation "friend'' is symmetric. Show that if $n\ge2$, then in any group of $n$ people there are two with the same number of friends in the group.

Exercise $\PageIndex{7.2}$

Suppose that 501 distinct integers are selected from $1\ldots1000$. Show that there are distinct selected integers $a$ and $b$ such that $a | b$. Show that this is not always true if 500 integers are selected.

Exercise $\PageIndex{7.3}$

Each of 15 red balls and 15 green balls is marked with an integer between 1 and 100 inclusive; no integer appears on more than one ball. The value of a pair of balls is the sum of the numbers on the balls. Show there are at least two pairs, consisting of one red and one green ball, with the same value. Show that this is not true if there are 13 balls of each color.

Exercise $\PageIndex{7.4}$

Suppose $(a_1,a_2,\ldots,a_{52})$ are integers, not necessarily distinct. Show that there are two, $a_i$ and $a_j$ with $i\ne j$, such that either $a_i+a_j$ or $a_i-a_j$ is divisible by 100. Show that this is not necessarily true for integers $(a_1,a_2,\ldots,a_{51})$.

Exercise $\PageIndex{7.5}$

Suppose five points are chosen from a square whose sides are length $s$. (The points may be either in the interior of the square or on the boundary.) Show that two of the points are at most $s\sqrt2/2$ apart. Find five points so that no two are less than $s\sqrt2/2$ apart.

Exercise $\PageIndex{7.6}$

Show that if the edges of $K_6$ are colored with two colors, there are at least two monochromatic triangles. (Two triangles are different if each contains at least one vertex not in the other. For example, two red triangles that share an edge count as two triangles.) Color the edges of $K_6$ so that there are exactly two monochromatic triangles.

Exercise $\PageIndex{7.7}$

Suppose the edges of a $K_5$ are colored with two colors, say red and blue, so that there are no monochromatic triangles. Show that the red edges form a cycle, and the blue edges form a cycle, each with five edges. (A cycle is a sequence of edges $\{v_1,v_2\},\{v_2,v_3\},\ldots,\{v_k,v_1\}$, where all of the $v_i$ are distinct. Note that this is true in Figure 1.7.1).

Exercise $\PageIndex{7.8}$

Show that $8< R(3,4)\le 10$.

Exercise $\PageIndex{7.9}$

Show that $R(3,4)=9$.

1.8: Sperner's Theorem

Exercise $\PageIndex{8.1}$

Sperner's Theorem (1.8.1) tells us that $\left[\begin{array}{c}6\\3\end{array}\right]$, with size 20, is the unique largest anti-chain for $2^{[6]}$. The next largest anti-chains of the form $\left[\begin{array}{c}6\\k\end{array}\right]$ are $\left[\begin{array}{c}6\\2\end{array}\right]$ and $\left[\begin{array}{c}6\\4\end{array}\right]$, with size 15. Find a maximal anti-chain with size larger than 15 but less than 20. (As usual, maximal here means that the anti-chain cannot be enlarged simply by adding elements. So you may not simply use a subset of $\left[\begin{array}{c}6\\3\end{array}\right]$.)

1.9: Stirling Numbers

Exercise $\PageIndex{9.1}$

Find a simple expression for $\left[\begin{array}{c}n\\n-1\end{array}\right]$.

Exercise $\PageIndex{9.2}$

Find a simple expression for $\left[\begin{array}{c}n\\1\end{array}\right]$.

Exercise $\PageIndex{9.3}$

What is $\sum_{k=0}^n \left[\begin{array}{c}n\\k\end{array}\right]$?

Exercise $\PageIndex{9.4}$

What is $\sum_{k=0}^n s(n,k)$?

Exercise $\PageIndex{9.5}$

Show that $x^{\underline n}=\prod_{k=0}^{n-1}(x-k)=\sum_{i=0}^n s(n,i)x^i$, $n\ge 1$; $x^{\underline n}$ is called a falling factorial. Find a similar identity for $x^{\overline n}=\prod_{k=0}^{n-1}(x+k)$; $x^{\overline n}$ is a rising factorial.

Exercise $\PageIndex{9.6}$

Show that $\sum_{k=0}^n \left\{\begin{array}{c}n\\k\end{array}\right\} x^{\underline k} = x^n$, $n\ge 1$; $x^{\underline k}$ is defined in the previous exercise. The previous exercise shows how to express the falling factorial in terms of powers of $x$; this exercise shows how to express the powers of $x$ in terms of falling factorials.

Exercise $\PageIndex{9.7}$

Prove: $S(n,k)=\sum_{i=k-1}^{n-1} {n-1\choose i}S(i,k-1)$.

Exercise $\PageIndex{9.8}$

Prove: $\left[\begin{array}{c}n\\k\end{array}\right]=\sum_{i=k-1}^{n-1} (n-i-1)! {n-1\choose i}\left[\begin{array}{c}i\\k-1\end{array}\right]$.

Exercise $\PageIndex{9}$

Use the previous exercise to prove $s(n,k)=\sum_{i=k-1}^{n-1} (-1)^{n-i-1}(n-i-1)! {n-1\choose i}s(i,k-1)$.

Exercise $\PageIndex{10}$

We have defined $\left[\begin{array}{c}n\\k\end{array}\right]$ and $\left\{\begin{array}{c}n\\k\end{array}\right\}$ for $n,k\ge 0$. We want to extend the definitions to all integers. Without some extra stipulations, there are many ways to do this. Let us suppose that for $n\not=0$ we want $\left[\begin{array}{c}n\\0\end{array}\right]=\left[\begin{array}{c}0\\n\end{array}\right]=\left\{\begin{array}{c}n\\0\end{array}\right\}=\left\{\begin{array}{c}0\\n\end{array}\right\}=0$, and we want the recurrence relations of equation 1.9.1 and in Theorem 1.9.1 to be true. Show that under these conditions there is a unique way to extend the definitions to all integers, and that when this is done, $\left\{\begin{array}{c}n\\k\end{array}\right\}=\left[\begin{array}{c}-k\\-n\end{array}\right]$ for all integers $n$ and $k$. Thus, the extended table of values for either $\left[\begin{array}{c}n\\k\end{array}\right]$ or $\left\{\begin{array}{c}n\\k\end{array}\right\}$ will contain all the values of both $\left[\begin{array}{c}n\\k\end{array}\right]$ and $\left\{\begin{array}{c}n\\k\end{array}\right\}$.

Exercise $\PageIndex{11}$

Under the assumptions that $s(n,0)=s(0,n)=0$ for $n\not=0$, and $s(n,k) = s(n-1,k-1) - (n-1)s(n-1,k)$, extend the table for $s(n,k)$ to all integers, and find a connection to $S(n,k)$ similar to that in the previous problem.

Exercise $\PageIndex{12}$

Prove Corollary 1.9.1.

Exercise $\PageIndex{13}$

Prove the remaining part of Theorem 1.9.2.