6.2 Permutations, Combinations, and Repeated Selection: Does Order and Repetition Matter?

Master Chen’s question was simple: “Pick four digits.” But Ah Hua paused first to clarify whether order mattered, whether digits could repeat, and whether the first digit could be zero.

“How many four-digit passwords can be formed from ten digits?” doesn’t have a single answer: can digits be repeated? Can the first digit be zero? Are 1234 and 4321 considered different? Before applying any combination formula, these questions must be answered.

Four Basic Models

Model	Order	Repeated	Count
Sequence of length r	Important	Yes	n^r
r-Permutation	Important	No	n!/(n-r)!
r-Combination	Not important	No	C(n,r)
r-Combination with repetition	Not important	Yes	C(n+r-1,r)

Choose the model first, then apply the formula.

Permutations: Ordered and Without Replacement

Selecting and arranging n distinct elements taken r at a time:

P(n,r)=n(n-1)...(n-r+1)=n!/(n-r)!

Choosing four digits from ten, without repetition, allowing leading zeros, and treating the result as a 4-digit code:

P(10,4)=10×9×8×7=5040

If we require a genuine four-digit decimal number, where the first digit cannot be zero:

9×9×8×7=4536

If repetition is allowed, there are 10⁴ possible 4-digit codes; and 9×10³ valid four-digit numbers.

Permutations and Duplicate Elements

n permutations of different elements:

n!

If there are duplicate elements, swapping identical elements won't produce a new sequence. Contains n₁,...,n_k elements of the same category, total length n:

n!/(n₁!n₂!...n_k!)

The word LEVEL has 5 letters: two L's and two E's.

5!/(2!2!)=30

The formula assumes results are distinguished only by character sequences; if character instances have hidden identities, the model changes.

Combinations: Unordered and Without Replacement

Selecting a subset of n elements from r distinct elements:

C(n,r)=n!/[r!(n-r)!]

Derivation: First count the number of ordered selections of P(n,r) elements; each unordered subset is counted r! times due to its permutations:

C(n,r)=P(n,r)/r!

Symmetry:

C(n,r)=C(n,n-r)

Choosing r elements is equivalent to deciding which n-r elements to exclude.

Pascal's Identity

Fix a particular element x, and partition the subsets of size r into two categories:

• Those that include x: choose r-1 elements from the remaining n-1;
• Those that exclude x: choose r elements from the remaining n-1.

Thus:

C(n,r) = C(n-1,r-1) + C(n-1,r)

This is both a combinatorial proof and the recurrence relation for Pascal's triangle. It can be leveraged when computing all combination values in a row using dynamic programming. If only a single value C(n,r) is needed, an alternating multiplication-and-division algorithm can be used to avoid computing large factorials upfront:

C(n,r) = ∏_{i=1..r} (n - r + i) / i, with r = min(r, n - r)

Integer implementations must include rational simplification or use arbitrary-precision integers to prevent intermediate overflow or floating-point rounding errors.

Binomial Theorem

When expanding (x+y)^n, we select r factors to take y and the remaining x to take n:

(x+y)^n = Σ_{r=0..n} C(n,r) x^(n-r) y^r

Let x=y=1:

Σ_{r=0..n} C(n,r) = 2^n

The left side groups terms by subset size, counting the power set. The right side counts each element as either selected or not. Both methods count the same set of objects, yielding the identity.

Combinations with Repetition and the Bar Method

Selecting n types from r items, allowing repetition and disregarding order, is equivalent to finding the number of non-negative integer solutions to:

x₁ + x₂ + ... + xₙ = r

This is encoded using r stars and n-1 bars:

***|*||**

representing the counts of four types totaling (3,1,0,2). With a total of r+n-1 positions, we choose n-1 positions for the bars:

C(r + n - 1, n - 1) = C(r + n - 1, r)

If each category must have at least one item, first allocate one item to each category, leaving r-n items to distribute:

C(r - 1, n - 1), provided that r ≥ n

If there are upper bounds on the counts (e.g., a maximum limit x_i≤u_i), the simple bar method no longer applies directly. In such cases, inclusion-exclusion or generating functions must be used instead.

Circular Arrangements and Symmetry

n distinct objects arranged in a circle, where rotations of the entire arrangement are considered the same:

(n-1)!

By fixing one object as a reference point, we eliminate n rotational duplicates.

If reflections are also considered identical, an additional factor of 2 must be divided out. However, for small cases or when additional symmetries exist, individual checks are often necessary. Generally, symmetry counting cannot be arbitrarily "divide by the number of symmetries", each equivalence class must have the same size, or Burnside's Lemma must be applied to ensure correctness.

Surjective Counting

Distributing m labeled tasks among n labeled work nodes, with each node receiving at least one task, is equivalent to counting the number of surjective (onto) functions from an m-element set to an n-element set.

Using the inclusion-exclusion principle:

Σ_{k=0..n} (-1)^k C(n,k)(n-k)^m

We first count all possible functions from the n^m tasks to the nodes, then subtract the cases where at least one specific node is empty, add back the cases where two specific nodes are both empty, and so on, alternating signs to correct for overcounting.

Completion Check

Calculate and explain each of the following models:

1. A 8-digit PIN code allowing repetition and leading zeros;
2. Selecting a class president, vice-president, and committee member from 10 candidates;
3. Choosing a group of 3 people from 10 candidates;
4. Distributing 12 identical tasks among 4 labeled nodes, allowing empty nodes;
5. Same as above, but each node must receive at least one task;
6. The number of distinct letter arrangements of the letters in MISSISSIPPI.

References

• MIT Mathematics for Computer Science