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}}}
$$
 A: 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}}.$$
A: 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.
