Table of Contents
Last modified on January 10th, 2024
Expanding an expression (x + y)n using the binomial theorem, we get:
${\left( x+y\right) ^{n}=\sum ^{n}_{k=0}\begin{pmatrix} n \\ k \end{pmatrix}x^{n-k}y^{k}}$, where n is a positive integer.
As we know, the binomial coefficient (n, k), read as ‘n choose k,’ is calculated using the combination formula ${\begin{pmatrix} n \\ k \end{pmatrix}=\dfrac{n!}{\left( n-k\right) !k!}}$
Considering n is any real number, we get:
${\begin{pmatrix} n \\ k \end{pmatrix}=\dfrac{n\left( n-1\right) \left( n-2\right) \ldots \left( n-k+1\right) }{k!}}$
Newton’s Binomial Theorem, proposed and explained by Sir Isaac Newton in the 17th century, expands expressions of the form (1+x)n, where n is any real number. It is similar to the generalized binomial theorem expression of the form (x + y)n.
It is mathematically written as: ${\left( x+1\right) ^{n}=\sum ^{\infty }_{k=0}\begin{pmatrix} n \\ k \end{pmatrix}x^{k}}$ (where n is any real number and -1 < x < 1), which reduces to the original version of the binomial theorem (where n is a positive integer).
Now, let us expand an expression (1 – x)-p using the above theorem (where p is a positive integer).
For the expansion of (1 – x)-p, first, we need to consider the expression (1 + x)-p and then simplify the binomial coefficients.
= ${\dfrac{\left( -p\right) \left( -p-1\right) \left( -p-2\right) \ldots \left( -p-k+1\right) }{k!}}$
= ${\left( -1\right) ^{k}\dfrac{p\left( p+1\right) \left( p+2\right) \ldots \left( p+k-1\right) }{k!}}$
= ${\left( -1\right) ^{k}\dfrac{\left( p+k-1\right) !}{k!\left( p-1\right) !}}$
= ${\left( -1\right) ^{k}\begin{pmatrix} p+k-1 \\ k \end{pmatrix}}$
= ${\left( -1\right) ^{k}\begin{pmatrix} p+k-1 \\ p-1 \end{pmatrix}}$
Thus, ${\left( 1+x\right) ^{-p}=\sum ^{\infty }_{k=0}\left( -1\right) ^{k}\begin{pmatrix} p+k-1 \\ p-1 \end{pmatrix}x^{k}}$ = ${\sum ^{\infty }_{k=0}\begin{pmatrix} p+k-1 \\ p-1 \end{pmatrix}\left( -x^{k}\right)}$
Now, replacing x by -x, we get ${\left( 1-x\right) ^{-p}=\sum ^{\infty }_{k=0}\begin{pmatrix} p+k-1 \\ p-1 \end{pmatrix}x^{k}}$
Again, using the above theorem, we can construct the generating functions whose coefficients solve the counting problem directly.
Let us find the generating function for the number of solutions to x1 + x2 + x3 = n, where 0 ≤ x1 ≤ ∞, 0 ≤ x2 ≤ 5, 0 ≤ x3 ≤ 5.
Considering the function as f(x), we get
f(x) = (1 + x + x2 + …) (1 + x + x2 + x3 + x4 + x5)2
Since (1 + x)-1 = (1 + x + x2 + x3 + …), the generating function of the given expression is:
f(x) = (1 – x)-1 (1 + x + x2 + x3 + x4 + x5)2
= ${\dfrac{\left( 1+x+x^{2}+x^{3}+x^{4}+x^{5}\right) ^{2}}{\left( 1-x\right) }}$
= ${\dfrac{x^{10}+2x^{9}+3x^{8}+4x^{7}+5x^{6}+6x^{5}+5x^{4}+4x^{3}+3x^{2}+2x+1}{1-x}}$
Expand the expression (1 + x)-4 using the Newton’s binomial theorem.
As we know, for any real number r and -1 < x < 1,
${\left( x+1\right) ^{n}=\sum ^{\infty }_{k=0}\begin{pmatrix} n \\ k \end{pmatrix}x^{k}}$
= ${1+nx+\dfrac{n\left( n-1\right) }{2!}x^{2}+\dfrac{n\left( n-1\right) \left( n-2\right) }{3!}x^{2}+\ldots}$
Thus, (1 + x)-4 = ${1-4x+\dfrac{\left( -4\right) \left( -4-1\right) }{2!}x^{2}+\dfrac{\left( -4\right) \left( -4-1\right) \left( -4-2\right) }{3!}x^{2}+\ldots}$
= 1 – 4x + 10x2 – 20x3 + …
Find the number of solutions to x1 + x2 + x3 + x4 = 9, where 0 ≤ x1 ≤ 5, 2 ≤ x2 ≤ 6, 0 ≤ x3 ≤ 3, 0 ≤ x4 ≤ 3.
Considering the function as f(x), we get
f(x) = (1 + x + x2 + x3 + x4 + x5) (x2 + x3 + x4 + x5 + x6) (1 + x + x2 + x3) (1 + x + x2 + x3)
= (1 + x + x2 + x3 + x4 + x5) (x2 + x3 + x4 + x5 + x6) (1 + x + x2 + x3)2
= x17 + 4x16 + 10x15 + 20x14 + 33x13 + 47x12 + 59x11 + 66x10 + 66x9 + 59x8 + 47x7 + 33x6 + 20x5 + 10x4 + 4x3 + x2
As we know, the number of solutions to x1 + x2 + x3 + x4 = k is the coefficient of xk, which is the number of ways of choosing one term from each factor so that the exponents of terms sum up to k.
Thus, the number of solutions to x1 + x2 + x3 + x4 = 9 is the coefficient of x9, that is, 66.