Prove summation related to cycles: For $n \geq r $ there is:$ \sum_{k=1}^{n} {b_r(n,k)x^k=(r-1)!\frac{x^\overline{n}}{(x+1)^\overline{r-1}}} $

Question

Let $b_r(n,k)$ be the number of n-permutations with $k$ cycles, in which numbers $1,2,\dots,r$ are in one cycle.

Prove that for $n \geq r $ there is:

$$ \sum_{k=1}^{n} {b_r(n,k)x^k=(r-1)!\frac{x^\overline{n}}{(x+1)^\overline{r-1}}} $$

Answer 1

As Brian Scott points out I have the wrong interpretation of the question. We want permutations where $1,2,\ldots r$ are on one cycle plus possibly some other elements, say $q.$

We obtain

$$b_r(n, k) = \sum_{q=0}^{n-r} {n-r\choose q} \frac{(r+q)!}{r+q} \left[n-r-q\atop k-1\right].$$

Recall the bivariate generating function of the Stirling numbers of the first kind, which is

$$G(z, u) = \exp\left(u\log\frac{1}{1-z}\right).$$

Observe that when we multiply two exponential generating functions of the sequences $\{a_n\}$ and $\{b_n\}$ we get that $$ A(z) B(z) = \sum_{n\ge 0} a_n \frac{z^n}{n!} \sum_{n\ge 0} b_n \frac{z^n}{n!} = \sum_{n\ge 0} \sum_{k=0}^n \frac{1}{k!}\frac{1}{(n-k)!} a_k b_{n-k} z^n\\ = \sum_{n\ge 0} \sum_{k=0}^n \frac{n!}{k!(n-k)!} a_k b_{n-k} \frac{z^n}{n!} = \sum_{n\ge 0} \left(\sum_{k=0}^n {n\choose k} a_k b_{n-k}\right)\frac{z^n}{n!}$$

i.e. the product of the two generating functions is the generating function of $$\sum_{k=0}^n {n\choose k} a_k b_{n-k}.$$

In the present case we have

$$A(z) = \sum_{q\ge 0} (r+q-1)! \frac{z^q}{q!} = (r-1)! \sum_{q\ge 0} {r+q-1\choose q} z^q \\ = (r-1)! \frac{1}{(1-z)^r}$$

and

$$B(z) = \sum_{q\ge 0} \left[q\atop k-1\right] \frac{z^q}{q!} = \frac{1}{(k-1)!} \left(\log\frac{1}{1-z}\right)^{k-1}.$$

We get for the sum

$$\sum_{k=1}^n b_r(n, k) x^k \\ = (n-r)! [z^{n-r}] (r-1)! \frac{1}{(1-z)^r} \sum_{k=1}^n x^k \frac{1}{(k-1)!} \left(\log\frac{1}{1-z}\right)^{k-1}.$$

We can certainly extend the sum to infinity as we are extracting the coefficient on $[z^{n-r}]:$

$$x (n-r)! [z^{n-r}] (r-1)! \frac{1}{(1-z)^r} \sum_{k=1}^\infty x^{k-1} \frac{1}{(k-1)!} \left(\log\frac{1}{1-z}\right)^{k-1} \\ = x (n-r)! [z^{n-r}] (r-1)! \frac{1}{(1-z)^r} \exp\left(x\log\frac{1}{1-z}\right) \\ = x (n-r)! [z^{n-r}] (r-1)! \frac{1}{(1-z)^r} \frac{1}{(1-z)^x} \\ = x (n-r)! [z^{n-r}] (r-1)! \frac{1}{(1-z)^{x+r}}.$$

This yields

$$x (n-r)! (r-1)! {x+r-1+n-r\choose n-r} \\ = x (n-r)! (r-1)! {x+n-1\choose n-r} \\ = (r-1)! \times x\times (x+n-1)^{\underline{n-r}} = (r-1)! \times x\times (x+r)^{\overline{n-r}}.$$

Answer 2

It should be clear by inspection that $$b_r(n,k) = (r-1)! \left[n-r\atop k-1\right].$$ The sum then becomes $$(r-1)! \sum_{k=1}^n x^k \left[n-r\atop k-1\right].$$

Recall the bivariate generating function of the Stirling numbers of the first kind, which is $$G(z, u) = \exp\left(u\log\frac{1}{1-z}\right).$$

This yields the following for the inner sum: $$\sum_{k=1}^n x^k (n-r)! [z^{n-r}] [u^{k-1}] G(z, u) \\= (n-r)! [z^{n-r}] \sum_{k=1}^n x^k \frac{1}{(k-1)!} \left(\log\frac{1}{1-z}\right)^{k-1}.$$

Now use the fact that $\log\frac{1}{1-z}$ starts at $z$ to see that terms with $k> n-r+1$ do not contribute to $[z^{n-r}]$ to get $$(n-r)! [z^{n-r}] \sum_{k=1}^\infty x^k \frac{1}{(k-1)!} \left(\log\frac{1}{1-z}\right)^{k-1}.$$

This simplifies to $$(n-r)! [z^{n-r}] x \exp\left(x\log\frac{1}{1-z}\right) = x \times (n-r)! [z^{n-r}] \left(\frac{1}{1-z}\right)^x \\= x \times (n-r)! \times {n-r+x-1\choose n-r} \\= x \times (n-r-1+x)(n-r-1+x-1)(n-r-1+x-2)\cdots x \\= x \times x^{\overline{n-r}}.$$

We thus have for the sum the formula $$\sum_{k=1}^n b_r(n, k) x^k = (r-1)! \times x \times x^{\overline{n-r}}.$$

I verified this by going back to the basics and implementing a Maple program that factors permutations. It confirms the above formula for small permutations ($n<10$). (This code is not optimized.)

with(combinat);

pet_disjcyc :=
proc(p)
        local dc, pos;

        dc := convert(p, 'disjcyc');

        for pos to nops(p) do
            if p[pos] = pos then
                dc := [op(dc), [pos]];
            fi;
        od;

        dc;
end;

gf :=
proc(n, r)
        option remember;
        local p, res, f, targ, q;

        res := 0; targ := {seq(q, q=1..r)};

        for p in permute(n) do
            f := pet_disjcyc(p);

            for cyc in f do
                if convert(cyc, set) = targ then
                   res := res + x^nops(f);
                   break;
                fi;
            od;   
        od;

        res;
end;

bs := (n,r)-> (r-1)!* sum(x^k*abs(stirling1(n-r,k-1)),k=1..n);
bsp := (n, r) -> (r-1)! * x * pochhammer(x, n-r);

Remark. This would seem to be a very basic calculation if the ordinary generating function instead of the exponential one is used. The OGF is in terms of the rising factorial, done. Very simple indeed.