Binomial coefficients
by math_explorer, Feb 22, 2011, 3:31 AM
The first time you see a binomial coefficient it was probably defined like this:
![\[ \binom{n}{k} = \frac{n!}{k!(n-k)!} \]](//latex.artofproblemsolving.com/a/5/6/a56650a7e8e5a3e6866c72b09a230f0482686e52.png)
Then somebody decides that the top number doesn't have to be a nonnegative integer, or even nonnegative. And the bottom number: it can be a negative integer too. What?
![\[ \binom{n}{k} = \prod_{j=1}^{k} \frac{r+1-j}{j} \]](//latex.artofproblemsolving.com/f/7/4/f74aac70d353f904f448745bce78e9569fc235df.png)
Things get worse.
![\[ B(x, y) = \int_{0}^{1} t^{x-1} (1-t)^{y-1} \]](//latex.artofproblemsolving.com/1/0/4/10450b705182c6c1b066d579382947dc3c87a234.png)
, 
, 
, so 
. 
. Oh, okay.
![\[ \binom{n}{k} = \frac{1}{(n+1)B(k+1, n-k+1)} \]](//latex.artofproblemsolving.com/c/8/5/c850f20df1bb694c4eb0ee6cfadfc37ef26e3238.png)
What this means is we now know how many ways there are to choose
objects from 
objects, where order doesn't matter. Something very useful if you're on a budget.
![\[ \binom{n}{1/2} = \frac{1}{(n+1)\frac{(1/2)(n-1/2)(n-3/2)\ldots(1/2)}{(n+1)(n)\ldots(1)}\pi} \]](//latex.artofproblemsolving.com/a/a/1/aa1a7f702ef5d90797ed2e7661707aa5f4196e9e.png)
which works out to be
![\[ \binom{n}{1/2} = \frac{2^{2n+1}}{\binom{2n}{n}\pi} \]](//latex.artofproblemsolving.com/0/f/c/0fc84309ae863605935f134b43bf00d484c9137e.png)
Plus, the symmetry
![\[ \binom{n}{k} = \binom{n}{n-k} \]](//latex.artofproblemsolving.com/b/9/9/b99ab04c69072e0d714fc2507f5c3b7946770ffe.png)
and the addition relation
![\[ \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} \]](//latex.artofproblemsolving.com/5/0/8/508a39af25cc9eefaa226626dcecf478532e130c.png)
still hold. Mostly. Stay away from the divide-by-zero area and you'll be okay.
Oh, and the well-known hockey stick identity
![\[ \binom{n+1}{m+1} = \binom{0}{m} + \binom{1}{m} + \ldots + \binom{n}{m} \]](//latex.artofproblemsolving.com/5/f/5/5f57abb09ec04732ddb767965fca1317a13cca32.png)
lets us do things like "Since
, we have 
."
Anyway, Vandermonde's convolution again for no reason.
![\[ \sum_{k} \binom{r}{k}\binom{s}{n-k} = \binom{r+s}{n} \]](//latex.artofproblemsolving.com/6/f/0/6f067542979cef7382fbe219fca9a1c68bdf5c4c.png)
If
then 
so we can adjust until all the 
have maximum distance 1 from each other, whereupon the inequality is trivial. Equality iff is constant.
![$\left[{n \atop k}\right]$](//latex.artofproblemsolving.com/a/1/8/a18e5777778c382bfce4d6c0a7f918701d12f1ba.png)
![\[ \binom{n}{k} = \frac{n!}{k!(n-k)!} \]](http://latex.artofproblemsolving.com/a/5/6/a56650a7e8e5a3e6866c72b09a230f0482686e52.png)
Then somebody decides that the top number doesn't have to be a nonnegative integer, or even nonnegative. And the bottom number: it can be a negative integer too. What?
![\[ \binom{n}{k} = \prod_{j=1}^{k} \frac{r+1-j}{j} \]](http://latex.artofproblemsolving.com/f/7/4/f74aac70d353f904f448745bce78e9569fc235df.png)
Things get worse.
![\[ B(x, y) = \int_{0}^{1} t^{x-1} (1-t)^{y-1} \]](http://latex.artofproblemsolving.com/1/0/4/10450b705182c6c1b066d579382947dc3c87a234.png)
, 
, 
, so 
. 
. Oh, okay.![\[ \binom{n}{k} = \frac{1}{(n+1)B(k+1, n-k+1)} \]](http://latex.artofproblemsolving.com/c/8/5/c850f20df1bb694c4eb0ee6cfadfc37ef26e3238.png)
What this means is we now know how many ways there are to choose
objects from 
objects, where order doesn't matter. Something very useful if you're on a budget.![\[ \binom{n}{1/2} = \frac{1}{(n+1)\frac{(1/2)(n-1/2)(n-3/2)\ldots(1/2)}{(n+1)(n)\ldots(1)}\pi} \]](http://latex.artofproblemsolving.com/a/a/1/aa1a7f702ef5d90797ed2e7661707aa5f4196e9e.png)
which works out to be
![\[ \binom{n}{1/2} = \frac{2^{2n+1}}{\binom{2n}{n}\pi} \]](http://latex.artofproblemsolving.com/0/f/c/0fc84309ae863605935f134b43bf00d484c9137e.png)
Plus, the symmetry
![\[ \binom{n}{k} = \binom{n}{n-k} \]](http://latex.artofproblemsolving.com/b/9/9/b99ab04c69072e0d714fc2507f5c3b7946770ffe.png)
and the addition relation
![\[ \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} \]](http://latex.artofproblemsolving.com/5/0/8/508a39af25cc9eefaa226626dcecf478532e130c.png)
still hold. Mostly. Stay away from the divide-by-zero area and you'll be okay.
Oh, and the well-known hockey stick identity
![\[ \binom{n+1}{m+1} = \binom{0}{m} + \binom{1}{m} + \ldots + \binom{n}{m} \]](http://latex.artofproblemsolving.com/5/f/5/5f57abb09ec04732ddb767965fca1317a13cca32.png)
lets us do things like "Since
, we have 
."Anyway, Vandermonde's convolution again for no reason.
![\[ \sum_{k} \binom{r}{k}\binom{s}{n-k} = \binom{r+s}{n} \]](http://latex.artofproblemsolving.com/6/f/0/6f067542979cef7382fbe219fca9a1c68bdf5c4c.png)
If
then 
so we can adjust until all the 
have maximum distance 1 from each other, whereupon the inequality is trivial. Equality iff is constant.![$\left[{n \atop k}\right]$](http://latex.artofproblemsolving.com/a/1/8/a18e5777778c382bfce4d6c0a7f918701d12f1ba.png)
This post has been edited 1 time. Last edited by math_explorer, Aug 19, 2011, 9:30 AM
May 2020
January 2020