Counting Basics

Fundamental Counting Principles

Product Rule (Multiplication Principle)

If a procedure has $k$ steps where:

• Step 1 can be done in $n_1$ ways
• Step 2 can be done in $n_2$ ways
• ...
• Step $k$ can be done in $n_k$ ways

Then the total number of ways to do the procedure is: $n_1 \times n_2 \times \cdots \times n_k$

Example: How many 3-letter codes can be made from 26 letters? $26 \times 26 \times 26 = 26^3 = 17,576$

Sum Rule (Addition Principle)

If a task can be done in $n_1$ ways OR $n_2$ ways (mutually exclusive): $n_1 + n_2$

Example: Choose a president from 10 men OR 8 women: $10 + 8 = 18 \text{ ways}$

Subtraction Rule (Inclusion-Exclusion for 2 Sets)

If we count some items multiple times: $|A \cup B| = |A| + |B| - |A \cap B|$

Example: Bit strings of length 8 starting with 1 OR ending with 00:

• Starting with 1: $2^7 = 128$
• Ending with 00: $2^6 = 64$
• Both: $2^5 = 32$
• Answer: $128 + 64 - 32 = 160$

Division Rule

If a procedure counts each outcome $d$ times: $\text{Actual count} = \frac{\text{Total count}}{d}$

Example: Seating $n$ people around a circular table: $\frac{n!}{n} = (n-1)!$ (Rotations are considered the same)

Bijection Principle

If there's a bijection between sets $A$ and $B$: $|A| = |B|$

Counting one set by counting another equivalent set.

Example: Binary strings of length $n$ with $k$ ones $=$ ways to choose $k$ positions from $n$ $= \binom{n}{k}$

Counting with Constraints

"At least one" Problems

Often easier to use complement: $\text{At least one} = \text{Total} - \text{None}$

Example: Bit strings of length 10 with at least one 1: $2^{10} - 1 = 1023$ (Subtract the all-zeros string)

"At most" Problems

$\text{At most } k = \sum_{i=0}^{k} \text{(exactly } i \text{)}$

Or use complement: $\text{At most } k = \text{Total} - \text{(more than } k \text{)}$

Common Counting Patterns

Bit Strings

Description	Count
Bit strings of length $n$	$2^n$
Bit strings of length $n$ with $k$ ones	$\binom{n}{k}$
Bit strings of length $n$ starting with 1	$2^{n-1}$
Bit strings with even number of ones	$2^{n-1}$

Strings from Alphabet

For alphabet of size $r$:

Description	Count
Strings of length $n$	$r^n$
Strings of length $n$ with distinct characters	$r(r-1)\cdots(r-n+1)$
Strings of length $\leq n$	$\frac{r^{n+1}-1}{r-1}$

Subsets

Description	Count
Subsets of $n$-element set	$2^n$
$k$-element subsets	$\binom{n}{k}$
Subsets of even size	$2^{n-1}$
Subsets of odd size	$2^{n-1}$

Tree Diagrams

Visualize sequential choices with a tree:

• Each path from root to leaf is one outcome
• Total outcomes = number of leaves

Complementary Counting

Count what you DON'T want and subtract: $|\text{Want}| = |\text{Total}| - |\text{Don't want}|$

Example: Integers from 1 to 1000 NOT divisible by 5 or 7:

• Total: 1000
• Divisible by 5: $\lfloor 1000/5 \rfloor = 200$
• Divisible by 7: $\lfloor 1000/7 \rfloor = 142$
• Divisible by both (35): $\lfloor 1000/35 \rfloor = 28$
• Not divisible by 5 or 7: $1000 - (200 + 142 - 28) = 686$

Double Counting

Count the same thing two different ways to establish an identity.

Example: Prove $\sum_{k=0}^{n} \binom{n}{k} = 2^n$

Method 1: Sum counts all subsets of an $n$-set. Method 2: Each element is in or out: $2^n$ subsets.

Therefore: $\sum_{k=0}^{n} \binom{n}{k} = 2^n$

Counting Functions

| Type | Count (for $f: A \to B$, $|A|=m$, $|B|=n$) | |------|-------------------------------------------| | All functions | $n^m$ | | Injections (one-to-one) | $\frac{n!}{(n-m)!} = P(n, m)$ | | Surjections (onto) | Complex formula using inclusion-exclusion | | Bijections | $n!$ (only when $m = n$) |

Counting Proofs

Algebraic Proof

Use algebraic manipulation to prove identities.

Combinatorial Proof

Show both sides count the same thing.

Example: Prove $\binom{n}{k} = \binom{n}{n-k}$

Combinatorial proof:

• Left: ways to choose $k$ elements to include
• Right: ways to choose $n-k$ elements to exclude
• Both count the same subsets! $\square$