chap5.tex

Concrete_Mathematics_2nd_Ed_TeX_Source_Code

% Chapter 5 of Concrete Mathematics
% (c) Addison-Wesley, all rights reserved.
\input gkpmac
\refin bib
\refin chap2
\refin chap4
\refin chap6

\pageno=153
\beginchapter 5 Binomial Coefficients

LET'S TAKE A BREATHER. The previous chapters have seen some heavy going,
with sums involving floor, ceiling, mod, phi, and mu functions.
Now we're going to study binomial coefficients, which turn out
to be (a)~more important in applications, and (b)~easier to manipulate,
\g Lucky us!\g
than all those other quantities.

\beginsection 5.1 Basic Identities

The symbol $n \choose k$ is a "binomial coefficient",
so called because of an important property we look at later this section,
the binomial theorem.
But we read the symbol ``$n$~choose~$k$.\qback''
This incantation arises from its "combinatorial interpretation"\dash---%
it is the number of ways to choose a $k$-element subset
from an $n$-element set.
\g Otherwise known as "combinations" of $n$~things, $k$~at a time.\g
For example, from the set $\{1,2,3,4\}$ we can choose two elements in six ways,
\begindisplay
 \{1,2\}\,,\quad \{1,3\}\,,\quad \{1,4\}\,,\quad \{2,3\}\,,\quad
	\{2,4\}\,,\quad \{3,4\}\,;
\enddisplay
so ${4 \choose 2} = 6$.

To express the number~$n \choose k$ in more familiar terms
it's easiest to first determine
the number of $k$-element {\it sequences},
rather than subsets, chosen from an $n$-element set;
for sequences, the order of the elements counts.
We use the same argument we used in Chapter~4 to show that
$n!$~is the number of permutations of $n$~objects.
There are $n$~choices for the first element of the sequence;
for each, there are $n-1$~choices for the second;
and so on, until there are $n-k+1$ choices for the~$k$th.
This gives $n(n-1) \ldots (n-k+1)=n\_k$ choices in all.
And since each $k$-element subset
has exactly $k!$ different orderings,
this number of {\it sequences\/} counts
each {\it subset\/} exactly $k!$~times.
To get our answer, we simply divide by~$k!$:
\begindisplay
 {n \choose k}
	= {n(n-1) \ldots (n-k+1)\over k(k-1) \ldots (1)} \,.
\enddisplay
For example,
\begindisplay
 {4 \choose 2}
	= {4 \cdt 3\over 2 \cdt 1}
	= 6 \,;
\enddisplay
this agrees with our previous enumeration.

We call $n$ the {\it"upper index"\/} and $k$ the {\it"lower index"}.
"!index, of a binomial coefficient"
The indices are
restricted to be nonnegative integers by the combinatorial interpretation,
because sets don't have negative or fractional numbers of elements.
But the binomial coefficient has many uses
besides its combinatorial interpretation,
so we will remove some of the restrictions.
It's most useful, it turns out,
to allow an arbitrary real (or even complex) number to appear in
the upper index, and to allow
an arbitrary integer in the lower.
Our formal definition therefore takes the following form:
\begindisplay
{r \choose k}=\cases{
	\displaystyle {r(r-1) \ldots (r-k+1)\over k(k-1) \ldots (1)}
	 = {r\_k\over k!}\,,&integer $k\ge0$;\cr
\noalign{\medskip}
	0\,,&integer $k < 0$.\cr}
\eqno\eqref|bc-def|
\enddisplay

This definition has several noteworthy features. First, the upper index
is called~$r$, not~$n$; the letter~$r$ emphasizes the fact
that binomial coefficients make sense
when any real number appears in this position.
For instance, we have ${-1 \choose 3} = (-1)(-2)(-3)/
(3 \cdt 2 \cdt 1) = -1$.
There's no combinatorial interpretation here, but $r=-1$ turns out to
be an important special case.
A noninteger index like $r = -1/2$ also turns out to be useful.

Second, we can view $r \choose k$ as a $k$th-degree polynomial in~$r$.
We'll see that this viewpoint is often helpful.

Third, we haven't defined binomial coefficients
for noninteger lower indices.
A reasonable definition can be given, but actual applications are
rare, so we will defer this generalization to
later in the chapter.

Final note:
We've listed the restrictions `integer $k \geq 0@$'
and `integer $k < 0@$' at the right of the definition.
Such restrictions will be listed
in all the identities we will study, so that the range of
applicability will be clear.
In general the fewer restrictions the better,
because an unrestricted identity is most useful;
still, any restrictions that apply are
an important part of the identity.
When we manipulate binomial coefficients,
it's easier to ignore
difficult-to-remember restrictions temporarily
and to check later that nothing has been violated.
But the check needs to be made.

For example, almost every time we encounter $n \choose n$ it equals~$1$,
so we can get lulled into thinking that it's always~$1$.
But a careful look at definition~\eq(|bc-def|) tells us that $n\choose n$ is~$1$
only when $n \geq 0$ (assuming that $n$~is an integer);
when $n < 0$ we have ${n \choose n} = 0$.
"Trap"s like this can (and will) make life adventuresome.

Before getting to the identities that we will use to tame binomial coefficients,
let's take a peek at some "small values".
The numbers in Table~|pascal-triangle|
form the beginning of {\it "Pascal's triangle"},
\vadjust{\vskip 14pt plus 4pt minus 2pt
\setbox0=\hbox{$\biggr)$}
\def\\#1{\displaystyle{n\choose#1}\kern-\wd0}
\table Pascal's triangle.\tabref|pascal-triangle|
\offinterlineskip
\halign to\hsize{\strut$\hfil#$\quad&\vrule#\kern-5pt\tabskip10pt plus 100pt&
 \hfil$#$&
 \hfil$#$&
 \hfil$#$&
 \hfil$#$&
 \hfil$#$&
 \hfil$#$&
 \hfil$#$&
 \hfil$#$&
 \hfil$#$&
 \hfil$#$&
 \hfil$#$\tabskip\wd0\cr
\omit&height 3pt\cr
n &&\\0&\\1&\\2&\\3&\\4&\\5&\\6&\\7&\\8&\\9&\\{10}\cr
\omit&height 2pt\cr
\noalign{\hrule width\hsize}
\omit&height 3pt\cr
0 && 1 \cr
1 && 1 & 1 \cr
2 && 1 & 2 & 1 \cr
3 && 1 & 3 & 3 & 1 \cr
4 && 1 & 4 & 6 & 4 & 1 \cr
5 && 1 & 5 & 10 & 10 & 5 & 1 \cr
6 && 1 & 6 & 15 & 20 & 15 & 6 & 1 \cr
7 && 1 & 7 & 21 & 35 & 35 & 21 & 7 & 1 \cr
8 && 1 & 8 & 28 & 56 & 70 & 56 & 28 & 8 & 1 \cr
9 && 1 & 9 & 36 & 84 & 126 & 126 & 84 & 36 & 9 & 1 \cr
10 && 1 & 10 & 45 & 120 & 210 & 252 & 210 & 120 & 45 & 10 & 1\ \cr
\omit&height 2pt\cr}
\hrule height .5pt width\hsize
\vskip 14pt plus 4pt minus 2pt}% end the \vadjust
named after Blaise "Pascal" (1623--1662)
because he wrote an influential treatise about them [|pascal-treatise|].
\g Binomial coefficients were well known in Asia,
many centuries before Pascal was born~[|edwards|],
but he had no way to know that.\g
The empty entries in this table are actually $0@$'s,
because of a zero in the numerator of \eq(|bc-def|);
for example, ${1 \choose 2} = (1 \cdt 0) / (2 \cdt 1) = 0$.
These entries have been left blank
simply to help emphasize the rest of the table.

It's worthwhile to memorize formulas for the first three columns,
\begindisplay
{r \choose 0} = 1 \,,
	\qquad {r \choose 1} = r \,,
	\qquad {r \choose 2} = {r(r-1)\over 2} \,;
\eqno
\enddisplay
these hold for arbitrary reals.
(Recall that ${n+1\choose2}=\half n(n+1)$ is the formula we derived
for triangular numbers in Chapter~1;
triangular numbers are
conspicuously present in the $n\choose 2$ column of Table~|pascal-triangle|.)
It's also a good idea to memorize the first five rows or so of Pascal's triangle,
so that when the pattern $1$,~$4$, $6$, $4$,~$1$ appears in some problem
we will have a clue that binomial coefficients probably lurk nearby.

The numbers in Pascal's triangle satisfy, practically speaking,
\g In Italy it's called Tartaglia's triangle.\g
infinitely many identities,
so it's not too surprising that we can find some surprising relationships
by looking closely.
For example, there's a curious ``"hexagon property",\qback'' illustrated by
the six numbers $56$,~$28$, $36$, $120$, $210$,~$126$ that surround $84$
in the lower right portion of Table~|pascal-triangle|.
Both ways of multiplying alternate numbers from this hexagon
give the same product:
$56\cdt36\cdt210=28\cdt120\cdt126=423360$. The same thing holds if we
extract such a hexagon from any other part of Pascal's triangle.

\goodbreak
And now the identities. Our goal in this section will be to learn
\g\noindent\llap{``}C'est une chose estrange combien il est fertile en proprietez.''
\par\hfill\dash---B. Pascal [|pascal-treatise|]\g
a few simple rules by which we can solve the vast majority
of practical problems involving binomial coefficients.

Definition \eq(|bc-def|) can be recast in terms of factorials
in the common case that the upper index~$r$ is an integer, $n$, that's
greater than or equal to the lower index~$k$:
\begindisplay
{n \choose k}
	= {n!\over k! \, (n-k)!} \,,
			\qquad\hbox{integers $n \geq k \geq 0$.}
\eqno\eqref|bc-factorial|
\enddisplay
To get this formula, we just multiply the
numerator and denominator of \eq(|bc-def|) by $(n-k)!$.
It's occasionally useful to expand a binomial coefficient into this
"!factorial expansion"
factorial form (for example, when proving the hexagon property). And we often
want to go the other way, changing factorials into binomials.

The factorial representation hints at a symmetry in Pascal's triangle:
Each row reads the same left-to-right as right-to-left.
The identity reflecting this\dash---called the {\it symmetry\/}
"!symmetry identity"
identity\dash---is obtained by changing $k$ to $n-k$:
\begindisplay
{n \choose k}
	= {n \choose n-k} \,,
		\qquad\tworestrictions{integer $n \geq 0$,}{integer $k$.}
\eqno\eqref|bc-symmetry|
\enddisplay
This formula makes combinatorial sense,
because by specifying the $k$~chosen things out of~$n$
we're in effect specifying the $n-k$~unchosen things.

The restriction that $n$~and~$k$ be integers in identity \thiseq\ is obvious,
since each lower index must be an integer.
But why can't $n$~be negative?
Suppose, for example, that $n=-1$. Is
\begindisplay
 {-1 \choose k}\buildrel ? \over={-1 \choose -1-k}
\enddisplay
a valid equation?
No.
For instance, when $k=0$ we get $1$ on the left and $0$ on the right.
In fact, for any integer~$k \geq 0$ the left side is
\begindisplay
 {-1 \choose k}
	= {(-1)(-2) \ldots (-k)\over k!}
	= (-1)^k \,,
\enddisplay
which is either $1$~or~$-1$;
but the right side is~$0$, because the lower index is negative.
And for negative~$k$ the left side is~$0$ but the right side is
\begindisplay
 {-1 \choose -1-k}
	= (-1)^{-1-k} \,,
\enddisplay
which is either $1$~or~$-1$.
So the equation `${-1 \choose k} = {-1 \choose -1-k}$' is always false!

The symmetry identity fails for all other negative integers~$n$, too.
But unfortunately it's all too easy to forget this restriction,
since the expression in the upper index is sometimes negative
only for obscure (but legal) values of its variables.
\g I just hope I don't fall into this trap during the midterm.\g
Everyone who's manipulated binomial coefficients much
has fallen into this "trap" at least three times.

But the symmetry identity does have a big redeeming feature:
It works for all values of $k$, even when $k<0$ or $k>n$. (Because
both sides are zero in such cases.) Otherwise $0\le k\le n$, and
symmetry follows immediately from \eq(|bc-factorial|):
\begindisplay
{n\choose k}
	= {n!\over k! \, (n-k)!}
	= {n!\over \bigl( n - (n-k) \bigr)! \; (n-k)!}
	= {n \choose n-k} \,.
\enddisplay

Our next important identity lets us move things
in and out of binomial coefficients:
\begindisplay
{r \choose k}
	= {r\over k} {r-1 \choose k-1} \,, \qquad\hbox{integer $k \neq 0$.}
\eqno\eqref|bc-absorb|
\enddisplay
The restriction on $k$ prevents us from dividing by~$0$ here.
We call \thiseq\ an {\it absorption\/} "!absorption identity" identity,
because we often use it
to absorb a variable into a binomial coefficient when
that variable is a nuisance outside.
The equation follows from definition \eq(|bc-def|),
because $r\_k=r(r-1)\_{k-1}$ and $k!=k(k-1)!$ when $k>0$;
both sides are zero when $k<0$.

If we multiply both sides of \thiseq\ by $k$, we get an absorption identity
that works even when $k=0$:
\begindisplay
k {r \choose k}
	&= r {r-1 \choose k-1} \,, \qquad\hbox{integer $k$.}
\eqno\eqref|bc-absorb-k|
\enddisplay
This one also has a companion that keeps the lower index intact:
\begindisplay
(r-k){r \choose k}
	= r {r-1 \choose k} \,, \qquad\hbox{integer $k$.}
\eqno\eqref|bc-absorb-r-k|
\enddisplay
We can derive \thiseq\ by "sandwiching" an application of~\eq(|bc-absorb-k|)
between two applications of symmetry:
\begindisplay \openup4pt
(r-k){r \choose k}
&	= (r-k){r \choose r-k}&\qquad\hbox{(by symmetry)}\cr
&	= r{r-1\choose r-k-1}&\qquad\hbox{$\bigl($by \eq(|bc-absorb-k|)$\bigr)$}\cr