6.4 The Binomial Theorem and Inclusion–Exclusion

This section brings together the chapter’s main ideas:

• the product principle counts choices made across stages;

• combinations count which positions receive one type of choice;

• the sum principle combines disjoint cases;

• overlap must be corrected to avoid repeated counting.

We first use these ideas to expand powers, then to count unions of overlapping sets.

Why binomial coefficients appear in powers

A binomial is an expression with two terms, such as $x+y$. Consider

To create one term in the expanded product, choose either $x$ or $y$ from each factor.

There are $2$ choices from each of $3$ factors, so the product principle gives

raw selections.

For example:

Three different selections produce $x^2y$, because we choose which one of the three factors supplies $y$:

Similarly, three selections produce $xy^2$:

Therefore

The binomial theorem

In

suppose exactly $k$ of the $n$ factors contribute $y$. The other $n-k$ factors contribute $x$, producing

We can choose the $k$ positions for $y$ in

ways. Summing over all possible $k$ gives the binomial theorem:

In many Chinese textbooks, the same coefficient is written $C_n^k$ instead of $\binom nk$. The theorem is identical:

Expanded, this is

Example: expanding $(a+b)^4$

The coefficients are

Thus

Check each term:

• exponents add to $4$;

• the exponent of $b$ increases from $0$ to $4$;

• the coefficient counts positions that supplied $b$.

Pascal’s identity

Binomial coefficients satisfy

To prove it, choose a $k$-element committee from $n$ people and focus on one distinguished person, Ada.

Every committee belongs to exactly one disjoint case:

1. Ada is included. Choose the remaining $k-1$ members from $n-1$ people:

2. Ada is excluded. Choose all $k$ members from the other $n-1$ people:

Adding the two cases proves the identity.

Arranging coefficients in rows produces Pascal’s triangle:

Each interior entry is the sum of the two entries above it.

A useful sum of coefficients

Set $x=1$ and $y=1$ in the binomial theorem:

Therefore

This also counts all subsets of an $n$-element set by grouping them according to size $k$. The left side adds the number of subsets of every possible size; the right side is the power-set count from Section 6.1.

Choose factors from $(x+y)^n$ and watch raw selection strings fuse into like terms. The coefficient forge grows Pascal rows by animated parent sums, while any selected cell reveals its committee split and its exact monomial contribution.

Inclusion–exclusion for two sets

Return to the overlap problem from Section 6.1. For finite sets $A$ and $B$, adding

counts every element in $A\cap B$ twice: once as a member of $A$ and once as a member of $B$.

Subtract the intersection once:

This is the inclusion–exclusion principle for two sets.

Example: students in two clubs

Among a group of students:

join the music club,

join the drama club, and

join both.

The number joining at least one club is

The number in music only is

and drama only is

The union can be checked from disjoint regions:

Counting neither by using a complement

Suppose the universal set $U$ contains $50$ students. If $40$ join at least one club, then the number joining neither is

This uses the complement rule

Words should be translated carefully:

• “at least one” means a union;

• “both” means an intersection;

• “only $A$” means $A\setminus B$;

• “neither” means the complement of the union;

• “exactly one” means the union of the two only-regions.

Inclusion–exclusion for three sets

For finite sets $A,B,C$, begin by adding all three sizes:

An element in a pairwise intersection is now counted twice, so subtract all three pairwise intersections:

But an element in $A\cap B\cap C$ was:

• added $3$ times;

• subtracted $3$ times;

and is therefore currently counted $0$ times. Add the triple intersection once:

The alternating signs correct repeated counts.

A three-set example

In a survey of $100$ people:

and

Then

Therefore

people belong to none of the three sets.

Region checks prevent interpretation errors

The number $|A\cap B|$ normally includes elements also in $C$. It is not the “$A$ and $B$ only” region unless the problem explicitly says so.

The $A\cap B$ only-region is

In the example, that value is

When a problem gives several overlap counts, fill the deepest intersection first and work outward. This prevents subtracting the triple-overlap population inconsistently.

Populate a three-set survey by painting region counts rather than only totals. The scanner reconstructs every marginal and intersection, visualizes how each inclusion–exclusion pass changes an element’s multiplicity, and flags impossible data before calculating the union.

Chapter bridge

Chapter 6 built a counting toolkit: add disjoint cases, multiply stages, translate by bijection, distinguish permutations from combinations, prove forced collisions, expand binomials, and correct overlap.

Chapter 7 will define objects recursively and study recurrence relations. Counting will reappear there because many recursive structures are formed by smaller choices whose counts satisfy equations from one size to the next.