c7.ans

Concrete_Mathematics_2nd_Ed_TeX_Source_Code

\ansno7.1:
\unitlength=3pt
\def\Domh{\beginpicture(3,1)(-.5,0) % horizontal, stand-alone
\put(2,0){\line(0,1){1}}
\put(0,0){\line(0,1){1}}
\put(0,0){\line(1,0){2}}
\put(0,1){\line(1,0){2}}
\endpicture}%
\def\Domv{\beginpicture(2,2)(-.5,0) % vertical, stand-alone
\put(0,0){\line(0,1){2}}
\put(1,0){\line(0,1){2}}
\put(0,0){\line(1,0){1}}
\put(0,2){\line(1,0){1}}
\endpicture}%
Substitute $z^4$ for \Domv\ and $z$ for \Domh\ in the generating
function, getting $1/(1-z^4-z^2)$. This is like the generating function
for~$T$, but with $z$ replaced by~$z^2$. Therefore the answer is
zero if $m$ is odd, otherwise $F_{m/2+1}$.

\ansno7.2:
 $G(z)=1/(1-2z)+1/(1-3z)$; \ $\widehat G(z)=e^{2z}+e^{3z}$.
\source{[|knuth1|, exercise 1.2.9--1].}

\ansno7.3:
 Set $z=1/10$ in the generating function, getting
${10\over9}\ln{10\over9}$.

\ansno7.4:
 Divide $P(z)$ by $Q(z)$, getting a quotient $T(z)$ and a
remainder $P_0(z)$ whose degree is less than the degree of~$Q$. The
coefficients of $T(z)$ must be added to the coefficients $[z^n]\,P_0(z)/Q(z)$
for small~$n$. (This is the polynomial $T(z)$ in \equ(7.|r-s-t|).)

\ansno7.5:
 This is the convolution of $(1+z^2)^r$ with $(1+z)^r$, so
\begindisplay
S(z)=(1+z+z^2+z^3)^r\,.
\enddisplay
Incidentally, no simple form is known
for the coefficients of this generating function; hence the stated
sum probably has no simple closed form. (We can use generating
functions to obtain negative results as well as positive ones.)

\ansno7.6:
 Let the solution to $g_0=\alpha$, $g_1=\beta$, $g_n=g_{n-1}+
2g_{n-2}+(-1)^n\gamma$ be $g_n=A(n)\alpha+B(n)\beta+C(n)\gamma$.
The function $2^n$ works when $\alpha=1$, $\beta=2$, $\gamma=0$;
the function $(-1)^n$ works when $\alpha=1$, $\beta=-1$, $\gamma=0$;
the function $(-1)^nn$ works when $\alpha=0$, $\beta=-1$, $\gamma=3$.
Hence $A(n)+2B(n)=2^n$, $A(n)-B(n)=(-1)^n$, and $-B(n)+3C(n)=(-1)^nn$.

\ansno7.7:
 $G(z)=\bigl(z/(1-z)^2\bigr)G(z)+1$, hence
\begindisplay
G(z)={1-2z+z^2\over1-3z+z^2}=1+{z\over1-3z+z^2}\,;
\enddisplay
we have $g_n=F_{2n}+\[n=0]$.
\g\vskip-30pt I bet that the controversial ``fan of order zero''
"!null case" "!empty case"
does have one spanning tree.\g

\ansno7.8:
 Differentiate $(1-z)^{-x-1}$ twice with respect to~$x$, obtaining
\begindisplay
{x+n\choose n}\bigl((H_{x+n}-H_x)^2-(H_{x+n}^{(2)}-H_x^{(2)})\bigr)\,.
\enddisplay
Now set $x=m$.
\source{"Zave" [|zave|].}

\ansno7.9:
 $(n+1)(H_n^2-H_n^{(2)})-2n(H_n-1)$.
\source{[|knuth1|, exercise 1.2.7--22].}

\ansno7.10:
 The identity $H_{k-1/2}-H_{-1/2}={2\over2k-1}+\cdots+{2\over1}=2H_{2k}-H_k$
implies that $\sum_k{2k\choose k}{2n-2k\choose n-k}(2H_{2k}-H_k)=4^nH_n$.

\ansno7.11:
 (a) $C(z)=A(z)B(z^2)/(1-z)$. (b) $zB'(z)=A(2z)e^z$, hence
$A(z)={z\over2}e^{-z/2}B'({z\over2})$.
(c)~$A(z)=B(z)/(1-z)^{r+1}$, hence $B(z)=(1-z)^{r+1}A(z)$ and we have
$f_k(r)={r+1\choose k}(-1)^k$.
\source{1971 final exam.}

\ansno7.12:
 $C_n$. The numbers in the upper row correspond to the positions
of $+1$'s in a sequence of $+1$'s and~$-1$'s that defines a
``mountain range''; the numbers in the lower row correspond to the
positions of $-1$'s. For example, the given array corresponds to
\begindisplay
\unitlength=10pt
\countdef\m=4 \countdef\n=6
\def\init{\thinlines\put(0,0){\line(1,0){10}}
 \thicklines \m=0 \n=0 \put(0,0){\disk{.2}}}
\def\+{\put(\number\m,\number\n){\line(1,1)1}\advance\m1 \advance\n1
 \put(\number\m,\number\n){\disk{.2}}}
\def\-{\put(\number\m,\number\n){\line(1,-1)1}\advance\m1 \advance\n-1
 \put(\number\m,\number\n){\disk{.2}}}
\beginpicture(10,3)(0,0)\init\+\+\-\+\+\-\-\+\-\-\endpicture\;.
\enddisplay
\source{[|knuth3|, pp.~63--64].}

\ansno7.13:
 Extend the sequence periodically (let $x_{m+k}=x_k$) and define
$s_n=x_1+\cdots+x_n$. We have $s_m=l$, $s_{2m}=2l$, etc. There must be
a largest index $k_j$ such that $s_{k_j}=j$, $s_{k_j+m}=l+j$, etc.
These indices $k_1$, \dots,~$k_l$ (modulo~$m$) specify the cyclic
shifts in question.\par
For example, in the sequence
$\<-2,1,-1,0,1,1,-1,1,1,1\>$ with $m=10$ and $l=2$ we have $k_1=17$, $k_2=24$.
\source{"Raney" [|raney|].}

\ansno7.14:
 $\widehat G(z)=-2z\widehat G(z)+\widehat G(z)^2+z$ (be careful about the final
term!) leads via the quadratic formula to
\begindisplay
\widehat G(z)={1+2z-\sqrt{1+4z^{2\mathstrut}}\over2}\,.
\enddisplay
Hence $g_{2n+1}=0$ and $g_{2n}=(-1)^n(2n)!\,C_{n-1}$, for all $n>0$.

\ansno7.15:
 There are ${n\choose k}\varpi_{n-k}$ partitions with $k$ other objects
in the subset containing~$n+1$. Hence $\widehat P'(z)=e^z\widehat P(z)$. The solution
to this differential equation is $\widehat P(z)=e^{e^z+c}$, and $c=-1$ since
$\widehat P(0)=1$. (We can also get this result by summing
\equ(7.|exp-power-gf|) on~$m$, since $\varpi_n=\sum_m{n\brace m}$.)
\source{"Bell" [|bell-numbers|].}

\ansno7.16:
 One way is to take the logarithm of
\begindisplay
B(z)=1\big/\bigl((1-z)^{a_1}(1-z^2)^{a_2}(1-z^3)^{a_3}(1-z^4)^{a_4}\ldots\,\bigr),
\enddisplay
then use the formula for $\ln{1\over1-z}$ and interchange the order of
summation.
\source{"P\'olya" [|polya-counting|, p.~149]; [|knuth1|, exercise 2.3.4.4--1].}

\ansno7.17:
 This follows since $\int_0^\infty t^ne^{-t}\,dt=n!@$.
There's also a formula that goes in the other direction:
\begindisplay
\widehat G(z)={1\over2\pi}\int_{-\pi}^{+\pi}G(ze^{-i\theta})\,e^{e^{i\theta}}
d\theta\,.
\enddisplay

\ansno7.18:
 (a) $\zeta(z-\half)$; \ (b) $-\zeta'(z)$; \ (c) $\zeta(z)/\zeta(2z)$.
Every positive integer is uniquely representable as $m^2q$, where $q$
is squarefree.

\ansno7.19:
 If $n>0$, the coefficient $[z^n]\,\exp\bigl(x\ln F(z)\bigr)$ is
a polynomial of degree~$n$ in~$x$ that's a multiple of~$x$. The first
convolution formula comes from equating coefficients of~$z^n$ in
$F(z)^xF(z)^y=F(z)^{x+y}$. The second comes from equating coefficients of
$z^{n-1}$ in $F'(z)@F(z)^{x-1}F(z)^y=F'(z)@F(z)^{x+y-1}$, because we have
\begindisplay
F'(z)@F(z)^{x-1}=x^{-1}{\partial\over\partial z}\bigl(F(z)^x\bigr)
=x^{-1}\sum_{n\ge0}nf_n(x)z^{n-1}\,.
\enddisplay
(Further convolutions follow by taking $\partial/\partial x$, as
in \equ(7.|harmonic-general|).)\par
Still more is true, as shown in [|knuth-cp|]: We have
\begindisplay
\sum_{k=0}^n{x@f_k(x+tk)\over x+tk}{y@f_{n-k}(y+t(n-k))\over y+t(n-k)}=
{(x+y)f_n(x+y+tn)\over x+y+tn}\,,
\enddisplay
for arbitrary $x$, $y$, and $t$. In fact, $x@f_n(x+tn)/(x+tn)$ is the
sequence of polynomials for the coefficients of $\Fscr_t(z)^x$, where
\begindisplay
\Fscr_t(z)=F\bigl(z@\Fscr_t(z)^t\bigr)\,.
\enddisplay
(We saw special cases in \equ(5.|t-series-rec|) and \equ(6.|t-series-stirl|).)
\source{[|knuth-cp|].}

\ansno7.20:
 Let $G(z)=\sum_{n\ge0}g_nz^n$. Then
\begindisplay
z^lG^{(k)}(z)=\sum_{n\ge0}
n\_kg_nz^{n-k+l}=\sum_{n\ge0}(n+k-l)\_kg_{n+k-l}z^n
\enddisplay
for all $k,l\ge0$,
if we regard $g_n=0$ for $n<0$. Hence if $P_0(z)$, \dots,~$P_m(z)$
are polynomials, not all zero, having maximum degree~$d$, then there are
polynomials $p_0(n)$, \dots,~$p_{m+d}(n)$ such that
\begindisplay
P_0(z)@G(z)+\cdots+P_m(z)@G^{(m)}(z)=\sum_{n\ge0}\sum_{j=0}^{m+d}p_j(n)@g_{n+j-d}z^n\,.
\enddisplay
Therefore a differentiably finite $G(z)$ implies that
\begindisplay
\sum_{j=0}^{m+d}p_j(n+d)@g_{n+j}=0\,,\qquad\hbox{for all $n\ge0$}.
\enddisplay
The converse is similar.
(One consequence is that $G(z)$ is differentiably finite if and only
if the corresponding egf, $\widehat G(z)$, is differentiably finite.)
\source{"Jungen" [|jungen|, p.~299] credits A. "Hurwitz".}

\ansno7.21:
 This is the problem of giving change with denominations $10$
and $20$, so $G(z)=1/(1-z^{10})(1-z^{20})=\check G(z^{10})$, where
$\check G(z)=1/(1-z)(1-z^2)$. (a)~The partial fraction decomposition
\g This slow method of finding the answer is just the cashier's way
of stalling until the police come.\g
of $\check G(z)$ is $\half(1-z)^{-2}+{1\over4}(1-z)^{-1}+{1\over4}(1+z)
^{-1}$, so $[z^n]\,\check G(z)={1\over4}\bigl(2n+3+(-1)^n\bigr)$.
Setting $n=50$ yields $26$ ways to make the payment.
(b)~$\check G(z)=(1+z)/(1-z^2)^2=(1+z)(1+2z^2+3z^4+\cdots\,)$, so
$[z^n]\,\check G(z)=\lfloor n/2\rfloor+1$. (Compare this with the
value $N_n=\lfloor n/5\rfloor+1$ in the text's coin-changing problem.
The bank robber's problem is equivalent to the problem of making change
\g The USA has two\hbox{-}cent pieces,
 but they haven't been minted since 1873.\g
with pennies and tuppences.)

\ansno7.22:
 Each polygon has a ``base'' (the line segment at the bottom).
If $A$ and~$B$ are triangulated polygons, let $A\triangle B$ be the
result of pasting the base of~$A$ to the upper left diagonal of $\triangle$,
and pasting the base of~$B$ to the upper right diagonal. Thus, for
example,
\def\tri#1{\cpic(4,4)(0,0) \put(0,0){\line(1,0){4}}
 \put(0,0){\line(1,2){2}} \put(4,0){\line(-1,2){2}}#1\endcpic}%
\def\sqr#1{\cpic(3,3)(0,0) \put(0,0){\line(0,1){3}}
 \put(0,0){\line(1,0){3}} \put(0,3){\line(1,0){3}}\put(3,0){\line(0,1){3}}
 #1\endcpic}%
\def\pnt#1{\cpic(6,5)(-1,0) \put(0,0){\line(1,0){4}}
 \put(0,0){\line(-1,3){1}} \put(-1,3){\line(3,2){3}} \put(2,5){\line(3,-2){3}}
 \put(4,0){\line(1,3){1}} #1\endcpic}%
\def\dgn{\cpic(3,2)(0,0)\put(0,0){\line(1,0){3}}\endcpic}%
\begindisplay
\unitlength=3.33333pt
\sqr{\put(0,0){\line(1,1){3}}}\;\triangle\;\dgn=
\pnt{\put(0,0){\line(2,5){2}}\put(0,0){\line(5,3){5}}}\,\,.
\enddisplay
(The polygons might need to be warped a bit and/or banged into shape.)
Every triangulation arises in this way, because the base line is part of
a unique triangle and there are triangulated polygons $A$ and~$B$ at its
left and right.\par
 Replacing each triangle by~$z$ gives a power series in which
the coefficient of~$z^n$ is the number of triangulations with $n$~triangles,
namely the number of ways to decompose an $(n+2)$-gon into triangles.
Since $P=1+zP^2$, this is the generating function for Catalan numbers
$C_0+C_1z+C_2z^2+\cdots\,$; the number of ways to triangulate an $n$-gon
is $C_{n-2}={2n-4\choose n-2}/(n-1)$.
\source{"P\'olya" [|polya-pictures|].}

\ansno7.23:
 Let $a_n$ be the stated number, and $b_n$ the number of ways
with a $2\times1\times1$ notch missing at the top. By considering
the possible patterns visible on the top surface, we have
\begindisplay
a_n&=2a_{n-1}+4b_{n-1}+a_{n-2}+\[n=0]\,;\cr
b_n&=a_{n-1}+b_{n-1}\,.
\enddisplay
Hence the generating functions satisfy $A=2zA+4zB+z^2A+1$,
$B=zA+zB$, and we have
\begindisplay
A(z)={1-z\over(1+z)(1-4z+z^2)}\,.
\enddisplay
This formula relates to the problem of $3\times n$ domino tilings; we have
$a_n={1\over3}\bigl(U_{2n}+V_{2n+1}+(-1)^n\bigr)=
{1\over6}(2+\sqrt3\,)^{n+1}+{1\over6}(2-\sqrt3\,)^{n+1}+{1\over3}(-1)^n$,
which is $(2+\sqrt3\,)^{n+1}\!/6$ rounded to the nearest integer.
\source{1983 homework.}

\ansno7.24:
 $n\sum_{k_1+\cdots+k_m=n}k_1\cdot\ldots\cdot k_m/m=F_{2n+1}+
F_{2n-1}-2$. (Consider the coefficient
$[z^{n-1}]\,{d\over dz}\ln\bigl(1/(1-G(z))\bigr)$,
where $G(z)=z/(1-z)^2$.)
\source{"Myers" [|myers|]; "Sedl\'a\v cek" [|sedlacek|].}

\ansno7.25:
 The generating function is $P(z)/(1-z^m)$, where
$P(z)=z+2z^2+\cdots+(m-1)z^{m-1}=\bigl((m-1)z^{m+1}-mz^m+z)/(1-z)^2$.
The denominator is $Q(z)=1-z^m=(1-\omega^0z)(1-\omega^1z)\ldots(1-\omega^{m-1}z)$.
By the rational expansion theorem for distinct roots, we obtain
\begindisplay
n\bmod m={m-1\over2}+\sum_{k=1}^{m-1}{\omega^{-kn}\over\omega^k-1}\,.
\enddisplay
\source{[|knuth2|, "Carlitz"'s proof of lemma 3.3.3B].}

\ansno7.26:
 $(1-z-z^2){\frak F}(z)=F(z)$ leads to ${\frak F}_n=\bigl(
2(n+1)F_n+nF_{n+1}\bigr)/5$ as in equation~\equ(7.|fib-conv|).
\source{[|knuth1|, exercise 1.2.8--12].}

\ansno7.27:
 Each oriented cycle pattern begins with
{\unitlength=8pt
\beginpicture(.5,1)(-.25,.1)
\multiput(0,0)(0,1){2}{\disk{.25}}
\put(-.1,0){\line(0,1)1} \put(-.1,0){\vector(0,1){1.0}}
\put(.1,0){\line(0,1)1} \put(.1,1){\vector(0,-1){1.0}}
\endpicture}
or
{\unitlength=8pt
\beginpicture(1.2,1)(-.1,.1)
\multiput(0,0)(1,0){2}{\disk{.25}}
\multiput(0,1)(1,0){2}{\disk{.25}}
\put(0,-.1){\line(1,0)1}
\put(0,.9){\line(1,0)1}
\put(0,.1){\line(1,0)1}
\put(0,1.1){\line(1,0)1}
\endpicture}
or a $2\times k$ cycle (for some $k\ge2$) oriented in one of two ways. Hence
\begindisplay
Q_n=Q_{n-1}+Q_{n-2}+2Q_{n-2}+2Q_{n-3}+\cdots+2Q_0
\enddisplay
for $n\ge2$; \ $Q_0=Q_1=1$. The generating function is therefore
\begindisplay \openup3pt
Q(z)&=zQ(z)+z^2Q(z)+2z^2Q(z)/(1-z)+1\cr
&=1/\bigl(1-z-z^2-2z^2\!/(1-z)\bigr)\cr
&={(1-z)\over(1-2z-2z^2+z^3)}\cr
&={\phi^2\!/5\over 1-\phi^2z}+{\phi^{-2}\!/5\over1-\phi^{-2}z}+{2/5\over 1+z}\,,\cr
\enddisplay
and $Q_n=\bigl(\phi^{2n+2}+\phi^{-2n-2}+2(-1)^n\bigr)/5
=\bigl((\phi^{n+1}-\hat\phi^{n+1})/\!\sqrt5\,\bigr)^2=F_{n+1}^2$.

\ansno7.28:
 In general if $A(z)=(1+z+\cdots+z^{m-1})B(z)$, we have
$A_r+A_{r+m}+A_{r+2m}+\cdots=B(1)$ for $0\le r<m$. In this case $m=10$
and $B(z)=(1+z+\cdots+z^9)(1+z^2+z^4+z^6+z^8)(1+z^5)$.

\ansno7.29:
 $F(z)+F(z)^2+F(z)^3+\cdots=z/(1-z-z^2-z)=\bigl(1/(1-(1+\sqrt2\,)z)
-(1/(1-(1-\sqrt2\,)z)\bigr)/\sqrt8$, so the answer is
$\bigl((1+\sqrt2\,)^n-(1-\sqrt2\,)^n\bigr)/\sqrt8$.

\ansno7.30:
 $\sum_{k=1}^n{2n-1-k\choose n-1}\bigl(a^nb^{n-k}\!/(1-\alpha z)^k
+a^{n-k}b^n\!/(1-\beta z)^k\bigr)$, by exercise 5.|ax+by-expansion|.

\ansno7.31:
 The dgf is $\zeta(z)^2\!/\zeta(z-1)$; hence we find $g(n)$ is
the product of $(k+1-kp)$ over all prime powers $p^k$ that exactly
divide~$n$.

\ansno7.32:
 We may assume that each $b_k\ge0$. A set of arithmetic progressions
forms an exact cover if and only if
\begindisplay
{1 \over 1-z}={z^{b_1}\over 1-z^{a_1}}+\cdots+{z^{b_m}\over 1-z^{a_m}}\,.
\enddisplay
Subtract $z^{b_m}/(1-z^{a_m})$ from both sides and set $z=e^{2\pi i/a_m}$.
The left side is infinite, and the right side will be finite unless
$a_{m-1}=a_m$.
\source{[|erdos-graham|, pp. 25--26] credits L. "Mirsky" and M. "Newman".}

\ansno7.33:
 $(-1)^{n-m+1}\[n>m]/(n-m)$.
\source{1971 final exam.}

\ansno7.34:
 We can also write $G_n(z)=\sum_{k_1+(m+1)k_{m+1}=n}{k_1+k_{m+1}
"!multinomial coefficient"
\choose k_{m+1}}(z^m)^{k_{m+1}}$. In general, if
\begindisplay
G_n=\sum_{k_1+2k_2+\cdots+rk_r=n}{k_1+k_2+\cdots+k_r\choose k_1,k_2,
\ldots,k_r}z_1^{k_1}z_2^{k_2}\ldots z_r^{k_r}\,,
\enddisplay
we have $G_n=z_1G_{n-1}+z_2G_{n-2}+\cdots+z_rG_{n-r}+\[n=0]$, and the
generating function is $1/(1-z_1w-z_2w^2-\cdots-z_rw^r)$. In the stated
special case
the answer is $1/(1-w-z^mw^{m+1})$. (See \equ(5.|bc-gen-fib|) for
the case $m=1$.)
\source{Tom\'as "Feder".*}