The multiplication principle and permutations

Computing a probability under equiprobability amounts to counting outcomes. But listing them by hand quickly becomes impossible: there are 2,598,960 five-card hands. Combinatorics provides the formulas that replace enumeration.

The multiplication principle

This is the foundation of the whole chapter:

If a choice is made in several independent stages, the total number of possibilities is the product of the number of possibilities at each stage.

A menu: 3 starters, 4 mains, 2 desserts

            starter      main      dessert
               3     ×     4    ×     2      =  24 menus

A tree makes it visible: each branch at the first level splits at the second, and so on.

            /--- main1 --- dessert1
  starter1 <                dessert2
            \--- main2 --- ...
  starter2 ...
  starter3 ...
                        3 × 4 × 2 = 24 leaves

Draws with replacement

When a choice among n possibilities is repeated k times, with repetition allowed, the multiplication principle gives directly:

n × n × ... × n  =  n^k
   (k factors)

A 4-digit PIN:  10 × 10 × 10 × 10 = 10⁴ = 10,000 codes
A 3-letter word: 26³ = 17,576

Factorials and permutations

Arranging n distinct objects in order means choosing the first among n, the second among the remaining n - 1, and so on:

n × (n-1) × (n-2) × ... × 2 × 1  =  n!        ("n factorial")

These arrangements are called the permutations of n objects.

Anagrams of the word MATHS (5 distinct letters):  5! = 120

0! = 1        1! = 1        2! = 2        3! = 6
4! = 24       5! = 120      6! = 720      10! = 3,628,800

The convention 0! = 1 is not arbitrary: there is exactly one way to arrange nothing, and that value is what makes every later formula consistent.

Factorials explode: 20! already exceeds 2 × 10¹⁸. That is why any problem requiring permutations to be enumerated quickly becomes out of reach, even for a computer — the famous travelling salesman problem is one.

When objects are identical

If some objects repeat, several arrangements become indistinguishable. We then divide by the internal permutations of each group:

Anagrams of BANANE (6 letters: A×2, N×2, B, E)

        6!            720
   -----------  =  -------  =  180 distinct anagrams
    2! × 2!           4

Summary

• Multiplication principle: independent stages multiply.
• Draw with replacement, k times among n: n^k possibilities.
• Permutations of n distinct objects: n! arrangements.
• 0! = 1, a convention consistent with every formula.
• Factorials explode: 20! already exceeds 10¹⁸.
• Identical objects: divide by the internal permutations of each group.