Stirling Number of Second Kind Identities

Stirling Number of Second Kind Identities Let N = {1, 2, 3, . . .} be the set of all natural numbers and k, m ∈ N. Denote by [n] the set N ∩ [1, n]. Let m-coloring on a set X be a function from X to [m]. Definition 0.1. S(k, m) is the number of ways to partition [k] into m sets. For convention, we put S(n, 0) = δ(n, 0). S(k, m)m! is the number of m-colorings of [k] which all colors are used, that is, the number of surjective functions from [k] to [m]. Theorem 0.1. For any x ∈ C, k x = k X S(k, m)(x)m m=0 where (x)m = x(x − 1) · · · (x − m + 1) is the falling factorial. Proof. It suffices to prove the identity for all natural number x. The LHS is the number of x-colorings of [k]. The summand in the RHS,   x S(k, m)m! , m is the number of ways to select m colors from x colors and color [k] using all selected colors. Corollary 0.1. For any x ∈ C, k X   x+m−1 S(k, m)m!(−1) (−x) = . m m=0
Proof. Put −x into x in Theorem 0.1 and note that −x = (−1)m m k m x+m−1 m Corollary 0.2. For |x| < 1, we have ∞ X  m k x 1 X ν x = S(k, m)m! . 1 − x 1 − x m=1 ν=0 k ν Proof. Expanding k X S(k, m)m!xm (1 − x)−m−1 m=1 by the binomial series, the coefficient of xν is   X   k X X m+w ν S(k, m)m! = S(k, m)m! . w m m=1 w≥0 m≥1 m+w=ν The result follows by S(k, 0) = 0 and Theorem 0.1. 1
. Theorem 0.2. Let m be an integer with 1 ≤ m ≤ k. We have m X   m S(k, m)m! = (m − i)k . (−1) i i=0 i Proof. Apply Inclusion-Exclusion Principle. Let Aj be the
set of functions from [k] to [m] such that j is excluded from the image. The term mi (m − i)k is the number of ways to select i members of [m] and exclude them from the image, that is, the number of elements in i-fold intersections of Aj . Corollary 0.3. Let r be a nonnegative integer. Then we have S(k, r + 1)(r + 1)! = k X m−k S(k, m)m!(−1) m=1   m−1 . r Proof. By Theorem 0.2 and Corollary 0.1, r+1 X   r+1 S(k, r + 1)(r + 1)! = (−1) (r + 1 − i)k i i=0  X   r+1 k X r+m−i i r+1 m−k = (−1) S(k, m)(−1) m! i m m=1 i=0    k r+1 X X r+m−i m−k i r+1 S(k, m)m!(−1) = (−1) i m m=1 i=0 i
The inner
sum is m−1 by noting that r i r+1 (−1) i is the coefficient of xi in (1 − x)r+1 ,
r+m−i is the
coefficient
of xr+1−i in x(1 − x)−m−1 , m and (−1)r r−m = m−1 is the coefficient of xr+1 of x(1−x)r+1−m−1 = x(1−x)r−m . r r Note that r = 0 case is proved by putting x = 1 in Corollary 0.1. There is a combinatorial proof of Corollary 0.3. The case r = 0 also has a combinatorial proof by involution between even number of parts and odd number of parts. We construct an involution Tk , mapping odd ordered partitions of k-element set to even and vice versa: if partition has part {k}, take a union with the previous part; otherwise move k into new separate part after itself. Example: ({3, 4}, {5}, {1, 2}) ↔ ({3, 4, 5}, {1, 2}). For ordered partitions of the form ({k}, . . .), use previous involution Tk−1 and so on. Example: ({5}, {4}, {1, 3}, {2}) ↔ ({5}, {4}, {1}, {3}, {2}). 2 The only partition without pair will be ({k}, {k − 1}, . . . , {1}) which is counted in S(k, k)k!. Therefore, we have X X S(k, m)m! = S(k, m)m! + (−1)k . m is even m is odd Then consider an ordered partition of m ≥ r + 1 parts, put r part-dividers among possible m − 1 positions. We nudge all colors between these dividers to one color. Then we have a surjective function from all m-coloring of [k] using all colors to all r + 1-coloring of [k] using all colors. Consider a coloring of [k] using all r + 1 colors with part sizes a1 , . . . , ar+1 . This particular coloring appears ! ! ar+1 a1 X X S(a1 , j)j!(−1)a1 −j · · · S(ar+1 , j)j!(−1)ar+1 −j = 1 j=0 j=0 times on the RHS. Thus, this shows that Corollary 0.3 for special case r = 0 imply the full version of Corollary 0.3. Corollary 0.4 (ec1-Chapter 3, Exercise 141(d)). For any t ∈ C, k X m−1 S(k, m)m!t = k X S(k, m)m!(−1)m−k (t + 1)m−1 . m=1 m=1 Proof. S(k, r + 1)(r + 1)! is the coefficient of tr on the LHS and
P k m−k m−1 is the coefficient of tr on the RHS. The result follows m=1 S(k, m)m!(−1) r by Corollary 0.3. Corollary 0.5. Let vk = 2k − 1. The expression ρ(x) = (1 − x)vk ∞ X ((ν + 1)k − ν k )xν ν=0 with the power series converges for |x| < 1, is a polynomial of degree vk − 1 satisfying 1 ρ(x) = (−1)k−1 xvk −1 ρ( ). x Proof. By Corollary 0.2, we have m  k ∞ X 1X x k k ν ((ν + 1) − ν )x = S(k, m)m! . x 1 − x m=1 ν=0 Then m  k 1X x ρ(x) = (1 − x) . S(k, m)m! x m=1 1−x vk Putting 1/x into ρ(x), we have  v  m k 1 k X 1 ρ(1/x) = 1 − x S(k, m)m! . x x−1 m=1 3 Then x vk −1  m k X 1 1 vk S(k, m)m! ρ( ) = (x − 1) x x−1 m=1  m k X 1 vk S(k, m)m! = −(1 − x) . x − 1 m=1 It suffices to prove that   m m k k X 1X 1 x k−1 S(k, m)m! S(k, m)m! = −(−1) . x m=1 1−x x−1 m=1 Put t = x 1−x = −1 − 1 , x−1 then we have x = t . t+1 Thus, we need to prove k k X t+1 X m k−1 S(k, m)m!t = −(−1) S(k, m)m!(−1)m (t + 1)m . t m=1 m=1 This is in fact Corollary 0.4. The polynomial ρ(x) has another expression ρ(x) = k X
S(k, m)m! + S(k, m + 1)(m + 1)! (1 − x)vk −m xm . m=0 4