Evanalysis
4.1Estimated reading time: 7 min

4.1 Binomial coefficients and expansions

Connect permutations, combinations, Pascal's identity, and the binomial theorem.

Course contents

MATH1025: Preparatory mathematics

Preparatory mathematics notes.

Language

ENEnglish繁Traditional Chinese简Simplified Chinese
All note collectionsSeries overview
0-12-34
Chapter 0-1Foundations and early methods2 sections
0.10.1 Course foundations and notation1.11.1 Equation structure and trigonometric identities
Chapter 2-3Proof and inequalities2 sections
2.12.1 Mathematical induction3.13.1 Inequalities and absolute value
Chapter 4Binomial theorem1 sections
4.14.1 Binomial coefficients and expansionsCurrent section

Counting before expanding

The binomial theorem is often remembered as a formula, but the formula is a counting statement. When expanding (x+y)n(x+y)^n, each term comes from choosing either x or y from each of the n factors. The coefficient records how many different choices lead to the same power of x and the same power of y.

That is why factorials and combinations appear before the theorem.

Factorials, permutations, and combinations

Definition

Factorial

For a positive integer n,

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

By convention, 0!=10! = 1.

Definition

Permutation

A k-permutation of n distinct objects is an ordered arrangement of k of those objects. The number of such arrangements is

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

Order matters for permutations. Choosing A,B,C and choosing C,B,A are different ordered arrangements.

Definition

Binomial coefficient

For integers 0≤k≤n0\le k\le n,

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

It counts the number of k-element subsets of an n-element set.

Order does not matter for combinations. The factor k! in the denominator removes the internal ordering of the selected objects.

Worked example

Arrange objects with a restriction

Suppose m girls and n boys are seated in a row, with m>nm>n, and no two boys may sit together.

First arrange the m girls. This can be done in m! ways. The girls create m+1m+1 possible gaps where boys may be placed: before the first girl, between two consecutive girls, or after the last girl.

Choose and order n of those gaps for the boys:

P(m+1,n)=(m+1)!(m+1−n)!.P(m+1,n)=\frac{(m+1)!}{(m+1-n)!}.

Thus the total number of arrangements is

m! P(m+1,n)=m!(m+1)!(m+1−n)!.m!\,P(m+1,n)=m!\frac{(m+1)!}{(m+1-n)!}.

Pascal's identity

Theorem

Basic binomial identities

For 0≤k≤n0\le k\le n,

(n0)=(nn)=1,(nk)=(nn−k).\binom{n}{0}=\binom{n}{n}=1, \qquad \binom{n}{k}=\binom{n}{n-k}.

For 0≤k≤n−10\le k\le n-1,

(nk)+(nk+1)=(n+1k+1).\binom{n}{k}+\binom{n}{k+1}=\binom{n+1}{k+1}.

The last identity is Pascal's identity. It explains why the entries of Pascal's triangle are obtained by adding the two entries above.

Proof

Algebraic proof of Pascal's identity

Worked example

Lattice paths

How many paths go from (0,0) to (5,3) if each step is either one unit right or one unit up?

The path has 8 steps total: 5 right steps and 3 up steps. Choosing which 5 of the 8 steps are right determines the path, so the number is

(85).\binom{8}{5}.

The binomial theorem

Theorem

Binomial theorem

For every positive integer n,

(x+y)n=∑k=0n(nk)xn−kyk.(x+y)^n=\sum_{k=0}^n \binom{n}{k}x^{n-k}y^k.

The term with yky^k occurs when y is chosen from exactly k of the n factors, and x is chosen from the remaining n−kn-k factors. There are (nk)\binom{n}{k} ways to choose those k factors.

Worked example

Expand a small power

For n=3n=3,

(x+y)3=x3+3x2y+3xy2+y3.(x+y)^3=x^3+3x^2y+3xy^2+y^3.

The coefficient 3 in front of x2yx^2y appears because exactly one of the three factors contributes y, and there are (31)=3\binom31=3 choices.

Coefficient extraction

The binomial theorem is especially useful when only one term is needed.

Worked example

Find a constant term

Find the constant term of

(x3−1x)9.\left(x^3-\frac{1}{x}\right)^9.

The general term is

(9k)(x3)9−k(−1x)k=(9k)(−1)kx27−4k.\binom{9}{k}(x^3)^{9-k}\left(-\frac1x\right)^k =\binom{9}{k}(-1)^k x^{27-4k}.

The exponent is zero when 27−4k=027-4k=0, which has no integer solution. Therefore this expansion has no constant term.

The method is more important than this particular answer:

  1. write the general term;
  2. compute the exponent of the variable;
  3. solve for the exponent required by the question;
  4. check whether the resulting k is an integer in the range 0≤k≤n0\le k\le n.

Common mistake

The binomial index must be an integer in range

Solving for a desired exponent may produce a non-integer or an integer outside 0,…,n0,\dots,n. In that case the requested term does not appear.

Quick checks

Quick check

Why is C(n,k) divided by k! while P(n,k) is not?

Compare ordered and unordered selection.

Solution

Answer

Quick check

How many paths go from (0,0) to (4,2) using only right and up steps?

Count the right-step positions.

Solution

Answer

Quick check

What is the coefficient of xn−2y2x^{n-2}y^2 in (x+y)n(x+y)^n?

Use the binomial theorem.

Solution

Answer

Exercises

  1. Compute (73)\binom{7}{3} and explain its counting meaning.
  2. Prove (nk)=(nn−k)\binom{n}{k}=\binom{n}{n-k} using the factorial formula.
  3. Find the coefficient of x4x^4 in (2x−3)6(2x-3)^6.
  4. Find the coefficient of x0x^0 in (x^2+1/x)^6.

Guided solutions

  1. (73)=35\binom73=35. It counts the number of three-element subsets of a seven-element set.
  2. Substitute into the formula: \binom{n}{n-k}=n!/((n-k)!k!)=\binom nk.
  3. The general term is (6k)(2x)6−k(−3)k\binom6k(2x)^{6-k}(-3)^k. To get x4x^4, set 6−k=46-k=4, so k=2k=2. The coefficient is (62)24(−3)2=2160\binom62 2^4(-3)^2=2160.
  4. The general term is (6k)(x2)6−kx−k=(6k)x12−3k\binom6k(x^2)^{6-k}x^{-k}=\binom6k x^{12-3k}. Set 12−3k=012-3k=0, so k=4k=4. The coefficient is (64)=15\binom64=15.

Prerequisites

2.1

2.1 Mathematical induction

Key terms in this unit

More notes in this series

Previous section

3.1 Inequalities and absolute value

Next section