Friday, October 4, 2019

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.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...