TAOCP 1.2.6: Binomial Coefficients
Section 1.2.6 exercises: 68/68 solved.
Section 1.2.6. Binomial Coefficients
Exercises from TAOCP Volume 1 Section 1.2.6: 68/68 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [00] | immediate | verified | 38s |
| 2 | [00] | immediate | verified | 1m58s |
| 3 | [00] | immediate | solved | 1m25s |
| 4 | [10] | simple | solved | 29s |
| 5 | [05] | simple | verified | 41s |
| 6 | [10] | simple | verified | 41s |
| 7 | [12] | simple | verified | 37s |
| 8 | [00] | immediate | verified | 35s |
| 9 | [01] | simple | verified | 39s |
| 10 | [M25] | math-medium | verified | 47s |
| 11 | [M20] | math-medium | verified | 2m16s |
| 12 | [M22] | math-medium | verified | 44s |
| 13 | [M13] | math-simple | verified | 38s |
| 14 | [M21] | math-medium | verified | 29s |
| 15 | [M15] | math-simple | verified | 42s |
| 16 | [M15] | math-simple | verified | 34s |
| 17 | [M18] | math-medium | verified | 1m08s |
| 18 | [M15] | math-simple | verified | 34s |
| 19 | [M18] | math-medium | verified | 38s |
| 20 | [M20] | math-medium | solved | 3m17s |
| 21 | [M05] | math-simple | verified | 34s |
| 22 | [M20] | math-medium | verified | 4m15s |
| 23 | [M13] | math-simple | verified | 33s |
| 24 | [M15] | math-simple | solved | 1m30s |
| 25 | [HM30] | hm-hard | solved | - |
| 26 | [HM25] | hm-medium | solved | - |
| 27 | [HM21] | hm-medium | solved | - |
| 28 | [M25] | math-medium | solved | - |
| 29 | [M20] | math-medium | solved | - |
| 30 | [M24] | math-medium | solved | - |
| 31 | [M20] | math-medium | solved | - |
| 32 | [M20] | math-medium | solved | - |
| 33 | [M20] | math-medium | solved | - |
| 34 | [M23] | math-medium | solved | - |
| 35 | [M23] | math-medium | solved | - |
| 36 | [M10] | math-simple | solved | - |
| 37 | [M10] | math-simple | solved | - |
| 38 | [HM30] | hm-hard | solved | - |
| 39 | [M10] | math-simple | solved | - |
| 40 | [HM17] | hm-medium | solved | - |
| 41 | [HM22] | hm-medium | solved | - |
| 42 | [HM10] | hm-simple | solved | - |
| 43 | [HM20] | hm-medium | solved | - |
| 44 | [HM20] | hm-medium | solved | - |
| 45 | [HM21] | hm-medium | solved | - |
| 46 | [M21] | math-medium | solved | - |
| 47 | [M21] | math-medium | solved | - |
| 48 | [M25] | math-medium | solved | - |
| 49 | [M20] | math-medium | solved | - |
| 50 | [M20] | math-medium | solved | - |
| 51 | [M21] | math-medium | solved | - |
| 52 | [HM11] | hm-simple | solved | - |
| 53 | [M25] | math-medium | verified | 2m03s |
| 54 | [M21] | math-medium | solved | - |
| 55 | [M21] | math-medium | verified | 1m33s |
| 56 | [20] | medium | solved | - |
| 57 | [M22] | math-medium | solved | - |
| 58 | [M23] | math-medium | solved | - |
| 59 | [M25] | math-medium | solved | - |
| 60 | [M23] | math-medium | solved | - |
| 61 | [M25] | math-medium | solved | - |
| 62 | [M23] | math-medium | solved | - |
| 63 | [M30] | math-hard | solved | - |
| 64 | [M20] | math-medium | solved | - |
| 65 | [HM35] | hm-hard | solved | - |
| 66 | [HM30] | hm-hard | solved | - |
| 67 | [M20] | math-medium | solved | - |
| 68 | [M25] | math-medium | solved | - |
TAOCP 1.2.6 Exercise 1
By the symmetry condition (6), \binom{n}{n-1}=\binom{n}{1}.
TAOCP 1.2.6 Exercise 2
In the context of _The Art of Computer Programming_, the intended value is 0^0 = 1.
TAOCP 1.2.6 Exercise 3
A bridge hand consists of 13 cards chosen from a standard deck of 52 cards.
TAOCP 1.2.6 Exercise 4
By Exercise 3, the number of bridge hands is \binom{52}{13} = \frac{52!
TAOCP 1.2.6 Exercise 5
The rows of Pascal's triangle give the coefficients of the expansion of $(x+y)^n$ according to the binomial theorem, Eq.
TAOCP 1.2.6 Exercise 6
Using Eq.
TAOCP 1.2.6 Exercise 7
By Eq.
TAOCP 1.2.6 Exercise 8
The symmetry condition, Eq.
TAOCP 1.2.6 Exercise 9
For every integer $n \ge 0$, Eq.
TAOCP 1.2.6 Exercise 10
Let n=ap+b,\qquad 0\le b<p, where $a=\lfloor n/p\rfloor$ and $b=n\bmod p$.
TAOCP 1.2.6 Exercise 11
Let v_p(m) denote the exponent of the highest power of $p$ dividing $m$, and let
TAOCP 1.2.6 Exercise 12
Let P(n):\qquad \binom{n}{k}\equiv 1 \pmod 2 \quad\text{for every }k\text{ with }0\le k\le n\text{ and }\binom{n}{k}\ne0.
TAOCP 1.2.6 Exercise 13
Equation (10) states that \sum_{k=0}^{n}\binom{r+k}{k} = \binom{r+n+1}{n}, \qquad \text{integer } n\ge 0.
TAOCP 1.2.6 Exercise 14
We seek a closed form for the sum \sum_{k=0}^{n} k^4.
TAOCP 1.2.6 Exercise 15
We prove Eq.
TAOCP 1.2.6 Exercise 16
We begin with the left-hand side of the identity and apply the definition (3) of binomial coefficients for general integers $r$: \binom{-n}{k-1} = \frac{(-n)(-n-1)\cdots(-n-(k-2))}{(k-1)!
TAOCP 1.2.6 Exercise 17
Equation (15) is the generalized binomial theorem, (1+x)^r=\sum_{j\ge0}\binom{r}{j}x^j.
TAOCP 1.2.6 Exercise 18
Equation (22) states that for integers $n \ge 0$ and $m \ge 0$: \sum_{k=0}^{n} \binom{k}{m} = \binom{n+1}{m+1}.
TAOCP 1.2.6 Exercise 19
Equation (23) is \sum_k (-1)^{r-k}\binom{r}{k}\binom{s+k}{n} = \binom{s}{n-r}, \qquad \text{integer } r \ge 0.
TAOCP 1.2.6 Exercise 20
We use the identities \sum_k \binom{r}{k}\binom{s}{n-k}=\binom{r+s}{n} \tag{21} and
TAOCP 1.2.6 Exercise 21
In Eq.
TAOCP 1.2.6 Exercise 22
Let S=\sum_{i=0}^{s}\binom{r+i}{r}\binom{t+s-i}{t}, \qquad s=(n-1)r+nt.
TAOCP 1.2.6 Exercise 23
Equation (26) is the identity \sum_k \binom{r}{m+k}\binom{s}{n-k}\binom{k}{t} = \binom{r+s-t}{m+n-t}\binom{r}{m+t},
TAOCP 1.2.6 Exercise 24
Exercise 22 proves Eq.
TAOCP 1.2.6 Exercise 25
Let $A_n(x,t)$ be the polynomial defined in Example 4 of Section 1.
TAOCP 1.2.6 Exercise 26
Exercise 25 established that, under the assumptions of Example 4, \sum_k A_k(r,t) z^k = x^r, \qquad z=x^{t+1}-x^t, provided that $x$ is sufficiently close to $1$.
TAOCP 1.2.6 Exercise 27
We begin with the setup from Exercise 25.
TAOCP 1.2.6 Exercise 28
Let S_n=\sum_k \binom{r+tk}{k}\binom{s-tk}{n-k}, where $n$ is a nonnegative integer.
TAOCP 1.2.6 Exercise 29
Equation (34) states that for integers $r \ge 0$ and $m$, \sum_k \binom{r}{k}(-1)^{r-k}k^m = \begin{cases} 0, & 0 \le m < r,\\
TAOCP 1.2.6 Exercise 30
Example 3 in Section 1.
TAOCP 1.2.6 Exercise 31
Let S=\sum_k \binom{m-r+s}{k}\binom{n+r-s}{n-k}\binom{r+k}{m+n}.
TAOCP 1.2.6 Exercise 32
By Eq.
TAOCP 1.2.6 Exercise 33
We prove the identities by induction on $n$, using the definitions of falling and rising factorial powers and the standard binomial formula for ordinary powers.
TAOCP 1.2.6 Exercise 34
We prove the stated identity by induction on $n$.
TAOCP 1.2.6 Exercise 35
We are asked to prove the addition formulas (46) for Stirling numbers directly from their definitions, Eqs.
TAOCP 1.2.6 Exercise 36
By the binomial theorem (13), with $x=y=1$, (1+1)^n = \sum_k \binom{n}{k}1^k1^{n-k} = \sum_k \binom{n}{k}.
TAOCP 1.2.6 Exercise 37
By Exercise 36 and the binomial theorem (13), \sum_k \binom{n}{k} = (1+1)^n = 2^n, and
TAOCP 1.2.6 Exercise 38
Let $n$ and $m$ be integers with $m \ge 1$, and let $k$ be an integer.
TAOCP 1.2.6 Exercise 39
Let $\left[{n \atop k}\right]$ denote the numbers in Stirling's first triangle.
TAOCP 1.2.6 Exercise 40
1.
TAOCP 1.2.6 Exercise 41
Define I(x,y)=\frac{\Gamma(x)\Gamma(y)}{\Gamma(x+y)}.
TAOCP 1.2.6 Exercise 42
By Exercise 40(3), B(k+1,r-k+1) =\frac{(r+1)!
TAOCP 1.2.6 Exercise 43
We are asked to evaluate the beta function B\!
TAOCP 1.2.6 Exercise 44
Exercise 42 suggests extending the binomial coefficient to arbitrary arguments by means of the beta function.
TAOCP 1.2.6 Exercise 45
By equation (3), \binom{r}{k} = \frac{r(r-1)\cdots(r-k+1)}{k!
TAOCP 1.2.6 Exercise 46
By Eq.
TAOCP 1.2.6 Exercise 47
Let $k$ be an integer.
TAOCP 1.2.6 Exercise 48
We are asked to evaluate \sum_{k \ge 0} \binom{n}{k} \frac{(-1)^k}{k+x}.
TAOCP 1.2.6 Exercise 49
By the binomial theorem (13), (1+x)^r=\sum_{k\ge0}\binom{r}{k}x^k, since the terms with $k<0$ vanish by definition (3).
TAOCP 1.2.6 Exercise 50
Let A_n(x,y)=\sum_{k=0}^n \binom{n}{k}(x+k)^{k-1}(y+n-k)^{n-k}.
TAOCP 1.2.6 Exercise 51
We are asked to prove Abel's formula, Eq.
TAOCP 1.2.6 Exercise 52
Abel's binomial formula (16) states that (x+y)^n = \sum_k \binom{n}{k}x(x-kz)^{k-1}(y+kz)^{n-k}.
TAOCP 1.2.6 Exercise 53
Define S_m=\sum_{k=0}^{m}\binom{r}{k}\binom{s}{n-k}\bigl(nr-(r+s)k\bigr).
TAOCP 1.2.6 Exercise 54
Let $P$ denote the infinite lower-triangular matrix whose $(i,j)$ entry is P_{i,j} = \binom{i}{j}, \qquad i,j \ge 0, with the convention that $\binom{i}{j} = 0$ when $j > i$.
TAOCP 1.2.6 Exercise 55
Let P=\bigl(\binom{n}{k}\bigr)_{n,k\ge 0} be Pascal's triangle regarded as an infinite lower-triangular matrix.
TAOCP 1.2.6 Exercise 56
For each $n$, choose $a$ as large as possible subject to $\binom{a}{3}\le n$.
TAOCP 1.2.6 Exercise 57
Let F(x)=\sum_{m\ge0}a_mx^m be Stirling's attempted generalization of the factorial function.
TAOCP 1.2.6 Exercise 58
We proceed by induction on $n$.
TAOCP 1.2.6 Exercise 59
Define B_{nk}=A_{nk}-\binom{n+1}{k}.
TAOCP 1.2.6 Exercise 60
Let the $n$ objects be labeled $1,2,\ldots,n$.
TAOCP 1.2.6 Exercise 61
Let S=\sum_k \left[{n+1 \atop k+1}\right]\left\{{k \atop m}\right\}(-1)^{k-m}.
TAOCP 1.2.6 Exercise 62
Let S=\sum_k (-1)^k \binom{l+m}{l+k}\binom{m+n}{m+k}\binom{n+l}{n+k}, \qquad l,m,n\ge0 .
TAOCP 1.2.6 Exercise 63
We must prove that, for integers $l,m,n$ with $n \ge 0$, \sum_{j,k} (-1)^{j+k}\binom{j+k}{k+l}\binom{r}{j}\binom{n}{k}\binom{s+n-j-k}{m-j} = (-1)^l \binom{n+r}{n+l}\binom{s-r}{m-n-l}.
TAOCP 1.2.6 Exercise 64
Let $S(n,m)$ denote the number of partitions of an $n$-element set into $m$ nonempty disjoint subsets.
TAOCP 1.2.6 Exercise 65
I need the statements of Eqs.
TAOCP 1.2.6 Exercise 66
Let $x, y, z$ be real numbers, and $n \ge 2$ an integer, satisfying \binom{x}{n} = \binom{y}{n} + \binom{z}{n-1}, \qquad x \ge n-1,\ y \ge n-1,\ z > n-2.