Chapter 6

Prove the binomial theorem, using mathematical induction.

Let \(A(n, r)\) denote the number of additions needed to compute \(C(n, r)\) by its recursive definition. Compute each. \(A(3,2)\)

Find the number of positive divisors of the following positive integers. $$ 600 $$

Solve each equation. $$P(n, n-1)=5040$$

Let \(p\) denote the probability of success in a Bernoulli trial. Prove that the expected number of successes in a sequence of \(n\) Bernoulli trials is \(n p .\) (Hint: Use the binomial theorem.)

Using a combinatorial argument prove that $$\left(\begin{array}{l} n \\ m \end{array}\right)\left(\begin{array}{l} m \\ r \end{array}\right)=\left(\begin{array}{l} n \\ r \end{array}\right)\left(\begin{array}{l} n-r \\ m-r \end{array}\right) \quad \text { (Newton's identity) }$$ (Hint: Select an \(r\) -element subset of an \(n\) -element set in two ways.)

Let \(A(n, r)\) denote the number of additions needed to compute \(C(n, r)\) by its recursive definition. Compute each. \(A(5,3)\)

A number-theoretic function used in the study of perfect numbers is the tau function \(\tau\) on \(\mathbb{N}\). \((\tau \text { is the Greek letter, tau.) } \tau(n)\) denotes the number of positive divisors of \(n \in \mathbb{N} .\) Let \(n=p_{1}^{e_{1}} p_{2}^{e_{2}} \cdots p_{k}^{e_{k}},\) where \(p_{1}, p_{2}, \ldots, p_{k}\) are distinct primes and \(e_{1}, e_{2}, \ldots, e_{k} \in \mathbf{W} .\) Find \(\tau(n)\).

Solve each equation. $$P(5, r)=20$$

Define \(A(n, r)\) recursively.

Using Theorem \(6.4,\) prove that \(P(n, r)=P(n-1, r)+r P(n-1, r-1)\) .

Prove the result in Exercise 44 algebraically. The following result is known as Vandermonde's identity, after the German mathematician Abnit-Theophile Vandermonde (1735-1796): $$\left(\begin{array}{c}m+n \\ r\end{array}\right)=\left(\begin{array}{c}m \\\ 0\end{array}\right)\left(\begin{array}{c}n \\\ r\end{array}\right)+\left(\begin{array}{c}m \\\ 1\end{array}\right)\left(\begin{array}{c}n \\\ r-1\end{array}\right)+\left(\begin{array}{c}m \\\ 2\end{array}\right)\left(\begin{array}{c}n \\\ r-2\end{array}\right)+\cdots+\left(\begin{array}{c}m \\\ r\end{array}\right)\left(\begin{array}{l}n \\ 0\end{array}\right)$$

The following result is known as Vandermonde's identity, after the German mathematician Abnit-Theophile Vandermonde \((1735-1796) :\) $$ \left(\begin{array}{c}{m+n} \\\ {r}\end{array}\right)=\left(\begin{array}{c}{m} \\\ {0}\end{array}\right)\left(\begin{array}{c}{n} \\\ {r}\end{array}\right)+\left(\begin{array}{c}{m} \\\ {1}\end{array}\right)\left(\begin{array}{c}{n} \\\ {1}\end{array}\right)\left(\begin{array}{c}{n} \\\ {r-1}\end{array}\right)+\left(\begin{array}{c}{m} \\\ {2}\end{array}\right)\left(\begin{array}{c}{n} \\\ {r-2}\end{array}\right)+\cdots+\left(\begin{array}{c}{m} \\\ {r}\end{array}\right)\left(\begin{array}{c}{n} \\ {0}\end{array}\right) $$ Prove Vandermonde's identity, using a combinatorial argument. (Hint: Consider the ways of selecting \(r\) people from a group of \(m\) men and \(n\) women.)

Verify each. $$(n+1) !+n !=(n+2) n !$$

Find the number of ternary words that have: Length at most 3.

Prove Vandermonde's identity, using a combinatorial argument. (Hint: Consider the ways of selecting \(r\) people from a group of \(m\) men and \(n\) women.

The following result is known as Vandermonde's identity, after the German mathematician Abnit-Theophile Vandermonde \((1735-1796) :\) $$ \left(\begin{array}{c}{m+n} \\\ {r}\end{array}\right)=\left(\begin{array}{c}{m} \\\ {0}\end{array}\right)\left(\begin{array}{c}{n} \\\ {r}\end{array}\right)+\left(\begin{array}{c}{m} \\\ {1}\end{array}\right)\left(\begin{array}{c}{n} \\\ {1}\end{array}\right)\left(\begin{array}{c}{n} \\\ {r-1}\end{array}\right)+\left(\begin{array}{c}{m} \\\ {2}\end{array}\right)\left(\begin{array}{c}{n} \\\ {r-2}\end{array}\right)+\cdots+\left(\begin{array}{c}{m} \\\ {r}\end{array}\right)\left(\begin{array}{c}{n} \\ {0}\end{array}\right) $$ Prove Vandermonde's identity algebraically. [Hint: Consider \((1+x)^{m}(x+1)^{n}=(1+x)^{m+n} . ]\)

Recall that the \(n\) th Catalan number \(C_{n}\) is defined by \(C_{n}=\frac{(2 n) !}{n !(n+1) !}, \quad n \geq 0\) Show that \(C_{n}=C(2 n, n)-C(2 n, n-1)\)

Find the number of ternary words that have: Length at most 5.

Prove Vandermonde's identity algebraically. [Hint: Consider \((1+x)^{m}(x+1)^{n}=(1+x)^{m+n} .\)]

Verify each. $$(n+1) !-n !=n(n !)$$

The following result is known as Vandermonde's identity, after the German mathematician Abnit-Theophile Vandermonde \((1735-1796) :\) $$ \left(\begin{array}{c}{m+n} \\\ {r}\end{array}\right)=\left(\begin{array}{c}{m} \\\ {0}\end{array}\right)\left(\begin{array}{c}{n} \\\ {r}\end{array}\right)+\left(\begin{array}{c}{m} \\\ {1}\end{array}\right)\left(\begin{array}{c}{n} \\\ {1}\end{array}\right)\left(\begin{array}{c}{n} \\\ {r-1}\end{array}\right)+\left(\begin{array}{c}{m} \\\ {2}\end{array}\right)\left(\begin{array}{c}{n} \\\ {r-2}\end{array}\right)+\cdots+\left(\begin{array}{c}{m} \\\ {r}\end{array}\right)\left(\begin{array}{c}{n} \\ {0}\end{array}\right) $$ Find a formula for \(\sum_{i=2}^{n}\left(\begin{array}{l}{i} \\\ {2}\end{array}\right)\)

Prove each. $$C_{n}=\frac{1}{n+1} C(2 n, n), \quad n \geq 0$$

Prove by induction that \(1 \cdot 1 !+2 \cdot 2 !+\cdots+n \cdot n !=(n+1) !-1, n \geq 1\).

Find a formula for \(\sum_{i=2}^{n}\left(\begin{array}{l}i \\\ 2\end{array}\right).\)

Prove each. $$C_{n}=\frac{2(2 n-1)}{n+1} C_{n-1}, \quad n \geq 1$$

Find the number of ternary words that have: Length 3 and are palindromes.

Find the number of ternary words that have: Length 4 and are palindromes.

Find a formula for \(\sum_{i=3}^{n}\left(\begin{array}{l}i \\\ 3\end{array}\right).\)

Show that \((n !) !>(2 n) !,\) if \(n>3\).

Find the number of ternary words that have: $$4 \leq \text { length } \leq 6$$

Show that \(C_{n}=3 C_{n-1}+\left(C_{n-1}-\frac{6}{n+1} C_{n-1}\right), n \geq 1\).

The following result is known as Vandermonde's identity, after the German mathematician Abnit-Theophile Vandermonde \((1735-1796) :\) $$ \left(\begin{array}{c}{m+n} \\\ {r}\end{array}\right)=\left(\begin{array}{c}{m} \\\ {0}\end{array}\right)\left(\begin{array}{c}{n} \\\ {r}\end{array}\right)+\left(\begin{array}{c}{m} \\\ {1}\end{array}\right)\left(\begin{array}{c}{n} \\\ {1}\end{array}\right)\left(\begin{array}{c}{n} \\\ {r-1}\end{array}\right)+\left(\begin{array}{c}{m} \\\ {2}\end{array}\right)\left(\begin{array}{c}{n} \\\ {r-2}\end{array}\right)+\cdots+\left(\begin{array}{c}{m} \\\ {r}\end{array}\right)\left(\begin{array}{c}{n} \\ {0}\end{array}\right) $$ Using Exercises \(48-51,\) predict a formula for \(\sum_{i=1}^{n}\left(\begin{array}{l}{i} \\ {k}\end{array}\right)\)

The \(n\)th Catalan number satisfies the recurrence relation \(C_{n}=\sum_{i=0}^{n-1} C_{i} C_{n-1-i},\) \(n \geq 2 .\) Note: This relation can be used to compute \(C_{n}\) using \(n\) multiplications, \(n-1\) additions, and no divisions.) Use it to compute each Catalan number. $$C_{4}$$

In an alphabet of \(m\) characters, how many words have: Length 3?

The \(n\) th Catalan number satisfies the recurrence relation \(C_{n}=\sum_{i=0}^{n-1} C_{i} C_{n-1-i}\) \(n \geq 2 .\) (Note: This relation can be used to compute \(C_{n}\) using \(n\) multiplications, \(n-1\) additions, and no divisions.) Use it to compute each Catalan number. $$C_{4}$$

The \(n\)th Catalan number satisfies the recurrence relation \(C_{n}=\sum_{i=0}^{n-1} C_{i} C_{n-1-i},\) \(n \geq 2 .\) Note: This relation can be used to compute \(C_{n}\) using \(n\) multiplications, \(n-1\) additions, and no divisions.) Use it to compute each Catalan number. $$C_{5}$$

In an alphabet of \(m\) characters, how many words have: Length not more than \(2 ?\)

The \(n\) th Catalan number satisfies the recurrence relation \(C_{n}=\sum_{i=0}^{n-1} C_{i} C_{n-1-i}\) \(n \geq 2 .\) (Note: This relation can be used to compute \(C_{n}\) using \(n\) multiplications, \(n-1\) additions, and no divisions.) Use it to compute each Catalan number. $$C_{5}$$

In an alphabet of \(m\) characters, how many words have: Length at least \(2,\) but not more than \(4 ?\)

In an alphabet of \(m\) characters, how many words have: Length not more than \(n ?\)

Let \(A\) and \(B\) be two finite sets with \(|A|=m\) and \(|B|=n .\) How many: Functions can be defined from \(A\) to \(B ?\)

Stirling numbers of the second kind \(S(n, r)\) are also given by the formula $$S(n, r)=\frac{1}{r !} \sum_{k=0}^{r-1}(-1)^{k}\left(\begin{array}{l}r \\\k\end{array}\right)(r-k)^{n}$$ Compute each Stirling number. $$S(3,2)$$

Let \(A\) and \(B\) be two finite sets with \(|A|=m\) and \(|B|=n .\) How many: Bijections can be defined from \(A\) to \(B\) (assume \(m=n\) )?

Stirling numbers of the second kind \(S(n, r)\) are also given by the formula $$S(n, r)=\frac{1}{r !} \sum_{k=0}^{r-1}(-1)^{k}\left(\begin{array}{l}r \\\k\end{array}\right)(r-k)^{n}$$ Compute each Stirling number. $$S(4,2)$$

Let \(A\) and \(B\) be two finite sets with \(|A|=m\) and \(|B|=n .\) How many: Invertible functions can be defined from \(A \text { to } B \text { (assume } m=n) ?\)

The number of surjections that can be defined from a finite set \(A\) to a finite set \(B\) is given by \(r ! S(n, r),\) where \(|A|=n\) and \(|B|=r .\) Compute the number of possible surjections from \(A\) to \(B\) if: $$|A|=3,|B|=2$$

Let \(A\) and \(B\) be two finite sets with \(|A|=m\) and \(|B|=n .\) How many: Injections can be defined from \(A \text { to } B \text { (assume } m \leq n) ?\)

The number of surjections that can be defined from a finite set \(A\) to a finite set \(B\) is given by \(r ! S(n, r),\) where \(|A|=n\) and \(|B|=r .\) Compute the number of possible surjections from \(A\) to \(B\) if: $$|A|=4,|B|=2$$

Let \(t\) denote the tau function. Prove each. \(t(n)\) is odd if and only if \(n\) is a square.