chap5.tex

Concrete_Mathematics_2nd_Ed_TeX_Source_Code

\begindisplay
 {a+b+c \choose a,\, b,\, c}={(a+b+c)!\over a!\,b!\,c!}
\enddisplay
in order to emphasize the symmetry present.

Binomial and trinomial coefficients generalize to {\it multinomial
coeffi\-cients}, which are always "!multinomial coefficients"
expressible as products of binomial coefficients:
\begindisplay \openup2pt
 {a_1+a_2+\cdots+a_m\choose a_1,a_2,\ldots,a_m}
 &={(a_1+a_2+\cdots+a_m)!\over a_1!\,a_2!\,\ldots\,a_m!}\cr
 &={a_1+a_2+\cdots+a_m\choose a_2+\cdots+a_m}\ldots{a_{m-1}+a_m\choose a_m}\,.\cr
\enddisplay
Therefore, when we run across such a beastie, our standard techniques apply.

Now we come to Table |bc-prod|, which lists identities that are
among the most important of our standard techniques.
These are the ones we rely on when struggling with a sum
involving a product of two binomial coefficients.
Each of these identities
is a sum over~$k$, with one appearance of~$k$ in each binomial
coefficient; there also are four nearly independent parameters, called
$m$, $n$, $r$, etc., one
in each index position. Different cases arise depending on whether $k$
appears in the upper or lower index,
and on whether it appears with a plus or minus sign.
Sometimes there's an additional factor of $(-1)^k$, which is needed to
make the terms summable in closed form.

\topinsert
\table Sums of products of binomial coefficients.\tabref|bc-prod|
%\begindisplay\abovedisplayskip=-2pt \belowdisplayskip=6pt \openup7pt%
\begindisplay\abovedisplayskip=0pt \belowdisplayskip=8pt \openup9pt%
 \advance\displayindent-\parindent\advance\displaywidth\parindent
&\sum_k{r\choose m+k}{s\choose n-k}={r+s\choose m+n}\,,
 \qquad}\hfill{\hbox{integers $m,n$.}
 \eqno\eqref|bc-prod1|\cr
&\sum_k{l\choose m+k}{s\choose n+k}={l+s\choose l-m+n}\,,
 \qquad}\hfill{\tworestrictions{integer $l\ge0$,}{integers $m,n$.}
 \eqno\eqref|bc-prod2|\cr
&\sum_k{l\choose m+k}{s+k\choose n}(-1)^k=(-1)^{l+m}{s-m\choose n-l}\,,
 \qquad}\hfill{\tworestrictions{integer $l\ge0$,}{integers $m,n$.}
 \eqno\eqref|bc-prod3|\cr
&\sum_{k\le l}{l-k\choose m}{s\choose k-n}(-1)^k=(-1)^{l+m}{s-m-1\choose l-m-n}\,,
 \quad}\hfill{\tworestrictions{integers}{$l,m,n\ge0$.}
 \eqno\eqref|bc-prod4|\cr
&\sum_{0\le k\le l}{l-k\choose m}{q+k\choose n}={l+q+1\choose m+n+1}\,,
 \quad}\hfill{\tworestrictions{integers $l,m\ge0$,}{integers $n\ge q\ge0$.}
 \eqno\eqref|bc-prod5|\cr
\enddisplay
\hrule width\hsize height.5pt
\kern4pt
\endinsert

Table |bc-prod| is far too complicated to memorize in full;
\g Fold down the corner on this page,
so you can find the table quickly later. You'll need it!\g
it is intended only for reference. 
But the first identity in this table is by far
the most memorable, and it should be remembered. It states that the
sum (over all integers~$k$) of the product
of two binomial coefficients, in which the upper indices are constant
and the lower indices have a constant sum for all~$k$,
is the binomial coefficient obtained by summing both lower and upper indices.
This identity is known as {\it "Vandermonde's convolution"}, because
Alexandre "Vandermonde" wrote a significant paper
about it in the late 1700s [|vandermonde|]; it was, however,
known to "Chu Shih-Chieh"
in China as early as 1303. All of the other identities in Table~|bc-prod|
can be obtained from Vandermonde's convolution by doing things
like negating upper indices or applying the symmetry law, etc., with
care; therefore Vandermonde's convolution is the most basic of all.

We can prove Vandermonde's convolution by giving it
a nice "combinatorial interpretation".
If we replace $k$ by~$k-m$ and $n$ by~$n-m$, we can assume that $m=0$; hence the
identity to be proved is
\begindisplay
\sum_k{r\choose k}{s\choose n-k}={r+s\choose n},\qquad\hbox{integer $n$}.
\eqno\eqref|vandermonde-conv|
\enddisplay
Let $r$ and $s$ be nonnegative integers; the general case then
follows by the polynomial argument.
On the right side, $r+s \choose n$ is the number of ways to
choose $n$~people from among $r$~men and $s$~women.
\g Sexist! You mentioned men first.\g
On the left, each term of the sum is the number of ways
to choose $k$~of the men and $n-k$~of the women.
Summing over all~$k$ counts each possibility exactly once.

Much more often than not we use these identities left to right,
since that's the direction of simplification.
But every once in a while it pays to go the other direction,
temporarily making an expression more complicated.
When this works, we've usually created a double sum
for which we can interchange the order of summation and then simplify.

Before moving on let's look at proofs for two more of the identities
in Table~|bc-prod|.
It's easy to prove \eq(|bc-prod2|); all we need to do is replace
the first binomial coefficient by $l\choose l-m-k$, then Vandermonde's
\eq(|bc-prod1|) applies.

 The next one, \eq(|bc-prod3|), is a bit more difficult.
We can reduce it to Vandermonde's convolution by a sequence of
transformations, but we can just as easily prove it by resorting
to the old reliable technique of mathematical induction.
Induction is often the first thing to try when
"!philosophy"
nothing else obvious jumps out at us, and
induction on~$l$ works just fine here.

For the basis~$l=0$, all terms are zero except when $k=-m$;
so both sides of the equation are~$(-1)^m{s-m\choose n}$.
Now suppose that the identity holds for all values less than some fixed~$l$,
where~$l>0$. We can use
the addition formula to replace $l\choose m+k$ by ${l-1\choose m+k}+
{l-1\choose m+k-1}$; the original sum now breaks into two sums, each
of which can be evaluated by the induction hypothesis:
\begindisplay \openup2pt
&\sum_k{l-1\choose m+k}{s+k\choose n}(-1)^k
 +\sum_k{l-1\choose m+k-1}{s+k\choose n}(-1)^k\cr
&\hskip5em=(-1)^{l-1+m}{s-m\choose n-l+1}+(-1)^{l+m}{s-m+1\choose n-l+1}\,.\cr
\enddisplay
And this simplifies to the right-hand side of \eq(|bc-prod3|), if we
apply the addition formula once again.

Two things about this derivation are worthy of note. First, we see again
the great convenience of summing over all integers~$k$, not just over
a certain range, because there's no need to fuss over boundary conditions.
Second, the addition formula works nicely with mathematical induction,
because it's a recurrence for binomial coefficients.
A binomial coefficient whose upper index is~$l$
is expressed in terms of two whose upper indices are~$l-1$,
and that's exactly what we need to apply the induction hypothesis.

So much for Table~|bc-prod|.
What about sums with three or more binomial coefficients?
If the index of summation is spread over all the coefficients,
our chances of finding a closed form aren't great:
Only a few closed forms are known for sums of this kind,
hence the sum we need might not match the given specs.
One of these rarities, proved in exercise~|prove-saalschutz|, is
\begindisplay
&\sum_k{m-r+s\choose k}{n+r-s\choose n-k}{r+k\choose m+n}\cr
&\qquad= {r\choose m}{s\choose n}\,,\qquad\hbox{integers $m,n\ge0$.}
\eqno\eqref|bc-saalschutz|
\enddisplay

Here's another, more symmetric example:
\begindisplay \openup3pt
&\sum_k{a+b\choose a+k}{b+c\choose b+k}{c+a\choose c+k}(-1)^k\cr
&\qquad ={(a+b+c)!\over a!\,b!\,c!}\,,\qquad\hbox{integers $a,b,c\ge0$.}
\eqno\eqref|bc-dixon|
\enddisplay
This one has a two-coefficient counterpart,
\begindisplay
\sum_k {a+b\choose a+k} {b+a\choose b+k} (-1)^k
	&= {(a+b)!\over a!\, b!} \,,\qquad\hbox{integers $a,b\ge0$,}
\eqno\eqref|bc-half-dixon|
\enddisplay
which incidentally doesn't appear in Table |bc-prod|. The analogous
four-coefficient sum doesn't have a closed form, but a similar sum does:
\begindisplay
&\sum_k(-1)^k{a+b\choose a+k}{b+c\choose b+k}{c+d\choose c+k}{d+a\choose d+k}
 \bigg/{2a+2b+2c+2d\choose a+b+c+d+k}\cr
&\global\medmuskip=1mu
\qquad={(a+b+c+d)!\,(a+b+c)!\,(a+b+d)!\,(a+c+d)!\,(b+c+d)!\over
 (2a+2b+2c+2d)!\,(a+c)!\,(b+d)!\,a!\,b!\,c!\,d!}\,,\cr
\noalign{\smallskip}
&\global\medmuskip=\normalmedmu
\hskip63mm\hbox{integers $a,b,c,d\ge0$.}
\enddisplay
This was discovered by John "Dougall" [|dougall|] early in the twentieth century.

Is Dougall's identity
 the hairiest sum of binomial coefficients known? No! The champion
so far is
\begindisplay \openup3pt
&\sum_{k_{ij}}(-1)^{\Sigma_{i<j}k_{ij}}
 \Biggl(\prod_{1\le i<j<n}\!{a_i{+}a_j\choose a_j{+}k_{ij}}\!\Biggr)
 \Biggl(\prod_{1\le j<n}\!{a_j+a_n\choose a_n+\Sigma_{i<j}k_{ij}-
  \Sigma_{i>j}k_{ji}}\!\Biggr)\cr
&\qquad={a_1+\cdots+a_n\choose a_1,a_2,\ldots,a_n}\,,
 \qquad\hbox{integers $a_1,a_2,\ldots,a_n\ge0$.}
\eqno\eqref|bc-dyson|
\enddisplay
Here the sum is over $n-1\choose2$ index variables $k_{ij}$ for $1\le i<j<n$.
Equation \eq(|bc-dixon|) is the special case $n=3$; the case $n=4$ can
be written out as follows, if we use $(a,b,c,d)$ for $(a_1,a_2,a_3,a_4)$ and
$(i,j,k)$ for $(k_{12},k_{13},k_{23})$:
\begindisplay \openup2pt
&\global\medmuskip=1mu
\sum_{i,j,k}(-1)^{i+j+k}{a+b\choose b+i}{a+c\choose c+j}{b+c\choose c+k}
 {a+d\choose d-i-j}{b+d\choose d+i-k}{c+d\choose d+j+k}\cr
&\global\medmuskip=\normalmedmu
\qquad={(a+b+c+d)!\over a!\,b!\,c!\,d!}\,,
 \qquad\hbox{integers $a,b,c,d\ge0$.}
\enddisplay
The left side of \thiseq\ is the coefficient of $z_1^0z_2^0\ldots z_n^0$
after
the product of $n(n-1)$ fractions
\begindisplay
\prod\twoconditions{1\le i,j\le n}{i\ne j}\left(1-{z_i\over z_j}\right)^{a_i}
\enddisplay
has been
fully expanded into positive and negative powers of the $z$'s. The
right side of \thiseq\ was conjectured by Freeman "Dyson" in 1962 and proved
by several people
shortly thereafter. Exercise~|dyson| gives a ``simple'' proof of \thiseq.

Another noteworthy identity involving lots of binomial coefficients is
\begindisplay
&\sum_{j,k}(-1)^{j+k}{j+k\choose k+l}{r\choose j}{n\choose k}
  {s+n-j-k\choose m-j}\cr
&\qquad =(-1)^l{n+r\choose n+l}{s-r\choose m-n-l}\,,
 \quad\hbox{integers $l,m,n$; \quad$n\ge0$.}
\eqno\eqref|bc-quad|
\enddisplay
This one, proved in exercise |prove-bc-quad|,
even has a chance of arising in practical applications. But we're
getting far afield from our theme of ``basic identities,\qback''
so we had better stop and take stock of what we've learned.

We've seen that binomial coefficients satisfy an almost bewildering
variety of identities. Some of these, fortunately,
are easily remembered, and we can use the memorable ones
to derive most of the others in a few steps. Table~|bc-tops|
collects ten of the most useful formulas, all in one place; these are the
best identities to know.

\beginsection 5.2 Basic Practice

In the previous section
 we derived a bunch of identities by manipulating
sums and plugging in other identities. It wasn't
too tough to find those derivations\dash---%
we knew what we were trying to prove,
so we could formulate a general plan and fill in the details
without much trouble.
Usually, however, out in the real world,
we're not faced with an identity to prove;
we're faced with a sum to simplify.
And we don't know what a simplified form might look like
(or even if one exists).
By tackling many such sums in this section and the next,
we will hone our binomial coefficient tools.

To start, let's try our hand at a few sums
involving a single binomial coefficient.

\subhead Problem 1: A sum of ratios.

We'd like to have a closed form for
\begindisplay
 \sum_{k=0}^m{m \choose k} \bigg/ {n \choose k} \,,
				\qquad\hbox{integers $n \geq m \geq 0$.}
\enddisplay
At first glance this sum evokes panic,
because we haven't seen any identities that
deal with a quotient of binomial coefficients.
(Furthermore the sum involves two binomial coefficients,
which seems to contradict the sentence preceding this problem.)
\g\vskip-1.5in\mathsurround=0pt\everypar{\hangindent2em}\hbadness=1200
\def\goto{g\kern-.1em\undertext{\kern.1emoto}}
 Algorithm \hfil\undertext{self-teach}:\par
1\enspace read problem\par
2\enspace attempt solution\par
3\enspace skim book solution\par
4\enspace \undertext{if} attempt failed
 \goto\ 1\par
\leavevmode\phantom{4\enspace}\undertext{else} \goto\ next problem
\vskip.75in\everypar{}
Unfortunately, that~algorithm can put you in an infinite loop.\smallskip
"!goto"
Suggested patches:\smallskip
\noindent\hbox to 1.5em{0\hfil}\undertext{set} $\,c\gets0$\par
\noindent\hbox to 1.5em{3a\hfil}\undertext{set} $\,c\gets c+1$\par
\noindent\hbox to 1.5em{3b\hfil}\undertext{if} $\,c=N$\par
\hskip2em\goto\ your TA\vskip.75in
\unitlength=1pt
\beginpicture(40,40)(-20,-20)
\thicklines
\put(0,0){\circle{28}}
\put(1,-1){\makebox(0,0){\goto}}
\put(-9.9,-9.9){\line(1,1){19.8}}\endpicture\smallskip
\hfill\dash---E.\thinspace W. "Dijkstra"
\vskip.75in
\dots\ But this sub\-chapter is called BASIC practice.\g
However, just as we can
use the factorial representations to reexpress a product
of binomial coefficients as another product\dash---%
that's how we got identity~\eq(|bc-tc|)\dash---%
we can do likewise with a quotient.
In fact we can avoid the grubby factorial representations
by letting $r=n$ and dividing both sides of equation~\eq(|bc-tc|)
by ${n \choose k} {n \choose m}$; this yields
\begindisplay
 {m \choose k} \bigg/ {n \choose k}
	= {n-k \choose m-k} \bigg/ {n \choose m} \,.
\enddisplay
So we replace the quotient on the left,
which appears in our sum,
by the one on the right; the sum becomes
\begindisplay
 \sum_{k=0}^m{n-k \choose m-k} \bigg/ {n \choose m} \,.
\enddisplay
We still have a quotient, but
the binomial coefficient in the denominator
doesn't involve the index of summation~$k$,
so we can remove it from the sum.
We'll restore it later.

\topinsert
\let\savethiseq=\thiseq
\def\\#1{\gdef\thiseq{\gtext#1}\eqno\global\advance\eqcount-1\cr}
\table The top ten binomial coefficient identities.\tabref|bc-tops|
\begindisplay\abovedisplayskip=-2pt \belowdisplayskip=6pt \openup7pt%
 \advance\displayindent-\parindent\advance\displaywidth\parindent
{n\choose k}&={n!\over k!\,(n-k)!}\,,
 \quad}\hfill{\tworestrictions
 {integers}{$n\ge k\ge0$.}\\{factorial expansion}
{n\choose k}&={n\choose n-k}\,,
 \quad}\hfill{\tworestrictions
 {integer $n\ge0$,}{integer $k$.}\\{symmetry}