🔢Enumerative Combinatorics Unit 3 – Binomial Coefficients & Pascal's Triangle

Key Concepts

• Binomial coefficients $\binom{n}{k}$ count the number of ways to choose $k$ objects from a set of $n$ objects
• Pascal's triangle is a triangular array of numbers where each number is the sum of the two numbers directly above it
• The binomial theorem expresses the expansion of powers of a binomial $(x+y)^n$ using binomial coefficients
• Combinatorial proofs establish identities involving binomial coefficients by counting the same set in two different ways
  • Often involve clever interpretations of the quantities being counted
• Binomial coefficients satisfy numerous algebraic identities and recurrence relations
  • Examples include the absorption identity $\binom{n}{k} = \frac{n}{k}\binom{n-1}{k-1}$ and the symmetry identity $\binom{n}{k} = \binom{n}{n-k}$
• Probability distributions such as the binomial distribution rely heavily on binomial coefficients
• Generating functions provide a powerful tool for studying sequences defined by binomial coefficients

Historical Background

• Binomial coefficients have a rich history dating back to ancient mathematicians like Pingala (200 BC) and Al-Karaji (953-1029)
• Pascal's triangle, while named after Blaise Pascal, was known to earlier mathematicians in various cultures
  • Chinese mathematician Yang Hui studied the triangle in the 13th century
  • Persian mathematician Al-Karaji described the triangle's properties in the 10th century
• The binomial theorem was formally stated and proved by Isaac Newton in his 1665 work on the generalized binomial theorem
• James Gregory also discovered the theorem independently around the same time
• The study of binomial coefficients and their properties flourished in the 18th and 19th centuries with contributions from Euler, Lagrange, and others
• Modern combinatorics, including the study of binomial coefficients, emerged in the 20th century with the work of mathematicians like Gian-Carlo Rota and Richard Stanley

Binomial Theorem Basics

• The binomial theorem states that $(x+y)^n = \sum_{k=0}^n \binom{n}{k} x^{n-k} y^k$
  • Expresses the expansion of a binomial raised to a power $n$ as a sum involving binomial coefficients
• The coefficients in the expansion are precisely the binomial coefficients $\binom{n}{k}$
• For example, $(x+y)^3 = \binom{3}{0}x^3y^0 + \binom{3}{1}x^2y^1 + \binom{3}{2}x^1y^2 + \binom{3}{3}x^0y^3 = x^3 + 3x^2y + 3xy^2 + y^3$
• The binomial theorem has numerous applications in algebra, combinatorics, and probability
• Generalizations of the binomial theorem exist for expanding multinomials and infinite series

Pascal's Triangle Structure

• Pascal's triangle is constructed by starting with a 1 at the top and then filling in each number as the sum of the two numbers above it
  • The edges of the triangle are always 1
• The $n$-th row of Pascal's triangle contains the binomial coefficients $\binom{n}{k}$ for $k=0,1,\ldots,n$
• The sum of the entries in the $n$-th row is equal to $2^n$, as each row gives the coefficients of $(1+1)^n$
• The diagonal sums of Pascal's triangle give the Fibonacci numbers
• Many combinatorial identities can be proven using the structure of Pascal's triangle
  • For example, the hockey-stick identity $\sum_{i=r}^n \binom{i}{r} = \binom{n+1}{r+1}$ can be visualized in the triangle

Combinatorial Interpretations

• Binomial coefficients $\binom{n}{k}$ can be interpreted as the number of ways to choose a subset of $k$ elements from a set of $n$ elements
  • Often written as $C(n,k)$ or $_nC_k$ in this context
• Alternatively, $\binom{n}{k}$ counts the number of lattice paths from $(0,0)$ to $(k,n-k)$ using only unit steps right and up
• These interpretations provide a basis for many combinatorial proofs involving binomial coefficients
• Binomial coefficients also appear in the formulas for permutations and combinations with repetition
  • The number of permutations of $n$ objects with repetition allowed is $n^k$, where $k$ is the number of positions
  • The number of combinations of $n$ objects chosen with repetition is $\binom{n+k-1}{k}$ or $\binom{n+k-1}{n-1}$

Algebraic Properties

• Binomial coefficients satisfy the recurrence relation $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$
  • Follows from the construction of Pascal's triangle or by counting subsets
• The absorption identity states that $\binom{n}{k} = \frac{n}{k}\binom{n-1}{k-1}$
  • Can be proved algebraically or by counting permutations
• The symmetry identity asserts that $\binom{n}{k} = \binom{n}{n-k}$
  • Evident from the symmetry of Pascal's triangle
• The Vandermonde identity $\sum_{k=0}^r \binom{m}{k}\binom{n}{r-k} = \binom{m+n}{r}$ relates sums of products of binomial coefficients
• Numerous other identities exist, many of which can be proved combinatorially or by manipulating sums

Applications in Probability

• Binomial coefficients are fundamental in the study of discrete probability distributions
• The binomial distribution $B(n,p)$ models the number of successes in $n$ independent trials with success probability $p$
  • The probability of exactly $k$ successes is $P(X=k) = \binom{n}{k}p^k(1-p)^{n-k}$
• The binomial distribution arises in many real-world situations (coin flips, defective products, etc.)
• Binomial coefficients also appear in the formulas for other distributions (hypergeometric, negative binomial)
• The central limit theorem implies that the binomial distribution can be approximated by a normal distribution for large $n$

Advanced Topics and Extensions

• Generating functions are formal power series that encode the terms of a sequence as coefficients
  • The generating function for the sequence of binomial coefficients $\binom{n}{k}$ (fixed $n$) is $(1+x)^n$
• Generating functions can be used to derive identities, solve recurrences, and study asymptotic behavior
• The binomial theorem can be generalized to the multinomial theorem for expanding $(x_1+\cdots+x_m)^n$
  • Involves multinomial coefficients that count partitions of a set into $m$ parts
• The study of integer partitions and q-analogs leads to q-binomial coefficients and Gaussian polynomials
• Polya's enumeration theorem uses algebraic methods to count the number of configurations up to symmetry
  • Involves the cycle index polynomial of the symmetry group action