Closed formula for Stirling Cycle Numbers

211 Views Asked by At

The unsigned Stirling numbers of the first kind (or Stirling cycle numbers) ${k\brack n}$ count the number of permutations of the set $\{1, 2, 3, 4, \cdots, k\}$ with exactly $n$ disjoint cycles.

It is well known that $$\sum_{k=n}^{\infty}{{k\brack n}\frac{z^k}{k!}}=(-1)^n\frac{(\ln(1-z))^n}{n!}.$$

Is there a known generalized closed-form expression for the related function

$$\sum_{k=n}^{\infty}{{k+1\brack k-n+1}z^{k-n}},$$ where $n=1, 2, 3, \cdots$? If yes, can anyone refer me to some literature on that?

1

There are 1 best solutions below

3
On BEST ANSWER

We start with the following claim

$$\bbox[5px,border:2px solid #00A000]{ Q_r(z) = \sum_{n\ge 0} {n+r+1\brack n+1} z^n = \frac{1}{(1-z)^{2r+1}} \sum_{k=0}^r \left\langle\!\! \left\langle r \atop r-k \right\rangle\!\! \right\rangle z^k.}$$

We will prove this by induction. Introduce $P_r(z) = z^r Q_r(z).$ Note that depending on whether ball $n+r+2$ joins an existing cycle or turns into a fixed point we have

$${n+r+2\brack n+2} = (n+r+1) {n+r+1\brack n+2} + {n+r+1\brack n+1}.$$

Multiply by $z^{n+r}$ and sum over $n\ge 0$ to get

$$\sum_{n\ge 0} {n+r+2\brack n+2} z^{n+r} = \sum_{n\ge 0} (n+r+1) {n+r+1\brack n+2} z^{n+r} + P_r(z).$$

The first term is

$$\frac{1}{z} (P_r(z)-r! z^r)$$

and the second one

$$\left(z\sum_{n\ge 0} {n+2+(r-1)\brack n+2} z^{n+1+r-1} \right)' \\ = (-(r-1)! z^r + z P_{r-1}(z))' = -r! z^{r-1} + P_{r-1}(z) + z P'_{r-1}(z).$$

This gives the recurrence

$$P_r(z) - r!z^r = -r! z^r + z P_{r-1}(z) + z^2 P'_{r-1}(z)+ z P_r(z).$$

We obtain

$$P_r(z) = \frac{z}{1-z} (P_{r-1}(z) + z P'_{r-1}(z)) = \frac{z}{1-z} (z P_{r-1}(z))'.$$

We now prove by induction that

$$P_r(z) = \frac{1}{(1-z)^{2r+1}} \sum_{k=0}^r \left\langle\!\! \left\langle r \atop r-k \right\rangle\!\! \right\rangle z^{r+k}.$$

It certainly holds for $r=0$ where the infinite series gives $1/(1-z)$ and it also holds at $r=1$ as well where the sum gives

$$\sum_{n\ge 1} {n+1\choose 2} z^n = z \sum_{n\ge 0} {n+2\choose 2} z^n = \frac{z}{(1-z)^3}$$

and the Eulerian numbers produce

$$\frac{1}{(1-z)^3} \left[ \left\langle\!\! \left\langle 1 \atop 1 \right\rangle\!\! \right\rangle z + \left\langle\!\! \left\langle 1 \atop 0 \right\rangle\!\! \right\rangle z^2 \right] = \frac{z}{(1-z)^3}.$$

Now supposing it holds with $r\ge 1$ we must show that it holds for $r+1$. Doing the differentiation and multiplication we obtain

$$\frac{z}{1-z} \frac{2r+1}{(1-z)^{2r+2}} \sum_{k=0}^r \left\langle\!\! \left\langle r \atop r-k \right\rangle\!\! \right\rangle z^{r+1+k} \\ + \frac{z}{1-z} \frac{1}{(1-z)^{2r+1}} \sum_{k=0}^r \left\langle\!\! \left\langle r \atop r-k \right\rangle\!\! \right\rangle (r+1+k) z^{r+k}.$$

Factoring out $1/(1-z)^{2r+3}$ for the moment this becomes

$$z (2r+1) \sum_{k=0}^r \left\langle\!\! \left\langle r \atop r-k \right\rangle\!\! \right\rangle z^{r+1+k} + (z-z^2) \sum_{k=0}^r \left\langle\!\! \left\langle r \atop r-k \right\rangle\!\! \right\rangle (r+1+k) z^{r+k}.$$

or

$$(2r+1) \sum_{k=-1}^r \left\langle\!\! \left\langle r \atop r-k \right\rangle\!\! \right\rangle z^{r+2+k} + \sum_{k=0}^{r+1} \left\langle\!\! \left\langle r \atop r-k \right\rangle\!\! \right\rangle (r+1+k) z^{r+1+k} \\ - \sum_{k=-1}^r \left\langle\!\! \left\langle r \atop r-k \right\rangle\!\! \right\rangle (r+1+k) z^{r+2+k}.$$

Here we have included three zero terms, one in every sum. Continuing,

$$(2r+1) \sum_{k=0}^{r+1} \left\langle\!\! \left\langle r \atop r+1-k \right\rangle\!\! \right\rangle z^{r+1+k} + \sum_{k=0}^{r+1} \left\langle\!\! \left\langle r \atop r-k \right\rangle\!\! \right\rangle (r+1+k) z^{r+1+k} \\ - \sum_{k=0}^{r+1} \left\langle\!\! \left\langle r \atop r+1-k \right\rangle\!\! \right\rangle (r+k) z^{r+1+k}.$$

We obtain

$$\sum_{k=0}^{r+1} \left[(r+1-k) \left\langle\!\! \left\langle r \atop r+1-k \right\rangle\!\! \right\rangle + (r+1+k) \left\langle\!\! \left\langle r \atop r-k \right\rangle\!\! \right\rangle \right] z^{r+1+k}.$$

The Eulerian number recurrence (second order) according to OEIS A349556 is

$$\left\langle\!\! \left\langle n \atop k \right\rangle\!\! \right\rangle = k \left\langle\!\! \left\langle n-1 \atop k \right\rangle\!\! \right\rangle + (2n-k) \left\langle\!\! \left\langle n-1 \atop k-1 \right\rangle\!\! \right\rangle$$

Putting $n:=r+1$ and $k:=r+1-k$ and restoring the factor in front now yields

$$\frac{1}{(1-z)^{2r+3}} \sum_{k=0}^{r+1} \left\langle\!\! \left\langle r+1 \atop r+1-k \right\rangle\!\! \right\rangle z^{r+1+k}$$

thus concluding the induction.

Addendum. The reader might well wonder how the conjecture from the beginning was obtained i.e. how we find the closed form for small $r$ for lookup in the OEIS, which then points us to Eulerian numbers, enabling the whole computation.

Recall e.g. from Concrete Mathematics chapter 6.2. that

$$\bbox[5px,border:2px solid #00A000]{ {n\brack m} = \frac{(n-1)!}{(m-1)!} [w^{n-m}] \left(\frac{w\exp(w)}{\exp(w)-1}\right)^n.}$$

We get for our series

$$Q_r(z) = [w^r] \sum_{n\ge 0} z^n \frac{(n+r)!}{n!} \left(\frac{w}{1-\exp(-w)}\right)^{n+r+1} \\ = r! [w^r] \left(\frac{w}{1-\exp(-w)}\right)^{r+1} \sum_{n\ge 0} z^n {n+r\choose r} \left(\frac{w}{1-\exp(-w)}\right)^{n} \\ = r! [w^r] \left(\frac{w}{1-\exp(-w)}\right)^{r+1} \frac{1}{(1-zw/(1-\exp(-w)))^{r+1}} \\ = r! [w^r] \frac{w^{r+1}}{(1-\exp(-w)-zw)^{r+1}}.$$

Note that the fraction is a formal power series in $w$ with no pole at zero. Continuing,

$$r! \; \underset{w}{\mathrm{res}} \; \frac{1}{(1-\exp(-w)-zw)^{r+1}}.$$

A CAS like Maple for example can recognize the pole of order $r+1$ at zero which has now appeared and quickly compute the residue by differentiation. This will produce e.g.

$$Q_5(z) = {\frac {{z}^{4}+52\,{z}^{3}+328\,{z}^{2} +444\,z+120}{ \left( 1-z \right) ^{11}}}$$

which is enough to spot the pattern.

There is a closely related identity which has the Eulerian numbers in increasing order at this MSE link.