Counting choices without double counting

Prerequisites: Sets, functions, factorial notation, and basic algebra.

Learning objectives

• Identify whether order and repetition matter.
• Count overlapping cases with inclusion-exclusion.
• Use counting to prove a collision must exist.

State what makes outcomes different

Counting starts with a model of the outcomes. A three-character string over an alphabet of four symbols has 444=64 possibilities because each position has four independent choices and repeated symbols are allowed. If symbols cannot repeat, the count is 432=24. If instead you are choosing an unordered three-symbol subset, each subset was counted 3!=6 times by the ordered calculation, leaving 4 possibilities.

The multiplication rule combines successive choices when you account correctly for the options available after earlier decisions. The addition rule combines disjoint cases. Neither rule licenses ignoring a constraint. Choosing a server and a compatible operating system is not always “number of servers times number of systems,” because compatibility can make the second choice depend on the first.

For n distinct items, the number of k-element subsets is n!/(k!(n-k)!). One derivation chooses an ordered list of k different items, then divides by the k! orders of each subset. This division works because every subset was counted equally often. When different outcomes have different numbers of representations, blindly dividing by a symmetry factor fails.

Correct overlapping cases

Suppose ten test cases include six network tests and five storage tests, with three belonging to both categories. The union contains 6+5-3=8 cases. Adding the category sizes counted every overlap twice; subtracting the intersection restores one copy. Therefore two tests belong to neither category. This is the two-set inclusion-exclusion principle, and it often makes “at least one” constraints easier to count.

For four-bit strings, there are sixteen total strings. Strings beginning with 1 number eight, and strings ending with 1 number eight. Four satisfy both conditions, so twelve satisfy at least one. Equivalently, subtract the four strings beginning and ending with 0 from the total. Complement counting is a second route that also checks the first calculation.

Counting can prove impossibility

The pigeonhole principle says that mapping more than m objects into m boxes forces some box to contain at least two objects. A hash with b output bits has at most 2^b outputs. Any larger input set must contain a collision, regardless of how clever the algorithm is. This does not identify a collision or say it is easy to find. Existence, constructive search, and computational feasibility are different claims. Counting supplies bounds; algorithms must still explain how to achieve a desired result within them.

Practice problem

A test suite forms inputs from four operation types and three payload sizes. An ordered test plan chooses three distinct input combinations. Count the plans. Then count unordered selections of three distinct combinations and explain the division. Finally, suppose every result is summarized by a three-bit signature. Prove that some two of the twelve input combinations share a signature. State why this does not imply that every signature is used, or that two particular inputs must collide. Give a small exhaustive enumeration strategy to check your plan count.

Worked solution

There are 43=12 input combinations. Ordered plans without repetition number 1211*10=1320. An unordered selection has exactly 3!=6 orders, so there are 220 selections. A three-bit signature offers only eight outputs; twelve inputs mapped to eight outputs force a collision. The mapping may send every input to one output, so surjectivity is not guaranteed. Nor does the principle identify a particular colliding pair. To check the plan count, label combinations 0 through 11 and enumerate triples of pairwise distinct labels. Count all such triples for 1320, then retain only strictly increasing triples for 220. Enumeration verifies this finite instance; the counting argument explains the general relationship.

Check your understanding

Why does choosing three distinct items from twelve without order require division by 3!?

• Every unordered selection has exactly six orderings.
• There are only three possible first items.
• Repeated items must be removed.

Explanation

The ordered count represents each unordered selection once for each permutation of its three distinct elements.

A function maps 100 distinct inputs to 16 outputs. What must be true?

• Every output is used.
• At least two inputs have the same output.
• A collision can be found in constant time.

Explanation

The pigeonhole principle guarantees existence, not surjectivity or any particular search complexity.

Primary reading

• Mathematics for Computer Science: MIT OpenCourseWare

Open the study and save your work →