Stirling numbers of the first kind
Numbers counting permutations by cycles and factorial expansions.
Stirling numbers of the first kind are a family of numbers studied in combinatorics, most notably in connection with permutations. The unsigned Stirling numbers of the first kind, often denoted with square brackets, directly count the number of permutations of a set of elements according to the number of disjoint cycles they contain, with fixed points counted as cycles of length one. For example, among the six permutations of three elements, one has three cycles, three have two cycles, and two have a single cycle. These numbers can also be defined algebraically as the coefficients that appear when expanding a falling factorial into powers of a variable, or when expanding a rising factorial. The signed Stirling numbers of the first kind have signs that depend solely on the parity of the difference between the two indices. These numbers satisfy a recurrence relation similar to that of Pascal's triangle, with specific boundary conditions. The unsigned Stirling numbers of the first kind also count permutations of a given size with a specified number of left-to-right maxima. The Stirling numbers of the first and second kinds are related as inverses of one another when arranged as triangular matrices. The values of the unsigned Stirling numbers can be arranged in a table resembling Pascal's triangle. These numbers are also expressible in terms of elementary symmetric polynomials evaluated at the integers from zero upward, and can be expanded using generalized harmonic numbers. Many identities link the Stirling numbers to binomial coefficients and to Bernoulli polynomials, and the study of these relationships is part of umbral calculus.
- field
- Mathematics, combinatorics
- known_for
- Coefficients in falling factorial expansions; counting permutations by number of cycles
Lore & Background
The Stirling numbers of the first kind, denoted s(n,k), are defined algebraically as the coefficients in the expansion of the falling factorial (x)_n = x(x-1)...(x-n+1) into powers of x. For example, (x)_3 = x^3 - 3x^2 + 2x gives s(3,3)=1, s(3,2)=-3, and s(3,1)=2. By convention, (x)_0=1 so s(0,0)=1. The unsigned Stirling numbers of the first kind, often written with square brackets, also appear as coefficients of the rising factorial x^\overline{n} = x(x+1)...(x+n-1). Subsequently, it was discovered that the absolute values |s(n,k)| equal the number of permutations of n elements with k disjoint cycles. For n=3, the six permutations yield one with three cycles, three with two cycles, and two with one cycle, matching the algebraic values. For n=4, the unsigned number [4 choose 2] equals 11, comprising three permutations of type (∙∙)(∙∙) and eight of type (∙∙∙)(∙). Alfréd Rényi observed that these numbers also count permutations with k left-to-right maxima. The signs of the signed Stirling numbers of the first kind depend only on the parity of n−k. The Stirling numbers of the first and second kind can be understood as inverses of one another when viewed as triangular matrices.
Reader's Guide
Stirling numbers of the first kind are fundamental in combinatorics, linking algebraic expansions with permutation cycle structure. Their dual definition—as coefficients of falling factorials and as counts of permutations by cycles—makes them a bridge between polynomial algebra and group theory. The unsigned versions, often denoted with square brackets, are particularly useful for enumerating permutations by cycle count, a concept central to the analysis of random permutations and the distribution of cycle lengths. The observation by Alfréd Rényi that these numbers also count left-to-right maxima adds another combinatorial interpretation. The relationship between signed and unsigned numbers, with signs determined by parity, and the inverse relationship with Stirling numbers of the second kind via triangular matrices, places them within a broader algebraic framework. These numbers appear in identities involving factorial expansions, generating functions, and the analysis of algorithms, such as the expected number of cycles in a random permutation. Their study continues to inform both pure combinatorics and applied fields like statistical mechanics and computer science.
Did You Know?
- The unsigned Stirling numbers of the first kind count permutations of n elements with k disjoint cycles, including fixed points as cycles of length one.
- For n=3, the unsigned numbers are [3 choose 3]=1, [3 choose 2]=3, and [3 choose 1]=2, matching the absolute values of the signed coefficients from the falling factorial expansion.
- Alfréd Rényi observed that the unsigned Stirling number of the first kind also counts the number of permutations of size n with k left-to-right maxima.
- The Stirling numbers of the first and second kind can be understood as inverses of one another when viewed as triangular matrices.
Frequently Asked Questions
Who is Stirling numbers of the first kind?
Stirling numbers of the first kind are a family of integers that sit at the intersection of permutation theory and polynomial algebra. Named after James Stirling, they appear whenever you need to express a falling factorial as a sum of ordinary powers of a variable.
What are Stirling numbers of the first kind's powers/role?
Their core function is twofold: they act as the coefficients that expand a falling factorial into plain powers, and their absolute values give the exact count of permutations of n elements that decompose into precisely k disjoint cycles.
How does Stirling numbers of the first kind's story end?
The narrative doesn't so much end as loop back into broader structures—these same integers feed into harmonic-number identities, logarithmic series, and the signed-versus-unsigned variants used in different algebraic contexts. In practice they keep resurfacing wherever cycle structure in permutations becomes the object of study.
Why is Stirling numbers of the first kind important?
They provide a clean integer-valued way to count permutations grouped by cycle count, which is one of the most fundamental structural questions in the subject. They also bridge discrete counting and analysis, since the identical coefficients reappear in logarithmic and harmonic expansions.
How do Stirling numbers of the first kind differ from the second kind?
The first kind is anchored to cycle decompositions of permutations and to expanding falling factorials into powers, whereas the second kind counts set partitions and performs the reverse expansion. They are essentially inverse operations when you switch between the two polynomial bases.
More in Combinatorics 1-24
Spotted an error? Know more?
This is a living reference — every entry is fact-audited, and reader corrections feed straight into our audit queue. Suggest an edit · See this site's audit record