Binomial Coefficient

The number of ways of picking $n$ unordered outcomes from $N$ possibilities. Also known as a Combination. The binomial coefficients form the rows of Pascal's Triangle. The symbols ${}_NC_n$ and

$${N\choose n} \equiv {N!\over (N-n)!n!}$$ (1)

are used, where the latter is sometimes known as $N$ Choose $n$. The number of Lattice Paths from the Origin $(0,0)$ to a point $(a,b$) is the Binomial Coefficient ${a+b\choose a}$ (Hilton and Pedersen 1991).

For Positive integer $n$, the Binomial Theorem gives

$$(x+a)^n = \sum_{k=0}^n {n\choose k} x^k a^{n-k}.$$ (2)

The Finite Difference analog of this identity is known as the Chu-Vandermonde Identity. A similar formula holds for Negative Integral $n$,

$$(x+a)^{-n}=\sum_{k=0}^\infty {-n\choose k} x^k a^{-n-k}.$$ (3)

A general identity is given by

$${(a+b)^n\over a} = \sum_{j=0}^n {n\choose j} (a - jc)^{j-1} (b + jc)^{n-j}$$ (4)

(Prudnikov et al. 1986), which gives the Binomial Theorem as a special case with $c=0$.

The binomial coefficients satisfy the identities:

$${n \choose 0} = {n\choose n}=1$$ (5)

$${n\choose k} = {n\choose n-k} = (-1)^k{k-n-1\choose k}$$ (6)

$${n+1\choose k} = {n\choose k}+{n\choose k-1}.$$ (7)

Sums of powers include

$$\sum_{k=0}^n {n\choose k}=2^n$$ (8)

$$\sum_{k=0}^n (-1)^k{n\choose k}=0$$ (9)

$$\sum_{k=0}^n {n\choose k}r^k=(1+r)^n$$ (10)

(the Binomial Theorem), and

$$\sum_{n=0}^\infty {2n+s\choose n}x^n={}_2F_1({\textstyle{1\o... ...ver 2}}(s+2); s+1, 4x)={2^s\over(\sqrt{1-4x}+1)^s\sqrt{1-4x}},$$ (11)

where ${}_2F_1(a,b;c;z)$ is a Hypergeometric Function (Abramowitz and Stegun 1972, p. 555; Graham et al. 1994, p. 203). For Nonnegative Integers $n$ and $r$ with $r\leq n+1$,

$\sum_{k=0}^n {(-1)^k\over k+1} {n\choose k}\left[{\,\sum_{j=0}^{r-1} (-1)^j{n\choose j}(r-j)^{n-k}}\right.$
$\left.{+\sum_{j=0}^{n-r}(-1)^j{n\choose j}(n+1-r-j)^{n-k}}\right]=n!.\qquad$	(12)

Taking $n=2r-1$ gives

$$\sum_{k=0}^n {(-1)^k\over k+1} {n\choose k}\sum_{j=0}^{r-1}{n\choose j}(r-j)^{n-k}={\textstyle{1\over 2}}n!.$$ (13)

Another identity is

$$\sum_{k=0}^n {n+k\choose k}[x^{n+1}(1-x)^k+(1-x)^{n+1}x^k]=1$$ (14)

(Beeler et al. 1972, Item 42).

Recurrence Relations of the sums

$$s_p\equiv \sum_{k=0}^n {n\choose k}^p$$ (15)

are given by

$$2s_1(n)-s_1(n+1)=0$$ (16)

$$-2(2n+1)s_2(n)+(n+1)s_2(n)=0$$ (17)

$$-8(n+1)^2s_3(n)+(-16-21n-7n^2)s_3(n+1)+(n+2)^2s_3(n+2)=0$$ (18)

$-4(n+1)(4n+3)(4n+5)s_4(n)-2(2n+3)(3n^2+9n+7)s_4(n+1)$
$+(n+2)^3s_4(n+2)=0.\quad$	(19)

This sequence for $s_3$ cannot be expressed as a fixed number of hypergeometric terms (Petkovsek et al. 1996, p. 160).

A fascinating series of identities involving binomial coefficients times small powers are

$$\sum_{n=1}^\infty {1\over{2n\choose n}}={\textstyle{1\over 27}}(2\pi\sqrt{3}+9)=0.7363998587\ldots$$ (20)

$$\sum_{n=1}^\infty {1\over n{2n\choose n}}={\textstyle{1\over 9}}\pi\sqrt{3}=0.6045997881\ldots$$ (21)

$$\sum_{n=1}^\infty {1\over n^2{2n\choose n}}={\textstyle{1\over 3}}\zeta(2)={\textstyle{1\over 8}}\pi^2$$ (22)

$$\sum_{n=1}^\infty {1\over n^4{2n\choose n}}={\textstyle{17\over 36}}\zeta(4)={\textstyle{17\over 3240}}\pi^4$$ (23)

(Comtet 1974, p. 89) and

$$\sum_{n=1}^\infty {(-1)^{n-1}\over n^3{2n\choose n}}={\textstyle{2\over 5}}\zeta(3),$$ (24)

where $\zeta(z)$ is the Riemann Zeta Function (Le Lionnais 1983, pp. 29, 30, 41, 36, and 35; Guy 1994, p. 257).

As shown by Kummer in 1852, the exact Power of $p$ dividing ${a+b\choose a}$ is equal to

$$\epsilon_0+\epsilon_1+\ldots+\epsilon_t,$$ (25)

where this is the number of carries in performing the addition of $a$ and $b$ written in base $b$ (Graham et al. 1989, Exercise 5.36; Ribenboim 1989; Vardi 1991, p. 68). Kummer's result can also be stated in the form that the exponent of a Prime $p$ dividing ${n\choose m}$ is given by the number of integers $j\geq 0$ for which

$$\mathop{\rm frac}({m/p^j}) > \mathop{\rm frac}({n/p^j}),$$ (26)

where $\mathop{\rm frac}(x)$ denotes the Fractional Part of $x$. This inequality may be reduced to the study of the exponential sums $\sum_n \Lambda(n) e(x/n)$, where $\Lambda(n)$ is the Mangoldt Function. Estimates of these sums are given by Jutila (1974, 1975), but recent improvements have been made by Granville and Ramare (1996).

R. W. Gosper showed that

$$f(n)={n-1\choose {\textstyle{1\over 2}}(n-1)}\equiv (-1)^{(n-1)/2}{\rm\ (mod\ }n)$$ (27)

for all Primes, and conjectured that it holds only for Primes. This was disproved when Skiena (1990) found it also holds for the Composite Number $n=3\times 11\times 179$. Vardi (1991, p. 63) subsequently showed that $n=p^2$ is a solution whenever $p$ is a Wieferich Prime and that if $n=p^k$ with $k>3$ is a solution, then so is $n=p^{k-1}$. This allowed him to show that the only solutions for Composite $n<1.3\times 10^7$ are 5907, $1093^2$, and $3511^2$, where 1093 and 3511 are Wieferich Primes.

Consider the binomial coefficients ${2n-1\choose n}$, the first few of which are 1, 3, 10, 35, 126, ... (Sloane's A001700). The Generating Function is

$${1\over 2}\left[{{1\over\sqrt{1-4x}}-1}\right]=x+3x^2+10x^3+35x^4+\ldots.$$ (28)

These numbers are Squarefree only for $n=2$, 3, 4, 6, 9, 10, 12, 36, ... (Sloane's A046097), with no others less than $n=10,000$. Erdös showed that the binomial coefficient ${n\choose k}$ is never a Power of an Integer for $n\geq 3$ where $k\not=0$, 1, $n-1$, and $n$ (Le Lionnais 1983, p. 48).

The binomial coefficients ${n\choose\left\lfloor{n/2}\right\rfloor }$ are called Central Binomial Coefficients, where $\left\lfloor{x}\right\rfloor$ is the Floor Function, although the subset of coefficients ${2n\choose n}$ is sometimes also given this name. Erdös and Graham (1980, p. 71) conjectured that the Central Binomial Coefficient ${2n\choose n}$ is never Squarefree for $n>4$, and this is sometimes known as the Erdös Squarefree Conjecture. Sárközy's Theorem (Sárközy 1985) provides a partial solution which states that the Binomial Coefficient ${2n\choose n}$ is never Squarefree for all sufficiently large $n\geq n_0$ (Vardi 1991). Granville and Ramare (1996) proved that the only Squarefree values are $n=2$ and 4. Sander (1992) subsequently showed that ${2n\pm d\choose n}$ are also never Squarefree for sufficiently large $n$ as long as $d$ is not ``too big.''

For $p$, $q$, and $r$ distinct Primes, then the above function satisfies

$$f(pqr)f(p)f(q)f(r)\equiv f(pq)f(pr)p(qr)\ \left({{\rm mod\ } {pqr}}\right)$$ (29)

(Vardi 1991, p. 66).

The binomial coefficient ${m\choose n}$ mod 2 can be computed using the XOR operation $n$ XOR $m$, making Pascal's Triangle mod 2 very easy to construct.

The binomial coefficient ``function'' can be defined as

$$C(x,y)\equiv {x!\over y!(x-y)!}$$ (30)

(Fowler 1996), shown above. It has a very complicated Graph for Negative $x$ and $y$ which is difficult to render using standard plotting programs.

See also Ballot Problem, Binomial Distribution, Binomial Theorem, Central Binomial Coefficient, Chu-Vandermonde Identity, Combination, Deficiency, Erdös Squarefree Conjecture, Gaussian Coefficient, Gaussian Polynomial, Kings Problem, Multinomial Coefficient, Permutation, Roman Coefficient, Sárközy's Theorem, Strehl Identity, Wolstenholme's Theorem

References

Abramowitz, M. and Stegun, C. A. (Eds.). ``Binomial Coefficients.'' §24.1.1 in Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, 9th printing. New York: Dover, pp. 10 and 822-823, 1972.

Beeler, M.; Gosper, R. W.; and Schroeppel, R. HAKMEM. Cambridge, MA: MIT Artificial Intelligence Laboratory, Memo AIM-239, Feb. 1972.

Comtet, L. Advanced Combinatorics: The Art of Finite and Infinite Expansions, rev. enl. ed. Amsterdam, Netherlands: Kluwer, 1974.

Conway, J. H. and Guy, R. K. In The Book of Numbers. New York: Springer-Verlag, pp. 66-74, 1996.

Erdös, P.; Graham, R. L.; Nathanson, M. B.; and Jia, X. Old and New Problems and Results in Combinatorial Number Theory. New York: Springer-Verlag, 1998.

Fowler, D. ``The Binomial Coefficient Function.'' Amer. Math. Monthly 103, 1-17, 1996.

Graham, R. L.; Knuth, D. E.; and Patashnik, O. ``Binomial Coefficients.'' Ch. 5 in Concrete Mathematics: A Foundation for Computer Science. Reading, MA: Addison-Wesley, pp. 153-242, 1990.

Granville, A. and Ramare, O. ``Explicit Bounds on Exponential Sums and the Scarcity of Squarefree Binomial Coefficients.'' Mathematika 43, 73-107, 1996.

Guy, R. K. ``Binomial Coefficients,'' ``Largest Divisor of a Binomial Coefficient,'' and ``Series Associated with the $\zeta$-Function.'' §B31, B33, and F17 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 84-85, 87-89, and 257-258, 1994.

Harborth, H. ``Number of Odd Binomial Coefficients.'' Not. Amer. Math. Soc. 23, 4, 1976.

Hilton, P. and Pedersen, J. ``Catalan Numbers, Their Generalization, and Their Uses.'' Math. Intel. 13, 64-75, 1991.

Jutila, M. ``On Numbers with a Large Prime Factor.'' J. Indian Math. Soc. 37, 43-53, 1973.

Jutila, M. ``On Numbers with a Large Prime Factor. II.'' J. Indian Math. Soc. 38, 125-130, 1974.

Le Lionnais, F. Les nombres remarquables. Paris: Hermann, 1983.

Ogilvy, C. S. ``The Binomial Coefficients.'' Amer. Math. Monthly 57, 551-552, 1950.

Petkovsek, M.; Wilf, H. S.; and Zeilberger, D. A=B. Wellesley, MA: A. K. Peters, 1996.

Press, W. H.; Flannery, B. P.; Teukolsky, S. A.; and Vetterling, W. T. ``Gamma Function, Beta Function, Factorials, Binomial Coefficients.'' §6.1 in Numerical Recipes in FORTRAN: The Art of Scientific Computing, 2nd ed. Cambridge, England: Cambridge University Press, pp. 206-209, 1992.

Prudnikov, A. P.; Marichev, O. I.; and Brychkow, Yu. A. Formula 41 in Integrals and Series, Vol. 1: Elementary Functions. Newark, NJ: Gordon & Breach, p. 611, 1986.

Ribenboim, P. The Book of Prime Number Records, 2nd ed. New York: Springer-Verlag, pp. 23-24, 1989.

Riordan, J. ``Inverse Relations and Combinatorial Identities.'' Amer. Math. Monthly 71, 485-498, 1964.

Sander, J. W. ``On Prime Divisors of Binomial Coefficients.'' Bull. London Math. Soc. 24, 140-142, 1992.

Sárközy, A. ``On the Divisors of Binomial Coefficients, I.'' J. Number Th. 20, 70-80, 1985.

Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 262, 1990.

Sloane, N. J. A. Sequences A046097 and A001700/M2848 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.

Spanier, J. and Oldham, K. B. ``The Binomial Coefficients ${\nu\choose m}$.'' Ch. 6 in An Atlas of Functions. Washington, DC: Hemisphere, pp. 43-52, 1987.

Sved, M. ``Counting and Recounting.'' Math. Intel. 5, 21-26, 1983.

Vardi, I. ``Application to Binomial Coefficients,'' ``Binomial Coefficients,'' ``A Class of Solutions,'' ``Computing Binomial Coefficients,'' and ``Binomials Modulo and Integer.'' §2.2, 4.1, 4.2, 4.3, and 4.4 in Computational Recreations in Mathematica. Redwood City, CA: Addison-Wesley, pp. 25-28 and 63-71, 1991.

Wolfram, S. ``Geometry of Binomial Coefficients.'' Amer. Math. Monthly 91, 566-571, 1984.