A committee of four from seven people chooses one spokesperson. Counting committees first gives four times C(7, 4)=140. Choosing the spokesperson first gives seven times C(6, 3)=140. The equality is not an accident between formulas: both count exactly the same pairs consisting of a committee and one distinguished member. Start every double-counting argument by naming that underlying set of objects.
Predict
Predict what happens if a committee can choose either one or two spokespersons. Dividing the number of marked committees by a fixed number would now fail unless the marking rule fixes the number of marks. Counting images by division requires equal-size fibers: every unmarked object must have the same number of marked versions. A symmetry argument often establishes that condition, but the word symmetry alone is not a proof of it.
Experiment
Inspect the marked-subset count by subset size for a four-element ground set.
Size k
Number of subsets
Marked versions
0
1
0
1
4
4
2
6
12
3
4
12
4
1
4
The total is 32. Independently choose the marked element in four ways, then include or exclude each of the other three elements, giving 4·2³. Explain why the empty subset contributes zero rather than an exceptional extra object.
Understand
For integers 0≤k≤n, count pairs (S, x) where S is a k-element subset of an n-element set and x belongs to S. Counting S first yields k C(n, k); counting x first yields n C(n−1, k−1). This proves the marked-binomial identity. Summing over k instead gives Σk C(n, k)=n2^(n−1) for n≥1. Another basic pattern partitions an object set into disjoint cases. If two disjoint populations have sizes a, b, an r-element selection contains some k from the first and r−k from the second. Summing C(a, k)C(b, r−k) proves Vandermonde’s identity. Define binomial coefficients outside their valid range as zero so the sum can be written without hiding feasibility conditions.
Apply
A bijection proves equality by sending every object of one class to exactly one object of another and supplying an inverse. For subsets, complementation is its own inverse and proves C(n, k)=C(n, n−k). For a more demanding example, encode a lattice path with r east steps and s north steps by the positions of its east steps in a word of length r+s; choosing those positions reverses the encoding. If paths have an additional barrier restriction, this unrestricted bijection still encodes them, but it does not count the restricted set without further analysis. The later reflection argument supplies that missing mechanism.
A word has positions, symbol labels and multiplicities
Use symbols0, 1, 2 and four ordered positions. The words0011 and0101 both have frequency vector(2, 2, 0): two zeros, two ones and no twos. This fixed vector has six words, because choosing the two zero positions determines the rest. The profile(2, 2) forgets which labels have those counts. It allows three choices for the two used labels, giving eighteen words. These are different counting questions.
For profile(3, 1), first choose the label used three times (three choices), then the singleton label (two choices), then its position (four choices): twenty-four words. For profile(2, 2), the two multiplicity roles are interchangeable. Ordering the labels gives six encodings for only three label pairs; divide by2! here. Do not divide the unequal roles3 and1 by2!: the frequent and singleton labels have different meanings.
Separate labels, frequencies and positions
Symbols are labels0 through q−1. Words may start with zero unless you change that rule. A frequency vector keeps symbol identities; a multiplicity profile keeps only its positive counts, sorted.
Selected profile has 18 eligible words. Unrestricted label assignments for this profile: 3 frequency vectors.
All profiles together: 81 eligible words. Eligible frequency classes: 15. Class sizes are not generally equal.
Predict which class loses more words when initial zero is forbidden. Compare the same profile with different frequency assigned to symbol0.
Frequency vector
Profile
Words
Nonzero first
Selected profile?
(4, 0, 0)
4
1
0
no
(3, 1, 0)
3,1
4
1
no
(3, 0, 1)
3,1
4
1
no
(2, 2, 0)
2,2
6
3
yes
(2, 1, 1)
2,1,1
12
6
no
(2, 0, 2)
2,2
6
3
yes
(1, 3, 0)
3,1
4
3
no
(1, 2, 1)
2,1,1
12
9
no
(1, 1, 2)
2,1,1
12
9
no
(1, 0, 3)
3,1
4
3
no
(0, 4, 0)
4
1
1
no
(0, 3, 1)
3,1
4
4
no
(0, 2, 2)
2,2
6
6
yes
(0, 1, 3)
3,1
4
4
no
(0, 0, 4)
4
1
1
no
This enumerates at most729 words and28 frequency vectors. The general counting proof is below; finite enumeration does not replace it. Settings are temporary and do not award mastery.
Derive the general profile count with a reversible encoding
Let q be the positive number of available labels and n the word length. For each positive integer j, let m_j be the number of labels used exactly j times. The number of used labels is r, the sum of all m_j; the word length n is the sum of j times m_j. Require r≤q and only finitely many nonzero m_j. Labels with zero occurrences are unused and do not get positive-multiplicity roles.
First assign distinct labels to the r roles. Listing all roles temporarily gives q(q−1)…(q−r+1) assignments. Permuting the m_j roles of the same multiplicity does not change the assignment of counts to labels; each final assignment has exactly the product of all m_j! such listings. Dividing by that constant fiber gives the number of labeled frequency vectors with this profile.
For each such vector, distribute its labels among the n positions. Start with n distinct occurrence tokens, group them by label and forget token identities. Every word has exactly the product of (j!) raised to m_j lifts, since the j tokens of each label may be permuted. Therefore the number of words with the profile is the falling product q(q−1)…(q−r+1), times n!, divided by both the product of m_j! and the product of (j!) raised to m_j. Empty products and0! are one, so the empty word has one encoding. If the stated length condition fails or r>q, there are no such words; the formula is not permission to use a factorial of a negative number.
The encoding is reversible after the stated identifications: a word supplies each label’s frequency and its occupied positions. The two denominators remove different redundancies, one from equal multiplicity roles and one from occurrences of the same label. Neither is an unexplained symmetry factor.
Frequency classes do not have a common size
Declare words equivalent when they have the same frequency vector (c0, …, c(q−1)). Every coordinate is a nonnegative integer and the coordinates sum to n. Each vector is realized by putting all zeros first, then all ones, and so on. Thus this is a bijection between equivalence classes and weak compositions of n into q parts, giving C(n+q−1, q−1) classes. The size of one class is n! divided by the product of its coordinate factorials. For q=3 and n=4 there are fifteen classes but eighty-one words: all-one-label classes have size1, whereas profile(2, 1, 1) classes have size12. Dividing the total words by one selected class size cannot count all classes.
If every label must occur, subtract one from each frequency: for n≥q there are C(n−1, q−1) classes, and for n<q there are none. The unrestricted empty word remains one class for any q≥1; it does not use every label.
Change the first-position rule and recheck the fibers
These are words, so leading zero was allowed. For a fixed vector with n>0, the words beginning with zero are counted by fixing that symbol, then arranging the remaining n−1 positions. If c0 is positive this gives (n−1)! divided by (c0−1)! and the other coordinate factorials; if c0=0 it gives zero. Subtracting leaves a fraction (n−c0)/n of the original class. Different vectors lose different fractions. At q=3, n=4, vector(2, 2, 0) keeps three of six words, while vector(0, 2, 2) keeps all six. The profile(2, 2) retains twelve of eighteen.
For n>0, every vector except the all-zero-symbol vector can put a nonzero symbol first, so the changed number of nonempty frequency classes is C(n+q−1, q−1)−1. The number of words is instead (q−1) times q^(n−1), by independent choices of positions. At n=0 the inspector interprets “require a first nonzero symbol” literally: no empty word qualifies. State the object and boundary convention before counting.
Continue
Use an identity as a design problem: decide what each side could count, identify the extra choice represented by a factor, and test the proposed correspondence on a small object. Algebraic verification is useful but does not replace the requested combinatorial proof. The discrete counting foundation reviews factorials and combinations. This unit will use these proof patterns inside more complicated restrictions rather than repeat introductory counting rules as isolated formulas.
Scope baseline, retrieved 25 October 2026: MIT 18.211, Fall 2021 syllabus informs the enumeration and structural breadth; Dartmouth Math 38, Spring 2026 informs connectivity and flow coverage. These are comparison sources, not claims of institutional equivalence.
Apply · explain · revise
Practice and reasoning
Drafts save locally as you type. Reveal worked solutions when useful; the site remembers that exposure. Automatic matches check the requested answer, while written arguments require review against the rubric.
An alphabet has q labels. A length-n word uses m_j labels exactly j times for each j≥1. Derive the general word count, stating feasibility and explaining both fiber divisors. Specialize to q=3, n=4 with profiles (2, 2) and (3, 1). Why is dividing by2! correct for only one of these label assignments?
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Prove that words of length n over q≥1 labeled symbols, equivalent when their frequency vectors agree, have C(n+q−1, q−1) classes. Are the classes equally large? For n>0 forbid a first symbol0: derive the remaining size of a class and count nonempty classes. Check q=3, n=4 using vectors(2, 2, 0) and(0, 2, 2).
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
How many pairs (S, x) have S a three-element subset of a six-element set and x in S?
Integers, fractions and finite decimals are accepted. Expressions such as sqrt(2) are not parsed by this checker.
Compute Σk·C(5, k), summing k from 0 through 5.
Integers, fractions and finite decimals are accepted. Expressions such as sqrt(2) are not parsed by this checker.
Prove Σ C(a, k)C(b, r−k)=C(a+b, r) for nonnegative integers.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Prove the sum of degrees in a finite simple graph is twice its edge count.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
When may one divide a count by k to count images?
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Prove Σ C(n, k)²=C(2n, n).
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Reflect and continue
Before marking this lesson complete, explain one key idea without the worked solution and identify a condition that matters. Marking complete records participation, not independent mastery.
