discrete mathematics - Prove summation related to cycles

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

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.