Gregory's Triangle
Gregory's Triangle
Gregory's Triangle, also known as the Stirling triangle of the second kind, is a triangular array of numbers that represents Stirling numbers of the second kind, denoted as \( S(n, k) \) or \( \left\{\begin{matrix} n \\ k \end{matrix}\right\} \). These numbers count the number of ways to partition a set of \( n \) elements into \( k \) non-empty subsets.
Definition
The Stirling number of the second kind \( S(n, k) \) represents the number of ways to partition a set of \( n \) labeled objects into \( k \) non-empty unlabeled subsets. The triangle is arranged with row \( n \) containing the values \( S(n, 0) \), \( S(n, 1) \), \( S(n, 2) \), \( \ldots \), \( S(n, n) \).
Construction
Gregory's Triangle can be constructed using the following recurrence relation:
\[ S(n, k) = k \cdot S(n-1, k) + S(n-1, k-1) \]
with the initial conditions:
- \( S(0, 0) = 1 \)
- \( S(n, 0) = 0 \) for \( n > 0 \)
- \( S(n, k) = 0 \) for \( k > n \)
The recurrence relation reflects two cases:
- The element \( n \) is added to one of the \( k \) existing subsets from a partition of \( n-1 \) elements (giving \( k \cdot S(n-1, k) \) ways)
- The element \( n \) forms a new singleton subset, with the remaining \( n-1 \) elements partitioned into \( k-1 \) subsets (giving \( S(n-1, k-1) \) ways)
Properties
- Row sum: The sum of all entries in row \( n \) equals the Bell number \( B_n \), which counts the total number of partitions of a set with \( n \) elements: \( \sum_{k=0}^n S(n, k) = B_n \)
- Boundary values: \( S(n, 1) = 1 \) (only one way to partition \( n \) elements into one subset) and \( S(n, n) = 1 \) (only one way to partition \( n \) elements into \( n \) subsets)
- Second diagonal: \( S(n, n-1) = \binom{n}{2} \) (the number of ways to partition \( n \) elements into \( n-1 \) subsets is the number of ways to choose 2 elements to put together)
- Explicit formula:
\[ S(n, k) = \frac{1}{k!} \sum_{j=0}^k (-1)^{k-j} \binom{k}{j} j^n \]
Example
The first few rows of Gregory's Triangle are: \[ \begin{array}{ccccccc} n=0: & & & & 1 & & & \\ n=1: & & & 0 & & 1 & & \\ n=2: & & 0 & & 1 & & 1 & \\ n=3: & 0 & & 1 & & 3 & & 1 \\ n=4: & 0 & & 1 & & 7 & & 6 & 1 \end{array} \]
For instance, \( S(4, 2) = 7 \) because there are 7 ways to partition a set of 4 elements \( \{1, 2, 3, 4\} \) into 2 non-empty subsets:
- \( \{\{1\}, \{2,3,4\}\} \)
- \( \{\{2\}, \{1,3,4\}\} \)
- \( \{\{3\}, \{1,2,4\}\} \)
- \( \{\{4\}, \{1,2,3\}\} \)
- \( \{\{1,2\}, \{3,4\}\} \)
- \( \{\{1,3\}, \{2,4\}\} \)
- \( \{\{1,4\}, \{2,3\}\} \)
Applications
Stirling numbers of the second kind appear in various areas of mathematics, including:
- Combinatorics and set partition problems
- Expressing falling factorials in terms of ordinary powers
- Moment calculations in probability theory
- Analysis of algorithms and data structures
