Counting methods let you find how many outcomes are possible without listing every outcome. The right method depends on what makes two outcomes different: their order, their members, or both. You also need to know whether an item may be selected more than once.
Start with the multiplication principle
Suppose a shop offers three shoe models in two colours, and every model comes in both colours. Choosing a model and then a colour gives 3 × 2 = 6 possibilities. Multiply the number of choices at each stage. If a choice changes the options available later, use the number actually available at that stage.
What does a factorial count?
The factorial of a positive integer multiplies it by every smaller positive integer. By convention, zero factorial equals one. This agrees with the single way to arrange an empty selection.
Arranging every item
For n distinct items placed in n positions, there are n choices for the first position, then n − 1, and so on. Three candidates can finish in 3 × 2 × 1 = 6 orders, assuming there are no ties.
When some items are identical, exchanging them does not create a new arrangement. Divide by the factorial of each repeated group. The word LEVEL has five letters, with two Ls and two Es, giving 30 distinct arrangements.
When does the order of a selection matter?
Selecting three different digits from {1, 2, 3, 5, 7, 9} to make a three-digit number is an ordered selection without repetition. The numbers 123 and 321 are different, so the count is 6 × 5 × 4 = 120.
If repetition is allowed, each position again has all n options. Two positions filled from the five vowels give 25 strings, including AA and AE.
Combinations count groups, not orders
Choosing three distinct marbles from twelve gives 220 possible selections. This counts one group of three, not a partition of all twelve marbles into several containers. Each group would otherwise have been counted in every possible internal order.
Why choosing three marbles from twelve gives 220 groups
Suppose twelve marbles are all different and we select three without replacement. The same three marbles in a different order are still the same selection, so use a combination with n = 12 and k = 3.
Substitute the two counts into the combination formula. Since 12 − 3 = 9, the second factorial in the denominator is 9 factorial.
Cancel the common factorial of 9. The three factors left in the numerator count ordered selections; the denominator removes the six orders of each group.
Multiply the numerator and denominator, then divide. Each unordered group is counted exactly once.
There are 220 selections. Multiplying 220 by the six internal orders gives 1,320 ordered selections, which checks the original count.
Choosing with repetition
If three pairs of shoes may be chosen from ten brands, brands may repeat and the purchase order does not matter, there are 220 brand selections. This assumes availability is unrestricted and distinguishes selections only by brand.
Here n is the number of available types and k is the number selected. For selections without repetition, k cannot exceed n. Before using a formula, compare two outcomes such as AB and BA: if they mean the same thing, order should not be counted. Then check separately whether AA is allowed. Those two decisions prevent most counting errors.
