# Counting and Combinatorics

Computer Science I · Discrete Mathematics · https://tryals.app/learn/computer-science-i/counting-and-combinatorics

## Counting Foundations

**Combinatorics** answers "how many ways?" for passwords, committees, and outcomes. Two basic rules build everything:

| Rule | Meaning | Operation |
| --- | --- | --- |
| **Sum rule** | Mutually exclusive choices ($m$ **or** $n$) | $m + n$ |
| **Product rule** | Sequential choices ($m$ **and** then $n$) | $m \times n$ |

**Common pitfall:** Mixing up sum and product rules. Remember that "and" multiplies while "or" adds. Reaching for the wrong operation severely inflates or deflates your total count.

## Permutations vs Combinations

The vital distinction is **order**. Rearranging chosen items creates a **Permutation** ($P(n,k)$) if order matters, but a **Combination** ($\binom{n}{k}$) if order is irrelevant.

- **Permutation:** $P(n,k) = \frac{n!}{(n-k)!}$. Counting ordered arrangements like race podiums or passwords.
- **Combination:** $\binom{n}{k} = \frac{n!}{k!(n-k)!}$. Unordered selections like committees or poker hands.

**Common pitfall:** Using permutations when order doesn't matter. Combinations divide by $k!$ to remove duplicate orderings.

## Practice questions

3 of this lesson's 9 practice questions, with answers. The full set is in the app.

### 1. Choosing 2 items from 5 gives 10 combinations and 20 permutations. Why is the permutation count exactly twice the combination count here, and what would the factor be for choosing 3?

A. Because permutations count with repetition allowed, which doubles the total.
B. Because permutations always give twice as many as combinations, whatever the numbers.
C. Because each combination can be ordered in 2! ways, counted separately.
D. Because the factor is the number of items chosen, so it would be 3 for choosing 3.

**Answer:** C. Because each combination can be ordered in 2! ways, counted separately.

**Why:** The pair {A, B} corresponds to AB and BA, so permutations count it twice; for a set of three there are 3! = 6 arrangements. Read P(n,k) = C(n,k)·k! as a combination being a permutation with the ordering forgotten. Both are defined *without* repetition, deciding whether order matters and whether repetition is allowed is most of the difficulty in elementary counting.

Page: https://tryals.app/practice/computer-science-i/counting-and-combinatorics/choosing-2-items-from-5-gives-10-combinations-and-20-permutations

### 2. In a room of 23 people the chance two share a birthday is about 50%. Why does that matter for hash functions and IDs?

A. Because it applies only to dates and has no bearing on identifier design
B. Because it means hash collisions are certain once 23 keys are inserted
C. Because collisions become likely near the square root of the space
D. Because it shows birthdays are not uniformly distributed through the year

**Answer:** C. Because collisions become likely near the square root of the space

**Why:** There are 253 pairs among 23 people, not 23 comparisons, and the same counting says collisions arrive near √N. A 64-bit random ID collides around four billion items, which is why UUIDs are 128 bits and why 'the space is huge' is not by itself an argument.

Page: https://tryals.app/practice/computer-science-i/counting-and-combinatorics/in-a-room-of-23-people-the-chance-two-share-a-birthday-is-about-50

### 3. Choosing a committee of 3 from 10 people gives a larger number than choosing a president, secretary and treasurer from the same 10.

**Answer:** False

**Why:** False. The committee is $\binom{10}{3} = 120$; the three distinct roles give $P(10,3) = 720$, six times more, because each committee can be assigned roles in 3! ways. The question to ask is always whether swapping two chosen items produces a different outcome.

Page: https://tryals.app/practice/computer-science-i/counting-and-combinatorics/choosing-a-committee-of-3-from-10-people-gives-a-larger-number-than