7.5 Probabilistic and Combinatorial Proofs

Probabilistic and combinatorial proofs establish a result by counting, arranging, or randomly selecting objects. They are especially useful for finite structures, existence statements, and identities involving numbers of configurations.

A combinatorial proof shows that two expressions are equal by showing that they count the same thing.

For example, the identity

has a direct combinatorial explanation. Choosing $k$ elements from an $n$-element set is equivalent to choosing which $n-k$ elements to leave out. The two choices determine each other, so the two numbers are equal.

This kind of proof is powerful because it explains why an identity holds. It does not merely transform symbols. It identifies the objects being counted.

Another example is the binomial identity

The right side counts all subsets of an $n$-element set, since each element is either included or not included. The left side counts the same subsets by size: first the subsets of size $0$, then size $1$, and so on up to size $n$. Since both sides count the same collection, they are equal.

Combinatorial proofs often depend on finding the right interpretation. An algebraic expression becomes a count of objects. Once the objects are identified, the proof follows from a bijection, a partition, or a double count.

A bijective proof constructs a one-to-one correspondence between two collections. If every object on one side corresponds to exactly one object on the other side, the two collections have the same size.

A double-counting proof counts the same collection in two different ways. This often produces useful identities.

For instance, count the number of ways to choose a committee of size $k$ from $n$ people and then choose a chair from the committee. One way is to choose the committee first, then the chair:

Another way is to choose the chair first, then choose the remaining $k-1$ members from the other $n-1$ people:

Since both count the same objects,

The probabilistic method proves existence by showing that a randomly chosen object has positive probability of satisfying a desired property. If the probability is positive, then at least one such object exists.

The proof may not construct the object explicitly. It shows that the set of good objects is nonempty.

The basic pattern is:

Choose an object at random. Show that the probability of success is greater than $0$. Conclude that at least one successful object exists.

For example, suppose a finite set of objects is divided into good and bad objects. If a random object has probability

then at least one good object exists.

This reasoning is simple but extremely useful. It can prove existence when explicit construction is difficult.

A common probabilistic proof uses expectation. If a random variable $X$ has average value greater than $0$, then some outcome must have $X > 0$. More generally, if the average value is at least $m$, then some outcome has value at least $m$.

The reason is direct: if every outcome were less than $m$, the average would also be less than $m$.

This principle can prove the existence of objects with many desired features. Instead of constructing the object, one shows that a random object has the desired feature on average.

Probabilistic proofs and constructive proofs differ in output. A constructive proof gives an object or algorithm. A probabilistic proof may show only that an object exists. However, many probabilistic arguments can be converted into randomized algorithms, and sometimes into deterministic constructions.

Combinatorial proofs also support inequalities. Instead of counting exactly, one may inject one collection into another to show that one size is at most another.

If there is an injective map

then

If there is a surjective map

then

for finite sets.

These simple principles underlie many finite arguments.

The main difficulty in combinatorial proof is choosing the right objects to count. The formula may be clear, but the interpretation may not be. The art is to find a set whose size can be computed in two useful ways.

The main difficulty in probabilistic proof is choosing the right random model. A poor random model may make the probability hard to analyze or may not reflect the structure of the problem. A good random model makes the desired property measurable and exposes the right estimates.

These methods are valuable because they turn proof into organization. Count the same thing twice. Build a correspondence. Show that random choice cannot always fail. These patterns recur throughout combinatorics, graph theory, number theory, probability, theoretical computer science, and discrete geometry.

Probabilistic and combinatorial proofs show that existence can be established through structure in a finite universe. They give another route to certainty: not by constructing directly, but by showing that counting or probability leaves no alternative.