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 | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

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

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

# How many permutations leave an element unchanged?

**Physics Forums | Science Articles, Homework Help, Discussion**