Permutations & Combinations

#Factorial

n! = n × (n − 1) × … × 2 × 1, with 0! = 1. n! is the number of ways to arrange n distinct objects in a row.

#Permutations: order matters

The number of ways to arrange r objects chosen from n distinct objects:

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

Example: gold, silver and bronze among 10 runners: P(10, 3) = 10 × 9 × 8 = 720.

#Combinations: order does not matter

The number of ways to choose r objects from n, ignoring order:

C(n, r) = n! / (r! (n − r)!), also written ⁿCᵣ or (n choose r)

Example: choose a 3-person team from 10: C(10, 3) = 720 / 3! = 120. Each team was counted 3! = 6 times among the permutations.

Useful identities: C(n, r) = C(n, n − r); C(n, 0) = C(n, n) = 1; and Pascal's rule C(n, r) = C(n − 1, r − 1) + C(n − 1, r).

from math import comb, perm, factorial
from itertools import permutations, combinations

print("P(10, 3) =", perm(10, 3), " C(10, 3) =", comb(10, 3))
print("arrangements of ABC:", ["".join(p) for p in permutations("ABC")])
print("2-subsets of ABCD:  ", ["".join(c) for c in combinations("ABCD", 2)])
print("5-card poker hands: ", comb(52, 5))
print("C(n, r) == C(n, n-r):", comb(12, 5) == comb(12, 7))

P(10, 3) = 720  C(10, 3) = 120
arrangements of ABC: ['ABC', 'ACB', 'BAC', 'BCA', 'CAB', 'CBA']
2-subsets of ABCD:   ['AB', 'AC', 'AD', 'BC', 'BD', 'CD']
5-card poker hands:  2598960
C(n, r) == C(n, n-r): True

#Which formula?

#Arrangements with identical objects

The number of distinct arrangements of n objects where n₁ are alike, n₂ are alike, …:

n! / (n₁! n₂! … nₖ!)

"MISSISSIPPI" has 11 letters: M×1, I×4, S×4, P×2 → 11! / (1! 4! 4! 2!) = 34,650.

from math import factorial
from collections import Counter

def arrangements(word):
    result = factorial(len(word))
    for count in Counter(word).values():
        result //= factorial(count)
    return result

for w in ["BOOK", "BANANA", "MISSISSIPPI", "KALVIUM"]:
    print(f"{w}: {arrangements(w)}")

BOOK: 12
BANANA: 60
MISSISSIPPI: 34650
KALVIUM: 5040

#Circular permutations

Arranging n people around a round table, where rotations count as the same: (n − 1)!. If clockwise and anticlockwise are also the same (a necklace): (n − 1)!/2.

#Stars and bars

The number of ways to put r identical items into n distinct boxes (or the number of non-negative integer solutions of x₁ + … + xₙ = r) is

C(n + r − 1, r)

Example: distribute 10 identical chocolates among 4 children: C(13, 10) = 286. If each child must get at least one, give one each first, then distribute 6: C(9, 6) = 84.

from math import comb
from itertools import product

r, n = 10, 4
brute = sum(1 for xs in product(range(r + 1), repeat=n) if sum(xs) == r)
print("brute force:", brute, " formula C(n+r-1, r):", comb(n + r - 1, r))

brute force: 286  formula C(n+r-1, r): 286