The binomial coefficient is a mathematical function that can be used to solve one of the basic problems of combinatorics . It indicates how many different ways one can select certain objects from a set of different objects (without replacing, without considering the order). The binomial coefficient is the number of -element subsets of a -element set.
"49 over 6" (or "45 over 6" in Austria and Switzerland) is z. B. the number of possible draws in the lottery (without considering the additional number).
A binomial coefficient depends on two natural numbers and . He will be with the symbol
written and spoken as “n over k”, “k out of n” or “n deep k”. The English abbreviation nCr for n choose r can be found on pocket calculators.
These numbers were named because they appear as coefficients in the powers of the binomial ; the so-called binomial theorem applies :
An extension of the binomial coefficient derived from combinatorics is the general binomial coefficient , which is used in analysis .
For a complex number and a nonnegative integer , the binomial coefficient "n over k" is defined as follows:
where denotes the factorial of . The empty product ( ) is included .
If it is a nonnegative integer with , the definition known from combinatorics can be used:
If the restriction is also made to non-negative whole numbers, the following applies:
is always a nonnegative integer. Is , so is , otherwise is .
. For is the right summand .
In the general case of real or complex values for , some of the expressions cited here can become undefined in the sense given above, if namely should no longer be whole and nonnegative; this concerns the statements , and . It turns out, however, that these statements become correct if, in accordance with the analytical generalization below, the beta function is also allowed for complex values.
Symmetry of the binomial coefficients
Binomial integer coefficients are symmetric in the sense of
for all non-negative and .
Recursive representation and Pascal's triangle
For whole numbers and with , the binomial coefficients can also be determined using the following recursion rule:
for everyone and for everyone with
With their help, all binomial coefficients can easily be determined up to a given limit for , a scheme for this is the Pascal triangle : The recursive part there corresponds to the fact that every number is the sum of the two numbers above it.
The coefficient can be found in the -th line at the -th position (both counting from zero!):
The same triangle represented in the -inomial symbols:
Algorithm for efficient calculation
For integers, there is an efficient algorithm that uses the product formula
of the binomial coefficient. Due to the constant change between multiplication and division, the intermediate results do not grow unnecessarily. In addition, all intermediate results are also natural numbers.
In order to avoid unnecessary computational effort, the binomial coefficient is calculated in the case :
The following pseudocode clarifies the calculation:
1 wenn 2*k > n dann k = n-k
2 ergebnis = 1
3 für i = 1 bis k
4 ergebnis = ergebnis * (n - k + i) / i
5 rückgabe ergebnis
Pocket calculators also use this calculation method if they offer the function. Otherwise the computing capacity would be exhausted. The labeling of the function key with nCr describes the order of the input values in infix notation ; first the number of elements n, then the function key Combinations, then the number of selected objects r ( referred to as k in the article ).
The calculation nPr ( permutations ) takes into account the permutations of the r elements, the division by is omitted:
The binomial coefficient in combinatorics
In combinatorial counting there are
the number of combinations without repetition of elements of elements. Due to this property, the binomial coefficient plays a central role in combinatorics and is used in the calculation and in the formulas of other combinatorial quantities.
Illustration with quantities
Compare also: Combination (combinatorics) → Set representation
Another interpretation of combinations without repetition of k out of n elements is the number of all -element subsets of a -element set.
It can be interpreted as follows:
First one counts all - tuples with pairwise different elements, which can be put together from the -element initial set. There are options for choosing the first tuple element. After any choice of this first, there are only options for the second element, after its selection only for the third, etc., up to options for the -th and last tuple element. The number of all tuples put together in this way is therefore the product of factors, which can also be noted as with the help of the faculty . Now, however, exactly each of the counted -Tuples are permutations of each other and therefore correspond to one and the same -element subset. After dividing by this “counting multiplicity”, the result is actually the number of subsets sought.
Another, more symmetrical illustration does not emphasize the act of selecting from elements, but rather the aspect of breaking it down into two subsets of and elements. Assume that an -element output tuple consists of red and white elements that are somehow lined up. If one forms all permutations of this sequence, they are each indistinguishable in terms of color, because permutations of the red elements with one another do not change anything in the color sequence, just as little as ever independent permutations within the white ones. So there are only color sequences of the length with all possible different assignments with red elements. Each sequence can now be uniquely assigned to one of the -element subsets of a -element set. The same applies because of the symmetry of red and white or of and also for the complementary -element subsets. The total number of these subsets is thus each .
The following applies to the number of possible draws or tickets for the German Lotto 6 out of 49 (without additional number or super number):
Obviously there is exactly one way to pick 6 correct numbers. counts the possibilities for 0 correct ones, namely to choose all 6 tips from the 43 wrong ones. The number of different tips with 5 correct numbers is very simple , because there are 6 ways to pick just 5 of the 6 numbers drawn (or to omit one of them), and then in each case there are ways to place the omitted tip on one of the 43 wrong numbers . In general, the number of different tips with correct ones results in 6 from 49 with the same consideration . At 6, 0 and 5 right one hardly notices that the factors used , and actually simple binomial coefficients. The sum of all the tip numbers mentioned gives the total number of 13983816 of all possible tips - this follows from the Vandermonde identity given below .
So the probability of 6 correct numbers with one tip is that of 5 correct numbers . For 0 correct numbers the result is about 44%. The general probability of being correct is a special case of the hypergeometric distribution , which combines three binomial coefficients in this way.
For more examples, see: Combination (combinatorics) → Examples
The combinatorial interpretation also allows simple proofs of relations between binomial coefficients, for example by double counting . Example: For :
Let it be a -element set and a fixed element. Then the -element subsets of split into two classes:
- the subsets that contain; They therefore consist of, together with a -element subset of the -element set ,
- the subsets that do not contain; they are -element subsets of the -element set .
The set of all -element subsets of a set is sometimes also referred to because of its power . So for every finite set :
Expressions with binomial coefficients
Sums with binomial coefficients
This formula is based on a combinatorial fact. Since the total number of -element subsets of is -element amount, the number is given by the summation of all its subsets, so . The formula can also be derived from the binomial theorem by putting.
Sums with alternating binomial coefficients
This formula follows for odd from the symmetry of the binomial coefficient. For any it can be derived from the binomial theorem by setting and (or and ).
Sums of binomial coefficients with even or odd numbers of selected objects
By subtraction or addition to the above equations and followed by halving for get:
like also ;
where  are Gaussian brackets .
Sum of shifted binomial coefficients
Starting from the induction start for anything that uses the recursion rule for binomial coefficients, it is easy to prove with induction after using the recursion rule again:
because of the symmetry of the summands as well as the sum, the following also applies:
There is also a combinatorial argument here: The right-hand side corresponds to the number of -element subsets of a -element set of spheres. One can now imagine that the balls have two different colors: balls are red and balls green. A subset of elements then consists of a certain number of red balls and many green ones. For each possible , the corresponding summand on the left gives the number of possibilities for such a division into red and green spheres. The sum provides the total number. A proof that is often perceived as simple uses the binomial theorem in the form
as well as the approach
and coefficient comparison.
In a special case , Vandermonde's identity results in the following formula for the sums of squares:
Is a prime number, and , then is
That means, modulo can be calculated efficiently with the help of the representations from and to the base , namely “digit by digit”.
Binomial coefficients in analysis
A generalization that plays a role in calculus is obtained if one allows for an arbitrary complex number , but continues to assume that it is an integer. In this case it is
the binomial coefficient " over " (the empty product in the case is defined as 1). This definition agrees for nonnegative integer with the combinatorial definition (i.e. the definition of as the number of all -element subsets of a fixed -elemental set), and for nonnegative with the algebraic definition (i.e. the definition of as the product ).
For example is
The second parameter can also be generalized to any complex assignment if the beta function is used to define:
where denotes the gamma function . If there is or is a negative integer, then the value on the right-hand side is 0 because the non-positive integers are the (only) poles of .
Obviously, the symmetry relationship still applies
and with a non-negative whole
In order to extract the sign from the first parameter, provided it is an integer, the relation
Generally, for complex , the relationship
The multinomial coefficients , which are required when generalizing the binomial to the multinomial theorem , offer a further generalization .
For and with you maintain the relationship
which is a generalization of the geometric series and belongs to the binomial series .
If , as well as , the following series converges according to
More exact conditions for and are given in the article Binomial Series .
Sum expression for the beta function
Another relationship can be proved for all relatively easily with complete induction,
from which immediately the symmetry
follows. A generalization for with and reads
Gaussian product representation for the gamma function
The last formula from the previous section is for
Looking at the case , replace the fractions in the sum with integrals according to
and summarizes the sum of the powers according to the binomial formulas, one obtains
where the substitution was used for the last integral . After all, you have the equation
from which the Gaussian product representation of the gamma function results directly from the border crossing ,
Digammafunction and Euler-Mascheroni constant
For with applies
which can also be proven by induction . For the special case this equation is simplified to
where is the sequence of the harmonic numbers, i.e. the partial sums of the harmonic series . The conversion of the left total into a row (limit instead of ) is allowed because of for
is on the other hand representable as
with the digamma function and the Euler-Mascheroni constant
can be continued for complex values - except for negative whole numbers. So you get the row
as a complex interpolation of the sequence of harmonic numbers.
The literal translation of " over " into English " over " does not denote the binomial coefficient , but the fraction . " Choose " is correct .
↑ Disquisitiones generales circa seriem infinitam 1 +… . 1813, p. 26 (also in Carl Friedrich Gauß: Werke. Volume 3, p. 145 ).