Motivation
Many counting problems ask how many ways there are to choose some objects from a larger collection when the order of choice does not matter. Examples include committees drawn from a group of people, positions in a binary string that hold a , and factors in a product that contribute a particular variable. These questions have the same mathematical shape. Each asks for the number of subsets of a given size.
This chapter defines binomial coefficients directly as such counts. The factorial formula is then a theorem that we prove, not a definition. This choice matters because every identity below is first a statement about sets. Each proof exhibits a bijection, a split into disjoint cases, or two ways of counting one collection. Algebraic manipulation is used only when it follows from these counts.
Throughout, denotes the set , with . For a finite set , is its number of elements. We use two basic counting principles:
- Sum rule. If a finite set is a union of pairwise disjoint pieces, its size is the sum of the sizes of the pieces.
- Product rule. If a selection is made in stages and the number of options at each stage does not depend on earlier choices, the total number of selections is the product of these numbers.
Definitions
Definition 2.5.1
(Binomial coefficient)
Let and let be any integer. Fix a set with . The binomial coefficient , also written , is the number of subsets with . Such a subset is called a -subset of .
Two remarks make this definition precise.
First, the number does not depend on which -set we fix. A bijection sends -subsets of to -subsets of by , and reverses this. We may therefore always use .
Second, the definition allows every integer . A subset of an -set cannot have negative size or size greater than . Hence
This is the out-of-range zero convention. Here it is a consequence of the definition, not an extra rule. It lets us write sums over all integers without boundary cases, since only finitely many terms are nonzero.
Definition 2.5.2
(Factorials and falling products)
For , is the product . When this is the empty product, which equals , so . For , the falling product has exactly factors. When it is the empty product, which equals .
Theorem 2.5.3
(Factorial formula)
For integers ,
Proof
(Counting ordered selections)
Let be the set of ordered -tuples of distinct elements of . We count in two ways.
Directly. Choose in ways. Then choose in ways, because it must differ from . Continue in this way until is chosen in ways. By the product rule,
The last equality holds because .
Through subsets. Send each tuple to its set of entries . Because the entries are distinct, this is a -subset. Conversely, every -subset arises from exactly those tuples that list the elements of in some order. By the product rule, there are such orderings. So the tuples split into disjoint groups, each of size . By the sum rule, .
Comparing the two counts gives . Dividing by the positive integer proves the formula. This division takes place in the rational numbers, where it is legitimate.
Edge cases. If , the set contains exactly one element, the empty tuple. It corresponds to the single -subset . Both counts equal , matching . If , then is forced, and , because has exactly one subset, namely itself. The argument above covers both cases without modification.
Theorem 2.5.4
(Symmetry)
For and every integer , .
Proof
(Complements)
The map sends a -subset to an -subset. Applying it twice returns the original set, so it is a bijection between -subsets and -subsets. If or , then or respectively, so both sides are . The bijection statement still holds in that case, as a bijection between two empty families.
Theorem 2.5.5
(Pascal's rule)
For and every integer ,
Proof
(A distinguished element)
Count the -subsets of , using as the distinguished element. Every such falls into exactly one of two cases.
- . Then is a -subset of . Conversely, every -subset of is such an . This case contributes subsets.
- . Removing gives the -subset of . The inverse map is . This case contributes subsets.
The cases are disjoint, because an element cannot be both in and not in . They are also exhaustive. The sum rule gives the identity.
Boundary values. The bijections remain valid when a family is empty, but it helps to check the extreme cases directly.
- If , all three terms are .
- If , the identity reads . The only -subset avoids , and no subset of size exists.
- If , it reads . The full set contains .
- If , all terms are .
The binomial theorem
Let be a commutative ring with identity . For and a nonnegative integer , means with summands, where . Also, , the empty product. No division by is needed, and such division is not generally available: may contain no element playing the role of .
Theorem 2.5.6
(Binomial theorem)
For commuting elements of a commutative unital ring and every ,
Proof
(Combinatorial model, then induction)
Model. Write as a product of factors. Repeated distributivity expands it into a sum of words , where each is or . Let be the set of positions where . Because and commute, the letters can be rearranged, so the word equals . Words correspond bijectively to subsets . Exactly of them have , and grouping them gives the coefficient. The induction below proves the same result without informal reasoning about "expanding".
Base case . The left side is the empty product . The right side is .
Inductive step. Assume the statement holds for . Keep the sum over so every power below has a nonnegative exponent:
In the first sum, multiplying by gives . Substitute . In the second sum, multiplying by gives , and this step uses . Integer multiples commute with every ring element by distributivity, so the coefficients cause no difficulty. After the substitution, the two sums are
To place both sums over the same range , we added the term to the first sum and the term to the second. Both added terms have coefficient , and all exponents involved are nonnegative. Combining the sums and applying Pascal's rule gives
This is the statement for , which completes the induction.
Proof X-ray
Where commutativity and the zero convention enter
The induction has one genuinely non-routine move and two hypotheses used at precise points. The move is the index shift equal to plus one in the first sum, which aligns the two sums so that Pascal's rule can merge them coefficient by coefficient. Commutativity is used exactly once, to rewrite times to the as to the times ; nowhere else does the order of factors matter. The out-of-range zero convention is used to extend both sums to the common range from 0 to plus 1 without changing their values, so that Pascal's rule may be applied at the two endpoints as well. The proof closes because the merged coefficient is precisely the statement for plus 1, and the base case is the empty product. The counterexample below removes the commutativity step and shows that nothing else can replace it.
The proof relies on the selected elements satisfying . Without that relation, the displayed identity can fail, as the following example shows.
Counterexample mode
Noncommuting matrices
In the ring of real matrices, let
Then
so . Also , and , which gives . On the other hand,
The correct expansion is . The two mixed products are different matrices and cannot be merged into .
Identities from subsets
Theorem 2.5.7
(Row sums and parity)
For , . For ,
Proof
(Two counts and a toggle bijection)
Row sum. We count the subsets of in two ways. First, by the product rule, each of the elements is independently in or out, which gives subsets. Second, by the sum rule, grouping the subsets by size gives . When , both counts equal , since is the only subset.
Parity, . Fix the element , which exists because . Define the toggle map . It removes if and adds otherwise. Then , so is a bijection from the subsets of to themselves. It changes by exactly , so it reverses parity. Hence restricts to a bijection from even-size subsets to odd-size subsets. The two families have equal size, and together they contain all subsets, so each has members.
The case is different. The even sum is and the odd sum is . There is no element to toggle, so the bijection does not exist. Algebraically, putting , in the binomial theorem gives . This is for , but it is the empty product for .
Theorem 2.5.8
(Weighted sum)
For , . For , the sum is .
Proof
(Counting pairs)
Let be the set of pairs with and . Think of as a committee and as its chair.
Committee first. A -subset has possible chairs. Summing over sizes gives .
Chair first. There are choices for . The rest of the committee is any subset of the remaining elements, and . That gives choices for , so .
Both counts describe the same finite set, so they are equal. When , no pair exists, and the sum is . The expression is not a count of anything in that case, which is why we state separately.
Theorem 2.5.9
(Vandermonde's identity)
For and every integer ,
Proof
(Splitting a committee)
Let and be disjoint sets with and . Count the -subsets , of which there are .
Each determines the number , which lies in . Different values of give disjoint cases, and together the cases cover every .
Fix . The map is a bijection onto the pairs consisting of a -subset of and a -subset of . Its inverse is . This inverse is injective because , so and can be recovered as and . By the product rule, this case contains subsets. The sum rule then gives the identity.
If or , the term is , which correctly counts an impossible case. If or , every term vanishes and so does the right side.
Setting and , and using symmetry , gives
In the proof of Vandermonde's identity, the selection is a single unordered set. The split records which original group each member came from. It does not impose an order and does not create new objects. The sets and are fixed and labeled, which is why the pair is well defined.
Concept lensAlgebraic
Vandermonde as a product of polynomials
The same identity is a coefficient comparison. By the binomial theorem in the polynomial ring ,
The coefficient of on the left collects the products with , which is the sum in Vandermonde's identity; on the right it is . The split of the bijective proof becomes the exponent contributed by the first factor.
Worked examples
Worked example 2.5.10
(Choosing from )
Choose people from mathematicians and physicists. Split by the number of mathematicians chosen:
The terms correspond to , namely . The total agrees with .
Worked example 2.5.11
(Three-element subsets with a distinguished member)
Pascal's rule with distinguished element gives . Ten of the -subsets of avoid , and ten contain it.
Now count pairs with and . Committee first gives . Chair first: choose in ways and then more members from the remaining elements in ways, giving . The counts agree.
Worked example 2.5.12
(Row and parity)
The values for are , and their sum is . The even- terms give , and the odd- terms give . Both equal .
The toggle map with fixed element illustrates the bijection. For example, it sends and .
Worked example 2.5.13
(Sum of squares for )
The values are . Their squares sum to , and . The term equals . It counts the -subsets of a -set that contain exactly one element from the first half and two from the second.
Common mistakes
Counterexample mode
Adding overlapping cases
Count the -subsets of that contain or . There are such subsets containing and containing , but the answer is not . The subset belongs to both cases and is counted twice.
The correct list is , which has members. Inclusion–exclusion gives the same result: . So does the complement: , since only avoids both elements. The sum rule requires disjoint cases. The proofs of Pascal's rule and Vandermonde's identity work because their cases are determined by a single value, either membership of one element or the number .
Common mistake
(Labeled versus unlabeled)
The number counts the ways to choose “team A” from people, with the rest forming team B. It does not count the ways to split people into two unlabeled pairs. Each such split corresponds to two labeled choices, so there are only splits.
Common mistake
(Applying parity at )
The parity identity needs an element to toggle, so it does not apply when : there the even sum is and the odd sum is .
Common mistake
(Dividing by in a ring)
In the binomial theorem, the coefficients act as integers on ring elements. Division by in is never needed and may be impossible.
Exercises
Quick check
(Compute from the definition and from the factorial formula.)
Count the subsets of the empty set.
Solution · Answer
The empty set has exactly one subset, itself, and it has size . So . The formula gives , using as an empty product.
Quick check
(Find and verify Pascal's rule for , .)
Use the out-of-range zero convention.
Solution · Answer
No subset has elements, so . Pascal's rule then reads , that is, . The only -subset of is , and it avoids the element .
Quick check
(Compute the even and odd row sums for and for .)
Check whether an element is available to toggle.
Solution
For , the even sum is and the odd sum is . They are not equal, because there is no element to toggle.
For , the even sum is and the odd sum is . Both equal . The toggle map swaps and .
Quick check
(Compute directly and compare it with the weighted-sum formula.)
Use the row .
Solution · Answer
. The formula gives , which agrees.
Quick check
(Find the coefficient of in .)
Match the exponent of with .
Solution · Answer
In the form , we need and . The coefficient is .
Quick check
(Verify Vandermonde's identity for , , .)
Sum over .
Solution · Answer
, and , which agrees.
Quick check
(Verify the sum-of-squares identity for .)
Use the row .
Solution · Answer
, and , which agrees.
Quick check
(For and , show that and that .)
Compute each product entry by entry.
Solution
The two products are
so . Next, , which gives . The squares are and , so
The difference is . This is consistent with the correct expansion .