TAOCP 1.2.9: Generating Functions
Section 1.2.9 exercises: 26/26 solved.
Section 1.2.9. Generating Functions
Exercises from TAOCP Volume 1 Section 1.2.9: 26/26 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [M12] | math-simple | solved | - |
| 2 | [M13] | math-simple | solved | - |
| 3 | [HM21] | hm-medium | verified | 5m40s |
| 4 | [M01] | math-simple | solved | - |
| 5 | [M20] | math-medium | solved | - |
| 6 | [HM15] | hm-simple | solved | - |
| 7 | [M15] | math-simple | verified | 4m53s |
| 8 | [M23] | math-medium | verified | 4m23s |
| 9 | [M11] | math-simple | verified | 2m41s |
| 10 | [M25] | math-medium | verified | 2m04s |
| 11 | [M25] | math-medium | verified | 7m |
| 12 | [M20] | math-medium | verified | 6m41s |
| 13 | [HM22] | hm-medium | verified | 1m52s |
| 14 | [HM21] | hm-medium | verified | 52s |
| 15 | [M28] | math-hard | verified | 1m26s |
| 16 | [M22] | math-medium | verified | 40s |
| 17 | [M25] | math-medium | verified | 50s |
| 18 | [M25] | math-medium | verified | 2m13s |
| 19 | [HM32] | hm-hard | verified | 1m24s |
| 20 | [M21] | math-medium | verified | 1m |
| 21 | [HM30] | hm-hard | verified | 1m06s |
| 22 | [M21] | math-medium | verified | 1m05s |
| 23 | [M33] | math-hard | solved | 7m12s |
| 24 | [M22] | math-medium | verified | 54s |
| 25 | [M23] | math-medium | solved | 4m29s |
| 26 | [M40] | math-project | verified | 42s |
TAOCP 1.2.9 Exercise 1
Let $G(z)$ be the generating function for the sequence \langle 2^n+3^n\rangle = 2,5,13,35,\ldots.
TAOCP 1.2.9 Exercise 2
We are asked to prove equation (11): \left(\frac{a_0}{0!
TAOCP 1.2.9 Exercise 3
Equation (18) gives the generating function for the harmonic numbers: G(z)=\sum_{n\ge0}H_nz^n =\frac{1}{1-z}\ln\frac1{1-z}.
TAOCP 1.2.9 Exercise 4
Equation (21) states that if $x^{t+1}=x^t+z$ and $x=1$ when $z=0$, then x^r=\sum_{k\ge0}\binom{r-kt}{k}\frac{r}{r-kt}z^k.
TAOCP 1.2.9 Exercise 5
For fixed $n$, define F_n(z) = (e^z-1)^n.
TAOCP 1.2.9 Exercise 6
Let us denote the sequence in question by a_n = \sum_{0<k<n} \frac{1}{k(n-k)}, \qquad n \ge 2, and $a_0=a_1=0$.
TAOCP 1.2.9 Exercise 7
The verification of the steps leading to Eq.
TAOCP 1.2.9 Exercise 8
Let $p(n)$ denote the number of partitions of $n$, with $p(0)=1$.
TAOCP 1.2.9 Exercise 9
We are asked to express $h_4$ in terms of the elementary symmetric functions $S_1, S_2, S_3, S_4$, using the notation of Eqs.
TAOCP 1.2.9 Exercise 10
Let E(z)=\sum_{m\ge0} e_m z^m be the generating function for the elementary symmetric functions.
TAOCP 1.2.9 Exercise 11
Let H(z)=\sum_{m\ge0}h_m z^m \] be the generating function for the complete homogeneous symmetric functions.
TAOCP 1.2.9 Exercise 12
A doubly subscripted sequence $\langle a_{mn} \rangle$ with $m,n \ge 0$ is represented by introducing two independent parameters $z$ and $w$ and forming the double power series G(z,w) = \sum_{m \ge 0}...
TAOCP 1.2.9 Exercise 13
Let $\langle a_k \rangle = a_0,a_1,a_2,\ldots$ be a sequence with generating function G(z) = \sum_{k \ge 0} a_k z^k.
TAOCP 1.2.9 Exercise 14
Let G(z)=\sum_{n\ge 0} a_n z^n.
TAOCP 1.2.9 Exercise 15
Define G_n(z)=\sum_{k=0}^{n}\binom{n-k}{k}z^k.
TAOCP 1.2.9 Exercise 16
For each of the $n$ objects, introduce a sequence $b^{(i)}_0,b^{(i)}_1,\ldots,b^{(i)}_r$ defined by b^{(i)}_j = 1 \quad (0 \le j \le r), \qquad b^{(i)}_j = 0 \quad (j > r).
TAOCP 1.2.9 Exercise 17
We seek the coefficients of \frac{1}{(1-z)^w} when expanded as a double power series in $z$ and $w$.
TAOCP 1.2.9 Exercise 18
Part (a) The original derivation is correct.
TAOCP 1.2.9 Exercise 19
For integers $0<p<q$, define H_{p/q}=\sum_{n\ge1}\left(\frac1n-\frac1{n+p/q}\right).
TAOCP 1.2.9 Exercise 20
We are asked to express the generating function \sum_{n \ge 0} n^m z^n in the form
TAOCP 1.2.9 Exercise 21
Let $\langle a_n \rangle = \langle n! \rangle$.
TAOCP 1.2.9 Exercise 22
We are asked to find a generating function $G(z)$ such that the coefficient of $z^n$ is [z^n]G(z) = \sum_{k_0+2k_1+4k_2+8k_3+\cdots=n} \binom{r}{k_0}\binom{r}{k_1}\binom{r}{k_2}\binom{r}{k_3}\cdots.
TAOCP 1.2.9 Exercise 23
Let F_m(n,r):= \sum_{k_1,\ldots,k_m\ge 0} \binom{r}{n-k_1} \binom{k_1}{n-k_2}\cdots
TAOCP 1.2.9 Exercise 24
We start from the right-hand side and extract the coefficient of $z^n$.