Number of permutations with a specified number of fixed points - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T19:20:01Z http://mathoverflow.net/feeds/question/9484 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/9484/number-of-permutations-with-a-specified-number-of-fixed-points Number of permutations with a specified number of fixed points Hans Stricker 2009-12-21T16:24:04Z 2010-02-16T00:54:18Z <p>Let F(k,n) be the number of permutations of an n-element set that keep k elements fixed.</p> <p>We know:</p> <ol> <li>F(n,n) = 1</li> <li>F(n-1,n) = 0</li> <li><p>F(n-2,n) = $\binom {n} {2}$</p> <p>...</p></li> <li><p>F(0,n) = n! $\cdot \sum_{k=0}^n \frac {(-1)^k}{k!}$ (the subfactorial)</p></li> </ol> <p>The summation formula is obviously</p> <p>$\displaystyle\sum_{k=0}^n F(k,n) = n!$</p> <p>A recursive definition of F(k,n) is (my claim):</p> <p>$F(k,n) = \binom {n} {k} \cdot ( k! - \displaystyle\sum_{i=0}^{k-1} F(i,k) )$</p> <p>Question 1: Is there a common name for the "generalized factorial" F(k,n)?</p> <p>Question 2: Does anyone know a closed form for F(k,n) or have an idea how to get it from the recursive definition? (generating function?)</p> http://mathoverflow.net/questions/9484/number-of-permutations-with-a-specified-number-of-fixed-points/9486#9486 Answer by Michael Lugo for Number of permutations with a specified number of fixed points Michael Lugo 2009-12-21T16:31:20Z 2009-12-21T17:15:16Z <p>The "semi-exponential" generating function for these is </p> <p>$\sum_{n=0}^\infty \sum_{k=0}^n {F(k,n) z^n u^k \over n!} = {\exp((u-1)z) \over 1-z}$</p> <p>which follows from the exponential formula. </p> <p>These numbers are apparently called the <a href="http://www.research.att.com/~njas/sequences/A008290" rel="nofollow">rencontres numbers</a> although I'm not sure how standard that name is.</p> <p>Now, how do we get a formula for these numbers out of this? First note that</p> <p>$$exp((u-1)z) = 1 + (u-1)z + {(u-1)^2 \over 2!} z^2 + {(u-1)^3 \over 3!} z^3 + \cdots$$</p> <p>and therefore the "coefficient" (actually a polynomial in $u$) of $z^n$ in $exp((u-1)z)/(1-z)$ is</p> <p>$$P_n(u) = 1 + (u-1) + {(u-1)^2 \over 2!} + \cdots + {(u-1)^n \over n!} = \sum_{j=0}^n {{(u-1)^j } \over j!}$$</p> <p>since division of a generating function by $1-z$ has the effect of taking partial sums of the coefficients.</p> <p>The coefficient of $u^k$ in $P_n(u)$ (which I'll denote $[u^k] P_n(u)$, where $[u^k]$ denotes taking the $u^k$-coefficient) is then</p> <p>$$[u^k] P_n(u) = \sum_{j=0}^n [u^k] {(u-1)^j \over j!}$$</p> <p>But we only need to do the sum for $j = k, \ldots, n$; the lower terms are zero, since they are the $u^k$-coefficient of a polynomial of degree less than $k$. So</p> <p>$$[u^k] P_n(u) = \sum_{j=k}^n [u^k] {(u-1)^j \over j!}$$</p> <p>and by the binomial theorem,</p> <p>$$[u^k] P_n(u) = \sum_{j=k}^n {(-1)^{j-k} \over k! (j-k)!}$$</p> <p>Finally, $F(k,n) = n! [u^k] P_n(u)$, and so we have</p> <p>$$F(k,n) = n! \sum_{j=k}^n {(-1)^{j-k} \over k!(j-k)!}$$</p> http://mathoverflow.net/questions/9484/number-of-permutations-with-a-specified-number-of-fixed-points/9491#9491 Answer by Reid Barton for Number of permutations with a specified number of fixed points Reid Barton 2009-12-21T17:09:07Z 2009-12-21T17:09:07Z <p>A permutation of {1, ..., n} with k fixed points is determined by choosing which k elements of {1, ..., n} it fixes and choosing a derangement of the remaining n-k elements. So,</p> <p>$F(k, n) = {n \choose k} F(0, n-k)$.</p> <p>(This formula is also on the page Michael Lugo linked to.) You have already given one formula for the number of derangements on n letters. Another one is F(0, n) = the nearest integer to n!/e.</p> http://mathoverflow.net/questions/9484/number-of-permutations-with-a-specified-number-of-fixed-points/15397#15397 Answer by Hans Stricker for Number of permutations with a specified number of fixed points Hans Stricker 2010-02-16T00:54:18Z 2010-02-16T00:54:18Z <p>see <a href="http://www.research.att.com/~njas/sequences/A000166" rel="nofollow">Subfactorial or rencontres numbers, or derangements: number of permutations of n elements with no fixed points</a></p>