Counting — Sum and Product Rules, Permutations, Combinations, Stars and Bars, Inclusion–Exclusion and Derangements

"How many passwords are possible?", "How many ways to pick a team?", "How many test cases does this loop run?" Counting questions appear in placement aptitude, GATE and algorithm analysis. The trick is choosing the right model — and checking it.

1. Sum and product rules

• Sum rule: if a task can be done in one of m ways or one of n ways (no overlap), there are m + n ways.
• Product rule: if a task has two steps with m and n ways, there are m × n ways.

Example: a password is 2 letters (A–Z) followed by 3 digits → 26 × 26 × 10 × 10 × 10 = 676,000.

2. Permutations and combinations

Examples: choosing a captain and vice-captain from 11 players is 11P2 = 110 (order matters). Choosing 2 players to rest is 11C2 = 55.

Let's verify the formulas by listing everything with itertools:

from itertools import permutations, combinations, product, combinations_with_replacement
from math import perm, comb

players = range(11)
print("captain + vice:", perm(11, 2), "=", len(list(permutations(players, 2))))
print("choose 2 to rest:", comb(11, 2), "=", len(list(combinations(players, 2))))
print("4-digit PINs:", 10 ** 4, "=", len(list(product(range(10), repeat=4))))
print("3 scoops from 5 flavours (repeats ok):", comb(5 + 3 - 1, 3), "=", len(list(combinations_with_replacement(range(5), 3))))

captain + vice: 110 = 110
choose 2 to rest: 55 = 55
4-digit PINs: 10000 = 10000
3 scoops from 5 flavours (repeats ok): 35 = 35

3. Arrangements with identical items

Arrangements of n items where some are identical: n! / (n₁! n₂! …).

"How many distinct arrangements of the letters of BANANA?" → 6! / (3! · 2!) = 720 / 12 = 60 (3 A's, 2 N's).

from itertools import permutations
from math import factorial

print("formula:", factorial(6) // (factorial(3) * factorial(2)))
print("brute force:", len(set(permutations("BANANA"))))

formula: 60
brute force: 60

4. Stars and bars

Distribute r identical items into n distinct boxes: C(r + n − 1, n − 1) (r stars, n − 1 bars).

"In how many ways can 10 identical chocolates be given to 3 children?" → C(12, 2) = 66. If each child must get at least one, give one each first, then distribute 7: C(9, 2) = 36.

Equivalent question: number of non-negative integer solutions of x + y + z = 10.

from math import comb

count = sum(1 for x in range(11) for y in range(11) for z in range(11) if x + y + z == 10)
print("x+y+z=10, x,y,z >= 0:", comb(12, 2), "=", count)
count_pos = sum(1 for x in range(1, 11) for y in range(1, 11) for z in range(1, 11) if x + y + z == 10)
print("x+y+z=10, x,y,z >= 1:", comb(9, 2), "=", count_pos)

x+y+z=10, x,y,z >= 0: 66 = 66
x+y+z=10, x,y,z >= 1: 36 = 36

5. Inclusion–exclusion

|A ∪ B ∪ C| = |A| + |B| + |C| − |A∩B| − |A∩C| − |B∩C| + |A∩B∩C|.

"How many numbers from 1 to 1000 are divisible by 2, 3 or 5?"

N = 1000
d = lambda k: N // k
formula = d(2) + d(3) + d(5) - d(6) - d(10) - d(15) + d(30)
brute = sum(1 for n in range(1, N + 1) if n % 2 == 0 or n % 3 == 0 or n % 5 == 0)
print("divisible by 2, 3 or 5:", formula, "=", brute)
print("divisible by none:", N - formula)

divisible by 2, 3 or 5: 734 = 734
divisible by none: 266

6. Derangements

A derangement is a permutation where no item stays in its original place — e.g. 4 students swap exam papers so nobody grades their own. The count:

Dₙ = n! (1 − 1/1! + 1/2! − … + (−1)ⁿ/n!), or recursively Dₙ = (n − 1)(Dₙ₋₁ + Dₙ₋₂), D₁ = 0, D₂ = 1.

from itertools import permutations

def d_recursive(n):
    if n == 1: return 0
    if n == 2: return 1
    return (n - 1) * (d_recursive(n - 1) + d_recursive(n - 2))

for n in range(2, 7):
    brute = sum(1 for p in permutations(range(n)) if all(p[i] != i for i in range(n)))
    print(f"D{n} = {d_recursive(n)} (brute force {brute})")

D2 = 1 (brute force 1)
D3 = 2 (brute force 2)
D4 = 9 (brute force 9)
D5 = 44 (brute force 44)
D6 = 265 (brute force 265)

Fun fact: as n grows, the chance that a random permutation is a derangement approaches 1/e ≈ 0.368.

7. Solving strategy

1. Does order matter? (arrangement vs selection)
2. Repetition allowed?
3. Identical or distinct items/boxes?
4. Restrictions? Handle the restricted item first, use complements ("total − bad"), or inclusion–exclusion.
5. Check small cases by brute force (like the code above).

Common mistakes

• Using nCr when order matters (captain/vice-captain) or nPr when it doesn't (a team).
• Double counting overlaps — use inclusion–exclusion.
• Forgetting identical letters in word arrangements.
• Stars and bars with the wrong number of bars (n boxes need n − 1 bars).

Quick recap

• Sum rule (or), product rule (and then).
• nPr = n!/(n−r)! (order), nCr = n!/(r!(n−r)!) (no order), nʳ with repetition, C(n+r−1, r) multisets.
• Identical items: n!/(n₁!n₂!…); stars and bars C(r+n−1, n−1).
• Inclusion–exclusion for "or" counts; derangements Dₙ = (n−1)(Dₙ₋₁ + Dₙ₋₂).