Given the possibilities of errors through several transcription, please do not rely on the fornulas given below without confirmation check or proof. Corrections and additions welcome.
Binomial coefficients are intimately related to Bernoulli numbers, Catalán numbers, Fibonacci numbers, statistics and a host of combinatoric problems. For more detailed exposition, uses and connections of binomial coefficients, see the Wikipedia article on binomial coefficients. Also, see Pascal's Triangle From Top to Bottom, and Binomial Coefficients from MathWorld.
The binomial coefficient defined by factorials
n!
(n k) := ---------
k! (n-k)!
The right half of the symmetric Pascal triangle for n=1, ...,20
1
2 1
3 1
6 4 1
10 5 1
20 15 6 1
35 21 7 1
70 56 28 8 1
126 84 36 9 1
252 210 120 45 10 1
462 330 165 55 11 1
924 792 495 220 66 12 1
1716 1287 705 276 78 13 1
3432 3003 2002 1001 364 91 14 1
6435 5005 3003 1365 455 105 15 1
12870 11440 8008 4368 1820 560 120 16 1
24310 19448 12376 6188 2380 680 136 17 1
48620 43758 31824 18564 8568 3060 816 153 18 1
92378 75582 50388 27132 11628 3876 969 171 19 1
184756 167960 125970 77520 38760 15504 4845 1140 190 20 1
------------------------------------------------------------------------
------------------------------------------------------------------------
(n 0) = (n n) = 1 (n 1) = (n n-1) = n
(n k) = (n n-k) [Pascal triangle Symmetry]
(n k) = (n-1 k-1) + (n-1 k) [Pascal triangle structure]
(n k-1) = k/(n-k+1) (n k) (n k+1) = (n-k)/(k+1) (n k)
(n k-j) = (n k) (n-k j) (k j) [j!]^2
= (n k) [(n-k j)/(k+j j)] [(k+j)!/(k-j)!]
(n k+j) = (n k) [(n-k j)/(k+j j)]
= (n k-j) [(k+j)!/(k-j)!]
(n-1 k) = (n-k)/n (n k)
(n+1 k) = (n+1)/(n+1-k) (n k)
(n+j k) = [(n+j j)/(n-k+j j)] (n k)
(2n k) = (2n n) (n k) / (2n-k n)
(n-j k) = [(n-k j)/(n j)] (n k)
(n-1 k-1) = k/n (n k) = k/(n-k) (n-1 k)
Was
(n-1 k-1) = k/n (n k) = n/(n-k) (n-1 k)
Thanks to Yale Madden for the correction (March 21, 2007)
(n-j k-j) = [(k j)/(n j)] (n k)
(2n)! = (2^n n!)[1(3)(5)(7)...(2n-1)]
(2n n) = (2n)!/(n! n!) = (2^n/n!) [1(3)(5)(7)...(2n-1)]
The Binomial theorem
n
SUM (n k) x^k y^{n-k} = (x + y)^n
k=0
n
SUM (n k) = 2^n
k=0
This being a special case of the generalization from the multinomial
theorem with m variables:
n m
SUM (n {a}) x_1^n_1 x_2^n_2 ... x_m^n_m = (SUM x_k)^n
{a} k=1
where (n {a}) are multinomial coefficients
m
(n {a}) := n! / PRODUCT a_k!
k=1
where {a} = {a_1, a_2, ..., a_m}, and
m
SUM a_k = n
k=1
Analogous to, and a generalization to the summation of all binomial
coefficients with fixed n, and with that as a special case,
m
SUM [n! / PRODUCT a_k!] = m^n
{a} k=1
Though it is often of little computational use, multinomial
coefficients can be represented as products of binomial coefficients:
Let,
j
n_j := n - SUM k_i => n_(j+1) - n_j = k_j
i=1
m-2
(n {k}) = PRODUCT ( n_j k_(j+1) )
j=0
Binomial Summation Formulas
Special cases
n-1
SUM (2n k) = (1/2)[2^{2n} - (2n n)]
k=0
n
SUM (2n k) = (1/2)[2^{2n} + (2n n)]
k=0
-------
n
SUM (-1)^k (n k) = 0
k=0
n
SUM (-1)^k k (n k) = 0
k=0
n
SUM (-1)^k k^2 (n k) = 0
k=0
... = 0
n
SUM (-1)^k k^n (n k) = (-1)^n n!
k=0
-------
n
SUM k (n k) = n 2^{n-1}
k=0
[Corrected February 12, 2003]
n
SUM 1/(k+1) (n k) = (2^(n+1) - 1) / (n+1)
k=0
--------
[n/2]+1
SUM (k n-1-k) = U(n) [nth Fibonacci number]
k=0
Fibonacci number - Wikipedia, the free encyclopedia
where [.] indicates the integer part of.
The Fibonacci sequence obeys the recursion relation,
U(0) = 0, U(1) = 1,
U(n) + U(n+1) = U(n+2)
as do the more general Lucas sequences with, the initial values
not so specifically constrained.
--------
B
SUM (A C+k) (B k) = (A+B C+B)
k=0
n
SUM (A n-k) (B k) = (A+B n)
k=0
Special cases
n
SUM (m n-k) (m k) = (2m n)
k=0
n
SUM (n k)^2 = (2n n)
k=0
Note: sums of higher powers of binomial coefficients
can be expressed in terms of the generalized
hypergeometric function.
oo
1/(1-x)^s = SUM (s-1+n s-1) x^n, x < 1
n=0
Opportunities present themselves here to derive, by
differentiation, a host of possibly interesting and useful
formulas, as in,
oo
xs/(1-x)^(s+1) = SUM n (s-1+n s-1) x^n, x < 1
n=0
m
SUM (a+k k) = (a+1+m m)
k=0
or,
m
SUM (n-1+k k) = (n+m m)
k=0
Special cases
n
SUM (n-1+k k) = (2n n)
k=0
m
SUM (-1)^k (n k) = (-1)^m (n-1 m)
k=0
(n/2)-m
SUM (n 2m-2k) (m+k k) = [n/2(n-m)] (n-m m) 2^(n-2m)
k=0
((n-1)/2)-m
SUM (n 2m+2k+1) (m+k k) = (n-m-1 m) 2^(n-2m-1)
k=0
n
SUM (n k) z^k = (1 + z)^n
k=0
By taking derivatives of both sides of the previous equation,
n
SUM k (n k) z^k = n z (1 + z)^(n-1)
k=0
n
SUM k^2 (n k) z^k = n z (1 + z)^(n-2) (n(2 + z) - 1)
k=0
n
SUM k(k-1) (n k) z^k = n z (1 + z)^(n-2) (n + (n-1)(1+z) )
k=0
j-1
(n-j k) = [ PROD (1 - k/(n-m)) ] (n k)
m=0
k-1
PROD (n - j) = n!/(n-k)! = k! (n k)
j=0
With term k=j omitted
n-1
PROD (k - j) = (-1)^(n-1-k) k! (n-1-k)!
j=0
= (-1)^(n-1-k) (1/(n-1)!) (n-1 k)
m
PROD (k + j) = (k+m)!/k! = (k+m k) m!
j=1
k! (n-k)!
(n k+m) = --------------- (n k)
(n-k-m)! (k+m)!
Stirling's approximation for large n
log n! -> (n + 1/2)log n - n + (1/2)log 2^(pi)
+ O( n^(-1) ), as n->oo
less precisely
log n! -> n(log n - 1)
Exponentiation of the more precise Stirling's approximation,
n! -> sqrt(2 pi n) n^n exp( -n )
For large n and k << n so that (n-k) can still be considered large
enough for approximation by Stirling's formula.
(n k) -> (n^k/k!) (1 - k/n)^(k-(n + 1/2)) exp( -k )
(n k) -> (n^k/sqrt(2 pi n)) k^-k (1 - k/n)^(k-(n + 1/2)) =
(n^k/sqrt(2 pi n)) (1 - k/n)^-1/2 k^-k (1 - k/n)^(k-n) =
(1/sqrt(2 pi n)) (1 - k/n)^-1/2 (k/n)^-k (1 - k/n)^k (1 - k/n)^-n =
(1/sqrt(2 pi n)) (1 - k/n)^-1/2 (-(1 - n/k))^k (1 - k/n)^-n =
The special case (2n n) -> 2^(2n)/sqrt( pi n )
(n k) n^(-k) -> (1/k!)(1 - k/n)^(k-(n + 1/2)) exp( -k )
[ sqrt(1 - k/n) ]^(2k) exp( -k ) ]
-> ----------------------------------
k! sqrt(1 - k/n) (1 - k/n)^n
[ sqrt(1 - k/n) ]^(2k) ]
-> --------------------------
k! sqrt(1 - k/n)
The asymptotic random flight approximation using Stirling's approximation
and log(1+z) = z - (1/2) z^2 for small z:
(A (A +|- B)/2) 2^(-A) -> sqrt(2/(pi A)) exp( - B^2/2A )
(n k)
lim ------- = 1/k!
n->oo n^k
exp( z ) = lim (1 + z/n)^n =
n->oo
n
lim SUM (n k) (z/n)^k
n->oo k=0
(N M-r) (N-(M-r) 2r)
(N-M r)(M r) = -------------------- (2r r)
(N M)
(1 + iz/n)^n =
(1 + iz/n)^2 (1 + iz/n)^(m-1) (1 + iz/n)^(n-m-1) =
m-1 n-m-1
(1 + iz/n)^2 SUM SUM (m-1 j) (n-m-1 k) n^(-j) n^(-k) (iz/n)^(k+j)
j=0 k=0
Let k+ = (1/2)(j + k)
k- = (1/2)(j - k)
---------------------------------------------------------------
[Wigner 1959] p. 191, eq. (17.26) p. 194 for proof
(N+a+b-k)!
SUM (-1)^k (N-a+b k) ----------- = (2b)! (2a N+a-b)
k (N+a-b-k)!
---------------------------------------------------------------
oo
SUM (m-1+n n) z^(m+n) = [z/(1 - z)]^m
n=0
oo
SUM (n-1 m-1) z^n = [z/(1 - z)]^m
n=0
My Thanks to Luke Porter for the following:
n
SUM | u - (n-j)/n | (n j) (1-u)^i u^(n-j)
j=0
= 2 k/n (n k) p^k (1-p)^(n-k+1)
where k = Floor(pn) + 1 and p = 1-u
Email me, Bill Hammel at