Unit 8, lesson 66

Factorials and Binomial Coefficients

What n! and the binomial coefficient mean for nonnegative integers, how to cancel factorials in a ratio safely, and why choosing positions in a product gives the coefficients of a binomial expansion.

  • Theory part 131
  • Practice part 132
  • Indices, Factorials, and Sums

Multiply out (x+1)4(x + 1)^4 and the middle coefficient comes out as 66. That number is no accident. It counts the ways to pick which two of the four factors supply an xx. Factorials and binomial coefficients are the bookkeeping behind such counts, and they appear in every Taylor series and in almost every use of the ratio test.

Key terms

Factorial

Definition For a positive integer nn, the factorial of nn is the product of all integers from nn down to 11,

n!=n(n−1)(n−2)⋯2⋅1.n! = n(n - 1)(n - 2) \cdots 2 \cdot 1.

It satisfies the step rule (n+1)!=(n+1)⋅n!(n + 1)! = (n + 1) \cdot n! for every integer n≥1n \ge 1. In this course factorials are used only with nonnegative integer arguments. Expressions like (−1)!(-1)! or (12)!\left(\frac{1}{2}\right)! are not defined here.

In plain words Count down from nn to 11 and multiply everything you meet. Each factorial is the previous one times the next integer.

Example The first factorials grow fast.

nn11223344556677
n!n!112266242412012072072050405040

Each entry is the one before it times nn, for instance 6!=6⋅120=7206! = 6 \cdot 120 = 720.

Zero factorial

Definition By convention

0!=1.0! = 1.

This is the only choice that keeps the step rule (n+1)!=(n+1)⋅n!(n + 1)! = (n + 1) \cdot n! true at n=0n = 0, since that rule reads 1!=1⋅0!1! = 1 \cdot 0!. It also matches the idea that a product of no factors at all equals 11.

In plain words Zero factorial is one, not zero. It is set that way so the formulas that use factorials keep working at the start of the list.

Example The term formula 1n!\frac{1}{n!} for n≥0n \ge 0 starts with

10!=1,11!=1,12!=12,13!=16.\begin{gathered} \frac{1}{0!} = 1, \quad \frac{1}{1!} = 1, \\[0.4em] \frac{1}{2!} = \frac{1}{2}, \quad \frac{1}{3!} = \frac{1}{6}. \end{gathered}

If 0!0! were 00, the very first term would be undefined.

Factor cancellation

Definition For integers 0≤m≤n0 \le m \le n, the factorial n!n! contains m!m! as a factor,

n!=n(n−1)⋯(m+1)⋅m!,n! = n(n - 1) \cdots (m + 1) \cdot m!,

so the quotient n!m!\frac{n!}{m!} equals the product of the integers from m+1m + 1 up to nn (and equals 11 when m=nm = n). In particular (n+1)!n!=n+1\frac{(n + 1)!}{n!} = n + 1 and (n+2)!n!=(n+2)(n+1)\frac{(n + 2)!}{n!} = (n + 2)(n + 1) for n≥0n \ge 0. Factorial does not distribute over sums or products. The equations (n+1)!=n!+1(n + 1)! = n! + 1 and (2n)!=2⋅n!(2n)! = 2 \cdot n! are not identities. Each one happens to hold at n=1n = 1, where both sides equal 22, and fails at every other nonnegative integer nn.

In plain words Write the larger factorial as a chain down to the smaller one, then cancel the whole smaller factorial at once. Never cancel pieces inside the exclamation mark.

Example The ratio of consecutive terms of an=3nn!a_n = \dfrac{3^n}{n!} for n≥0n \ge 0 simplifies by writing (n+1)!=(n+1)⋅n!(n + 1)! = (n + 1) \cdot n!.

an+1an=3n+1(n+1)!⋅n!3n=3n+1.\frac{a_{n+1}}{a_n} = \frac{3^{n+1}}{(n + 1)!} \cdot \frac{n!}{3^n} = \frac{3}{n + 1}.

A doubled index needs two factors, since (2n+2)!=(2n+2)(2n+1)(2n)!(2n + 2)! = (2n + 2)(2n + 1)(2n)!. At n=2n = 2 that says 6!4!=6⋅5=30\frac{6!}{4!} = 6 \cdot 5 = 30, and indeed 72024=30\frac{720}{24} = 30. The tempting rewrite (2n)!=2⋅n!(2n)! = 2 \cdot n! already fails at n=2n = 2, where 4!=244! = 24 but 2⋅2!=42 \cdot 2! = 4.

Binomial coefficient

Definition For integers n≥0n \ge 0 and kk with 0≤k≤n0 \le k \le n, the binomial coefficient is

(nk)=n!k! (n−k)!.\binom{n}{k} = \frac{n!}{k!\,(n - k)!}.

After cancellation it can also be written with kk factors on top,

(nk)=n(n−1)⋯(n−k+1)k!,\binom{n}{k} = \frac{n(n - 1) \cdots (n - k + 1)}{k!},

with the empty product on top equal to 11 when k=0k = 0. For these nn and kk it is always a positive integer, and it is symmetric, (nk)=(nn−k)\binom{n}{k} = \binom{n}{n - k}. It is read as nn choose kk. This lesson uses (nk)\binom{n}{k} only in this range. Some books also set (nk)=0\binom{n}{k} = 0 for integers k<0k < 0 or k>nk > n, which matches counting zero ways to choose, but the factorial formula itself does not apply there.

In plain words It is a count, so both nn and kk are whole numbers that count things, and kk never exceeds nn.

Example Two ways to the same value.

(52)=5!2! 3!=1202⋅6=10,(52)=5⋅42⋅1=10.\begin{gathered} \binom{5}{2} = \frac{5!}{2!\,3!} = \frac{120}{2 \cdot 6} = 10, \\[0.4em] \binom{5}{2} = \frac{5 \cdot 4}{2 \cdot 1} = 10. \end{gathered}

At the ends, (60)=6!0! 6!=1\binom{6}{0} = \frac{6!}{0!\,6!} = 1, which uses 0!=10! = 1.

Choosing positions

Definition For integers 0≤k≤n0 \le k \le n, the number (nk)\binom{n}{k} equals the number of ways to choose a set of kk positions out of nn distinct positions, where the order of choosing does not matter.

In plain words Line up nn slots and mark kk of them. The binomial coefficient counts the different patterns of marks.

Example Write (x+1)4(x + 1)^4 as a product of four factors and number them.

(x+1)4=(x+1)(x+1) ⋅(x+1)(x+1).\begin{aligned} (x + 1)^4 &= (x + 1)(x + 1) \\ &\quad\ \cdot (x + 1)(x + 1). \end{aligned}

Multiplying out means picking either xx or 11 from each factor and multiplying the picks. A term x2x^2 arises exactly when two of the four factors give xx. The possible pairs of positions are {1,2}\{1, 2\}, {1,3}\{1, 3\}, {1,4}\{1, 4\}, {2,3}\{2, 3\}, {2,4}\{2, 4\} and {3,4}\{3, 4\}. That is six choices, and (42)=6\binom{4}{2} = 6, so the coefficient of x2x^2 is 66. The full product is x4+4x3+6x2+4x+1x^4 + 4x^3 + 6x^2 + 4x + 1.

Finite binomial expansion

Definition For every integer n≥0n \ge 0 and all real numbers aa and bb,

(a+b)n=∑k=0n(nk)an−kbk,(a + b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k,

where a0a^0 and b0b^0 are read as 11 even when aa or bb is zero. The term with bkb^k comes from choosing which kk of the nn factors supply bb, and the other n−kn - k supply aa.

In plain words Each term of the expansion records one way of splitting the factors between aa and bb, and the binomial coefficient counts how many ways give the same powers.

Example Take a=2xa = 2x and b=−3b = -3 with n=5n = 5. The coefficient of x2x^2 in (2x−3)5(2x - 3)^5 comes from the term where two factors give 2x2x and three give −3-3, which is the term with k=3k = 3. Keep the signs and the constants inside each choice.

(53)(2x)2(−3)3=10⋅4x2⋅(−27)=−1080x2.\begin{aligned} \binom{5}{3} (2x)^2 (-3)^3 &= 10 \cdot 4x^2 \cdot (-27) \\[0.4em] &= -1080x^2. \end{aligned}

So the coefficient is −1080-1080. Forgetting the 22 in (2x)2(2x)^2 or the sign in (−3)3(-3)^3 is the usual slip.

Integer conditions

Definition Everything in this lesson needs integers. A factorial n!n! requires an integer n≥0n \ge 0. The coefficient (nk)\binom{n}{k} is defined here only for integers with 0≤k≤n0 \le k \le n, and the finite expansion above holds only for exponents that are integers n≥0n \ge 0. For a negative or a fractional exponent there is no finite expansion, and the binomial series of calculus is the infinite replacement.

In plain words Before you use a factorial formula, check that every argument is a whole number and that nothing has slipped below zero.

Example Trying n!k! (n−k)!\frac{n!}{k!\,(n - k)!} with n=3n = 3 and k=5k = 5 would need (−2)!(-2)!, which is undefined, so (35)\binom{3}{5} is not given by this formula. Under the convention mentioned above it is 00, since there is no way to choose 55 positions out of 33. For the exponent −1-1 no finite expansion can exist either. As xx approaches −1-1, the values of

(1+x)−1=11+x(1 + x)^{-1} = \frac{1}{1 + x}

grow without bound, while every polynomial stays bounded near −1-1. So no polynomial equals (1+x)−1(1 + x)^{-1}, not even on its domain x≠−1x \ne -1.

Check yourself

  1. Simplify the consecutive-term ratio of an=2n(2n)!a_n = \dfrac{2^n}{(2n)!} for n≥0n \ge 0.
Show the answer

The shifted term has (2(n+1))!=(2n+2)!(2(n + 1))! = (2n + 2)! in the denominator, and (2n+2)!=(2n+2)(2n+1)(2n)!(2n + 2)! = (2n + 2)(2n + 1)(2n)!. So

an+1an=2n+1(2n+2)!⋅(2n)!2n=2(2n+2)(2n+1)=1(n+1)(2n+1).\begin{aligned} \frac{a_{n+1}}{a_n} &= \frac{2^{n+1}}{(2n + 2)!} \cdot \frac{(2n)!}{2^n} \\[0.4em] &= \frac{2}{(2n + 2)(2n + 1)} \\[0.4em] &= \frac{1}{(n + 1)(2n + 1)}. \end{aligned}

At n=0n = 0 this is 11, and indeed a0=a1=1a_0 = a_1 = 1.

  1. Find the coefficient of x3x^3 in (1+2x)6(1 + 2x)^6.
Show the answer

Three of the six factors must supply 2x2x, which can happen in (63)=20\binom{6}{3} = 20 ways, and each such choice contributes (2x)3=8x3(2x)^3 = 8x^3. The coefficient is 20⋅8=16020 \cdot 8 = 160.

  1. Compute (72)\binom{7}{2} with the product form and explain why (75)\binom{7}{5} has the same value.
Show the answer

The product form gives (72)=7⋅62=21\binom{7}{2} = \frac{7 \cdot 6}{2} = 21. Choosing 55 positions out of 77 is the same as choosing the 22 positions left out, so (75)=(72)=21\binom{7}{5} = \binom{7}{2} = 21.

How this lesson connects