Binomial Coefficient - Top Future Point

In mathematics , binomial coefficients are positive integers that have the form of coefficients in the binomial theorem . Generally, the binomial coefficient is indexed by a pair of integers n k 0 and is written as the coefficient of x k term in the binomial power of the polynomial expansion (1 + x )ⁿ , and is given by the formula

{\binom {n}{k}}.

{\binom {n}{k}}={\frac {n!}{k!(nk)!}}.

For example, the fourth power of 1 + x is

{\begin{aligned}(1+x)^{4}&={\binom {4}{0}}x^{0}+{\binom {4}{1}}x^{1 }+{\binom {4}{2}}x^{2}+{\binom {4}{3}}x^{3}+{\binom {4}{4}}x^{4}\ \&=1+4x+6x^{2}+4x^{3}+x^{4},\end{aligned}}

and the binomial coefficient x ² is the coefficient of the term.

{\binom {4}{2}}={\frac {4!}{2!2!}}=6

Arranging numbers in consecutive rows gives a triangular array called Pascal’s triangle , satisfying the recurrence relation

{\displaystyle {\binom {n}{0}},{\binom {n}{1}},\ldots ,{\binom {n}{n}}}n=0,1,2,\ldots

{\binom {n}{k}}={\binom {n-1}{k}}+{\binom {n-1}{k-1}}.

Binomial coefficients are found in many areas of mathematics, and especially in combination . The symbol is usually read as ” n select k ” because there are n ways to select an (unordered) subset of k elements from a fixed set of elements. For example, there are

{\binom {n}{k}}{\binom {n}{k}}{\displaystyle {\binom {4}{2}}=6}

ways of selecting 2 elements from ie and

\{1,2,3,4\},}{\displaystyle \{1,2\}{\text{, }}\{1,3\}{\text{, }}\{1,4\}{\text{, }}\{2,3 \}{{, }}\{2,4\}{{,}}}{\displaystyle \{3,4\}.

The binomial coefficients can be generalized to any complex number z and the integer k 0 , and many of their properties remain in this more general form.

{\binom {z} {k}}

History and notation

Andreas von Ettingshausen introduced the notation in 1826, [1] although the numbers were known centuries earlier ( see Pascal’s triangle ). The earliest known detailed discussion of binomial coefficients is in a tenth-century commentary on the Chandashastra of Pingala , an ancient Sanskrit text, by Halyudh . In about 1150, the Indian mathematician Bhaskaracharya explained binomial coefficients in his book Lilavati .

{\binom {n}{k}}

Alternative notations include

C(n, k), ~_nC_k, ~^nC_k, ~C^k_n, ~C^n_k, ~and~ Cn,k

all of which mean combinations or substitutes of C . Many calculators use a variant of the C notation because they can display it on a single-line display. In this form the binomial coefficients are compared with k – permutations of n., which are written as P ( n , k ) , etc.

Definitions and Interpretation

KNo	0	1	2	3	4	⋯
0	1	0	0	0	0	⋯
1	1	1	0	0	0	⋯
2	1	2	1	0	0	⋯
3	1	3	3	1	0	⋯
4	1	4	6	4	1	⋯
⋮	⋮	⋮	⋮	⋮	⋮	⋱

The first few binomial coefficients on the left-aligned Pascal’s triangle

For the natural numbers (taken to include 0) n and k , the binomial coefficient (1 + X )ⁿ in the expansion of n can be defined as the coefficient of the monomial X^k . The binomial formula has the same coefficient even if ( in k n )

{\binom {n}{k}}

(x+y)^{n}=\sum _{k=0}^{n}{\binom {n}{k}}x^{nk}y^{k}

( valid for any element x , y of the commutative ring ), which explains the name “binomial coefficient”.

Another occurrence of this number is in combinatorics, where it gives the number of ways, regardless of order, that k objects can be chosen from n objects; More formally, the number of k -element subsets (or k – combinations ) of n elements of a set. This number can be seen as equivalent to the one in the first definition, to be calculated independently of any of the formulas below: If each of the n factors of the power (1 + X )ⁿ has some temporal form . Labels the word from X with an index i (1 to ngoing up to ), then each subset of k indices gives a contribution X^k , and the coefficient of that monomial in the result will be the number of such subsets. It specifically shows that there is a natural number for any natural number n and k . There are many other combined interpretations of binomial coefficients (counting problems for which the binomial coefficient is answered by the expression), for example the number of words made up of n bits (the digit 0 or 1) whose sum is k , is given by , Whereas the number of ways of writing where each one i is a non-negative integer is given by

{\tbinom {n}{k}} {\tbinom {n}{k}}k=a_{1}+a_{2}+\cdots +a_{n}{\tbinom {n+k-1}{n-1}}

Most of these interpretations are easily equated to computing k -combinations.

Calculating the Value of Binomial Coefficients

Several methods exist for computing the value of value without actually expanding to a binomial power or computing k -combinations.

{\binom {n}{k}}

Recursive formula

One method uses a recursive , purely additive formula

{\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}}}~~such~~ that ~~for~~ all~~ integersn~~,k{\displaystyle 1 \leq k \leq n-1,

with starting/limit values

{\binom {n}{0}}={\binom {n}{n}}=1}~~for~~ all~~ integers~~{\displaystyle n\geq 0.

Considering the sets {1, 2, 3, …, n } and counting separately, this formula follows (a) a k -element group containing a particular set element, such as ” i “, in each group. (since ” i “) ” has already been chosen to fill a position in each group, we have to choose only k – 1 from the remaining n – 1) and (b) pick all k -groups which do not contain ” i “; it counts all possible k -combinations of n elements . This is X ^k in (1 + X ) ^n −1 (1 + X) also follows from tracing the contribution. Since (1 + X ) ⁿ has zero X ^n +1 or X ⁻¹ , one can extend the definition beyond the above limits to include

{\binom {n}{k}}=0

When either k > n or k < 0. This recursive formula then allows the construction of Pascal’s triangle , surrounded by white spaces where there will be zero, or trivial coefficients.

Multiplier formula

A more efficient method for computing the individual binomial coefficients is given by the formula

{\binom {n}{k}}={\frac {n^{\underline {k}}}{k!}}={\frac {n(n-1)(n-2)\cdots (n-(k-1))}{k(k-1)(k-2)\cdots 1}}=\prod _{i=1}^{k}{\frac {n+1-i}{i}},

where the numerator of the first fraction is expressed as a falling factorial power . This formula is easiest to understand for the combined interpretation of binomial coefficients. Returns the number of ways to select a sequence of k specific items , while maintaining the order of selection, from a set of n items. The denominator counts the number of distinct sequences that define the same k -combination when the order is disregarded. n^k

Because of the symmetry of the binomial coefficients with respect to k and n – k , the calculation can be optimized by setting the upper bound of the product above to the smallest of k and n – k .

Factorial Formula

Finally, although computationally inappropriate, there is the compact form, often used in proofs and derivations, which makes repeated use of the familiar factorial function:

{\binom {n}{k}}={\frac {n!}{k!\,(n-k)!}}\quad {\text{for }}\ 0\leq k\leq n,

where n ! Shows the factorial of n . This formula follows from the above multiplication formula by multiplying the numerator and denominator by ( n – k ) ! , As a result, it includes many factors common to the numerator and denominator. This is less practical for explicit calculations (in the case that k is small and n is large) unless the common factors are first canceled out (especially because factorial values grow very rapidly). The formula exhibits an isomerism that is less obvious than the multiplicative formula (although it is from the definitions).

{\binom {n}{k}}={\binom {n}{n-k}}\quad {\text{for }}\ 0\leq k\leq n,

Which leads to a more efficient multiplicative computational routine. Using Falling Factorial Notation,

{\binom {n}{k}}={\begin{cases}n^{\underline {k}}/k!&{\text{if }}\ k\leq {\frac {n}{2}}\\n^{\underline {n-k}}/(n-k)!&{\text{if }}\ k>{\frac {n}{2}}\end{cases}}.

Generalization and Relation for Binomial Series

The multiplicative formula allows the definition of the binomial coefficient to be expanded [3] by replacing n by an arbitrary number α (negative, real, complex) or even an element of any commutative ring in which all positive integers are invertible. Contains:

{\binom {\alpha }{k}}={\frac {\alpha ^{\underline {k}}}{k!}}={\frac {\alpha (\alpha -1)(\alpha -2)\cdots (\alpha -k+1)}{k(k-1)(k-2)\cdots 1}}\quad {\text{for }}k\in \mathbb {N} {\text{ and arbitrary }}\alpha .

With this definition one has a generalization of the binomial formula (with one variable set to 1), which still justifies calling the binomial coefficient:

{\binom {\alpha }{k}}

(1+X)^{\alpha }=\sum _{k=0}^{\infty }{\alpha \choose k}X^{k}.

This formula , is valid for all complex numbers α and X with X | <1. It can also be interpreted as the identity of a formal power series in X , where it can actually serve as a definition of arbitrary powers of power series with coefficients equal to 1; The point is that all identities with this definition assume that one expects the exponent , in particular

(1+X)^{\alpha }(1+X)^{\beta }=(1+X)^{\alpha +\beta }\quad {\text{and}}\quad ((1+X)^{\alpha })^{\beta }=(1+X)^{\alpha \beta }.

If α is a negative integer n , then all terms with k > n are zero, and the infinite series becomes a finite sum, recovering the binomial formula. However, for other values of α, including negative integers and rational numbers , the series is actually infinite.

Pascal’s Triangle

Pascal’s law is the important recursive relation

1000th row of Pascal’s triangle, arranged vertically, with a gray-scale representation of the decimal digits of the coefficients, right-aligned. The left boundary of the image roughly corresponds to the graph of the logarithm of the binomial coefficients, and shows that they form a log-concave sequence .

{n \choose k}+{n \choose k+1}={n+1 \choose k+1},

which can be used by mathematical induction to prove that for all integers n 0 and all integers k is a natural number, a fact that is not immediately apparent from formula (1) . On the left and right of the Pascal triangle, the entries (shown as blanks) are all zeros.

{\binom {n}{k}}

Pascal’s law also gives rise to Pascal’s triangle :

0:									1
1:								1		1
2:							1		2		1
3:						1		3		3		1
4:					1		4		6		4		1
5:				1		5		10		10		5		1
6:			1		6		15		20		15		6		1
7:		1		7		21		35		35		21		7		1
8:	1		8		28		56		70		56		28		8		1

The row number n contains the numbers for k = 0, …, n . It is constructed by first placing the 1s in the outermost position, and then filling each inner position with the sum of the two numbers directly above. This method allows quick calculation of binomial coefficients without the need for fractions or multiplications. For example, looking at row number 5 of the triangle, one can immediately read that

{\binom {n}{k}}

(x+y)^{5}={\underline {1}}x^{5}+{\underline {5}}x^{4}y+{\underline {10}}x^{3}y^{2}+{\underline {10}}x^{2}y^{3}+{\underline {5}}xy^{4}+{\underline {1}}y^{5}.

Combination and Statistics

Binomial coefficients are important in combinatorics , as they provide ready-made formulas for certain computational problems:

There are ways to select k elements from a set of n elements. See combination.

{\binom {n}{k}}

There are ways to choose k elements from a set of n elements if repetition is allowed. See Multiset.

{\binom {n+k-1}{k}}

There strings containing k ones and n zeros.

{\binom {n+k}{k}}

There are strings containing k ones and n zeros in such a way that no two are adjacent.

{\binom {n+1}{k}}

Catalan numbers are

{\frac {1}{n+1}}{\binom {2n}{n}}.

The data in the binomial distribution is

{\binom {n}{k}}p^{k}(1-p)^{nk}\!.

Binomial coefficient as a polynomial

For any negative integer k , the expression can be simplified and defined as a polynomial divisible by k !

{\binom {t}{k}}

{\binom {t}{k}}={\frac {(t)_{k}}{k!}}={\frac {(t)_{k}}{(k)_{k}}}={\frac {t(t-1)(t-2)\cdots (t-k+1)}{k(k-1)(k-2)\cdots 2\cdot 1}};

This gives a polynomial in t with rational coefficients .

As such, it can be evaluated on any real or complex number t to define the binomial coefficient with such first arguments. These “generalized binomial coefficients” appear in Newton’s generalized binomial theorem.

For each k , the polynomial For unique degree k can be described as the polynomial p ( t ) satisfying p (0) = p (1) = = p ( k – 1) = 0 and p ( k ) = 1 Is .

{\binom {t}{k}}

Its coefficients can be expressed as Stirling numbers of the first kind:

{\binom {t}{k}}=\sum _{i=0}^{k}s(k,i){\frac {t^{i}}{k!}}.

The derivative can be calculated by logarithmic differentiation:

{\binom {t}{k}}

{\frac {\mathrm {d} }{\mathrm {d} t}}{\binom {t}{k}}={\binom {t}{k}}\sum _{i=0}^{k-1}{\frac {1}{t-i}}.

This can cause problems when evaluated on integers from to , but using the identities below we can calculate the derivative as follows: 0t – 1

{\frac {\mathrm {d} }{\mathrm {d} t}}{\binom {t}{k}}=\sum _{i=0}^{k-1}{\frac {(-1)^{k-i-1}}{k-i}}{\binom {t}{i}}.

Binomial Coefficient as a Base of the Space of Polynomials

In any field of characteristic 0 (that is, any field containing rational numbers), the maximum d of every polynomial p ( t ) of power is uniquely expressed as a linear combination.

{\sum _{k=0}^{d}a_{k}{\binom {t}{k}}}

Binomial coefficient. The coefficient a _k , is the k th difference of the sequence p (0), p (1), …, p ( k ). clearly,

a_{k}=\sum _{i=0}^{k}(-1)^{k-i}{\binom {k}{i}}p(i).

integer-valued polynomial

Every polynomial has an integer value: it has an integer value on all integer inputs . (One way to prove this is by induction on k using Pascal’s identity .) Therefore, any integer linear combination of binomial coefficient polynomials is also integer-valued. In contrast, ( 4 ) shows that any integer-valued polynomial is an integer linear combination of these binomial coefficient polynomials. More generally, for any subring R of a characteristic 0 field K , a polynomial in K [ t ] assumes values in R over all integers if and only if this binomial coefficient is an R- linear combination of polynomials.

{\binom {t}{k}}t

Example

The integer-valued polynomial 3T ( 3T + 1)/2 can be rewritten as

9{\binom {t}{2}}+6{\binom {t}{1}}+0{\binom {t}{0}}.

Identities with Binomial Coefficients

The factorial formula provides a facility to relate the adjoining binomial coefficients. For example, if k is a positive integer and n is arbitrary, then

{\binom {n}{k}}={\frac {n}{k}}{\binom {n-1}{k-1}}

And, with a little more work,

{\binom {n-1}{k}}-{\binom {n-1}{k-1}}={\frac {n-2k}{n}}{\binom {n}{k}}.

In addition, the following may be useful:

{\binom {n}{h}}{\binom {n-h}{k}}={\binom {n}{k}}{\binom {n-k}{h}}.

For a constant n , we have the following iteration:

{\binom {n}{k}}={\frac {n+1-k}{k}}{\binom {n}{k-1}}.

Sum of Binomial Coefficients

Formula

\sum _{k=0}^{n}{\binom {n}{k}}=2^{n}

Say that the elements of the nth row of Pascal’s triangle always add up to the nth power of 2 . This is derived from the binomial theorem ( * ) by setting x = 1 and y = 1. The formula also has a natural compound interpretation: the sum of the number of subsets on the left {1, …, n } of size k = 0, 1, …, n , giving the total number of subsets. (That is, the left-hand side computes the power set of {1, …, n }.) However, these subsets can also be generated by sequentially selecting or omitting each element 1, …, n . ; allow a total of n independent binary options (bit strings) 2ⁿOption. The left and right sides are two ways of enumerating the same collection of subsets, so they are equal.

Formula

\sum _{k=0}^{n}k{\binom {n}{k}}=n2^{n-1}

And

\sum _{k=0}^{n}k^{2}{\binom {n}{k}}=(n+n^{2})2^{n-2}

Follow the binomial theorem to differentiate with respect to x (twice for the latter) and then substitute x = y = 1 .

The Chu–Vandermonde identity, which holds for any complex-values a and n and any non-negative integer k , is

\sum _{j=0}^{k}{\binom {m}{j}}{\binom {n-m}{k-j}}={\binom {n}{k}}

and can be found by examining the coefficients of ( 1 + x ) ^m (1 + x ) ^n – m = (1 + x ) ⁿ using the equation ( 2 ). When m = 1 , Equation ( 7 ) is reduced to Equation ( 3 ). Using the special case n = 2 m , k = m , ( 1 ), the expansion ( 7 ) becomes (as seen in Pascal’s triangle to the right)

\sum _{j=0}^{m}{\binom {m}{j}}^{2}={\binom {2m}{m}},

where the term on the right is a central binomial coefficient.

The second form of the Chu –Vandermonde identity, applicable for any integers, j , k , and n satisfying 0 j k n , is

\sum _{m=0}^{n}{\binom {m}{j}}{\binom {n-m}{k-j}}={\binom {n+1}{k+1}}.

The proof is similar, but uses the binomial series expansion ( 2 ) with negative integer exponentiation. When j = k , Equation ( 9 ) gives the identity of the hockey-stick

\sum _{m=k}^{n}{\binom {m}{k}}={\binom {n+1}{k+1}}

and his relatives

\sum _{r=0}^{m}{\binom {n+r}{r}}={\binom {n+m+1}{m}}.

Let F ( n ) denote the n -th Fibonacci number. Then

\sum _{k=0}^{\lfloor n/2\rfloor }{\binom {n-k}{k}}=F(n+1).

This can be proved by induction using ( 3 ) or by Zeckendorff’s representation. A combination proof is given below.

Multiples of Sums

For the integers s and t such that the series polynomial gives the following identity for the sum of the binomial coefficients:

0 \leq t<~s,

{\binom {n}{t}}+{\binom {n}{t+s}}+{\binom {n}{t+2s}}+\ldots ={\frac {1}{s}}\sum _{j=0}^{s-1}\left(2\cos {\frac {\pi j}{s}}\right)^{n}\cos {\frac {\pi (n-2t)j}{s}}.

For short messages , these series have especially good forms; For example,

{\binom {n}{0}}+{\binom {n}{3}}+{\binom {n}{6}}+\cdots ={\frac {1}{3}}\left(2^{n}+2\cos {\frac {n\pi }{3}}\right)

{\binom {n}{1}}+{\binom {n}{4}}+{\binom {n}{7}}+\cdots ={\frac {1}{3}}\left(2^{n}+2\cos {\frac {(n-2)\pi }{3}}\right)

{\binom {n}{2}}+{\binom {n}{5}}+{\binom {n}{8}}+\cdots ={\frac {1}{3}}\left(2^{n}+2\cos {\frac {(n-4)\pi }{3}}\right)

{\binom {n}{0}}+{\binom {n}{4}}+{\binom {n}{8}}+\cdots ={\frac {1}{2}}\left(2^{n-1}+2^{\frac {n}{2}}\cos {\frac {n\pi }{4}}\right)

{\binom {n}{1}}+{\binom {n}{5}}+{\binom {n}{9}}+\cdots ={\frac {1}{2}}\left(2^{n-1}+2^{\frac {n}{2}}\sin {\frac {n\pi }{4}}\right)

{\binom {n}{2}}+{\binom {n}{6}}+{\binom {n}{10}}+\cdots ={\frac {1}{2}}\left(2^{n-1}-2^{\frac {n}{2}}\cos {\frac {n\pi }{4}}\right)

{\binom {n}{3}}+{\binom {n}{7}}+{\binom {n}{11}}+\cdots ={\frac {1}{2}}\left(2^{n-1}-2^{\frac {n}{2}}\sin {\frac {n\pi }{4}}\right)

Partial amount

Although there is no closed formula for fractional sums.

\sum _{j=0}^{k}{\binom {n}{j}}

Of the binomial coefficients, [7] one can again use ( 3 ) and induction to show that for k = 0, …, n – 1 ,

\sum _{j=0}^{k}(-1)^{j}{\binom {n}{j}}=(-1)^{k}{\binom {n-1}{k}},

with special case

\sum _{j=0}^{n}(-1)^{j}{\binom {n}{j}}=0

for n > 0. This latter result is also a special case of the result of the principle of finite difference that for any polynomial P ( x ) of degree less than n ,

\sum _{j=0}^{n}(-1)^{j}{\binom {n}{j}}P(j)=0.

Differentiating ( 2 ) k times and setting x = −1 gives this for k , when 0 k < n , and the general case follows taking linear combinations of these.

P(x)=x(x-1)\cdots (x-k+1)

When P ( x ) is of degree less than or equal to n ,

\sum _{j=0}^{n}(-1)^{j}{\binom {n}{j}}P(n-j)=n!a_{n}

where is P ( x ) is the coefficient of degree n . a_n

More generally for ( 10 ),

\sum _{j=0}^{n}(-1)^{j}{\binom {n}{j}}P(m+(n-j)d)=d^{n}n!a_{n}

where m and d are complex numbers. This occurs immediately after putting the polynomial in ( 10 ) instead of , and noting that the degree is still less than or equal to n , and that the coefficient of its degree n is d ⁿ a _n

{\displaystyle Q(x):=P(m+dx)}P(x)Q(x)

The series converges to k 2 . This formula is used in the analysis of the German tank problem. This follows from which is proved by induction on M.

{\frac {k-1}{k}}\sum _{j=0}^{\infty }{\frac {1}{\binom {j+x}{k}}}={\frac {1}{\binom {x-1}{k-1}}}}{\frac {k-1}{k}}\sum _{j=0}^{M}{\frac {1}{\binom {j+x}{k}}}={\frac {1}{\binom {x-1}{k-1}}}-{\frac {1}{\binom {M+x}{k-1}}

Identity with Cohesive Evidence

Many identities with binomial coefficients can be proved by combinatorial means. For example, for non-negative integers , the identity

\sum _{k=q}^{n}{\binom {n}{k}}{\binom {k}{q}}=2^{n-q}{\binom {n}{q}}

(which decreases to ( 6 ) when q = 1) can be given a double counting proof as follows. Counts the number of ways to select a subset of [ n ] = {1, 2, …, n } with at least q elements on the left and mark the q elements in the selected array. the right side counts the same thing, because there are

{\binom {n}{q}}

To mark q ways to choose a set of elements, and to choose which of the remaining elements of [ n ] belong to the subset.

2^{n-q}

In Pascal’s Identity

{n \choose k}={n-1 \choose k-1}+{n-1 \choose k},

Both sides count the number of k -element subsets of [ n ] : the two terms on the right group them into elements that contain element n and those that do not.

There is also a combative proof of identity ( 8 ). reads the identity

\sum _{k=0}^{n}{\binom {n}{k}}^{2}={\binom {2n}{n}}.

Suppose you have empty squares arranged in a row and you want to mark (select) n of them. There are ways to do this. On the other hand, you first n and . You can choose your n squares by choosing k squares from

2n{\binom {2n}{n}}n-k

square off the remaining n squares; Any k from 0 to n will work. it gives

\sum _{k=0}^{n}{\binom {n}{k}}{\binom {n}{n-k}}={\binom {2n}{n}}.

Apply now ( 1 ) to get the result.

If one indexes the sequence of Fibonacci numbers from F ( i ) in such a way that F (0) = F (1) = 1 , then the identity

\sum _{k=0}^{\left\lfloor {\frac {n}{2}}\right\rfloor }{\binom {n-k}{k}}=F(n)

The following is a combination proof. ^[10] One can show by induction that f ( n ) counts the number of ways that an n × 1 strip of squares can be covered by 2 × 1 and 1 × 1 tiles. On the other hand, if such a tiling uses exactly k of 2 × 1 tiles, then it uses n – 2 k of 1 × 1 tiles, and then uses n – k tiles Total. There are ways of arranging these tiles, and hence k

{\binom {nk}{k}}

Adding this coefficient to all possible values gives the identity.

Coefficient Row Sum

k – number of combinations for all k ,

\sum _ {0 \leq {k} \leq {n}} {\binom {n} {k}} = 2 ^ {n}

is the sum of the nth row (counting from 0) of the binomial coefficients . These combinations are numbered by the 1 digit of the set of base 2 numbers, counting from 0 to 0 , where the position of each digit is an item from the set of n .2ⁿ – 1

Dixon’s identity

\sum _{k=-a}^{a}(-1)^{k}{2a \choose k+a}^{3}={\frac {(3a)!}{(a!)^{3}}}

or, more commonly,

\sum _{k=-a}^{a}(-1)^{k}{a+b \choose a+k}{b+c \choose b+k}{c+a \choose c+k}={\frac {(a+b+c)!}{a!\,b!\,c!}}\,,

where a , b , and c are non-negative integers.

Continuous Identification

The values of some trigonometric integrals can be expressed as binomial coefficients: for any

m,n\in \mathbb {N} ,

\int _ {- \pi} ^ {\pi} \cos ((2m-n) x) \cos ^ {n} (x) dx = {\frac {\pi} {2 ^ {n -1}}} {\binom {n} {m}}

\int _{-\pi }^{\pi }\sin((2m-n)x)\sin ^{n}(x)\ dx={\begin{cases}(-1)^{m+(n+1)/2}{\frac {\pi }{2^{n-1}}}{\binom {n}{m}},&n{\text{ odd}}\\0,&{\text{otherwise}}\end{cases}}

\int _{-\pi }^{\pi }\cos((2m-n)x)\sin ^{n}(x)\ dx={\begin{cases}(-1)^{m+(n/2)}{\frac {\pi }{2^{n-1}}}{\binom {n}{m}},&n{\text{ even}}\\0,&{\text{otherwise}}\end{cases}}

Converting trigonometric functions to complex exponents can be proved by using Euler’s formula, expanding using the binomial theorem, and integrating word by word.

Generating Function

Common Generating Tasks

For a certain n, the normal generating function of the sequence is

{\binom {n}{0}},{\binom {n}{1}},{\binom {n}{2}},\ldots

\sum _{k=0}^{\infty }{n \choose k}x^{k}=(1+x)^{n}.

For a certain k, the common generating function of the sequence is

{\binom {0}{k}},{\binom {1}{k}},{\binom {2}{k}},\ldots ,

\sum{n=0}^{\infty }{n \choose k}y^{n}={\frac {y^{k}}{(1-y)^{k+1} }}.

The binomial generating function is of the binomial coefficient

\sum _{n=0}^{\infty }\sum _{k=0}^{n}{n \choose k}x^{k}y^{n}={\frac {1}{1-y-xy}}.

The function producing a symmetric binomial of the binomial coefficients is

\sum _{n=0}^{\infty }\sum _{k=0}^{\infty }{n+k \choose k}x^{k}y^{n}={\frac {1}{1-x-y}}.

Which is the same as the previous generating function after the replacement of .

x\to xy

Exponential Generating Function

The function producing a symmetric exponentiation bivariate of the binomial coefficients is:

\sum _{n=0}^{\infty }\sum _{k=0}^{\infty }{n+k \choose k}{\frac {x^{k}y^{n}}{(n+k)!}}=e^{x+y}.

Divisibility Property

In 1852, Kummer proved that if m and n are non-negative integers and p is a prime number, then the greatest power of dividing p is equal to p ^c , where c is the number of times m and n are divided. is added to the base p . Similarly, a prime p in . The exponent of the non-negative integer number j equals such that the fractional part of k / p ^j is greater than the fractional part of n / p ^j

{\binom {m+n}{m}}{\binom {n}{k}}

This can be inferred from the fact that n / gcd is divisible by ( n , k ). Specifically so it follows that p is divisible by all positive integers r and s such that s < p ^r . However this is not true for higher powers of p : for example 9 does not divide .

{\binom {n}{k}}{\binom {p^{r}}{s}}{\binom {9}{6}}

The somewhat surprising result of David Singmaster (1974) is that any integer divides almost all binomial coefficients. More precisely, assign an integer d and assume that f ( N ) denotes the number of binomial coefficients with n < N such that d divides . Then

{\binom {n}{k}}{\binom {n}{k}}

\lim _{N\to \infty }{\frac {f(N)}{N(N+1)/2}}=1.

Since the number of binomial coefficients with n < n is n ( n +1)/2, this indicates that the density of the binomial coefficient is divisible by d to 1.

{\binom {n}{k}}

Binomial coefficients have divisibility properties related to least common multiples of consecutive integers. For example:

{\binom {n+k}{k}}}~~divided~~ .{\displaystyle {\frac {{\text{lcm}}(n,n+1,\ldots ,n+k)}{n}}

{\binom {n+k}{k}}}~~is~~ a ~~multiple~~ of~~ .{\displaystyle {\frac {{\text{lcm}}(n,n+1,\ldots ,n+k)}{n\cdot {\text{lcm}}({\binom {k}{0}},{\binom {k}{1}},\ldots ,{\binom {k}{k}})}}

Another fact: An integer n 2 is prime if and only if all intermediate binomial coefficients

{\binom {n}{1}},{\binom {n}{2}},\ldots ,{\binom {n}{n-1}}

is divisible by n .

Proof: When p is prime, p is divisible by

{\binom {p}{k}}={\frac {p\cdot (p-1)\cdots (p-k+1)}{k\cdot (k-1)\cdots 1}}0 < k < p ~for~ all

Since is a natural number and p divides the numerator but not the denominator. When n is composite, let p be the smallest prime factor of n and let k = n / p . then 0 < p < n and

{\binom {p}{k}}

{\binom {n}{p}}={\frac {n(n-1)(n-2)\cdots (n-p+1)}{p!}}={\frac {k(n-1)(n-2)\cdots (n-p+1)}{(p-1)!}}\not \equiv 0{\pmod {n}}

Otherwise the fraction k ( n − 1)( n − 2)×…×( n – p + 1) must be divisible by n = k × p , this can only happen if ( n − 1)( n – 2)×…×( n – p + 1) is divisible by p . But n is divisible by p , so p is not divisible by n – 1, n – 2, …, n – p + 1 and because pis prime, we know that p is not divisible by ( n – 1) ( n – 2)×…×( n – p + 1) and hence the numerator cannot be divisible by n .

limit and asymptotic formula

The following limits: Hold for all values of n and k such that 1 k n :

{\binom {n}{k}}

{\displaystyle {\frac {n^{k}}{k^{k}}}\leq {n \choose k}\leq {\frac {n^{k}}{k!}}<\left({\frac {n\cdot e}{k}}\right)^{k}}.

The first inequality comes from the fact that

{n \choose k}={\frac {n}{k}}\cdot {\frac {n-1}{k-1}}\cdots {\frac {n-(k-1)}{1}}

And each of these has conditions in this product . A similar argument can be made to show the second inequality. The last strict inequality is equal to , this is clear because the RHS is a term of the exponential series .

k{\displaystyle \geq {\frac {n}{k}}}{\displaystyle e^{k}>k^{k}/k!}{\displaystyle e^{k}=\sum _{j=0}^{\infty }k^{j}/j!}

From the divisibility properties we can infer that

{\displaystyle {\frac {{\text{lcm}}(n-k,\ldots ,n)}{(n-k)\cdot {\text{lcm}}({\binom {k}{0}},\ldots ,{\binom {k}{k}})}}\leq {\binom {n}{k}}\leq {\frac {{\text{lcm}}(n-k,\ldots ,n)}{n-k}}},

where both similarities can be achieved.

Both n and k large

Stirling’s approximation gives the following approximation, when valid: Both tend toward infinity: n, k

{n \choose k}\sim {\sqrt {n \over 2\pi k(n-k)}}\cdot {n^{n} \over k^{k}(n-k)^{n-k}}

Because the inequality forms of Stirling’s formula also have bound factorizations, minor variations on the asymptotic approximation above provide precise limits.

In particular, when sufficiently large: n

{2n \choose n}\sim {\frac {2^{2n}}{\sqrt {n\pi }}}}~~And~~{\sqrt {n}}{2n \choose n}\geq 2^{2n-1

And, in general, for m2 and n 1,

{\sqrt {n}}{mn \choose n}\geq {\frac {m^{m(n-1)+1}}{(m-1)^{(m-1)(n-1)}}}

Another useful asymptotic approximation when both numbers increase at the same rate is.

\log _{2}{n \choose k}\sim nH(k/n)=k\log _{2}(n/k)+(n-k)\log _{2}(n/(n-k))

where is is the binary entropy function.

H(p)=-p\log _{2}(p)-(1-p)\log _{2}(1-p)

If n is large and k is linear in n , then there exist various exact asymptotic approximations for the binomial coefficient . For example, if then

{\binom {n}{k}}

|n/2-k|=o(n^{2/3})

{\binom {n}{k}}\sim {\binom {n}{\frac {n}{2}}}e^{-d^{2}/(2n)}\sim {\frac {2^{n}}{\sqrt {{\frac {1}{2}}n\pi }}}e^{-d^{2}/(2n)}

where d = n – 2 k .

n k. much bigger than

If n is greater and k is o ( n ) (that is, if k / n → 0 ), then

{\binom {n}{k}}\sim \left({\frac {ne}{k}}\right)^{k}\cdot (2\pi k)^{-1/2}\cdot \exp \left(-{\frac {k^{2}}{2n}}(1+o(1))\right)

where again o is the little o notation.

Sum of Binomial Coefficients

A simple and rough upper bound for the sum of the binomial coefficients can be obtained using the binomial theorem:

\sum _{i=0}^{k}{n \choose i}\leq \sum _{i=0}^{k}n^{i}\cdot 1^{k-i}\leq (1+n)^{k}

The more precise limits are given by

{\frac {1}{\sqrt {8n\epsilon (1-\epsilon )}}}\cdot 2^{H(\epsilon )\cdot n}\leq \sum _{i=0}^{k}{\binom {n}{i}}\leq 2^{H(\epsilon )\cdot n}.

which is valid for all integers with .

{\displaystyle n>k\geq 1}\epsilon \doteq k / n \leq 1/2

Normalized Binomial Coefficient

The infinite product formula for the gamma function also gives an expression for the binomial coefficient.

(-1) ^ {k} {z \choose k} = {- z + k-1 \choose k} = {\frac {1} {\Gamma (-z)}} {\frac {1} {( k + 1) ^ {z + 1}}} \prod _ {j = k + 1} {\frac {(1 + {\frac {1} {j}}) ^ {- z-1}} {1 - {\frac {z + 1} {j}}}}

which produces the asymptotic formula

{z \choose k}\approx {\frac {(-1)^{k}}{\Gamma (-z)k^{z+1}}}\qquad \mathrm {and} \qquad {z+k \choose k}={\frac {k^{z}}{\Gamma (z+1)}}\left(1+{\frac {z(z+1)}{2k}}+{\mathcal {O}}\left(k^{-2}\right)\right)

Like .~~k\to \infty

This asymptotic behavior is rooted in the approximation

{z+k \choose k}\approx {\frac {e^{z(H_{k}-\gamma )}}{\Gamma (z+1)}}

as well. (Here k is the th harmonic number and is the Euler-Mascheroni constant.)

H_{k}\gamma

Furthermore, the asymptotic formula

{\frac {z+k \choose j}{k \choose j}}\to \left(1-{\frac {j}{k}}\right)^{-z}\quad {\text{and}}\quad {\frac {j \choose j-k}{j-z \choose j-k}}\to \left({\frac {j}{k}}\right)^{z}

Assume true, whenever and for any complex number .

k\to \infty~j/k\to xx

Generalization

Generalization to Polynomials

The binomial coefficient can be generalized to a polynomial coefficient defined as a number :

{n \choose k_{1},k_{2},\ldots ,k_{r}}={\frac {n!}{k_{1}!k_{2}!\cdots k_{r}!}}

Where from

\sum _{i=1}^{r}k_{i}=n.

While the binomial coefficients ( x + y ) represent ^{the coefficients of n} , the polynomial coefficients represent the coefficients of the polynomial.

(x_{1}+x_{2}+\cdots +x_{r})^{n}.

The condition r = 2 gives the binomial coefficient:

{n \choose k_{1},k_{2}}={n \choose k_{1},n-k_{1}}={n \choose k_{1}}={n \choose k_{2}}.

The combined interpretation of multinomial coefficients is the distribution of n distinct elements over r (separate) containers , each containing exactly k _i elements, where i is the index of the container.

Polynomial coefficients have many of the same properties as binomial coefficients, for example the recurrence relation:

{n \choose k_{1},k_{2},\ldots ,k_{r}}={n-1 \choose k_{1}-1,k_{2},\ldots ,k_{r}}+{n-1 \choose k_{1},k_{2}-1,\ldots ,k_{r}}+\ldots +{n-1 \choose k_{1},k_{2},\ldots ,k_{r}-1}

and symmetry:

{n \choose k_{1},k_{2},\ldots ,k_{r}}={n \choose k_{\sigma _{1}},k_{\sigma _{2}},\ldots ,k_{\sigma _{r}}}

where is a permutation (1, 2, …, k r ).

(\sigma _{i})

Taylor series

The extension of the series around any arbitrarily chosen point using Stirling numbers of the first kind is Z_o

{\begin{aligned}{z \choose k}={\frac {1}{k!}}\sum _{i=0}^{k}z^{i}s_{k,i}&=\sum _{i=0}^{k}(z-z_{0})^{i}\sum _{j=i}^{k}{z_{0} \choose j-i}{\frac {s_{k+i-j,i}}{(k+i-j)!}}\\&=\sum _{i=0}^{k}(z-z_{0})^{i}\sum _{j=i}^{k}z_{0}^{j-i}{j \choose i}{\frac {s_{k,j}}{k!}}.\end{aligned}}

n = 1/2 . Binomial Coefficient with

The definition of the binomial coefficient can be extended to the case where is is real and is integer. nk

In particular, the following identity holds for any non-negative integer : k

{{1/2} \choose {k}}={{2k} \choose {k}}{\frac {(-1)^{k+1}}{2^{2k}(2k-1)}}.

This is visible when expanding into a power series using the Newton binomial series:

{\sqrt {1+x}}

{\sqrt {1+x}}=\sum _{k\geq 0}{\binom {1/2}{k}}x^{k}.

Products of Binomial Coefficients

The product of two binomial coefficients can be expressed as a linear combination of the binomial coefficients:

{z \choose m}{z \choose n}=\sum _{k=0}^{m}{m+n-k \choose k,m-k,n-k}{z \choose m+n-k},

where the connection coefficients are the polynomial coefficients. In the context of labeled combinatorial objects, the connection coefficients m + n – represent the number of ways to assign k labels to a pair of labeled combinatorial objects – weights m and n respectively – whose first k labels are identified. of weight m + n – kTo get a new labeled Combinatorial object. (That is, separating the label into three parts to apply to the glued part, the uncorrelated part of the first object, and the disjointed part of the second object.) In this respect, the binomial coefficients are for the exponentially generated series with the falling factorial. are for general generating series.

The product of all binomial coefficients in the nth row of Pascal’s triangle is given by the formula:

\prod _{k=0}^{n}{\binom {n}{k}}=\prod _{k=1}^{n}k^{2k-n-1}.

Partial Decomposition

The partial fraction decomposition reciprocal is given by

{\frac {1}{z \choose n}}=\sum _{i=0}^{n-1}(-1)^{n-1-i}{n \choose i}{\frac {n-i}{z-i}},\qquad {\frac {1}{z+n \choose n}}=\sum _{i=1}^{n}(-1)^{i-1}{n \choose i}{\frac {i}{z+i}}.

Newton’s Binomial Series

Newton’s binomial series, named after Sir Isaac Newton, is a generalization of the binomial theorem for infinite series:

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

The identity can be obtained by showing that both sides satisfy the differential equation (1 + z ) f’ ( z ) = α f ( z ).

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

{\frac {1}{(1-z)^{\alpha +1}}}=\sum _{n=0}^{\infty }{n+\alpha \choose n}z^{n}

where the identity

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

is applicable.

Multiset (Increasing) Binomial Coefficients

Binomial coefficients calculate a subset of a given size from a given set. A related combinatorial problem is computing a multiset of determined size with elements drawn from a given set, that is, to select a certain number of elements from the given set with the probability of selecting the same element repeatedly. The number of ways is to count. The resulting numbers are called multiplet coefficients ; ^[15] The number of ways to “multichoose” (ie, choose with replacement) k items from a n element set is denoted .

\left(\!\!{\binom {n}{k}}\!\!\right)

To avoid ambiguity and confusion with the main notation of n’ in this article ,
let f = n = r + ( k – 1) and r = f – ( k – 1).

The multiplet coefficient can be expressed as the binomial coefficient by the rule

{\binom {f}{k}}=\left(\!\!{\binom {r}{k}}\!\!\right)={\binom {r+k-1}{k}}.

A possible alternative characterization of this identity is as follows: We can define the falling factor as

(f)_{k}=f^{\underline {k}}=(f-k+1)\cdots (f-3)\cdot (f-2)\cdot (f-1)\cdot f,

and as a growing factor

{\color {white}{\big |}}r^{(k)}=\,r^{\overline {k}}=\,r\cdot (r+1)\cdot (r+2)\cdot (r+3)\cdots (r+k-1);

So, for example,

17\cdot 18\cdot 19\cdot 20\cdot 21=(21)_{5}=21^{\underline {5}}=17^{\overline {5}}=17^{(5)}.

Then the binomial coefficients can be written as

{\binom {f}{k}}={\frac {(f)_{k}}{k!}}={\frac {(f-k+1)\cdots (f-2)\cdot (f-1)\cdot f}{1\cdot 2\cdot 3\cdot 4\cdot 5\cdots k}},

Whereas the corresponding multiset coefficient is defined by changing from falling with increasing factorial:

\left(\!\!{\binom {r}{k}}\!\!\right)={\frac {r^{(k)}}{k!}}={\frac {r\cdot (r+1)\cdot (r+2)\cdots (r+k-1)}{1\cdot 2\cdot 3\cdot 4\cdot 5\cdots k}}.

Normalization of negative integers n

For any n ,

{\begin{aligned}{\binom {-n}{k}}&={\frac {-n\cdot -(n+1)\dots -(n+k-2)\cdot -(n+k-1)}{k!}}\\&=(-1)^{k}\;{\frac {n\cdot (n+1)\cdot (n+2)\cdots (n+k-1)}{k!}}\\&=(-1)^{k}{\binom {n+k-1}{k}}\\&=(-1)^{k}\left(\!\!{\binom {n}{k}}\!\!\right)\;.\end{aligned}}

In particular, the binomial coefficients evaluated on negative integer n are given by signed multiset coefficients. In the special case , it reduces to

n=-1{\displaystyle (-1)^{k}={\binom {-1}{k}}=\left(\!\!{\binom {-k}{k}}\!\!\right).}

For example, if n = −4 and k = 7, then r = 4 and f = 10:

{\begin{aligned}{\binom {-4}{7}}&={\frac {-10\cdot -9\cdot -8\cdot -7\cdot -6\cdot -5\cdot -4}{1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6\cdot 7}}\\&=(-1)^{7}\;{\frac {4\cdot 5\cdot 6\cdot 7\cdot 8\cdot 9\cdot 10}{1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6\cdot 7}}\\&=\left(\!\!{\binom {-7}{7}}\!\!\right)\left(\!\!{\binom {4}{7}}\!\!\right)={\binom {-1}{7}}{\binom {10}{7}}.\end{aligned}}

Two real or complex valued arguments

Binomial coefficients are normalized to two real or complex valued arguments using the gamma function or beta function.

{x \choose y}={\frac {\Gamma (x+1)}{\Gamma (y+1)\Gamma (x-y+1)}}={\frac {1}{(x+1 )\mathrm {B} (x-y+1,y+1)}}.

This definition inherits the following additional properties :

\Gamma

{x \choose y}={\frac {\sin(y\pi )}{\sin(x\pi )}}{-y-1 \choose -x-1}={\frac {\sin(( xy)\pi )}{\sin(x\pi )}}{yx-1 \choose y};

Other than this,

{x \choose y}\cdot {y \choose x}={\frac {\sin((xy)\pi )}{(xy)\pi }}.

The resulting function has been little studied, apparently being graphed for the first time (Fowler 1996). In particular, many binomial identities fail: but a for n is positive (so as to be negative). The behavior is quite complex, and differs markedly in different octaves (that is, with respect to the x and y axes and the line ), with the behavior of negative x singularities at negative integer values and a chessboard of positive and negative fields:

\textstyle {{n \choose m}={n \choose n-m}}{\displaystyle \textstyle {{-n \choose m}\neq {-n \choose -n-m}}}-ny=x

In octaves it is a smoothly interpolated form of the normal binomial with a ridge (“Pascal’s Ridge”).

0\leq y\leq x

In the octave and in the quadrant the function is close to zero.

0\leq x\leq yx \geq 0, y \leq 0

The function in the quadrant is alternately with vertices on very large positive and negative parallelograms

x \leq 0, y \geq 0

(-n,m+1),(-n,m),(-n-1,m-1),(-n-1,m)

The behavior in the octave is again very large positive and negative alternating, but on a square grid.

0>x>y

In octaves it is close to zero, except near the singularity.

-1>y>x+1

Generalization of q- series

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

Generalization to Infinite Cardinals

The definition of the binomial coefficient can be generalized to infinite cardinals by defining:

{\alpha \choose \beta }=|\{B\subseteq A:|B|=\beta \}|

where A is some set with cardinality . One can show that the generalized binomial coefficient is well defined, in the sense that no matter which set we choose to represent the cardinal numbers, , will remain the same. For finite cardinals, this definition coincides with the standard definition of the binomial coefficient.

\alpha\alpha{\alpha \choose \beta }

Assuming the axiom of choice, one can show that for any infinite cardinal.

{\alpha \choose \alpha }=2^{\alpha }\alpha

Binomial coefficients in programming languages

The notation is convenient in handwriting but inconvenient for typewriters and computer terminals. Many programming languages do not offer a standard subroutine for computing binomial coefficients, but for example the APL programming language and the (related) J programming language both use the exclamation mark : . The binomial coefficient is implemented in SciPy as in scipy. special. comb .

{n \choose k}~k ! n

from math import factorial
def binomial_coefficient(n: int, k: int) -> int:
    return factorial(n) // (factorial(k) * factorial(n - k))

are too slow and useless for computing the factorial of very large numbers (in languages like C or Java they are prone to overflow errors for this reason). A direct implementation of the multiplier formula works well:

def  binomial_coefficient ( n :  int ,  k :  int )  ->  int :  if  k  <  0  or  k  >  n :  return  0  if  k  ==  0  or  k  ==  n :  return  1  k  =  min ( k ,  n  -  k )  # Take advantage of the symmetry  for c  =  1  i  in  range ( k ):  c  =  c  *  ( n  -  i )  /  ( i  +  1 )  return  c

(In Python, range(k) produces a list from 0 to k-1.)

Pascal’s Law provides a recursive definition that can also be implemented in Python, although it is less efficient:

def  binomial_coefficient ( n :  int ,  k :  int )  ->  int :  if  k  <  0  or  k  >  n :  return  0  if  k  >  n  -  k :  # take advantage of the symmetry  k  =  n  -  k  if  k  ==  0  or  n  <=  1 :  return  1  binomial_coefficient ( n- 1 , k ) + return the binomial coefficient ( n - 1 , k - 1 )

The example described above can also be written in a functional style. The following scheme example uses a recursive definition

{n \choose k+1}={\frac {n-k}{k+1}}{n \choose k}

Rational arithmetic can be easily avoided by using integer division

{n \choose k+1}=\left[(n-k){n \choose k}\right]\div (k+1)

The following implementation uses all these ideas

( define ( binomial  n  k ) ;; helper function to compute c(n,k) via forward recursion  ( define ( binomial-iter  n  k  i  prev )  ( if ( >= i  k )  previous  ( binomial-iter  n  k  ( + i  1 )  ( / ( * ( - n  i )  previous )  ( +i  1 )))) ;; Use the symmetry property C(n,k)=C(n, nk)  ( if ( < k  ( -  n  k) ))  ( binomial-iteration  n  k  0  1 )  ( binomial-iteration  n  ( - n  k )  0  1 )))

In a language with fixed-length integers, when performing calculations that are multiplied by, the result may overflow even if it doesn’t fit. The overflow can be avoided by first dividing and fixing the result using the remainder:

\textstyle {n \choose k+1}=\left[(n-k){n \choose k}\right]\div (k+1)(n-k)

{n \choose k+1}=\left[\textstyle {n \choose k}\div (k+1)\right](n-k)+{\left[{n \choose k}\ \mathrm {mod} \ (k+1)\right](n-k) \over (k+1)}

Implementation in C language:

#include unsigned  long  binomial ( unsigned  long  n ,  unsigned  long  k )  {  unsigned  long  c  =  1 ,  i ; if ( k > n - k ) // take advantage of symmetry k = n - k ; for ( i = 1 ; i <= k ; i ++ , n --                   )  {  if  ( c / i  >  ULONG_MAX / n )  // return 0 on overflow  return  0 ; c = c / i * n + c % i * n / i ; // split c * n / i into (c / i * i + c % i) * n / i } return c ; ,

Another way to calculate the binomial coefficient when using large numbers is to identify

{n \choose k} = {\frac {n!} {k! \, (nk)!}} = {\frac {\Gamma (n + 1)} {\Gamma (k + 1) \, \Gamma (n-k + 1)}} =exp ~ (\ln \Gamma (n + 1) - \ln \Gamma (k + 1) - \ln \Gamma (n-k + 1)),

where is the mean in the gamma function of the natural logarithm . It is a special function that is easily calculated and is standard in some programming languages such as using log_gamma in maxima, Log Gamma in Mathematica, GAMMALN in MATLAB and Python’s SciPy modules, lngamma in PARI/GP or lgamma In C, R, and Julia. The returned value cannot be an integer due to a roundoff error.