Combinatorics Unit 8 Review: Partitions and Stirling Numbers

Key Concepts and Definitions

• Partition of a positive integer $n$ is a way of writing $n$ as a sum of positive integers, where the order of the summands does not matter
• Partitions are often represented using a partition diagram or Ferrers diagram, which consists of rows of dots or squares representing each summand
• Conjugate partition is obtained by reflecting the Ferrers diagram along the main diagonal, swapping rows and columns
• Stirling numbers are two types of numbers that arise in the study of permutations and combinations
  • Stirling numbers of the first kind count the number of permutations of $n$ elements with $k$ cycles
  • Stirling numbers of the second kind count the number of ways to partition a set of $n$ elements into $k$ non-empty subsets
• Generating functions are formal power series used to encode the sequence of values in a compact form, facilitating the study of their properties and relationships

Types of Partitions

• Integer partitions are the most common type, where a positive integer $n$ is expressed as a sum of positive integers (e.g., $5 = 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1$)
• Distinct partitions are partitions where no summand appears more than once (e.g., $5 = 4 + 1 = 3 + 2$)
• Odd partitions are partitions where all summands are odd numbers (e.g., $5 = 3 + 1 + 1 = 1 + 1 + 1 + 1 + 1$)
• Even partitions are partitions where all summands are even numbers (e.g., $6 = 4 + 2 = 2 + 2 + 2$)
• Restricted partitions are partitions where the summands are subject to certain constraints, such as being distinct or belonging to a specific set of numbers
• Partitions into parts greater than $k$ are partitions where all summands are greater than a fixed positive integer $k$
• Partitions into at most $m$ parts are partitions where the number of summands is less than or equal to a fixed positive integer $m$

Partition Functions and Properties

• Partition function $p(n)$ counts the number of partitions of a positive integer $n$
  • For example, $p(5) = 7$ because there are 7 partitions of 5: $5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1$
• Partition function satisfies the recurrence relation $p(n) = p(n-1) + p(n-2) - p(n-5) - p(n-7) + p(n-12) + p(n-15) - \dots$, known as Euler's pentagonal number theorem
• Generating function for the partition function is given by $\sum_{n=0}^{\infty} p(n)x^n = \prod_{k=1}^{\infty} \frac{1}{1-x^k}$
• Partition function grows asymptotically as $p(n) \sim \frac{1}{4n\sqrt{3}} e^{\pi \sqrt{\frac{2n}{3}}}$ (Hardy-Ramanujan asymptotic formula)
• Conjugate partitions have the same number of partitions, i.e., $p(n) = p(n')$, where $n'$ is the sum of the parts in the conjugate partition
• Number of distinct partitions of $n$, denoted by $q(n)$, is related to the partition function by the generating function $\sum_{n=0}^{\infty} q(n)x^n = \prod_{k=1}^{\infty} (1+x^k)$

Stirling Numbers of the First Kind

• Stirling numbers of the first kind, denoted by $s(n, k)$ or $\left[ \begin{smallmatrix} n \\ k \end{smallmatrix} \right]$, count the number of permutations of $n$ elements with $k$ cycles
• Stirling numbers of the first kind satisfy the recurrence relation $s(n+1, k) = s(n, k-1) + ns(n, k)$ with initial conditions $s(0, 0) = 1$ and $s(n, 0) = s(0, k) = 0$ for $n, k > 0$
• Unsigned Stirling numbers of the first kind, denoted by $|s(n, k)|$ or $c(n, k)$, count the number of permutations of $n$ elements with $k$ cycles, disregarding the sign
• Generating function for the unsigned Stirling numbers of the first kind is given by $\sum_{n=k}^{\infty} c(n, k)x^n = \frac{x^k}{(1-x)(1-2x)\dots(1-kx)}$
• Stirling numbers of the first kind appear in the expansion of the falling factorial: $(x)_n = \sum_{k=0}^{n} s(n, k)x^k$, where $(x)_n = x(x-1)(x-2)\dots(x-n+1)$

Stirling Numbers of the Second Kind

• Stirling numbers of the second kind, denoted by $S(n, k)$ or $\left\{ \begin{smallmatrix} n \\ k \end{smallmatrix} \right\}$, count the number of ways to partition a set of $n$ elements into $k$ non-empty subsets
• Stirling numbers of the second kind satisfy the recurrence relation $S(n+1, k) = kS(n, k) + S(n, k-1)$ with initial conditions $S(0, 0) = 1$ and $S(n, 0) = S(0, k) = 0$ for $n, k > 0$
• Generating function for the Stirling numbers of the second kind is given by $\sum_{n=k}^{\infty} S(n, k)x^n = \frac{x^k}{(1-x)(1-2x)\dots(1-kx)}$
• Stirling numbers of the second kind appear in the expansion of the rising factorial: $x^{(n)} = \sum_{k=0}^{n} S(n, k)x^k$, where $x^{(n)} = x(x+1)(x+2)\dots(x+n-1)$
• Bell numbers, denoted by $B_n$, count the total number of partitions of a set with $n$ elements and can be expressed as $B_n = \sum_{k=0}^{n} S(n, k)$

Generating Functions for Partitions

• Generating functions are powerful tools for studying partitions and their properties
• Ordinary generating function for the partition function $p(n)$ is given by $P(x) = \sum_{n=0}^{\infty} p(n)x^n = \prod_{k=1}^{\infty} \frac{1}{1-x^k}$
• Exponential generating function for the partition function $p(n)$ is given by $\widetilde{P}(x) = \sum_{n=0}^{\infty} p(n)\frac{x^n}{n!} = e^{e^x-1}$
• Generating functions can be manipulated using algebraic operations to derive identities and relationships between partition functions
  • For example, the generating function for distinct partitions $q(n)$ can be obtained from the generating function for $p(n)$ by replacing $x^k$ with $x^k + x^{2k} + x^{3k} + \dots = \frac{x^k}{1-x^k}$
• Generating functions can be used to derive asymptotic formulas for partition functions using complex analysis techniques, such as saddle point methods or circle methods

Applications in Combinatorics

• Partitions have numerous applications in various areas of combinatorics and discrete mathematics
• Partitions can be used to solve counting problems related to the distribution of objects into distinct categories or groups
• Stirling numbers of the second kind are used to count the number of ways to partition a set into non-empty subsets, which has applications in graph theory, coding theory, and computer science
• Stirling numbers of the first kind are related to the study of permutations and their cycle structure, which has applications in algebra and group theory
• Partitions and generating functions are used in the study of q-series and q-analogs, which have connections to various areas of mathematics, including number theory, representation theory, and mathematical physics
• Partitions and generating functions are also used in the study of lattice paths and their enumeration, which has applications in computer science, physics, and chemistry

Problem-Solving Techniques

• Identify the type of partition or counting problem and choose an appropriate representation or technique
• Use recurrence relations to derive formulas for partition functions or Stirling numbers
  • For example, to find $p(n)$, start with the base cases $p(0) = 1$ and $p(1) = 1$, then use the recurrence relation to calculate $p(2), p(3), \dots$
• Utilize generating functions to study the properties and relationships between partition functions or Stirling numbers
  • Manipulate generating functions using algebraic operations to derive identities or solve problems
• Apply combinatorial reasoning and bijective proofs to establish connections between different partition problems or counting problems
• Use the inclusion-exclusion principle to solve problems involving the enumeration of partitions or sets with specific properties
• Employ asymptotic analysis and approximation techniques to estimate the growth and behavior of partition functions for large values of $n$
• Break down complex partition problems into simpler subproblems and solve them using recursive or iterative approaches
• Look for symmetries, patterns, or special properties in the partition problem that can simplify the solution or provide insights into the underlying structure