This seems like it should be easy, but my combinatorics is (are?) a little rusty. I want to know how many permutations of a given length leave at least one element unchanged, and how many leave exactly one unchanged. Started wondering about it when picking names out of a hat for a secret santa, but several times in a row at least one person picked their own name.(adsbygoogle = window.adsbygoogle || []).push({});

To define things a little more precisely:

A permutation [tex]\sigma[/tex] of length n is a bijection from the set {1, ..., n} to itself. For a given n, I want to know how many permutations satisfy:

[tex]a) \exists \: i \, \sigma(i) = i[/tex]

[tex]b) \exists \: \text{unique } i \, \sigma(i) = i[/tex]

I have an answer for (a), and a brief computerised check suggests it's correct, but it's in the form of a nested sum, and it feels like such a simple question should have a less calculation-heavy answer.

The answer I have is to add up:

- all the permutations for which 1 is left unchanged

- permutations for which 2 is left unchanged, minus those for which 1and2 are left unchanged (since these are now double-counted)

- perms for which 3 is left unchanged, minus those for which (3 and 1) or (3 and 2) are left unchanged, plus those for which 1, 2, and 3 are left unchanged (to take account of two occurrences of double-counting)

- perms for which 4 is unchanged, minus perms with (4 and 1) or (4 and 2) or (4 and 3) unchanged, plus perms with (4 and 1 and 2) or (4 and 1 and 3) or...

etc.

For any given number k, there are (n-1)! permutations such that [tex]\sigma(k)=k[/tex].

For a number i <= k, there are [tex]\begin{pmatrix}k-1 \\ i-1 \\ \end{pmatrix}[/tex] sets of size i-1 which are subsets of {1, ..., k-1}, and for each such subset {j_{1}, ..., j_{i}, k}, there are (n-i)! permutations for which j_{1}, ..., j_{i}, k are unchanged. Here I'm using the notation [tex]\begin{pmatrix}n \\ k \\ \end{pmatrix} = \frac{n!}{k!(n-k)!}[/tex]

So, for a permutation of size n, the answer to (a) is the sum:

[tex]\begin{tabular}{l r}

(n-1)! & \text{perms with }\sigma(1)=1 \\

(n-1)! - (n-2)! & \sigma(2)=2 \,\land\, \neg (\sigma(1)=1) \\

(n-1)! - 2*(n-2)! + (n-3)! & \sigma(3)=3 \,\land\, \neg ((\sigma(1)=1) \,\lor\, (\sigma(2)=2)) \\

(n-1)! - 3*(n-2)! + 3*(n-3)! - (n-4)! & \sigma(4)=4 \,\land\, \neg ((\sigma(1)=1) \,\lor\, (\sigma(2)=2) \,\lor\, (\sigma(3)=3)) \\

\ldots & \ldots \\

\end{tabular}[/tex]

Summing the rows first, this can be written as:

[tex]

\Sigma_{k=1}^n \, \Sigma_{i=1}^k \, (-1)^{i+1} \begin{pmatrix} k-1 \\ i-1 \\ \end{pmatrix} (n-i)!

[/tex]

Summing the columns first, it can equivalently be written as:

[tex]

\Sigma_{k=1}^n \left ((-1)^{k+1} (n-k)! \Sigma_{i=k-1}^{n-1} \begin{pmatrix} i \\ k-1 \\ \end{pmatrix} \right )

[/tex]

So, my question is, can either of the above nested sums be simplified, or can somebody come up with a smarter formula? By "smarter", I basically mean one with a fixed number of terms, rather than a number of terms that grows with n. Now that I've spent ages working out how to word my solution and code it up, I'm sure someone will come out with a 2-line answer that blows mine out of the water, but c'est la vie.

Thoughts on (b) are also welcome! And as a bonus open-ended question, since it was the Secret Santa Problem which got me thinking about this, can anyone think of a smart answer to the following problem:

Out of a group of n people, each is to be assigned a different person in the group to buy a present for, in such a way that nobody knows who the others in the group are buying for. An obvious solution is to pick names out of a hat, and if anybody picks their own name, repeat the whole thing. However, this can take quite a while (crunching the numbers above, you'll find there is quite a high probability that at least one person will pick themselves). Is there a constant time solution using common household objects (pen, paper, dice, coins, ... anything else you might find useful, butnota computer program, and not a third party picking names for you), which allows people to avoid picking themselves while giving them no information about who everybody else has picked?

**Physics Forums - The Fusion of Science and Community**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# How many permutations leave an element unchanged?

Loading...

Similar Threads - many permutations leave | Date |
---|---|

A "Many-to-One" Mapping of Variables in Logistic Regression | Jan 8, 2017 |

I Change of variables many-to-many transformation | Sep 6, 2016 |

How many permutations? | Jan 25, 2010 |

How many permutations can be made out of the letters of the word STATISTICS? | Mar 14, 2009 |

How many possible arrangements Permutations | Oct 25, 2004 |

**Physics Forums - The Fusion of Science and Community**