Multiplication Principle

The Multiplication Principle (or Fundamental Counting Principle) is the bedrock of combinatorics. It states that if a task consists of a sequence of independent choices, the total number of ways to perform the task is the product of the number of choices at each step.

Statement

Theorem (Multiplication Principle)

If an operation can be performed in

k

steps, where:

Step 1 has $n_{1}$ options
Step 2 has $n_{2}$ options
...
Step $k$ has $n_{k}$ options

Then the total number of ways to perform the entire operation is:

N = n_{1} \times n_{2} \times \dots \times n_{k}

Independence is Key

The number of choices for step

i

must not depend on the specific choice made in previous steps (though the set of available choices might change, the count must remain consistent).

Example

How many strictly increasing sequences of length 3 can be formed using digits

{1, 2, 3, 4, 5}

Proof (Standard Approach). This seems like it might not fit the multiplication principle directly because choosing '4' first limits us. However, observe that any subset of 3 distinct digits can be arranged in exactly one strictly increasing order. Thus, we just need to choose 3 digits: $(3 5) = 10$ . ∎

Proof (Alternative (Multiplication)). Let's try to count directly?

Choice 1: Any of 5? No.
Correct Logic: We are choosing a subset, not a sequence directly. ∎

The "License Plate" Model

Standard example: A license plate has 3 letters followed by 3 numbers.

Letters: $26 \times 26 \times 26$
Numbers: $10 \times 10 \times 10$
Total: $2 6^{3} \times 1 0^{3}$

Practice Problems

Exercise (Problem 1)

A divisor of

360 = 2^{3} \cdot 3^{2} \cdot 5^{1}

is of the form

2^{a} \cdot 3^{b} \cdot 5^{c}

. How many positive divisors does 360 have?

Exercise (Problem 2)

How many 4-digit positive integers are there where all digits are distinct?

Exercise (Problem 3)

In how many ways can a rook move from

(1, 1)

(8, 8)

on a chessboard if it only moves up or right?