1
$\begingroup$

I'm interested in the number of permutations for a specified number of fixed points and cycles.

Suppose we are in $S_n$. For any permutation in $S_n$, let $h$ be the number of changed points (the complement of fixed points) and $N$ be the number of cycles of the permutation with length no less than 2 (number of cycles for the changed points). Therefore, for a given $h$, the number of cycles $N$ can range from $1$ to $\lfloor h/2\rfloor$.

So my question is how many permutations are there in $S_n$ for a given $h$ and $N$? If the exact expression is complicated, can we derive a concise and sharp upper bound of the number in terms of $n,h,N$?

Improve this question
$\endgroup$

3 Answers 3

Reset to default
7
$\begingroup$

This is an easy exercise in the application of exponential generating functions. (See, for example, Richard Stanley's Enumerative Combinatorics, Vol. 2, chapter 5, for an exposition of the theory of exponential generating functions.)

A permutation can be viewed as a set of fixed points together with a derangement. The exponential generating function for sets of fixed points is $e^x$. If we weight each fixed point by $f$ then the generating function for weighted sets of fixed points is $e^{fx}$. The exponential generating function for derangements is $D(x)=e^{-x}/(1-x)$. Since each derangement is a set of cycles of length at least 2, if we weight each cycle of length at least 2 by $c$ then the exponential generating function for weighted derangements is $D(x)^c$. Thus the number of permutations in $S_n$ with $i$ fixed points (and therefore $n-i$ changed points) and $N$ cycles of length at least 2 is the coefficient of $\displaystyle f^ic^N\frac{x^n}{n!}$ in $$ e^{fx}D(x)^c = \frac{e^{(f-c)x}}{(1-x)^c}.$$ From this generating function you can easily get an explicit formula.

Improve this answer
$\endgroup$
0
5
$\begingroup$

The answer is $$\binom nh d_{h,N},$$ where $d_{h,N}$ is the number of derangements of size $h$ with $N$ cycles. By inclusion-exclusion we have: $$d_{h,N} = \sum_{i=0}^N (-1)^i\binom hi c(h-i,N-i),$$ where $c(\cdot,\cdot)$ are (unsigned) Stirling numbers of 1st kind.

P.S. Numbers $d_{h,N}$ are called associated Stirling numbers of first kind and listed in the sequence A008306 in the OEIS.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you! Is there any good upper bound for $d_{h,N}$? $\endgroup$
    – neverevernever
    Commented Sep 10, 2018 at 17:09
0
$\begingroup$

A formula can easily be obtain by summing over the expressions in this MSE Answer. How useful it is is a different question...

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .