6 The Binomial Coefficients

Theorem 6.1

Let \( n \) be a positive integer. Then, for all \( x \) and \( y \),

\[ (x+y)^{n}=x^{n}+\binom {n}{1}x^{n-1}y+\binom {n}{2}x^{n-2}y^{2}+\cdots +\binom {n}{n-1}x^{1}y^{n-1}+y^{n}. \]

In summation notation,

\[ (x+y)^n=\sum _{k=0}^n\binom {n}{k} x^{n-k} y^k. \]

Proof ▶

Theorem 6.2

Let \( n \) be a positive integer. Then, for all \( x \),

\[ (1+x)^n = \sum _{k=0}^n \binom {n}{k} x^k = \sum _{k=0}^n \binom {n}{n-k} x^k. \]

Proof ▶

Theorem 6.3

Let \( n \) be a positive integer. The sequence of binomial coefficients

\[ \binom {n}{0}, \binom {n}{1}, \binom {n}{2}, \ldots , \binom {n}{n} \]

is a unimodal sequence. More precisely, if \( n \) is even,

\begin{align*} \binom {n}{0} & {\lt} \binom {n}{1} {\lt} \cdots {\lt} \binom {n}{n/2}, \\ \binom {n}{n/2} & {\gt} \cdots {\gt} \binom {n}{n-1} {\gt} \binom {n}{n}, \end{align*}

and if \( n \) is odd,

\begin{align*} \binom {n}{0} & {\lt} \binom {n}{1} {\lt} \cdots {\lt} \binom {n}{(n-1)/2} = \binom {n}{(n+1)/2}, \\ & \binom {n}{(n+1)/2} {\gt} \cdots {\gt} \binom {n}{n-1} {\gt} \binom {n}{n}. \end{align*}

Proof ▶

Corollary 6.4

For \( n \) a positive integer, the largest of the binomial coefficients

\[ \binom {n}{0}, \binom {n}{1}, \binom {n}{2}, \ldots , \binom {n}{n} \]

\[ \binom {n}{\lfloor n/2 \rfloor } = \binom {n}{\lceil n/2 \rceil }. \]

Proof ▶

Theorem 6.5

Let \( S \) be a set of \( n \) elements. Then an antichain on \( S \) contains at most \( \binom {n}{\lfloor \frac{n}{2} \rfloor } \) sets.

Proof ▶

Theorem 6.6

Let \( n \) be a positive integer. For all \( x_1, x_2, \ldots , x_t \), \( (x_1 + x_2 + \cdots + x_t)^n = \sum \binom {n}{n_1n_2\ldots n_t} x_1^{n_1} x_2^{n_2} \cdots x_t^{n_t}, \) where the summation extends over all nonnegative integral solutions is \( n_1, n_2, \ldots , n_t \) of \( n_1 + n_2 + \cdots + n_t = n \).

Proof ▶

Theorem 6.7

Let \( \alpha \) be a real number. Then, for all \( x \) and \( y \) with \( 0 \leq |x| {\lt} |y| \),

\[ (x + y)^\alpha = \sum _{k=0}^{\infty } \binom {\alpha }{k} x^k y^{\alpha -k}, \]

where

\[ \binom {\alpha }{k} = \frac{\alpha (\alpha - 1) \cdots (\alpha - k + 1)}{k!}. \]

Proof ▶

Theorem 6.8

Let \((X, \leq )\) be a finite partially ordered set, and let \( r \) be the largest size of a chain. Then \( X \) can be partitioned into \( r \) but no fewer antichains.

Proof ▶

Theorem 6.9

Let \((X, \leq )\) be a finite partially ordered set, and let \(m\) be the largest size of an antichain. Then \(X\) can be partitioned into \(m\) but no fewer chains.

Proof ▶