A Collection of Identities and Formulas
Involving Binomial Coefficients



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




Return to Math Page Return to Home Page

Email me, Bill Hammel at
bhammel@graham.main.nc.us
READ WARNING BEFORE SENDING E-MAIL

The URL for this document is:
http://graham.main.nc.us/~bhammel/MATH/binom.html
Created: November 18, 1997
Last Updated: May 28, 2000
Last Updated: July 21, 2002
Last Updated: August 9, 2002
Last Updated: February 12, 2003
Last Updated: June 6, 2004
Last Updated: December 27, 2004
Last Updated: March 4, 2005
Last Updated: March 2, 2006
Last Updated: March 21, 2007