Combinations, selections and distributions

Combinations count selections in which order does not matter: a team, a committee, a plate of side dishes. Choosing r of n different objects can be done in nCr = n!/(r!(n − r)!) ways, so a 3-member team from 8 students can be picked in 56 ways, while filling 3 different posts from the same 8 gives 336, because each team can be ordered in 3! = 6 ways. Selections with a condition, such as “at least two women”, are counted by cases or as the total minus what is not allowed. Distributions put items into boxes, and the count depends on whether the items, and the boxes, are identical or different. Derangements count the orders in which nothing is in its own place.

Choosing: nCr, at least and at most

Combinations and arrangements are linked by nPr = nCr × r!, since each selection of r objects can be put in r! orders. Two facts save time. nCr = nC(n − r): choosing the 3 who stay back from 10 is the same count as choosing the 7 who go. And the selections of every size add up to 2ⁿ, because each object is either in or out. “At least one” is almost always easiest as the total minus “none”. For “at least” and “at most” with two groups, add the allowed cases or subtract the forbidden ones, and use one method to check the other.

Distributions: identical or different items and boxes

Distributions of identical items into different boxes use stars and bars: the n items and r − 1 bars stand in a row, and choosing the bars’ places gives C(n + r − 1, r − 1) ways, or C(n − 1, r − 1) when no box may be empty.

Stirling numbers of the second kind, S(n, r), count the ways to split n different items into r identical non-empty groups.

Derangements, and the check against counting twice

A derangement is an order in which no item is in its own place, such as letters that all go into the wrong envelopes. Their number is D(n) = n!(1 − 1/1! + 1/2! − … ± 1/n!), which gives D(3) = 2, D(4) = 9 and D(5) = 44, and each value also follows from D(n) = (n − 1)(D(n − 1) + D(n − 2)). With exactly k items in place, choose those k and derange the rest: C(n, k) × D(n − k). Before trusting any method, ask whether it could produce the same selection twice; if it could, the count is too large, and splitting into cases is safer.

Five solved examples

1. A team with a condition. A 4-member team comes from 7 final-year and 5 pre-final-year students, with at least 2 final-year students. By cases: C(7, 2) × C(5, 2) + C(7, 3) × C(5, 1) + C(7, 4) = 210 + 175 + 35 = 420. By the complement: C(12, 4) − C(5, 4) − 7 × C(5, 3) = 495 − 5 − 70 = 420.
2. At least one. A thali comes with 5 side dishes, and a diner takes at least one: 2⁵ − 1 = 31 choices.
3. Points and lines. Ten points, no three in a line, give C(10, 2) = 45 lines and C(10, 3) = 120 triangles. A 12-sided polygon has C(12, 2) − 12 = 54 diagonals, since 12 of the 66 joins are its sides.
4. Sweets. Ten identical sweets for 3 children: C(12, 2) = 66 splits, or C(9, 2) = 36 if each child gets at least one, as in the figure.
5. Envelopes. Four letters go into four addressed envelopes. None in the right envelope: D(4) = 9. Exactly one right: choose it, then derange the other three, 4 × D(3) = 8.

# The five solved examples of the lesson, each counted twice: with the formula from the text and by listing every
# selection, distribution or arrangement with itertools.
from itertools import combinations, permutations, product
from fractions import Fraction
from math import comb, factorial

# 1. A team of 4 from 7 final-year (F) and 5 pre-final-year (P) students, with at least 2 final-year students.
students = [f"F{i}" for i in range(7)] + [f"P{i}" for i in range(5)]
teams = list(combinations(students, 4))
listed = sum(1 for t in teams if sum(s[0] == "F" for s in t) >= 2)
cases = comb(7, 2) * comb(5, 2) + comb(7, 3) * comb(5, 1) + comb(7, 4)
complement = comb(12, 4) - comb(5, 4) - comb(7, 1) * comb(5, 3)
print(f"1. Team: cases 210 + 175 + 35 = {cases}, complement 495 − 5 − 70 = {complement}, listed {listed} of {len(teams)}")

# 2. A thali with 5 side dishes, at least one of them taken.
taken = sum(1 for k in range(1, 6) for _ in combinations(range(5), k))
print(f"2. At least one of 5 dishes: 2⁵ − 1 = {2 ** 5 - 1}, listed {taken}")

# 3. Ten points with no three in a line: lines and triangles; the diagonals of a 12-sided polygon.
points = range(10)
diagonals = sum(1 for i, j in combinations(range(12), 2) if (j - i) % 12 not in (1, 11))
print(f"3. Lines {comb(10, 2)} (listed {len(list(combinations(points, 2)))}), "
      f"triangles {comb(10, 3)} (listed {len(list(combinations(points, 3)))}), "
      f"diagonals of a 12-gon {comb(12, 2)} − 12 = {comb(12, 2) - 12} (listed {diagonals})")

# 4. Ten identical sweets for 3 children: any split, and at least one sweet each.
splits = [(a, b, 10 - a - b) for a in range(11) for b in range(11 - a)]
print(f"4. Sweets: C(12, 2) = {comb(12, 2)}, listed {len(splits)}; at least one each: "
      f"C(9, 2) = {comb(9, 2)}, listed {sum(1 for s in splits if min(s) >= 1)}")

# 5. Four letters in four addressed envelopes: none in its own envelope, and exactly one in its own.
def right(order):
    return sum(order[i] == i for i in range(len(order)))

def derangements(n):
    """n!(1 − 1/1! + 1/2! − … ± 1/n!), the formula for D(n)."""
    return factorial(n) * sum(Fraction((-1) ** k, factorial(k)) for k in range(n + 1))

orders = list(permutations(range(4)))
print(f"5. Envelopes: none right D4 = {derangements(4)}, listed {sum(1 for o in orders if right(o) == 0)}; "
      f"exactly one right 4 × D3 = {4 * derangements(3)}, listed {sum(1 for o in orders if right(o) == 1)}")

# Distinct prizes are a different count: 4 different prizes for 3 students, any student may get several.
print(f"Distinct prizes: 3⁴ = {3 ** 4}, listed {len(list(product(range(3), repeat=4)))}")

1. Team: cases 210 + 175 + 35 = 420, complement 495 − 5 − 70 = 420, listed 420 of 495
2. At least one of 5 dishes: 2⁵ − 1 = 31, listed 31
3. Lines 45 (listed 45), triangles 120 (listed 120), diagonals of a 12-gon 66 − 12 = 54 (listed 54)
4. Sweets: C(12, 2) = 66, listed 66; at least one each: C(9, 2) = 36, listed 36
5. Envelopes: none right D4 = 9, listed 9; exactly one right 4 × D3 = 8, listed 8
Distinct prizes: 3⁴ = 81, listed 81

The program does not use the formulas for its own counts: it lists all 495 teams, every split of the sweets and every order of the letters, and keeps the ones that fit. Each listed count matches the formula beside it.

Exercise: distributions with limits, and derangements

The exercise counts distributions with a lower and an upper limit per box, and derangements of up to 15 letters, and the ten questions after it are untimed.

from functools import cache


def distributions(n, boxes, low=0, high=None):
    """Ways to put n identical items into the given number of different boxes, each holding low to high items."""
    # Replace this line with your code.
    return 0


def derangements(n):
    """Orders of n letters in which no letter is in its own envelope."""
    # Replace this line with your code.
    return 0

from counts import derangements, distributions


def test_the_lesson_sweets():
    """10 identical sweets for 3 children, then at least one each"""
    assert distributions(10, 3) == 66
    assert distributions(10, 3, low=1) == 36


def test_an_upper_limit():
    """7 items in 3 boxes holding at most 3 each, and a range of 2 to 8 items per box"""
    assert distributions(7, 3, high=3) == 6
    assert distributions(20, 4, low=2, high=8) == 231


def test_nothing_and_impossible_cases():
    """No items, and minimums that need more items than there are"""
    assert distributions(0, 3) == 1
    assert distributions(5, 2, low=3) == 0


def test_a_large_case_without_listing():
    """60 items in 6 boxes of at most 20"""
    assert distributions(60, 6, high=20) == 2248575


def test_small_derangements():
    """No letters, one letter, then the lesson's four envelopes"""
    assert [derangements(n) for n in range(6)] == [1, 0, 1, 2, 9, 44]


def test_larger_derangements():
    """Ten and fifteen letters"""
    assert derangements(10) == 1334961
    assert derangements(15) == 481066515734

Twelve selection and distribution items with full working Pro: opens with a Pro, Premium or Ultimate pass

Overcounting reproduced: four wrong methods against a full listing Pro: opens with a Pro, Premium or Ultimate pass

A 12-minute set of ten items, with answers and a rubric Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

Key takeaways

• nCr = n!/(r!(n − r)!) counts selections; nPr = nCr × r! orders them.
• “At least one” is the total minus “none”; check case sums with the complement.
• Identical items in different boxes: C(n + r − 1, r − 1), or C(n − 1, r − 1) with none empty.
• Different items in different boxes: rⁿ.
• Derangements: D(3) = 2, D(4) = 9, D(5) = 44; exactly k in place is C(n, k) × D(n − k).
• If a method can count the same selection twice, switch to cases.