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

“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.

Here n,r are nonnegative integers. Factorial ratios require 0≤r≤n; choosing more than n items without replacement gives zero possibilities. The stars-and-bars formula requires n≥1. With zero types, selecting zero items gives one empty selection, while selecting a positive number gives none.

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

All permutations of n distinct elements:

n!

If there are duplicate elements, swapping identical elements won't produce a new sequence. With category counts n₁,...,n_k summing to 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 an r-element subset from n distinct elements:

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

Derivation: First count the P(n,r) ordered selections; 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 used 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.

Python 3 has arbitrary-precision integers. Multiply before dividing at each step below. After iteration i, value=C(n-r+i,i), so that division is exact; rounding each fractional factor down first would be wrong:

def choose(n, r):
    if n < 0 or r < 0:
        raise ValueError("nonnegative integer inputs required")
    if r > n:
        return 0
    r = min(r, n - r)
    value = 1
    for i in range(1, r + 1):
        value = value * (n - r + i) // i
    return value

print(choose(10, 3))   # 120
print(choose(0, 0))    # 1
print(choose(3, 4))    # 0
print(choose(100, 50)) # 100891344545564193334812497256

Production code can use Python 3.8+ math.comb. Big integers avoid overflow, while increasing bit lengths still increase computation and storage costs.

Binomial Theorem

When expanding (x+y)^n, we choose r of the n factors to contribute y, and the other n-r to contribute x:

(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 Stars and Bars

Selecting r items from n types, 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 stars-and-bars formula no longer applies directly. In such cases, inclusion-exclusion or generating functions must be used instead.

Circular Arrangements and Symmetry

n≥1 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 also count as identical, n≥3 distinct objects give (n−1)!/2 arrangements. For n=1,2, there is one arrangement and no further division by 2. Repeated colors or other symmetries can produce different orbit sizes; check the group action or use Burnside’s lemma.

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 n^m functions from the 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.

For nonnegative integers m,n, this Python 3.8+ example counts 36 assignments of 4 labeled tasks to 3 nonempty nodes, confirmed by independent enumeration. Empty-set boundaries use the counting convention 0^0=1:

from math import comb
from itertools import product

def onto_count(m, n):
    return sum((-1)**k * comb(n, k) * (n - k)**m for k in range(n + 1))

m, n = 4, 3
by_enumeration = sum(len(set(outputs)) == n
                     for outputs in product(range(n), repeat=m))
print(onto_count(m, n), by_enumeration)  # 36 36
print(onto_count(0, 0), onto_count(0, 2), onto_count(2, 0))  # 1 0 0

Completion Check

Calculate and explain each of the following models:

1. An 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