BINOMIAL COEFFICIENTS
Introduction —
In statistics, binomial coefficients are majorly used along with distributions. But, there is more to them when applied to computational algorithms. They are used extensively in the field of statistical machine learning as well as dynamic programming. The most basic idea about binomial coefficients is derived from a binomial distribution. The coefficients are used in the binomial theorem, and hence, the name. A binomial coefficient is the number of ways to select a set of objects from various objects without taking into account the order of location of these elements (i.e. the number of disordered sets).
Some Properties of Binomial — Binomial coefficients have many different properties, we present the simplest of them: ➢ Symmetry Rule: ➢ ➢ Deposit-removal: ➢ ➢ Summation by : ➢ ➢ Summation by : ➢ ➢ Summation over and : ➢ ➢ Summation of squares: ➢ ➢ Weighted Summation: ➢ ➢ Relationship with Fibonacci numbers : ➢
MORE ON PROPERTIES OF BINOMIAL COEFFICIENTS —
The process by which any given exponentiation of a binomial can be expanded is the Binomial Theorem. Let n be a positive integer, x, y ∈ C, then (x + y)n = nC0 x n-0 y 0 + nC1 x n-1 y 1 + nC2 x n-2 y 2 + ………. + nCr x n-r y r + …. nCn-1 xyn-1 + nCn x 0 y n (x + y)n = ∑r=0 n nCr x n-r y r Here nC0, nC1, nC2 …… nCn are binomial coefficients
Key features of the binomial theorem are as follows:
1] In the binomial expansion, there exists one extra term which is more than that of the value of the index.
2] In the binomial theorem, the coefficients of binomial expressions are at the same distance from the beginning to the end.
3] an and bn are the 1st and final terms, respectively. x = y or x + y = n is valid if nCx = nCy.
4] C0 + C1 + C2 + ….. + Cn = 2n
5] C0 + C2 + C4 + ….. = C1 + C3 + C5 + ….. = 2n-1
6] C0 2 + C1 2 + C2 2 + ….. + Cn 2 = 2nCn = (2n!) / n! n!
7] The general term of a binomial expansion is given by Tr+1 = nCr x n-r a r . 8] nCr + nCr-1 = n+1Cr
More on properties of binomial coefficients are discussed below.
1] ∑r=0 n nCr x n-r y r = (x + y)n
2] ∑r=0 n nCr y r 1 n-r = (1 + y)n
3] ∑r=0 n nCr 1 n-r 1 r = (1 + 1)n = 2n
4] ∑r=0 n nCr (- 1)r 1 n-r = (1 + (- 1))n = 0
5] ∑r=0 n n-1Cr-1 = ∑r=1 n n-1Cr-1 1 n-r (1)r-1 = (1 + 1)n-1 = 2n-1
6] ∑r=0 n n+2Cr+2 = 2n+2 — n+2C0 — n+2C1
7] ∑r=0 n n-1Cr-1 (- 1)r+1 = ∑ n-1Cr-1 (- 1)r-1 (- 1)2 = (1 + (- 1))n = 0
Get shreyans jain’s stories in your inbox
Join Medium for free to get updates from this writer.
8] nCr = (n / r) (n-1Cr-1)
9] nCr / n = (n-1Cr-1) / r
10] (nCr) / (r + 1) = n+1Cr+1 / (n + 1) 11] (n+1Cr+1) / (r + 2) = n+2Cr+2 / (n + 2)
❑ Binomial coefficients have two definitions. They are as follows:
- Binomial Coefficients for Finding Combinations
— Binomial coefficients are used to find the number of ways to select a certain number of objects from the provided pool of objects. Statistically, a binomial coefficient can help find the number of ways y objects can be selected from a total of x objects. The number of y element subsets from x. The formula is derived as:
For selecting the y element subsets from x objects, binomial coefficient or combinations possible are xCy = x! / y! * (x-y)!
Example
Imagine there is a class with 15 students. If you need to select a team of 7 students for a competition, you need to figure out the possible combinations. While using the formula of binomial coefficients, the answer could be calculated easily. The total combinations = 15! / 7! * (15–7)! = 15! / 7! * 8!
2. Binomial Coefficients for Distribution —
This definition is more formal and statistical. It means finding the coefficients of a polynomial expansion. To put it simply, the binomial coefficient C(a, b) can be defined as the coefficient of x^b in the distributed form of (x+1)^a. Example
For example, you want a polynomial expansion of (x+1)². If we compare it to our definition, we get a=2 and b=0,1,2. By manual calculation we know that the expansion of (x+1)² = x² + 2x + 1. But, how are those coefficients calculated?
Let us apply the formula:
The coefficient of x⁰ = C(2,0)
The coefficient of x¹ = C(2,1)
The coefficient of x² = C(2,2)
Hence, the expansion can be written as: C(2,0)x⁰ + C(2,1)x¹ + C(2,2)x²
The formula remains the same. C(a,b) = a! / b! * (a-b)!
Applying the same formula here, C(2,0) = 2! / 0! * (2–0)! = 1
C(2,1) = 2! / 1! * (2–1)! = 2
C(2,2) = 2! / 2! * (2–2)! = 1
Now, if we substitute these values in the expansion, we get x² + 2x + 1.
