Counting Principles and Combinatorics

Ask two questions before choosing a formula

Does order distinguish outcomes? Can an item be selected more than once? A three-person committee, three labeled job assignments and a three-character password have different sample spaces even if each draws from the same pool.

The multiplication principle counts a sequence of choices by multiplying the number of available options at each step. It does not require probabilistic independence: it counts possibilities, and the number of options may change after each choice.

Worked example: choose from five people

Suppose five distinct people are eligible.

Choose a chair, secretary and treasurer without repeating a person. There are 5 choices for chair, 4 for secretary and 3 for treasurer: 5 × 4 × 3 = 60 assignments. Order matters because swapping roles changes the outcome.

Choose a three-person committee with no roles. Each committee was counted 3! = 6 times in those assignments, once for each ordering of its three members. Divide by 6: 60/6 = 10 committees.

For n distinct items and r selections without replacement:

$P(n,r)=\frac{n!}{(n-r)!},\qquad \binom nr=\frac{n!}{r!(n-r)!}.$

Here n! = n(n − 1)…1, and 0! = 1. The formulas require whole numbers with 0 ≤ r ≤ n. P denotes a permutation count in this formula, not a probability.

Replacement changes the options

A four-digit code allowing digits 0 through 9 and repeated digits has 10⁴ = 10,000 possibilities, including 0000. If digits cannot repeat, the count is 10 × 9 × 8 × 7 = 5,040. If the first digit cannot be zero, its choices drop to 9; say so explicitly.

Combinations with replacement use a different formula from the ordinary committee formula. Avoid applying n choose r merely because an outcome is called a “selection.” Also account for indistinguishable items: rearrangements of repeated letters are not all distinct.

From counts to probability

Suppose a three-person committee is selected uniformly from the ten committees above. The number including a named person is choose two from the other four: C(4,2) = 6. The inclusion probability is 6/10 = 0.6, matching 3/5.

Dividing counts produces a probability only when the counted elementary outcomes have the intended equal probabilities. If committee selection favors particular people, the same ten possible committees need not each have probability 1/10.

A useful check is C(n,r) = C(n,n − r): selecting included people is equivalent to selecting excluded people. Counts and probabilities should not be confused; a count can exceed 1 while a probability cannot.

Practice

A menu has six distinct toppings. How many ways can you choose two different toppings if their order does not matter?

Show the explanation

C(6,2) = 6 × 5 / 2 = 15. Using 6 × 5 = 30 counts every pair twice. If repeats were allowed, the sample space and answer would change.

Continue

Try the combinations and permutations calculator, then use the counts in the binomial model. OpenStax covers the binomial setting.