The Central Idea
Suppose \(n\) distinct objects are available and we choose \(r\) of them, without repetition and without caring about order.
The number of possible selections is
\[ \boxed{\binom{n}{r}}. \]This number is called a binomial coefficient.
For example,
\[ \binom{5}{2}=10 \]because there are ten two-element subsets of a five-element set.
Reading the Notation
The expression
\[ \binom{n}{r} \]is read
\(n\) choose \(r\).
The top number \(n\) represents the size of the available collection.
The bottom number \(r\) represents how many objects are selected.
The Factorial Formula
For integers \(n\ge0\) and \(0\le r\le n\),
\[ \boxed{\binom{n}{r}=\frac{n!}{r!(n-r)!}}. \]This is the standard factorial formula for binomial coefficients.
Why the Formula Works
First count ordered selections:
\[ P(n,r)=\frac{n!}{(n-r)!}. \]But every group of \(r\) selected objects appears in
\[ r! \]different orders.
Divide by \(r!\):
\[ \binom{n}{r} = \frac{P(n,r)}{r!} = \boxed{\frac{n!}{r!(n-r)!}}. \]Example: Evaluate \(\binom{6}{2}\)
\[ \binom{6}{2} = \frac{6!}{2!4!}. \]Expand only as far as necessary:
\[ \frac{6\cdot5\cdot4!}{2\cdot4!}. \]Cancel \(4!\):
\[ \frac{6\cdot5}{2} = \boxed{15}. \]Example: Evaluate \(\binom{10}{4}\)
\[ \binom{10}{4} = \frac{10!}{4!6!}. \]Expand \(10!\) down to \(6!\):
\[ \frac{10\cdot9\cdot8\cdot7\cdot6!}{4!\cdot6!}. \]Cancel \(6!\):
\[ \frac{10\cdot9\cdot8\cdot7}{24}. \]Therefore,
\[ \boxed{\binom{10}{4}=210}. \]Cancel Before Multiplying
Binomial coefficients often simplify more efficiently when denominator factors are canceled before large products are evaluated.
For example,
\[ \binom{12}{3} = \frac{12\cdot11\cdot10}{3\cdot2\cdot1}. \]Cancel \(12/3=4\) and \(10/2=5\):
\[ 4\cdot11\cdot5 = \boxed{220}. \]The Product Form
The factorial formula can also be written
\[ \binom{n}{r} = \frac{n(n-1)(n-2)\cdots(n-r+1)}{r!}. \]This form contains exactly \(r\) descending factors in the numerator.
It is especially useful when \(r\) is small.
Example: A Large Top Number
Evaluate
\[ \binom{30}{3}. \]Use the product form:
\[ \binom{30}{3} = \frac{30\cdot29\cdot28}{3!}. \]Therefore,
\[ \boxed{\binom{30}{3}=4060}. \]Boundary Value: \(\binom{n}{0}\)
There is exactly one way to choose nothing from \(n\) objects.
Therefore,
\[ \boxed{\binom{n}{0}=1}. \]The factorial formula confirms this:
\[ \binom{n}{0} = \frac{n!}{0!n!} = 1. \]Boundary Value: \(\binom{n}{n}\)
There is exactly one way to choose every available object.
Thus,
\[ \boxed{\binom{n}{n}=1}. \]Choosing One Object
There are \(n\) ways to choose one object from \(n\).
Therefore,
\[ \boxed{\binom{n}{1}=n}. \]Leaving Out One Object
Choosing \(n-1\) objects is equivalent to deciding which single object is excluded.
Therefore,
\[ \boxed{\binom{n}{n-1}=n}. \]Symmetry
One of the most important identities is
\[ \boxed{\binom{n}{r}=\binom{n}{n-r}}. \]Choosing \(r\) objects automatically determines the \(n-r\) objects that were not chosen.
Why Symmetry Works Algebraically
\[ \binom{n}{r} = \frac{n!}{r!(n-r)!}. \]Replacing \(r\) by \(n-r\) gives
\[ \binom{n}{n-r} = \frac{n!}{(n-r)![n-(n-r)]!}. \]Since
\[ n-(n-r)=r, \]we obtain
\[ \binom{n}{n-r} = \frac{n!}{(n-r)!r!} = \binom{n}{r}. \]Example: Use Symmetry
Evaluate
\[ \binom{20}{18}. \]Symmetry gives
\[ \binom{20}{18} = \binom{20}{2}. \]Then
\[ \binom{20}{2} = \frac{20\cdot19}{2} = \boxed{190}. \]Binomial Coefficients Count Subsets
If a set has \(n\) elements, then
\[ \boxed{\binom{n}{r}} \]counts its subsets containing exactly \(r\) elements.
This interpretation is one of the most useful ways to understand binomial identities.
Example: Four-Element Subsets
A set has \(9\) elements.
The number of four-element subsets is
\[ \binom{9}{4} = \boxed{126}. \]All Subset Sizes Together
An \(n\)-element set has
\[ \binom{n}{0} \]subsets of size \(0\),
\[ \binom{n}{1} \]subsets of size \(1\), and so on through
\[ \binom{n}{n}. \]Therefore, the total number of subsets is
\[ \sum_{r=0}^{n}\binom{n}{r}. \]The Row-Sum Identity
Every element of an \(n\)-element set has two possibilities:
- included in a subset;
- excluded from the subset.
Therefore, the set has
\[ 2^n \]total subsets.
Hence,
\[ \boxed{\sum_{r=0}^{n}\binom{n}{r}=2^n}. \]Example: Row Sum for \(n=5\)
\[ \binom{5}{0} + \binom{5}{1} + \binom{5}{2} + \binom{5}{3} + \binom{5}{4} + \binom{5}{5}. \]The values are
\[ 1+5+10+10+5+1. \]Therefore,
\[ 1+5+10+10+5+1=32=2^5. \]Pascal's Identity
Another fundamental identity is
\[ \boxed{ \binom{n}{r} = \binom{n-1}{r} + \binom{n-1}{r-1} }. \]This recurrence generates the interior entries of Pascal's triangle.
Combinatorial Proof of Pascal's Identity
Suppose we choose \(r\) objects from \(n\), and focus on one particular object \(A\).
Every \(r\)-element selection belongs to exactly one of two cases.
Case 1: \(A\) is excluded.
\[ \binom{n-1}{r}. \]Case 2: \(A\) is included.
Then choose the remaining \(r-1\) objects from the other \(n-1\):
\[ \binom{n-1}{r-1}. \]Adding the disjoint cases gives Pascal's identity.
Example: Pascal's Identity
\[ \binom{8}{3} = \binom{7}{3} + \binom{7}{2}. \]Since
\[ \binom{7}{3}=35 \]and
\[ \binom{7}{2}=21, \]we obtain
\[ \boxed{\binom{8}{3}=56}. \]Algebraic Verification of Pascal's Identity
Start with
\[ \binom{n-1}{r} + \binom{n-1}{r-1}. \]Using factorials,
\[ \frac{(n-1)!}{r!(n-r-1)!} + \frac{(n-1)!}{(r-1)!(n-r)!}. \]Rewrite both terms over the common denominator
\[ r!(n-r)!. \]This gives
\[ \frac{(n-r)(n-1)!+r(n-1)!}{r!(n-r)!}. \]Factor:
\[ \frac{[(n-r)+r](n-1)!}{r!(n-r)!}. \]Since \((n-r)+r=n\),
\[ \frac{n(n-1)!}{r!(n-r)!} = \frac{n!}{r!(n-r)!} = \boxed{\binom{n}{r}}. \]Binomial Coefficients Form Symmetric Rows
For fixed \(n\), the sequence
\[ \binom{n}{0}, \binom{n}{1}, \ldots, \binom{n}{n} \]reads the same forward and backward because
\[ \binom{n}{r} = \binom{n}{n-r}. \]For \(n=6\), the row is
\[ 1,\ 6,\ 15,\ 20,\ 15,\ 6,\ 1. \]Where the Largest Coefficients Occur
Binomial coefficients in a fixed row increase toward the middle and then decrease symmetrically.
When \(n\) is even, the largest coefficient occurs at
\[ r=\frac{n}{2}. \]When \(n\) is odd, the two middle coefficients are equal and largest.
Comparing Consecutive Coefficients
A useful ratio is
\[ \frac{\binom{n}{r+1}}{\binom{n}{r}}. \]Using factorial formulas,
\[ \frac{\binom{n}{r+1}}{\binom{n}{r}} = \frac{n-r}{r+1}. \]Therefore,
\[ \boxed{ \binom{n}{r+1} = \binom{n}{r}\frac{n-r}{r+1} }. \]Using the Consecutive-Coefficient Ratio
Suppose
\[ \binom{10}{3}=120. \]Then
\[ \binom{10}{4} = \binom{10}{3}\frac{10-3}{4}. \]Therefore,
\[ \binom{10}{4} = 120\cdot\frac{7}{4} = \boxed{210}. \]A Rearranged Identity
From
\[ \binom{n}{r} = \frac{n!}{r!(n-r)!}, \]we can derive
\[ \boxed{ r\binom{n}{r} = n\binom{n-1}{r-1} }. \]Both sides count a selection of \(r\) objects together with one distinguished selected object.
Combinatorial Meaning of \(r\binom{n}{r}\)
First choose an \(r\)-element subset:
\[ \binom{n}{r}. \]Then choose one distinguished object from the \(r\) selected objects:
\[ r. \]The total is
\[ r\binom{n}{r}. \]Combinatorial Meaning of \(n\binom{n-1}{r-1}\)
Alternatively, first choose the distinguished object from all \(n\) objects:
\[ n. \]Then choose the remaining \(r-1\) selected objects from the other \(n-1\):
\[ \binom{n-1}{r-1}. \]The same objects are counted, so
\[ \boxed{ r\binom{n}{r} = n\binom{n-1}{r-1} }. \]Another Useful Identity
Similarly,
\[ \boxed{ (n-r)\binom{n}{r} = n\binom{n-1}{r} }. \]This identity can be interpreted by distinguishing one object that is not selected.
The Alternating Row Sum
For \(n\ge1\),
\[ \boxed{ \sum_{r=0}^{n}(-1)^r\binom{n}{r}=0 }. \]Written out,
\[ \binom{n}{0} - \binom{n}{1} + \binom{n}{2} -\cdots+ (-1)^n\binom{n}{n} = 0. \]Even-Size and Odd-Size Subsets
For an \(n\)-element set with \(n\ge1\), exactly half of all subsets have even size and half have odd size.
Since there are \(2^n\) total subsets,
\[ \boxed{ \sum_{\substack{r=0\\r\text{ even}}}^{n}\binom{n}{r} = \sum_{\substack{r=0\\r\text{ odd}}}^{n}\binom{n}{r} = 2^{n-1} }. \]Subtracting the two equal totals gives the alternating row sum \(0\).
Example: Even and Odd Subsets of a Four-Element Set
Even-sized subsets:
\[ \binom{4}{0}+\binom{4}{2}+\binom{4}{4} = 1+6+1 = 8. \]Odd-sized subsets:
\[ \binom{4}{1}+\binom{4}{3} = 4+4 = 8. \]Both equal
\[ 2^{4-1}=8. \]The Hockey-Stick Identity
Another recurring identity is
\[ \boxed{ \binom{r}{r} + \binom{r+1}{r} + \binom{r+2}{r} +\cdots+ \binom{n}{r} = \binom{n+1}{r+1} }. \]Its pattern becomes especially visible in Pascal's triangle.
Example: Hockey-Stick Identity
\[ \binom{2}{2} + \binom{3}{2} + \binom{4}{2} + \binom{5}{2} = \binom{6}{3}. \]The left side is
\[ 1+3+6+10=20. \]The right side is
\[ \binom{6}{3}=20. \]A Combinatorial View of the Hockey-Stick Identity
Consider choosing \(r+1\) objects from
\[ \{1,2,\ldots,n+1\}. \]Classify each selection according to its largest selected element.
If the largest element is \(k+1\), then the remaining \(r\) selected elements must come from
\[ \{1,2,\ldots,k\}, \]giving
\[ \binom{k}{r} \]possibilities.
Summing over all possible largest elements yields the identity.
Vandermonde's Identity
If two disjoint groups contain \(m\) and \(n\) objects, then choosing \(r\) objects from the combined collection gives
\[ \boxed{ \binom{m+n}{r} = \sum_{k=0}^{r} \binom{m}{k}\binom{n}{r-k} }. \]Terms with impossible selections are interpreted as zero.
Why Vandermonde's Identity Works
Choose \(r\) objects from two groups.
If exactly \(k\) selected objects come from the first group, then
\[ \binom{m}{k} \]choices are available there, while
\[ \binom{n}{r-k} \]choices are available from the second group.
Multiply within each case and add across the possible values of \(k\).
Example: Vandermonde's Identity
Suppose a group contains \(4\) engineers and \(5\) designers, and we choose \(3\) people.
Directly,
\[ \binom{9}{3}=84. \]By category count,
\[ \binom{4}{0}\binom{5}{3} + \binom{4}{1}\binom{5}{2} + \binom{4}{2}\binom{5}{1} + \binom{4}{3}\binom{5}{0}. \]This gives
\[ 10+40+30+4 = \boxed{84}. \]Binomial Coefficients and Repeated Objects
Suppose a sequence contains \(r\) identical \(A\)'s and \(n-r\) identical \(B\)'s.
The number of distinguishable arrangements is
\[ \frac{n!}{r!(n-r)!}. \]Therefore,
\[ \boxed{ \frac{n!}{r!(n-r)!} = \binom{n}{r} }. \]Choosing the positions of the \(A\)'s produces the same count.
Example: Binary Strings with Fixed Weight
How many binary strings of length \(10\) contain exactly four \(1\)'s?
Choose the four positions that contain \(1\)'s:
\[ \binom{10}{4}. \]Therefore,
\[ \boxed{210}. \]Hamming Weight
In a binary string, the number of \(1\)'s is often called its Hamming weight.
The number of length-\(n\) binary strings with Hamming weight \(r\) is
\[ \boxed{\binom{n}{r}}. \]This gives another direct interpretation of binomial coefficients.
Binomial Coefficients and Lattice Paths
Suppose a shortest path uses \(a\) rightward steps and \(b\) upward steps.
The path contains
\[ a+b \]steps total.
Choose which \(a\) positions are rightward steps:
\[ \boxed{\binom{a+b}{a}}. \]By symmetry, this equals
\[ \binom{a+b}{b}. \]Example: Grid Paths
A shortest route uses \(5\) steps right and \(4\) steps up.
There are \(9\) total steps.
Choose which five are rightward:
\[ \binom{9}{5} = \boxed{126}. \]Binomial Coefficients and Probability
Suppose an experiment consists of \(n\) trials, and exactly \(r\) of them are successes.
The number of ways to choose which trials are the successes is
\[ \boxed{\binom{n}{r}}. \]This counting factor is why binomial coefficients appear in the binomial probability distribution.
Example: Exactly Three Successes
In five trials, the number of success-failure sequences containing exactly three successes is
\[ \binom{5}{3} = \boxed{10}. \]Each sequence corresponds to choosing which three trial positions contain successes.
Binomial Coefficients and the Binomial Theorem
The name binomial coefficient comes from expansions of a binomial:
\[ (x+y)^n. \]The coefficient of
\[ x^{n-r}y^r \]is
\[ \boxed{\binom{n}{r}}. \]A later lesson will develop the full binomial theorem.
Why the Coefficients Appear
Write
\[ (x+y)^n = (x+y)(x+y)\cdots(x+y). \]To obtain a term containing exactly \(r\) copies of \(y\), choose which \(r\) of the \(n\) factors contribute \(y\).
There are
\[ \binom{n}{r} \]ways to make that selection.
Every such choice produces the same monomial
\[ x^{n-r}y^r. \]Example: Coefficients of \((x+y)^5\)
The coefficients are
\[ \binom{5}{0}, \binom{5}{1}, \binom{5}{2}, \binom{5}{3}, \binom{5}{4}, \binom{5}{5}. \]Therefore, they are
\[ \boxed{1,\ 5,\ 10,\ 10,\ 5,\ 1}. \]Recursive Computation
Binomial coefficients can be computed recursively from
\[ \binom{n}{0}=1, \qquad \binom{n}{n}=1, \]together with Pascal's identity:
\[ \binom{n}{r} = \binom{n-1}{r} + \binom{n-1}{r-1}. \]This approach avoids direct factorial calculations and produces Pascal's triangle naturally.
Example: Recursive Calculation
Suppose we know
\[ \binom{6}{2}=15 \]and
\[ \binom{6}{3}=20. \]Then
\[ \binom{7}{3} = \binom{6}{3} + \binom{6}{2} = 20+15 = \boxed{35}. \]Binomial Coefficients Are Integers
The factorial formula
\[ \frac{n!}{r!(n-r)!} \]may look like an arbitrary fraction, but its value is always an integer for \(0\le r\le n\).
The reason is combinatorial: it counts actual finite collections of subsets.
Counting interpretations often reveal integrality more directly than algebra alone.
Outside the Basic Range
In elementary combinatorics, it is often convenient to define
\[ \binom{n}{r}=0 \]when \(r<0\) or \(r>n\).
This convention expresses the fact that it is impossible to choose a negative number of objects or more distinct objects than are available.
It also makes many identities easier to write without special boundary cases.
Example: Impossible Selection
Choosing \(7\) distinct objects from a set of \(5\) is impossible.
Therefore, under the standard combinatorial convention,
\[ \boxed{\binom{5}{7}=0}. \]Combinatorial Identities as Double Counting
Many binomial identities can be proved by counting the same collection of objects in two different ways.
This technique is called double counting.
If two expressions count exactly the same finite set, then the expressions must be equal.
Example of Double Counting
The identity
\[ r\binom{n}{r} = n\binom{n-1}{r-1} \]counts pairs consisting of:
- an \(r\)-element subset;
- one distinguished member of that subset.
Choosing the subset first gives the left side.
Choosing the distinguished member first gives the right side.
Why Combinatorial Proofs Matter
Algebraic manipulation can verify an identity, but a combinatorial proof explains why the identity exists.
It connects symbolic formulas to structures such as:
- subsets;
- distinguished elements;
- category choices;
- paths;
- binary strings;
- success-failure patterns.
These structural explanations are central to discrete mathematics.
Common Error: Reversing \(n\) and \(r\)
In
\[ \binom{n}{r}, \]the top number \(n\) is the number available.
The bottom number \(r\) is the number selected.
For example, choosing \(3\) from \(8\) is
\[ \boxed{\binom{8}{3}}, \]not
\[ \binom{3}{8}. \]Common Error: Forgetting the \(r!\) Correction
The expression
\[ \frac{n!}{(n-r)!} \]counts permutations, not combinations.
To remove the \(r!\) internal orders of each selected group, divide by
\[ r!. \]Thus,
\[ \boxed{ \binom{n}{r} = \frac{n!}{r!(n-r)!} }. \]Common Error: Treating Symmetry as \(\binom{n}{r}=\binom{r}{n}\)
The symmetry identity does not exchange the top and bottom numbers.
The correct identity is
\[ \boxed{ \binom{n}{r} = \binom{n}{n-r} }. \]The available total \(n\) stays fixed.
Common Error: Expanding Large Factorials
To evaluate
\[ \binom{50}{2}, \]do not calculate \(50!\).
Use
\[ \binom{50}{2} = \frac{50\cdot49}{2} = \boxed{1225}. \]Common Error: Applying the Formula to Ordered Outcomes
Binomial coefficients count unordered selections.
If distinct positions or ranks are assigned, a permutation model may be required instead.
Choosing three committee members from eight uses
\[ \binom{8}{3}, \]while assigning president, vice president, and secretary uses
\[ P(8,3). \]Common Error: Ignoring Impossible Values
The basic factorial formula assumes
\[ 0\le r\le n. \]If \(r>n\), there is no valid distinct-object selection.
Under the standard combinatorial convention,
\[ \boxed{\binom{n}{r}=0}. \]A Reliable Procedure for Evaluating Binomial Coefficients
- Identify \(n\) and \(r\).
- Check that \(0\le r\le n\).
- Use symmetry if \(n-r\) is smaller than \(r\).
- Write the factorial or product form.
- Expand only as far as necessary.
- Cancel factors before multiplying large numbers.
- Verify that the result is a nonnegative integer.
A Reliable Procedure for Proving Binomial Identities
- Look first for a counting interpretation.
- Identify one finite collection counted by both sides.
- Explain how the left side counts it.
- Explain how the right side counts it.
- Use disjoint cases when terms are added.
- Use sequential choices when factors are multiplied.
- Use algebraic verification as a secondary check when useful.
Example: Full Evaluation Workflow
Evaluate
\[ \binom{25}{22}. \]Use symmetry:
\[ \binom{25}{22} = \binom{25}{3}. \]Use the product form:
\[ \binom{25}{3} = \frac{25\cdot24\cdot23}{3\cdot2\cdot1}. \]Cancel:
\[ 25\cdot4\cdot23. \]Therefore,
\[ \boxed{\binom{25}{22}=2300}. \]Practice 1: Basic Coefficient
Evaluate:
\[ \binom{8}{3}. \]Practice 2: Use Symmetry
Evaluate:
\[ \binom{14}{12}. \]Practice 3: Boundary Value
Evaluate:
\[ \binom{19}{0}. \]Practice 4: Pascal's Identity
Use Pascal's identity to evaluate
\[ \binom{9}{4} \]from
\[ \binom{8}{4}=70 \]and
\[ \binom{8}{3}=56. \]Practice 5: Row Sum
Evaluate:
\[ \sum_{r=0}^{7}\binom{7}{r}. \]Practice 6: Alternating Row Sum
Evaluate:
\[ \sum_{r=0}^{6}(-1)^r\binom{6}{r}. \]Practice 7: Binary Strings
How many binary strings of length \(12\) contain exactly five \(1\)'s?
Practice 8: Grid Paths
How many shortest paths use \(6\) steps right and \(4\) steps up?
Practice 9: Hockey-Stick Identity
Evaluate:
\[ \binom{3}{3} + \binom{4}{3} + \binom{5}{3} + \binom{6}{3}. \]Practice 10: Identify the Error
A student writes
\[ \binom{10}{3} = \frac{10!}{7!} = 720. \]Explain what factor is missing and give the correct value.
Practice Answers
Practice 1
\[ \binom{8}{3} = \frac{8\cdot7\cdot6}{3!} = \frac{336}{6} = \boxed{56}. \]Practice 2
Use symmetry:
\[ \binom{14}{12} = \binom{14}{2} = \frac{14\cdot13}{2} = \boxed{91}. \]Practice 3
\[ \boxed{\binom{19}{0}=1}. \]Practice 4
\[ \binom{9}{4} = \binom{8}{4} + \binom{8}{3} = 70+56 = \boxed{126}. \]Practice 5
Use the row-sum identity:
\[ \sum_{r=0}^{7}\binom{7}{r} = 2^7 = \boxed{128}. \]Practice 6
For \(n\ge1\), the alternating row sum is zero:
\[ \boxed{0}. \]Practice 7
Choose the five positions containing \(1\)'s:
\[ \binom{12}{5} = \boxed{792}. \]Practice 8
There are ten total steps. Choose the six rightward positions:
\[ \binom{10}{6} = \binom{10}{4} = \boxed{210}. \]Practice 9
By the hockey-stick identity,
\[ \binom{3}{3} + \binom{4}{3} + \binom{5}{3} + \binom{6}{3} = \binom{7}{4}. \]Therefore,
\[ \boxed{\binom{7}{4}=35}. \]Practice 10
The expression
\[ \frac{10!}{7!} \]counts ordered selections of three objects.
A combination must also divide by
\[ 3!. \]Therefore,
\[ \binom{10}{3} = \frac{10!}{3!7!} = \frac{10\cdot9\cdot8}{6} = \boxed{120}. \]What to Remember
Binomial coefficients are the numbers
\[ \boxed{\binom{n}{r}=\frac{n!}{r!(n-r)!}}. \]They count \(r\)-element subsets of an \(n\)-element set.
Core identities include
\[ \boxed{\binom{n}{r}=\binom{n}{n-r}} \]and
\[ \boxed{ \binom{n}{r} = \binom{n-1}{r} + \binom{n-1}{r-1} }. \]Summing a full row gives
\[ \boxed{ \sum_{r=0}^{n}\binom{n}{r}=2^n }. \]Binomial coefficients appear in subsets, binary strings, repeated-object arrangements, lattice paths, probability, Pascal's triangle, and binomial expansions.
Their real power comes from recognizing that many apparently different problems share the same underlying counting structure.
Where We Go Next
Binomial coefficients do not occur as isolated numbers. When arranged by their top index \(n\), they form a highly structured triangular array.
The next lesson, Pascal's Triangle, develops that array directly and shows how symmetry, recursion, row sums, diagonals, and other binomial patterns become visible geometrically.