Home > Binomial coefficient

and

(Here m! denotes the factorial of m). The binomial coefficient of n and k is also written as C(n, k) or ⁿC_k (C for combination) and read as "n choose k".

For example,

The binomial coefficients are the coefficients in the expansion of the binomial (x + y)ⁿ (hence the name):

This is generalized by the binomial theorem, which allows the exponent n to be negative or a non-integer.

The important recurrence relation

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 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)⁵ = 1x⁵ + 5 x⁴y + 10 x³y² + 10 x²y³ + 5 x y⁴ + 1y⁵.

The third diagonal form the sequence of the triangular numbers. The differences between elements on other diagonals are the elements in the previous diagonal - consequential to the recurrence relation (3) above.

The triangle was described by Zhu Shijie in 1303 AD in his book Precious Mirror of the Four Elements. In his book, Zhu mentioned the triangle as an ancient method (over 200 years before his time) for solving binomial coefficients, which indicated that the method was known to Chinese mathematicians five centuries before Pascal.

If you color in all even numbers on this triangle and leave the odd numbers blank, you get the Sierpinski triangle. Try coloring in multiples of 3, 4, 5, and so on and see what patterns emerge.

1 Combinatorics and statistics

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

• Every setThis article is about sets in mathematics. For other meanings, see Set (disambiguation). Sets are one of the most important and fundamental concepts in modern mathematics. Basic set theory, having only been invented at the end of the 19th century, is now with n elements has C(n, k) different subsets having k elements each (these are called k-combinations).
• The number of stringGenerally, string is a thin piece of fiber which is used to tie, bind, or hang other objects. String can be made from a variety of fibres. You can get different kinds, twine for example. The term has more specific meanings, within certain academic discipls of length n containing k ones and n-k zeros is C(n, k).
• There are 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 numbers whose sum equals k is 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 numberThe Catalan numbers named after the Belgian mathematician Eugene Charles Catalan (1814—1894), form a sequence of natural numbers that occur in various counting problems in combinatorics. The n''th Catalan number is defined by : (see binomial coefficient).s have an easy formula involving binomial coefficients; they can be used to count various structures, such as treeGraph theory Trees (structure) In graph theory, a tree is a graph in which any two vertices are connected by exactly one path. A forest is a graph in which any two vertices are connected by at most one path. An equivalent definition is that a forest is as and parenthesized expressions.

The binomial coefficients also occur in the formula for the binomial distributionIn mathematics, the binomial distribution is a discrete probability distribution which describes the number of successes in a sequence of n independent yes/no experiments, each of which yielding success with probability p''. Such a success/failure experim in statisticsStatistics is the science and practice of developing human knowledge through the use of empirical data. It is based on statistical theory which is a branch of applied mathematics. Within statistical theory, randomness and uncertainty are modelled by proba and in the formula for a Bézier curve.