Counting and Combinatorial Proofs

How many ways can seven identical task slots be distributed among three named teams? Before choosing a formula, decide what counts as one allocation. If only each team's share matters, an outcome is a triple $(x_1,x_2,x_3)$. If the seven tasks have distinct identities and each task's destination matters, the objects being counted change.

The discrete mathematics map lists basic permutation and combination formulas. Combinatorial proofs explain why counts agree, how to correct overlaps, and why some arrangements are impossible.

Define the objects and when they are equal

Counting asks for the size $|S|$ of a finite set $S$. Specify its objects, their constraints, and when two records represent the same outcome.

• A sequence records positions, so AB and BA differ. A set records membership; both represent $\{A,B\}$.
• Allowing repeated choices of a value and treating copies of that value as indistinguishable are separate conditions.
• Several construction paths may reach one outcome. Before counting paths, check whether paths are what the problem asks for.

For example, length-two sequences over A and B, with repetition allowed, are AA, AB, BA, and BB. Recording only the number of each letter merges AB and BA, leaving three outcomes. There is no uniform factor by which to divide the sequence count: AA has one ordering, while AB has two. Berkeley CS70's counting notes require every target outcome to have the same number of preimages before applying the division rule.

Multiply stages, add disjoint cases

If an object is constructed uniquely in $k$ stages and every valid prefix has exactly $n_i$ choices at stage $i$, the generalized product rule (MIT Section 14.3) gives $\prod_{i=1}^k n_i$. The available choices may depend on earlier choices; their number must be constant at each level. Choosing one of three distinct letters and one of four distinct digits, in letter–digit order, gives $3\times4=12$ sequences.

When branch sizes differ, count each branch separately and add. If choosing A first permits two following characters and choosing B permits three, the total is $2+3=5$.

The sum rule applies to pairwise disjoint cases. For finite, pairwise disjoint sets $S_1,\ldots,S_k$,

$$\left|\bigcup_{i=1}^k S_i\right|=\sum_{i=1}^k|S_i|.$$

This disjointness condition appears in MIT's Mathematics for Computer Science, Section 14.2. Decimal strings of length two or three, with leading zeroes allowed, form disjoint classes by length, giving $10^2+10^3=1100$ strings. Classes such as “contains A” and “contains B” overlap on strings containing both, so their counts need a correction.

Prove identities with bijections and double counting

A bijection pairs the elements of two sets: each source element has one target, and each target comes from exactly one source. Giving the map and its inverse proves that the sets have equal sizes.

Within a fixed set of $n$ elements, map a $k$-element subset to its complement, an $(n-k)$-element subset. Taking the complement again recovers the original subset, so for $0\le k\le n$,

$$\binom nk=\binom n{n-k}.$$

For example, choosing two people from five corresponds uniquely to choosing the three left out. Each count is 10.

Double counting counts the same set in two ways. For $n\ge1$ and $1\le k\le n$, let an outcome be a $k$-person committee with one member designated as its chair. Choosing the committee and then its chair gives $k\binom nk$. Choosing the chair first, then $k-1$ members from the other $n-1$ people, gives $n\binom{n-1}{k-1}$. Hence

$$k\binom nk=n\binom{n-1}{k-1}.$$

For a three-person committee from eight people, with a designated chair, both counts give $3\binom83=8\binom72=168$. The counted objects are committees with a marked member. Counting committees alone omits the three possible chairs for each committee.

Repetition and indistinguishable objects

Allocate identical slots with stars and bars

Return to the allocation problem. The slots are identical, the three teams are distinguishable, and each team may receive zero slots with no upper limit. We count nonnegative integer solutions to

$$x_1+x_2+x_3=7.$$

Represent the slots by seven stars and separate the teams with two bars: **|***|** represents $(2,3,2)$. Adjacent bars allow an empty middle team; bars at either end allow an empty end team. Each triple determines one string, and each string determines one triple.

Choose the two bar positions among nine positions, giving $\binom92=36$ allocations. In general, distributing $r\ge0$ identical objects among $b\ge1$ distinguishable boxes, allowing empty boxes and imposing no capacity limit, gives $\binom{r+b-1}{b-1}$ outcomes. The CS70 notes use this correspondence for sampling with replacement when order does not matter.

If each team must receive at least one slot, give each one first and distribute the remaining four, giving $\binom62=15$. If the objects are distinct, the original problem has $3^7=2187$ outcomes. If the teams are also indistinguishable, different bar positions can describe the same allocation, so the model must change.

Arrange a fixed multiset

In AABC, the two copies of A are indistinguishable. Label them temporarily: the four distinct objects have $4!$ permutations. Removing the labels maps exactly $2!$ labelled permutations to each visible arrangement, giving $4!/2!=12$ outcomes.

More generally, if $n$ values have multiplicities $m_1,\ldots,m_t$ with $\sum_i m_i=n$, the number of distinct sequences is

$$\frac{n!}{m_1!\cdots m_t!}.$$

MIT Section 14.6 gives this rule. Division works because every visible outcome has the same number of labelled versions. For removing these duplicate branches during search, see permutations by backtracking.

Overlapping sets: inclusion–exclusion

Inclusion–exclusion in MIT Section 14.9 corrects overlap in unions of finite sets. For two sets, $|A\cup B|=|A|+|B|-|A\cap B|$. For three,

$$\begin{aligned} |A\cup B\cup C|={}&|A|+|B|+|C|\\ &-|A\cap B|-|A\cap C|-|B\cap C|\\ &+|A\cap B\cap C|. \end{aligned}$$

An element in all three sets is added three times and subtracted three times, so it must be added once more. For more sets, continue alternating signs according to the number of sets in each intersection, through the last level.

Worked example: filter integers from 1–100

Count the integers from 1 through 100 inclusive that are divisible by none of 2, 3, or 5. Let $U=\{1,\ldots,100\}$ and let $A,B,C$ contain its multiples of 2, 3, and 5 respectively.

Set	Membership condition	Count
$A$	Multiple of 2	$\lfloor100/2\rfloor=50$
$B$	Multiple of 3	$\lfloor100/3\rfloor=33$
$C$	Multiple of 5	$\lfloor100/5\rfloor=20$
$A\cap B$	Multiple of 6	16
$A\cap C$	Multiple of 10	10
$B\cap C$	Multiple of 15	6
$A\cap B\cap C$	Multiple of 30	3

Intersections use the least common multiple of the relevant divisors. This equals their product only when they are pairwise coprime. Thus

$$|A\cup B\cup C|=50+33+20-16-10-6+3=74.$$

These are the integers to exclude, so the answer is $|U|-74=100-74=26$. Python 3 can enumerate the sets directly:

U = set(range(1, 101))
A = {x for x in U if x % 2 == 0}
B = {x for x in U if x % 3 == 0}
C = {x for x in U if x % 5 == 0}
union_count = (len(A) + len(B) + len(C)
               - len(A & B) - len(A & C) - len(B & C)
               + len(A & B & C))
valid = U - (A | B | C)
assert union_count == len(A | B | C)
print(union_count, len(valid))
print(sorted(valid))

Output:

74 26
[1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73, 77, 79, 83, 89, 91, 97]

Pigeonhole arguments and impossibility

The pigeonhole principle assigns objects to finitely many classes: if $N$ objects each occupy one of $b\ge1$ boxes, some box contains at least $\lceil N/b\rceil$ objects. MIT Section 14.8 states it as a property of functions: a map from a larger set to a smaller set cannot be injective.

For example, allocating 17 tasks to five workers puts at least four tasks on one worker. If each received at most three, their total capacity would be $5\times3=15$, too small for 17 tasks.

Likewise, any deterministic function mapping every nine-bit binary string to an eight-bit string has a collision: there are $2^9=512$ inputs but only $2^8=256$ outputs. It cannot have a unique inverse on every input. The proof guarantees that a colliding pair exists; it neither identifies the pair nor establishes the cost of finding it.

Search spaces, output bounds, and distinction bounds

Counting estimates the candidates a search must consider. The 36 allocations among three teams can be counted with stars and bars or found by enumerating triples:

from itertools import product
from math import comb

allocations = [x for x in product(range(8), repeat=3) if sum(x) == 7]
assert len(allocations) == comb(9, 2)
print(len(allocations), allocations[:5])

Output:

36 [(0, 0, 7), (0, 1, 6), (0, 2, 5), (0, 3, 4), (0, 4, 3)]

This code examines $8^3=512$ triples to retain 36. Candidate count, valid outcome count, and actual runtime require separate calculations. Pruning changes the number of visited nodes, and processing a node can incur additional work.

If a task requires explicitly outputting $M$ sequences of length $\ell$, writing every element of each sequence costs at least $\Omega(M\ell)$ time under a constant-cost element-write model. Keeping all results simultaneously as separate lists also requires at least $\Omega(M\ell)$ space. Ten distinct values have $10!=3628800$ permutations; complete output writes 36288000 elements. Streaming reduces simultaneous storage but still requires those writes. Computing only the count is a different task.

A second bound comes from how many cases must be distinguished. If a deterministic algorithm distinguishes $M\ge1$ cases only through queries with at most $q\ge2$ possible outcomes each, a decision tree of depth $h$ has at most $q^h$ leaves. Therefore $h\ge\lceil\log_q M\rceil$. For comparison sorting of arbitrary distinct keys, $M=n!$ and comparisons between distinct keys have $q=2$ outcomes. This is the decision-tree argument in Open Data Structures, Section 11.1.4. Eight distinct keys have $8!=40320$ relative orders, requiring at least 16 comparisons in the worst case because $2^{15}<40320\le2^{16}$.

An output bound counts what must be written; a decision-tree bound counts the information needed to distinguish cases. They help assess whether all results can be enumerated faster or a decision reached with fewer queries. The sorting algorithms map explains the comparison model's scope and why additional key structure permits other sorting methods.

My reading · Opened notes are remembered in this browser.