Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I was reading "The Introduction to Combinatorial Analysis" by John Riordan. Let $c(n,k)$ denote the signless Stirling number of the first kind.

He asks, how many permutations there are with $k$ cycles, regardless of lengths, and then gives (link to Google books) the computation: $$ \begin{align*} \exp uc(t) &=\exp t(u+u^2/2+u^3/3+\cdots)\\ &=\exp t\log(1-u)^{-1}\\ &=(1-u)^{-t}\\ &= 1+\sum_1^\infty t(t+1)\cdots(t+n-1)\frac{u^n}{n!} \end{align*} $$ And so $c_n(t)=t(t+1)\cdots(t+n-1)$ is the generating function of the signless Stirling numbers. I understand all the equalities, but I don't get how he arrives at the result. Why does he start out by looking at $\exp uc(t)$? What's the $u$ for? Can someone please break it down? Thanks.

share|improve this question
add comment

1 Answer 1

up vote 5 down vote accepted

First, $\exp uC(t)$ is not an exponential of $uC(t)$, rather it is a notation for the following generating function $$ \sum_{n=0}^\infty C_n(t_1,t_2,\ldots,t_n) \frac{u^n}{n!} $$ where $C_n$ is a cycle indicator, also related to the Bell polynomial. As explained on the linked wiki page, as in the book you are reading, this generating function is, in fact, as exponential of another series: $$ \exp\left( \sum_{m=1}^\infty \frac{u^m}{m} t_m \right) $$

$C_n(t_1,t_2,\ldots, t_n)$ is a cycle indicator, meaning that coefficient by $t_1^{m_1} t_2^{m_2} \cdots t_n^{m_n}$ gives the number of permutations with $m_1$ cycles of length 1, $m_2$ cycles of length 2, and so on. As we are interested in the number of permutations with $k$ cycles, irrespective of their length, the generating function for such a number in a permutation of $S_n$ is $$ c_n(t) = \sum_{k=1}^n t^k \sum_{m_1+m_2+\cdots+m_n=k} C\left(m_1,m_2,\ldots,m_n\right) = C_n(t,t,\ldots,t) $$ Thus $$ \sum_{n=0}^\infty c_n(t) \frac{u^n}{n!} = \sum_{n=0}^\infty C_n(t,t,\ldots,t) \frac{u^n}{n!} = \exp\left( \sum_{m=1}^\infty \frac{u^m}{m!}t \right) = \exp\left(-t \log(1-u)\right) = (1-u)^{-t} $$ Now the latter, by the generalized binomial theorem is $$ \left(1-u\right)^{-t} = \sum_{m=0}^\infty \binom{-t}{m} (-u)^m = \sum_{m=0}^\infty \frac{(-t)(-t-1)\cdots (-t-m-1)}{m!} (-1)^m u^m = \sum_{m=0}^\infty \frac{(t)_m}{m!} u^m $$ where $(t)_m$ denotes the Pochhammer symbol.

share|improve this answer
    
Thank you Sasha, this definitely clears it up for me. –  Jakucha Feb 11 '12 at 22:35
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.