Ferkans — Interactive Telecom Tutor

Counting as the Engine of Combinatorial Probability

When all outcomes in a finite sample space are equally likely, computing $\mathbb{P}(A) = |A|/|\Omega|$ reduces probability to pure counting. This sounds simple, but counting is surprisingly subtle — the answer depends critically on whether order matters and whether repetition is allowed.

The four sampling paradigms developed in this section generate almost every counting problem in discrete probability. They also appear repeatedly in coding theory: the number of codewords in a codebook is an ordered sample without replacement; the number of distinct error patterns is an unordered sample; the multinomial coefficient counts the ways to assign $n$ symbols across $r$ bins. Getting the counting right is, in Feller's words, "a matter of utmost importance."

,

Definition:
The Four Sampling Paradigms

Given a set $S$ with $|S| = n$ , we extract a sample of size $k$ . The number of distinct samples depends on two choices:

	With replacement	Without replacement
Ordered	$n^k$	$\frac{n!}{(n-k)!}$
Unordered	$\binom{n+k-1}{k}$	$\binom{n}{k}$

Ordered with replacement (sequences): $n^k$ — each of $k$ draws has $n$ choices independently.
Ordered without replacement (permutations): $n(n-1)\cdots(n-k+1) = n!/(n-k)!$ — choices decrease by one with each draw.
Unordered without replacement (combinations): $\binom{n}{k} = n!/(k!(n-k)!)$ — divide permutations by $k!$ since order within the sample does not matter.
Unordered with replacement (multisets): $\binom{n+k-1}{k}$ — equivalently, the number of ways to place $k$ indistinguishable balls into $n$ bins.

,

Theorem: Properties of Binomial Coefficients

For non-negative integers $n$ and $k$ with $k \leq n$ :

Symmetry: $\binom{n}{k} = \binom{n}{n-k}$ .
Pascal's rule: $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$ .
Binomial theorem: $(x+y)^n = \sum_{k=0}^{n} \binom{n}{k} x^k y^{n-k}$ .
Sum: $\sum_{k=0}^{n} \binom{n}{k} = 2^n$ .
Vandermonde's identity: $\binom{m+n}{r} = \sum_{k=0}^{r} \binom{m}{k}\binom{n}{r-k}$ .

Pascal's rule is the recursion underlying Pascal's triangle and enables efficient computation. The binomial theorem says the $\binom{n}{k}$ are exactly the coefficients in the expansion of $(x+y)^n$ , explaining the name "binomial coefficients." Property 4 follows by setting $x = y = 1$ .

Proof

Symmetry

$\binom{n}{k} = \frac{n!}{k!(n-k)!} = \frac{n!}{(n-k)!k!} = \binom{n}{n-k}$ . Combinatorially: choosing $k$ elements to include is the same as choosing $n-k$ elements to exclude.

Pascal's rule

Combinatorial proof: fix element $n \in S$ . Every $k$ -subset either includes $n$ (choose the remaining $k-1$ from the other $n-1$ elements: $\binom{n-1}{k-1}$ ways) or excludes $n$ (choose all $k$ from the other $n-1$ : $\binom{n-1}{k}$ ways). These cases are disjoint and exhaustive.

Binomial theorem (induction)

Base case $n=1$ : $(x+y)^1 = x + y = \binom{1}{0}y + \binom{1}{1}x$ . $\checkmark$

Inductive step: $(x+y)^n = (x+y)(x+y)^{n-1} = (x+y)\sum_{k=0}^{n-1}\binom{n-1}{k}x^k y^{n-1-k}$ . Distributing and collecting the coefficient of $x^k y^{n-k}$ : $\binom{n-1}{k} + \binom{n-1}{k-1} = \binom{n}{k}$ by Pascal's rule. $\blacksquare$

Example: The Birthday Problem

In a group of $n$ people, what is the probability that at least two share a birthday? Assume 365 equally likely birthdays and that birthdays are independent.

Solution

Define the complementary event

Let $A$ = "at least two people share a birthday." It is easier to compute $\mathbb{P}(A^c)$ = "all $n$ birthdays are distinct."

Count outcomes

The sample space of $n$ birthday assignments (ordered, with replacement) has $|\Omega| = 365^n$ outcomes.

The event $A^c$ (all distinct, ordered, without replacement): $|A^c| = 365 \times 364 \times \cdots \times (365 - n + 1) = \frac{365!}{(365-n)!}$ .

Compute the probability

$\mathbb{P}(A^c) = \frac{365!}{(365-n)! \cdot 365^n} = \prod_{k=0}^{n-1} \left(1 - \frac{k}{365}\right).KATEXPLACEHOLDER0END\mathbb{P}(A) = 1 - \prod_{k=0}^{n-1}\left(1 - \frac{k}{365}\right).$ $

Key threshold

For $n = 23$ : $\mathbb{P}(A) \approx 0.507$ . With only 23 people, it is already more likely than not that two share a birthday. For $n = 57$ : $\mathbb{P}(A) > 0.99$ . This counterintuitive result — the birthday paradox — arises because the number of pairs grows as $\binom{n}{2}$ , which reaches 365 far sooner than $n$ itself does.

The birthday paradox has direct applications in hashing and collision analysis for error-correcting codes and MAC protocols.

,

Birthday Problem: Collision Probability

Plot the probability that at least two people in a group of $n$ share a birthday, as a function of $n$ . Also compare with the Poisson approximation.

Parameters

Maximum group size

n

60

Days in year

d

365

Definition:
Multinomial Coefficient

Let $k_1, \ldots, k_r$ be non-negative integers with $k_1 + \cdots + k_r = n$ . The multinomial coefficient $\binom{n}{k_1, k_2, \ldots, k_r} \triangleq \frac{n!}{k_1!\, k_2! \cdots k_r!}$ counts the number of ways to partition a set of $n$ distinct objects into $r$ ordered groups of sizes $k_1, \ldots, k_r$ .

The multinomial theorem generalizes the binomial theorem: $(x_1 + x_2 + \cdots + x_r)^n = \sum_{\substack{k_1,\ldots,k_r \geq 0 \\ k_1+\cdots+k_r=n}} \binom{n}{k_1,\ldots,k_r} x_1^{k_1} \cdots x_r^{k_r}.$

The multinomial coefficient is fundamental in coding theory and information theory. The number of binary strings of length $n$ with exactly $k$ ones is $\binom{n}{k}$ (the $r = 2$ case). The number of sequences of $n$ symbols from an alphabet of size $r$ with prescribed type $(k_1, \ldots, k_r)$ is the multinomial coefficient — and bounding these counts is the starting point for the method of types in information theory (Book ITA, Chapter 3).

Example: Combinatorics in Binary Codes

(a) How many binary strings of length $n$ have Hamming weight exactly $k$ ? (b) How many binary strings of length $n$ have Hamming weight at most $t$ ? (c) In a random codebook of $M$ codewords, each chosen uniformly from $\{0,1\}^n$ , what is the expected number of codeword pairs at Hamming distance exactly $d$ ?

Solution

(a) Weight-$k$ binary strings

The positions of the $k$ ones can be chosen in $\binom{n}{k}$ ways. Each choice gives a distinct binary string of weight $k$ . Answer: $\binom{n}{k}$ .

(b) Hamming ball of radius $t$

Strings of weight at most $t$ form the Hamming ball of radius $t$ around the all-zeros codeword. Their count is: $\sum_{k=0}^{t} \binom{n}{k}.$ This quantity appears in the Hamming (sphere-packing) bound for error-correcting codes: a code with minimum distance $2t+1$ can correct all $t$ -error patterns, and the Hamming balls around codewords must be disjoint.

(c) Expected number of colliding pairs

Fix two codewords $\mathbf{c}_i \neq \mathbf{c}_j$ . Since each is chosen uniformly from $\{0,1\}^n$ , the probability that $d_H(\mathbf{c}_i, \mathbf{c}_j) = d$ is $\binom{n}{d}/2^n$ (there are $\binom{n}{d}$ strings at distance $d$ from $\mathbf{c}_i$ ). There are $\binom{M}{2}$ pairs, so by linearity of expectation: $\mathbb{E}[\text{\# pairs at distance } d] = \binom{M}{2}\frac{\binom{n}{d}}{2^n}.$ For the pairs to be rare (good codebook), we need this expectation to be small — which requires $M^2 \binom{n}{d} \ll 2^{n+1}$ .

Historical Note: The Birthday Paradox in Cryptography and Hashing

1939–present

The birthday problem was apparently first solved by von Mises in 1939, though Feller popularized it in his 1950 classic. The "paradox" is psychological: humans drastically underestimate the number of pairs in a group. With $n$ people, there are $\binom{n}{2} \approx n^2/2$ pairs — and any single pair has a 1/365 chance of a collision. The expected number of colliding pairs is approximately $\binom{n}{2}/365 \approx n^2/730$ , which equals 1 when $n \approx 27$ .

In cryptography, the birthday attack exploits exactly this calculation: a hash function with $2^m$ -bit outputs has a collision probability of 50% after approximately $2^{m/2}$ evaluations, not $2^m$ . This is why SHA-256 (256-bit output) is designed to resist attacks up to $2^{128}$ operations, not $2^{256}$ .

Birthday (Collision) Attack

Complexity:

O(2^{m/2})

expected, by the birthday bound

Input: Hash function

H: \{0,1\}^* \to \{0,1\}^m

Output: Collision pair

(x, x')

with

H(x) = H(x')

,

x \neq x'

Expected cost:

O(2^{m/2})

evaluations

1. Initialize hash table

T \leftarrow \emptyset

2. repeat

3.

\quad

Sample

x

uniformly from

\{0,1\}^*

4.

\quad

Compute

h \leftarrow H(x)

5.

\quad

if

h \in T

with stored preimage

x'

then

6.

\quad\quad

return

(x, x')

⟵ collision found

7.

\quad

else store

T[h] \leftarrow x

8. until collision found

The birthday bound is tight: by the Poisson approximation to the birthday problem, after $k \approx \sqrt{2 \ln 2} \cdot 2^{m/2}$ evaluations, a collision exists with probability $\geq 1/2$ .

Common Mistake: Ordered vs. Unordered: The Most Common Counting Mistake

Mistake:

In a lottery where 6 numbers are drawn without replacement from $\{1,\ldots,49\}$ , a student counts the total number of outcomes as $49 \times 48 \times 47 \times 46 \times 45 \times 44 = 49!/43!$ . This gives a much lower probability of winning than the correct answer.

Correction:

The lottery outcome is an unordered sample without replacement: the winner need not match the order of drawing, only the set of numbers. The correct count is $\binom{49}{6} = 49!/(6! \cdot 43!) = 13{,}983{,}816$ . The ordered count $49!/43! = 10{,}068{,}347{,}520$ overcounts each winning outcome by $6! = 720$ . The two counts differ by a factor of 720.

Rule: If the problem asks for a set of outcomes (the drawn numbers, a hand of cards, a subset of antennas), use combinations. If the problem asks for a sequence (the order of names drawn, a ranked list), use permutations.

Monty Hall Simulation

Simulate the Monty Hall problem. A car is hidden behind one of three doors; the host opens a losing door. Compare the win probability of the 'stay' vs 'switch' strategies across many simulations.

Parameters

Number of trials2000

Random seed7

Quick Check

A wireless base station has 8 antennas and must select 3 to activate for a transmission. How many distinct antenna subsets can be chosen?

$8 \times 7 \times 6 = 336$

$\binom{8}{3} = 56$

$8^3 = 512$

$\binom{10}{3} = 120$

Correction:

\binom{8}{3} = 56

An antenna subset is an unordered selection without replacement: $\binom{8}{3} = 8!/(3! \cdot 5!) = 56$ .

Combination

An unordered selection of $k$ elements from a set of $n$ , without replacement. Count: $\binom{n}{k} = n!/(k!(n-k)!)$ .

Permutation

An ordered selection of $k$ elements from a set of $n$ , without replacement. Count: $n!/(n-k)!$ . For $k=n$ : $n!$ ordered arrangements of all $n$ elements.

Related: Combination

Combinatorial Probability

Counting as the Engine of Combinatorial Probability

Definition: The Four Sampling Paradigms

Theorem: Properties of Binomial Coefficients

Symmetry

Pascal's rule

Binomial theorem (induction)

Example: The Birthday Problem

Define the complementary event

Count outcomes

Compute the probability

Key threshold

Birthday Problem: Collision Probability

Parameters

Definition: Multinomial Coefficient

Example: Combinatorics in Binary Codes

(a) Weight-$k$ binary strings

(b) Hamming ball of radius $t$

(c) Expected number of colliding pairs

Historical Note: The Birthday Paradox in Cryptography and Hashing

Birthday (Collision) Attack

Common Mistake: Ordered vs. Unordered: The Most Common Counting Mistake

Monty Hall Simulation

Parameters

Quick Check

Combination

Permutation

Definition:
The Four Sampling Paradigms

Definition:
Multinomial Coefficient