|
|
 |
ChooseIn mathematics, particularly in combinatorics, the binomial coefficient of the natural number n and the integer k is defined to be the natural number and where m! denotes the factorial of m. According to Nicholas J. Higham, the 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), nCk or (C for combination). For compactness, from here on we will use the first of these three notations. The binomial coefficients are the coefficients in the expansion of the binomial (x + y)n (hence the name): 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. 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. For exponent 1, (x+y)1 is x+y. For exponent 2, (x+y)2 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 x2, the only possibility is to choose x from both factors; likewise for y2. 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)3 reduces to (x+y)2(x+y), where we already know that (x+y)2= x2+2xy+y2. Again the extremes, x3 and y3 arise in a unique way. However, the term x2y is either 2xy times x or x2 times y, for a coefficient of 3; likewise xy2 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 xn and yn. If k is neither 0 nor n, then the term arises in two ways, from xn-k-1yk × x and from xn-kyk-1 × y. For example, x2y2 is both xy2 times x and x2y times y, thus its coefficient is 3 (the coefficient of xy2) + 3 (the coefficient of x2y). This is the origin of Pascal's triangle, discussed below. Another perspective is that to form xn−kyk 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! permutations 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 xn−kyk. 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 x2y2. Check out the following recipes that are tagged "Choose":
|