Binomial Coefficient

In Mathematics , particularly in Combinatorics , the binomial coefficient of the Natural Number ''n'' and the Integer ''k'' is defined to be the natural number
:

{n \choose k} = rac{n \cdot (n-1) \cdots (n-k+1)}{k \cdot (k-1) \cdots 1} = rac{n!}{k!(n-k)!} \quad \mbox{if } n\geq k\geq 0 \qquad \mbox{(1)}

and
:

{n \choose k} = 0 \quad \mbox{if } k<0 \mbox{ or } k>n

where ''m''! denotes the Factorial of ''m''. According to Nicholas J. Higham , the

:

{n \choose k}

notation was introduced by Albert Von Ettinghausen in 1826 , although these numbers have been known centuries before that; see Pascal's Triangle .

An alternative name for the binomial coefficient is choose function; the binomial coefficient of ''n'' and ''k'' is often read as "''n'' choose ''k''". Alternative notations include C(''n'', ''k''), _''n''C_''k'' or

C^{k}_{n}

(C for Combination ). For compactness, from here on we will use the first of these three notations.

The binomial coefficients are the Coefficient s in the expansion of the binomial (''x'' + ''y'')^''n'' (hence the name):

:

(x+y)^n = \sum_{k=0}^{n} C(n, k) x^{n-k} y^k. \qquad (2)

This is generalized by the Binomial Theorem , which allows the exponent ''n'' to be negative or a non-integer.

The importance of the binomial coefficients lies in the fact that C(''n'', ''k'') is the number of ways that ''k'' objects can be chosen from ''n'' objects, regardless of order. See the article on Combination .

EXAMPLE

:

{7 \choose 3} 
= rac{7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{(3 \cdot 2 \cdot 1)(4 \cdot 3 \cdot 2 \cdot 1)} 
= rac{7\cdot 6 \cdot 5}{3\cdot 2\cdot 1} 
= 35.

The practical calculation of the binomial coefficient is conveniently arranged like this: ((((5/1)×6)/2)×7)/3, alternatingly dividing and multiplying with increasing integers. Each division is guaranteed to produce an integer result.

DERIVATION FROM BINOMIAL EXPANSION

For exponent 1, (''x''+''y'')¹ is ''x''+''y''. For exponent 2, (''x''+''y'')² is (''x''+''y'')(''x''+''y''), which forms terms as follows. The first factor supplies either an ''x'' or a ''y''; likewise for the second factor. Thus to form ''x''², the only possibility is to choose ''x'' from both factors; likewise for ''y''². However, the ''xy'' term can be formed by ''x'' from the first and ''y'' from the second factor, or ''y'' from the first and ''x'' from the second factor; thus it acquires a coefficient of 2. Proceeding to exponent 3, (''x''+''y'')³ reduces to (''x''+''y'')²(''x''+''y''), where we already know that (''x''+''y'')²= ''x''²+2''xy''+''y''². Again the extremes, ''x''³ and ''y''³ arise in a unique way. However, the term ''x''²''y'' is either 2''xy'' times ''x'' or ''x''² times ''y'', for a coefficient of 3; likewise ''xy''² arises in two ways, summing the coefficients 1 and 2 to give 3.

This suggests an Induction . Thus for exponent ''n'', each term has Total Degree (sum of exponents) ''n'', with ''n''−''k'' factors of ''x'' and ''k'' factors of ''y''. If ''k'' is 0 or ''n'', the term arises in only one way, and we get the terms ''x''ⁿ and ''y''ⁿ. If ''k'' is neither 0 nor ''n'', then the term arises in two ways, from x^n-k-1y^k × x and from x^n-ky^k-1 × y. For example, ''x''²''y''² is both ''xy''² times ''x'' and ''x''²''y'' times ''y'', thus its coefficient is 3 (the coefficient of ''xy''²) + 3 (the coefficient of ''x''²''y''). This is the origin of Pascal's triangle, discussed below.

Another perspective is that to form ''x''^{''n''−''k''}''y''^''k'' from ''n'' factors of (''x''+''y''), we must choose ''y'' from ''k'' of the factors and ''x'' from the rest. To count the possibilities, consider all ''n''! Permutation s of the factors. Represent each permutation as a shuffled list of the numbers from 1 to ''n''. Select an ''x'' from the first ''n''−''k'' factors listed, and a ''y'' from the remaining ''k'' factors; in this way each permutation contributes to the term ''x''^{''n''−''k''}''y''^''k''. For example, the list ⟨4,1,2,3⟩ selects ''x'' from factors 4 and 1, and selects ''y'' from factors 2 and 3, as one way to form the term ''x''²''y''².

: (''x'' +¹ ''y'')(''x'' +² ''y'')(''x'' +³ ''y'')(''x'' +⁴ ''y'')

But the distinct list ⟨1,4,3,2⟩ makes exactly the same selection; the binomial coefficient formula must remove this redundancy. The ''n''−''k'' factors for ''x'' have (''n''−''k'')! permutations, and the ''k'' factors for ''y'' have ''k''! permutations. Therefore ''n''!/(''n''−''k'')!''k''! is the number of truly distinct ways to form the term ''x''^{''n''−''k''}''y''^''k''.

PASCAL'S TRIANGLE

Pascal's Rule is the important Recurrence Relation
:

\mathrm{C}(n,k) +  \mathrm{C}(n,k+1) = C(n+1,k+1), \qquad (3)

which follows directly from the definition. This recurrence relation can be used to prove by Mathematical Induction that C(''n'', ''k'') is a natural number for all ''n'' and ''k'', a fact that is not immediately obvious from the definition.

It also gives rise to Pascal's Triangle :
row 0 1
row 1 1 1
row 2 1 2 1
row 3 1 3 3 1
row 4 1 4 6 4 1
row 5 1 5 10 10 5 1
row 6 1 6 15 20 15 6 1
row 7 1 7 21 35 35 21 7 1
row 8 1 8 28 56 70 56 28 8 1
Row number ''n'' contains the numbers C(''n'', ''k'') for ''k'' = 0,...,''n''. It is constructed by starting with ones at the outside and then always adding two adjacent numbers and writing the sum directly underneath. This method allows the quick calculation of binomial coefficients without the need for fractions or multiplications. For instance, by looking at row number 5 of the triangle, one can quickly read off that
:(''x'' + ''y'')⁵ = 1''x''⁵ + '''5''' ''x''⁴''y'' + '''10''' ''x''³''y''² + '''10''' ''x''²''y''³ + '''5''' ''x'' ''y''⁴ + 1''y''⁵.
The differences between elements on other diagonals are the elements in the previous diagonal - consequential to the recurrence relation (3) above.

In the 1303 AD treatise ''Precious Mirror of the Four Elements'', Zhu Shijie mentioned the triangle as an ancient method for solving binomial coefficients indicating that the method was known to Chinese mathematicians five centuries before Pascal .

COMBINATORICS AND STATISTICS

Binomial coefficients are of importance in Combinatorics , because they provide ready formulas for certain frequent counting problems:

Every Set with ''n'' elements has $\mathrm{C}(n, k)$ different subsets having ''k'' elements each (these are called ''k''-combinations ).

The number of Strings of length ''n'' containing ''k'' ones and ''n'' − ''k'' zeros is $\mathrm{C}(n, k).$

There are $\mathrm{C}(n+1, k)$ strings consisting of ''k'' ones and ''n'' zeros such that no two ones are adjacent.

The number of sequences consisting of ''n'' Natural Number s whose sum equals ''k'' is $\mathrm{C}(n+k-1, k)$ ; this is also the number of ways to choose ''k'' elements from a set of ''n'' if repetitions are allowed.

The Catalan Number s have an easy formula involving binomial coefficients; they can be used to count various structures, such as Tree s and parenthesized expressions.

The binomial coefficients also occur in the formula for the Binomial Distribution in Statistics and in the formula for a Bézier Curve .

FORMULAS INVOLVING BINOMIAL COEFFICIENTS

One has that
:

\mathrm{C}(n,k)= \mathrm{C}(n, n-k),\qquad\qquad(4)\,

which follows from expansion (2) by using (''x'' + ''y'')^''n'' = (''y'' + ''x'')^''n'', and is reflected in the numerical "symmetry" of Pascal's Triangle .

Another formula is
:

\sum_{k=0}^{n} \mathrm{C}(n,k) = 2^n; \qquad (5)

it is obtained from expansion (2) using ''x'' = ''y'' = 1. This is equivalent to saying that the elements in one row of Pascal's triangle always add up to two raised to an integer power.

The formula
:

\sum_{k=1}^{n} k \mathrm{C}(n,k) = n 2^{n-1} \qquad (6)

follows from expansion (2), after Differentiating and substituting ''x'' = ''y'' = 1.

Vandermonde's Identity
:

\sum_{j} \mathrm{C}(m,j) \mathrm{C}(n-m,k-j) = \mathrm{C}(n,k) \qquad (7a)

is found by expanding (1+''x'')^''m'' (1+''x'')^''n-m'' = (1+''x'')^''n'' with (2). As C(''n'', ''k'') is zero if ''k'' > ''n'', the sum is finite for integer n and m. Equation (7a) generalizes equation (3). It holds for arbitrary, complex-valued

m

and

n

, the Chu-Vandermonde Identity .

A related formula is

:

\sum_{m} \mathrm{C}(m,j) \mathrm{C}(n-m,k-j) = \mathrm{C}(n+1,k+1). \qquad (7b)

While equation (7a) is true for all values of ''m'', equation (7b) is true for all values of ''j''.

From expansion (7a) using ''n''=2''m'', ''k'' = ''n'', and (4), one finds

:

\sum_{j=0}^{m} \mathrm{C}(m,j)^2 = \mathrm{C}(2m,m). \qquad (8)

Denote by ''F''(''n'' + 1) the Fibonacci Number s. We obtain a formula about the diagonals of Pascal's triangle
:

\sum_{k=0}^{n} \mathrm{C}(n-k,k) = \mathrm{F}(n+1). \qquad (9)

This can be proved by Induction using (3).

Also using (3) and induction, one can show that

:

\sum_{j=k}^{n} \mathrm{C}(j,k) = \mathrm{C}(n+1,k+1). \qquad (10)

DIVISORS OF BINOMIAL COEFFICIENTS

The of ''k''/''p''^''j'' is bigger than the fractional part of ''n''/''p''^''j''. In particular, C(''n'', ''k'') is always divisible by ''n''/ Gcd (''n'',''k'').

A somewhat surprising result by David Singmaster (1974) is that any integer divides almost all binomial coefficients. More precisely, fix an integer ''d'' and let ''f''(''N'') denote the number of binomial coefficients C(''n'', ''k'') with ''n'' < ''N'' such that ''d'' divides C(''n'', ''k''). Then
:

\lim_{N	o\infty} rac{f(N)}{N(N+1)/2} = 1.

Since the number of binomial coefficients C(''n'', ''k'') with ''n'' < ''N'' is ''N''(''N''+1) / 2, this implies that the density of binomial coefficients divisible by ''d'' goes to 1.

BOUNDS FOR BINOMIAL COEFFICIENTS

The following bounds for C(''n'', ''k'') hold:

$\mathrm{C}(n, k) \le rac{n^k}{k!}$

$\mathrm{C}(n, k) \le \left(rac{n\cdot e}{k}
ight)^k$

$\mathrm{C}(n, k) \ge \left(rac{n}{k}
ight)^k.$

GENERALIZATION TO MULTINOMIALS

While the binomial coefficients represent the coefficients of (''x''+''y'')^''n'', the multinomial coefficients represent the coefficients of
:(''x''₁ + ''x''₂ + ... + ''x''_''k'')^''n''.
See Multinomial Theorem . The case ''k'' = 2 gives binomial coefficients.

GENERALIZATION TO REAL AND COMPLEX ARGUMENT

The binomial coefficient

{z\choose k}

can be defined for any Complex Number ''z'' and any Natural Number ''k'' as follows:
:

{z\choose k} = \prod_{n=1}^{k}{z-k+n\over n}= rac{z(z-1)(z-2)\cdots (z-k+1)}{k!}. \qquad (11)

This generalization is known as the generalized binomial coefficient and is used in the formulation of the Binomial Theorem and satisfies properties (3) and (7).

For fixed ''k'', the expression

f(z)={z\choose k}

is a Polynomial in ''z'' of degree ''k'' with Rational coefficients.

''f''(''z'') is the unique polynomial of degree ''k'' satisfying

f

Any polynomial ''p''(''z'') of degree ''d'' can be written in the form

:

p(z) = \sum_{k=0}^{d} a_k {z\choose k}.

This is important in the theory of Difference Equation s and Finite Difference s, and can be seen as a discrete analog of Taylor's Theorem . It is closely related to Newton's Polynomial . Alternating sums of this form may be expressed as the Nörlund-Rice Integral .

NEWTON'S BINOMIAL SERIES

Newton's binomial series, named after Sir Isaac Newton , is one of the simplest Newton Series :

:

(1+z)^{\alpha} = \sum_{n=0}^{\infty}{\alpha\choose n}z^n = 1+{\alpha\choose1}z+{\alpha\choose 2}z^2+\cdots.

The radius of convergence of this series is 1. An alternative expression is

:

rac{1}{(1-z)^{\alpha+1}} = \sum_{n=0}^{\infty}{\alpha+n\choose \alpha}z^n

where the identity

:

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

is applied.

The formula for the binomial series was etched onto Newton's gravestone in Westminster Abbey in 1727 .

GENERALIZATION TO ''Q''-SERIES

The binomial coefficient has a Q-analog generalization known as the Gaussian Binomial .

SEE ALSO

Central Binomial Coefficient

Binomial Transform

Table Of Newtonian Series

List Of Factorial And Binomial Topics

Multiplicities Of Entries In Pascal's Triangle

REFERENCES

''This article incorporates material from the following PlanetMath articles, which are licensed under the : Binomial Coefficient , Bounds for binomial coefficients , Proof that C(n,k) is an integer , Generalized binomial coefficients .''

Donald Knuth . ''The Art of Computer Programming'', Volume 1: ''Fundamental Algorithms'', Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4. Section 1.2.6: Binomial Coefficients, pp.52–74.

David Singmaster, Notes on binomial coefficients. III. Any integer divides almost all binomial coefficients. ''J. London Math. Soc. (2),'' volume 8 (1974), 555–560.

	CATEGORIES ABOUT BINOMIAL COEFFICIENT

	combinatorics

	factorial and binomial topics

	integer sequences

	APPAREL
	BABY
	BEAUTY
	BOOKS
	CAR TOYS
	CELL PHONES
	DVD'S
	ELECTRONICS
	GOURMET FOOD
	GROCERIES
	HEALTH & PERSONAL
	HOME & GARDEN
	JEWELRY
	MUSIC
	MUSIC INSTRUMENTS
	OFFICE PRODUCTS
	SOFTWARE
	SPORTING GOODS
	TOOLS & HARDWARE
	TOYS
	VIDEO GAMES
	SHOPPING HOME

	MORE SHOPPING...

Information About

Binomial Coefficient