Combinatorial Probability - Applications

Combinatorial methods extend beyond basic counting to solve complex probability problems involving partitions, matchings, and recursive structures.

Stars and Bars Method

Theorem

The number of ways to distribute $n$ indistinguishable balls into $r$ distinguishable boxes is: $\binom{n+r-1}{r-1} = \binom{n+r-1}{n}$

Proof: Represent $n$ balls as stars and $r-1$ dividers as bars. Any arrangement of $n$ stars and $r-1$ bars corresponds to a distribution. The number of such arrangements is choosing $r-1$ positions for bars among $n+r-1$ total positions. □

Example

How many non-negative integer solutions are there to $x_1 + x_2 + x_3 = 10$ ?

Using stars and bars with $n = 10$ balls and $r = 3$ boxes: $\binom{10+3-1}{3-1} = \binom{12}{2} = 66$

If we require each $x_i \geq 1$ (positive integers), first place one ball in each box, leaving $n-r$ balls to distribute freely: $\binom{n-r+r-1}{r-1} = \binom{n-1}{r-1}$

Catalan Numbers

Definition

The $n$ -th Catalan number is: $C_n = \frac{1}{n+1}\binom{2n}{n} = \frac{(2n)!}{(n+1)!n!}$

Catalan numbers count many combinatorial structures:

Number of ways to properly parenthesize a product of $n+1$ factors
Number of paths from $(0,0)$ to $(n,n)$ staying below the diagonal $y = x$
Number of binary trees with $n$ internal nodes

The first few Catalan numbers: $1, 1, 2, 5, 14, 42, 132, \ldots$

Example

Ballot Problem: In an election, candidate A receives $n$ votes and candidate B receives $m$ votes, where $n > m$ . What is the probability that A is always ahead throughout the counting?

If votes are counted in random order, the probability is: $\frac{n-m}{n+m}$

For $n = 5, m = 3$ : probability = $\frac{5-3}{5+3} = \frac{2}{8} = 0.25$

Principle of Inclusion-Exclusion (General Form)

Theorem

For events $A_1, \ldots, A_n$ and sets $S_1, \ldots, S_n$ , the number of elements in none of the sets is: $\left|S_1^c \cap S_2^c \cap \cdots \cap S_n^c\right| = |U| - \sum |S_i| + \sum_{i<j} |S_i \cap S_j| - \sum_{i<j<k} |S_i \cap S_j \cap S_k| + \cdots$

where $U$ is the universal set.

Example

Derangements Revisited: The number of derangements $D_n$ (permutations with no fixed points) is: $D_n = n! \sum_{k=0}^n \frac{(-1)^k}{k!}$

For large $n$ , $D_n \approx \frac{n!}{e}$ .

Thus $D_{10} = 1,334,961$ compared to $10! = 3,628,800$ total permutations.

Stirling Numbers

Definition

Stirling numbers of the second kind $S(n,k)$ count the number of ways to partition $n$ distinct objects into $k$ non-empty unlabeled subsets.

Stirling numbers of the first kind $s(n,k)$ count the number of permutations of $n$ elements with exactly $k$ cycles.

These satisfy recurrence relations: $S(n,k) = k \cdot S(n-1,k) + S(n-1,k-1)$ $s(n,k) = (n-1) \cdot s(n-1,k) + s(n-1,k-1)$

Remark

Advanced combinatorial structures like Catalan numbers and Stirling numbers appear throughout discrete mathematics, computer science, and probability theory. They provide exact formulas for quantities that seem intractable at first glance.