Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Stirling numbers and exponential generating functions in symbolic combinatorics
open-in-new
<h2 id="stirling-numbers-of-the-first-kind">Stirling numbers of the first kind</h2> <p>The unsigned Stirling numbers of the first kind count the number of permutations of [<i>n</i>] with <i>k</i> cycles. A permutation is a set of cycles, and hence the set P {\displaystyle {\mathcal {P}}\,} of permutations is given by </p> P = SET ( U × CYC ( Z ) ) , {\displaystyle {\mathcal {P}}=\operatorname {SET} ({\mathcal {U}}\times \operatorname {CYC} ({\mathcal {Z}})),\,} <p>where the singleton U {\displaystyle {\mathcal {U}}} marks cycles. This decomposition is examined in some detail on the page on the <a href="/facts/Random_permutation_statistics/fMI8d5p8">statistics of random permutations</a>. </p><p>Translating to generating functions we obtain the mixed generating function of the unsigned Stirling numbers of the first kind: </p> G ( z , u ) = exp ( u log 1 1 − z ) = ( 1 1 − z ) u = ∑ n = 0 ∞ ∑ k = 0 n [ n k ] u k z n n ! . {\displaystyle G(z,u)=\exp \left(u\log {\frac {1}{1-z}}\right)=\left({\frac {1}{1-z}}\right)^{u}=\sum _{n=0}^{\infty }\sum _{k=0}^{n}\left[{\begin{matrix}n\\k\end{matrix}}\right]u^{k}\,{\frac {z^{n}}{n!}}.} <p>Now the signed Stirling numbers of the first kind are obtained from the unsigned ones through the relation </p> ( − 1 ) n − k [ n k ] . {\displaystyle (-1)^{n-k}\left[{\begin{matrix}n\\k\end{matrix}}\right].} <p>Hence the generating function H ( z , u ) {\displaystyle H(z,u)} of these numbers is </p> H ( z , u ) = G ( − z , − u ) = ( 1 1 + z ) − u = ( 1 + z ) u = ∑ n = 0 ∞ ∑ k = 0 n ( − 1 ) n − k [ n k ] u k z n n ! . {\displaystyle H(z,u)=G(-z,-u)=\left({\frac {1}{1+z}}\right)^{-u}=(1+z)^{u}=\sum _{n=0}^{\infty }\sum _{k=0}^{n}(-1)^{n-k}\left[{\begin{matrix}n\\k\end{matrix}}\right]u^{k}\,{\frac {z^{n}}{n!}}.} <p>A variety of identities may be derived by manipulating this <a href="/facts/Generating_function/K7UVjnjL">generating function</a>: </p> ( 1 + z ) u = ∑ n = 0 ∞ ( u n ) z n = ∑ n = 0 ∞ z n n ! ∑ k = 0 n ( − 1 ) n − k [ n k ] u k = ∑ k = 0 ∞ u k ∑ n = k ∞ z n n ! ( − 1 ) n − k [ n k ] = e u log ( 1 + z ) . {\displaystyle (1+z)^{u}=\sum _{n=0}^{\infty }{u \choose n}z^{n}=\sum _{n=0}^{\infty }{\frac {z^{n}}{n!}}\sum _{k=0}^{n}(-1)^{n-k}\left[{\begin{matrix}n\\k\end{matrix}}\right]u^{k}=\sum _{k=0}^{\infty }u^{k}\sum _{n=k}^{\infty }{\frac {z^{n}}{n!}}(-1)^{n-k}\left[{\begin{matrix}n\\k\end{matrix}}\right]=e^{u\log(1+z)}.} <p>In particular, the order of summation may be exchanged, and derivatives taken, and then <i>z</i> or <i>u</i> may be fixed. </p> <h3>Finite sums</h3> <p>A simple sum is for n ≥ 2 {\displaystyle n\geq 2} </p> ∑ k = 0 n ( − 1 ) k [ n k ] = 0. {\displaystyle \sum _{k=0}^{n}(-1)^{k}\left[{\begin{matrix}n\\k\end{matrix}}\right]=0.} <p>This formula holds because the exponential generating function of the sum is </p> H ( z , − 1 ) = 1 1 + z and hence n ! [ z n ] H ( z , − 1 ) = ( − 1 ) n n ! . {\displaystyle H(z,-1)={\frac {1}{1+z}}\quad {\mbox{and hence}}\quad n![z^{n}]H(z,-1)=(-1)^{n}n!.} <h3>Infinite sums</h3> <p>Some infinite sums include </p> ∑ n = k ∞ [ n k ] z n n ! = ( − log ( 1 − z ) ) k k ! {\displaystyle \sum _{n=k}^{\infty }\left[{\begin{matrix}n\\k\end{matrix}}\right]{\frac {z^{n}}{n!}}={\frac {\left(-\log(1-z)\right)^{k}}{k!}}} <p>where | z | < 1 {\displaystyle |z|<1} (the singularity nearest to z = 0 {\displaystyle z=0} of log ( 1 + z ) {\displaystyle \log(1+z)} is at z = − 1. {\displaystyle z=-1.} ) </p><p>This relation holds because </p> [ u k ] H ( z , u ) = [ u k ] exp ( u log ( 1 + z ) ) = ( log ( 1 + z ) ) k k ! . {\displaystyle [u^{k}]H(z,u)=[u^{k}]\exp \left(u\log(1+z)\right)={\frac {\left(\log(1+z)\right)^{k}}{k!}}.} <h2 id="stirling-numbers-of-the-second-kind">Stirling numbers of the second kind</h2> <p>These numbers count the number of partitions of [<i>n</i>] into <i>k</i> nonempty subsets. First consider the total number of partitions, i.e. <i>B</i><i>n</i> where </p> B n = ∑ k = 1 n { n k } and B 0 = 1 , {\displaystyle B_{n}=\sum _{k=1}^{n}\left\{{\begin{matrix}n\\k\end{matrix}}\right\}{\mbox{ and }}B_{0}=1,} <p>i.e. the <a href="/facts/Bell_number/LXzHyaIF">Bell numbers</a>. The <a href="/facts/Flajolet%E2%80%93Sedgewick_fundamental_theorem/Sq6Q7JgX">Flajolet–Sedgewick fundamental theorem</a> applies (labelled case). The set B {\displaystyle {\mathcal {B}}\,} of partitions into non-empty subsets is given by ("set of non-empty sets of singletons") </p> B = SET ( SET ≥ 1 ( Z ) ) . {\displaystyle {\mathcal {B}}=\operatorname {SET} (\operatorname {SET} _{\geq 1}({\mathcal {Z}})).} <p>This decomposition is entirely analogous to the construction of the set P {\displaystyle {\mathcal {P}}\,} of permutations from cycles, which is given by </p> P = SET ( CYC ( Z ) ) . {\displaystyle {\mathcal {P}}=\operatorname {SET} (\operatorname {CYC} ({\mathcal {Z}})).} <p>and yields the Stirling numbers of the first kind. Hence the name "Stirling numbers of the second kind." </p><p>The decomposition is equivalent to the EGF </p> B ( z ) = exp ( exp z − 1 ) . {\displaystyle B(z)=\exp \left(\exp z-1\right).} <p>Differentiate to obtain </p> d d z B ( z ) = exp ( exp z − 1 ) exp z = B ( z ) exp z , {\displaystyle {\frac {d}{dz}}B(z)=\exp \left(\exp z-1\right)\exp z=B(z)\exp z,} <p>which implies that </p> B n + 1 = ∑ k = 0 n ( n k ) B k , {\displaystyle B_{n+1}=\sum _{k=0}^{n}{n \choose k}B_{k},} <p>by convolution of <a href="/facts/Exponential_generating_function/K7UVjnjL">exponential generating functions</a> and because differentiating an EGF drops the first coefficient and shifts <i>B</i><i>n</i>+1 to <i>z</i> <i>n</i>/<i>n</i>!. </p><p>The EGF of the Stirling numbers of the second kind is obtained by marking every subset that goes into the partition with the term U {\displaystyle {\mathcal {U}}\,} , giving </p> B = SET ( U × SET ≥ 1 ( Z ) ) . {\displaystyle {\mathcal {B}}=\operatorname {SET} ({\mathcal {U}}\times \operatorname {SET} _{\geq 1}({\mathcal {Z}})).} <p>Translating to generating functions, we obtain </p> B ( z , u ) = exp ( u ( exp z − 1 ) ) . {\displaystyle B(z,u)=\exp \left(u\left(\exp z-1\right)\right).} <p>This EGF yields the formula for the Stirling numbers of the second kind: </p> { n k } = n ! [ u k ] [ z n ] B ( z , u ) = n ! [ z n ] ( exp z − 1 ) k k ! {\displaystyle \left\{{\begin{matrix}n\\k\end{matrix}}\right\}=n![u^{k}][z^{n}]B(z,u)=n![z^{n}]{\frac {(\exp z-1)^{k}}{k!}}} <p>or </p> n ! [ z n ] 1 k ! ∑ j = 0 k ( k j ) exp ( j z ) ( − 1 ) k − j {\displaystyle n![z^{n}]{\frac {1}{k!}}\sum _{j=0}^{k}{k \choose j}\exp(jz)(-1)^{k-j}} <p>which simplifies to </p> n ! k ! ∑ j = 0 k ( k j ) ( − 1 ) k − j j n n ! = 1 k ! ∑ j = 0 k ( k j ) ( − 1 ) k − j j n . {\displaystyle {\frac {n!}{k!}}\sum _{j=0}^{k}{k \choose j}(-1)^{k-j}{\frac {j^{n}}{n!}}={\frac {1}{k!}}\sum _{j=0}^{k}{k \choose j}(-1)^{k-j}j^{n}.} <ul><li><a href="/facts/Ronald_Graham/ukKzczTL">Ronald Graham</a>, <a href="/facts/Donald_Knuth/GozNzDM6">Donald Knuth</a>, <a href="/facts/Oren_Patashnik/BTtERonb">Oren Patashnik</a> (1989): <i>Concrete Mathematics</i>, Addison–Wesley, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-201-14236-8</li> <li><a href="/facts/Dragoslav_Mitrinovi%C4%87/2KIjHClh">D. S. Mitrinovic</a>, <i>Sur une classe de nombre relies aux nombres de Stirling</i>, C. R. Acad. Sci. Paris 252 (1961), 2354–2356.</li> <li>A. C. R. Belton, <i>The monotone Poisson process</i>, in: <i>Quantum Probability</i> (M. Bozejko, W. Mlotkowski and J. Wysoczanski, eds.), Banach Center Publications 73, Polish Academy of Sciences, Warsaw, 2006</li> <li><a href="/facts/Milton_Abramowitz/6yRyez7P">Milton Abramowitz</a> and <a href="/facts/Irene_A._Stegun/FjSS1LDR">Irene A. Stegun</a>, <i>Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables</i>, USGPO, 1964, Washington DC, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-486-61272-4</li></ul>