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

Source: https://skills101.in/learn/discrete-math/counting-permutations-combinations — Skills101 free tutorial (Discrete Mathematics). Updated 2026-11-09.

"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

| Situation | Order matters? | Repetition? | Formula |
|---|---|---|---|
| arrange r of n distinct items | **yes** | no | **nPr = n!/(n−r)!** |
| choose r of n distinct items | **no** | no | **nCr = n!/(r!(n−r)!)** |
| sequences of length r from n symbols | yes | yes | **nʳ** |
| choose r from n types, repetition allowed | no | yes | **C(n + r − 1, r)** (stars and bars) |

![Deciding the counting formula: if order matters and no repetition use permutations nPr; order matters with repetition gives n to the power r; order doesn't matter without repetition gives combinations nCr; order doesn't matter with repetition gives stars and bars C(n+r-1, r)](https://skills101.in/learn-img/discrete-math/counting-decision.svg)

**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`:

```python
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))))
```

```text
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).

```python
from itertools import permutations
from math import factorial

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

```text
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.

```python
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)
```

```text
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?"

![Inclusion-exclusion for three sets: add the three circles, subtract the three pairwise overlaps that were counted twice, then add back the centre counted three times then removed three times](https://skills101.in/learn-img/discrete-math/inclusion-exclusion.svg)

```python
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)
```

```text
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.

```python
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})")
```

```text
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ₙ₋₂).


Practice quiz and free certificate: https://skills101.in/learn/discrete-math/counting-permutations-combinations