Binomial Coefficient

Binomial Coefficient

The binomial coefficient

is the number of ways of picking unordered outcomes from possibilities, also known as a combinati

or combinatorial number. The symbols "

and

are used to denote a binomial coefficient, and are sometimes read as " choos

therefore gives the number of k-subsets possible out of a set of distinct items. For example, The 2-subsets of

six pairs

,

,

,

,

, and

, so

are

.

The value of the binomial coefficient is given explicitly by

where denotes a factorial. Writing the factorial as a gamma function allows the binomial coefficient to be generalize to non-integer arguments, including complex and . The binomial coefficient is implemented in Mathematica as Binomial[n, k]. The binomial coefficients form the rows of Pascal's triangle, and the number of lattice paths from the origin the binomial coefficient

to a point

)i

(Hilton and Pedersen 1991).

Plotting the binomial coefficient

in the -plane (Fowler 1996) gives the beautiful plot shown above, which has a very complicated graph for negative therefore difficult to render using standard plotting programs.

and

and

For a positive integer , the binomial theorem gives

The finite difference analog of this identity is known as the Chu-Vandermonde identity. A similar formula holds for negative intege

There are a number of elegant binomial sums. The binomial coefficients satisfy the identities

As shown by Kummer in 1852, if is the largest power of a prime that divides , where and are nonnegative integers then is the number of carries that occur when is added to in base (Graham et al. 1989, Exercise 5.36, p. 245; Ribenboim 19 Vardi 1991, p. 68). Kummer's result can also be stated in the form that the exponent of a prime of integers for which

dividing

is given by the num

(

where denotes the fractional part of . This inequality may be reduced to the study of the exponential sums where is the Mangoldt function. Estimates of these sums are given by Jutila (1974, 1975), but recent improvements have be made by Granville and Ramare (1996). R. W. Gosper showed that

( 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 and that if

with are 5907,

. Vardi (1991, p. 63) subsequently showed that is a solution, then so is , and

Consider the binomial coefficients

is a solution whenever

is a Wieferich p

. This allowed him to show that the only solutions for composite

, where 1093 and 3511 are Wieferich primes.

, the first few of which are 1, 3, 10, 35, 126, ... (Sloane's A001700). The

generating function is

(

These numbers are squarefree only for , 3, 4, 6, 9, 10, 12, 36, ... (Sloane's A046097), with no others known. It turns out th is divisible by 4 unless belongs to a 2-automatic set , which happens to be the set of numbers whose binary representatio contain at most two 1s: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 16, 17, 18, ... (Sloane's A048645). Similarly, is divisible by 9 unless belongs to a 3-automatic set , consisting of numbers for which the representation of in ternary consists entirely of 0s and 2 (except possibly for a pair of adjacent 1s; D. Wilson, A. Karttunen). The initial elements of are 1, 2, 3, 4, 6, 7, 9, 10, 11, 12, 13 18, 19, 21, 22, 27, ... (Sloane's A051382). If is squarefree, then must belong to . It is very probable that is fini but no proof is known. Now, squares larger than 4 and 9 might also divide , but by eliminating these two alone, the only poss

for are 1, 2, 3, 4, 6, 9, 10, 12, 18, 33, 34, 36, 40, 64, 66, 192, 256, 264, 272, 513, 514, 516, 576 768, 1026, 1056, 230 16392, 65664, 81920, 532480, and 545259520. All of these but the last have been checked (D. Wilson), establishing that there a no other such that is squarefree for .

Erdos showed that the binomial coefficient

with

is a power of an integer for the single case

(Le Lionna

1983, p. 48). Binomial coefficients are squares when is a triangular number, which occur for , 6, 35, 204, 11 6930, ... (Sloane's A001109). These values of have the corresponding values , 9, 50, 289, 1682, 9801, ... (Sloane's A0524

The binomial coefficients coefficients coefficient

are called central binomial coefficients, where

is the floor function, although the subset of

is sometimes also given this name. Erdos and Graham (1980, p. 71) conjectured that the central binomial is never squarefree for

, and this is sometimes known as the Erdos squarefree conjecture. Sárkozy's theorem

(Sárkozy 1985) provides a partial solution which states that the binomial coefficient is never squarefree for all sufficiently la (Vardi 1991). Granville and Ramare (1996) proved that the only squarefree values are and 4. Sander (1992) subseque showed that For

are also never squarefree for sufficiently large as long as is not "too big."

, , and distinct primes, then the function (◇) satisfies

( (Vardi 1991, p. 66).

Most binomial coefficients with have a prime factor , and Lacampagne et al. (1993) conjecture that this inequa is true for all , or more strongly that any such binomial coefficient has least prime factor or with the exceptions

,

The binomial coefficient

,

,

for which

, 19, 23, 29 (Guy 1994, p. 84).

(mod 2) can be computed using the XOR operation XOR

, making Pascal's triangle mod 2 very eas

construct. Sondow (2005) and Sondow and Zudilin (2006) noted the inequality

( for

a positive integer and

a real number.