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.