How many permutations leave an element unchanged?

[Pi]

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.

To define things a little more precisely:
A permutation $$\sigma$$ 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:
$$a) \exists \: i \, \sigma(i) = i$$
$$b) \exists \: \text{unique } i \, \sigma(i) = i$$

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 1 and 2 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 $$\sigma(k)=k$$.
For a number i <= k, there are $$\begin{pmatrix}k-1 \\ i-1 \\ \end{pmatrix}$$ sets of size i-1 which are subsets of {1, ..., k-1}, and for each such subset {j₁, ..., j_i, k}, there are (n-i)! permutations for which j₁, ..., j_i, k are unchanged. Here I'm using the notation $$\begin{pmatrix}n \\ k \\ \end{pmatrix} = \frac{n!}{k!(n-k)!}$$

So, for a permutation of size n, the answer to (a) is the sum:
$$\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}$$

Summing the rows first, this can be written as:
$$\Sigma_{k=1}^n \, \Sigma_{i=1}^k \, (-1)^{i+1} \begin{pmatrix} k-1 \\ i-1 \\ \end{pmatrix} (n-i)!$$

Summing the columns first, it can equivalently be written as:
$$\Sigma_{k=1}^n \left ((-1)^{k+1} (n-k)! \Sigma_{i=k-1}^{n-1} \begin{pmatrix} i \\ k-1 \\ \end{pmatrix} \right )$$

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, but not a 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?

 

[Pi]

I find it easier to think about these things with concrete examples in front of me, so, since I've coded it anyway, you can have this in case it's helpful...


Here are all the permutations of length 4:

[1, 2, 3, 4] [2, 1, 3, 4] [3, 1, 2, 4] [4, 1, 2, 3]
[1, 2, 4, 3] [2, 1, 4, 3] [3, 1, 4, 2] [4, 1, 3, 2]
[1, 3, 2, 4] [2, 3, 1, 4] [3, 2, 1, 4] [4, 2, 1, 3]
[1, 3, 4, 2] [2, 3, 4, 1] [3, 2, 4, 1] [4, 2, 3, 1]
[1, 4, 2, 3] [2, 4, 1, 3] [3, 4, 1, 2] [4, 3, 1, 2]
[1, 4, 3, 2] [2, 4, 3, 1] [3, 4, 2, 1] [4, 3, 2, 1]

And all the ones of length 5:

[1, 2, 3, 4, 5] [2, 1, 3, 4, 5] [3, 1, 2, 4, 5] [4, 1, 2, 3, 5] [5, 1, 2, 3, 4]
[1, 2, 3, 5, 4] [2, 1, 3, 5, 4] [3, 1, 2, 5, 4] [4, 1, 2, 5, 3] [5, 1, 2, 4, 3]
[1, 2, 4, 3, 5] [2, 1, 4, 3, 5] [3, 1, 4, 2, 5] [4, 1, 3, 2, 5] [5, 1, 3, 2, 4]
[1, 2, 4, 5, 3] [2, 1, 4, 5, 3] [3, 1, 4, 5, 2] [4, 1, 3, 5, 2] [5, 1, 3, 4, 2]
[1, 2, 5, 3, 4] [2, 1, 5, 3, 4] [3, 1, 5, 2, 4] [4, 1, 5, 2, 3] [5, 1, 4, 2, 3]
[1, 2, 5, 4, 3] [2, 1, 5, 4, 3] [3, 1, 5, 4, 2] [4, 1, 5, 3, 2] [5, 1, 4, 3, 2]
[1, 3, 2, 4, 5] [2, 3, 1, 4, 5] [3, 2, 1, 4, 5] [4, 2, 1, 3, 5] [5, 2, 1, 3, 4]
[1, 3, 2, 5, 4] [2, 3, 1, 5, 4] [3, 2, 1, 5, 4] [4, 2, 1, 5, 3] [5, 2, 1, 4, 3]
[1, 3, 4, 2, 5] [2, 3, 4, 1, 5] [3, 2, 4, 1, 5] [4, 2, 3, 1, 5] [5, 2, 3, 1, 4]
[1, 3, 4, 5, 2] [2, 3, 4, 5, 1] [3, 2, 4, 5, 1] [4, 2, 3, 5, 1] [5, 2, 3, 4, 1]
[1, 3, 5, 2, 4] [2, 3, 5, 1, 4] [3, 2, 5, 1, 4] [4, 2, 5, 1, 3] [5, 2, 4, 1, 3]
[1, 3, 5, 4, 2] [2, 3, 5, 4, 1] [3, 2, 5, 4, 1] [4, 2, 5, 3, 1] [5, 2, 4, 3, 1]
[1, 4, 2, 3, 5] [2, 4, 1, 3, 5] [3, 4, 1, 2, 5] [4, 3, 1, 2, 5] [5, 3, 1, 2, 4]
[1, 4, 2, 5, 3] [2, 4, 1, 5, 3] [3, 4, 1, 5, 2] [4, 3, 1, 5, 2] [5, 3, 1, 4, 2]
[1, 4, 3, 2, 5] [2, 4, 3, 1, 5] [3, 4, 2, 1, 5] [4, 3, 2, 1, 5] [5, 3, 2, 1, 4]
[1, 4, 3, 5, 2] [2, 4, 3, 5, 1] [3, 4, 2, 5, 1] [4, 3, 2, 5, 1] [5, 3, 2, 4, 1]
[1, 4, 5, 2, 3] [2, 4, 5, 1, 3] [3, 4, 5, 1, 2] [4, 3, 5, 1, 2] [5, 3, 4, 1, 2]
[1, 4, 5, 3, 2] [2, 4, 5, 3, 1] [3, 4, 5, 2, 1] [4, 3, 5, 2, 1] [5, 3, 4, 2, 1]
[1, 5, 2, 3, 4] [2, 5, 1, 3, 4] [3, 5, 1, 2, 4] [4, 5, 1, 2, 3] [5, 4, 1, 2, 3]
[1, 5, 2, 4, 3] [2, 5, 1, 4, 3] [3, 5, 1, 4, 2] [4, 5, 1, 3, 2] [5, 4, 1, 3, 2]
[1, 5, 3, 2, 4] [2, 5, 3, 1, 4] [3, 5, 2, 1, 4] [4, 5, 2, 1, 3] [5, 4, 2, 1, 3]
[1, 5, 3, 4, 2] [2, 5, 3, 4, 1] [3, 5, 2, 4, 1] [4, 5, 2, 3, 1] [5, 4, 2, 3, 1]
[1, 5, 4, 2, 3] [2, 5, 4, 1, 3] [3, 5, 4, 1, 2] [4, 5, 3, 1, 2] [5, 4, 3, 1, 2]
[1, 5, 4, 3, 2] [2, 5, 4, 3, 1] [3, 5, 4, 2, 1] [4, 5, 3, 2, 1] [5, 4, 3, 2, 1]

And here are the answers to (a) and (b) for small n. These were found by directly counting the relevant permutations, and they agree to the nested sum formulas above.

with 1 people, there are 1 ways out of 1 for at least one person to pick themselves, and 1 ways for exactly one person to pick themselves.
with 2 people, there are 1 ways out of 2 for at least one person to pick themselves, and 0 ways for exactly one person to pick themselves.
with 3 people, there are 4 ways out of 6 for at least one person to pick themselves, and 3 ways for exactly one person to pick themselves.
with 4 people, there are 15 ways out of 24 for at least one person to pick themselves, and 8 ways for exactly one person to pick themselves.
with 5 people, there are 76 ways out of 120 for at least one person to pick themselves, and 45 ways for exactly one person to pick themselves.

 

[CRGreathouse]

You're looking for the number of permutations minus the number of derangements: n! - !n. See Sloane's http://www.research.att.com/~njas/sequences/A000166 for information and a nice formula for derangements.

 

[Pi]

Thanks! I found that link a little too brief, but the wikipedia article is good, once I knew to look for "derangements". Glad to see I wasn't missing anything obvious (or nothing I would have expected to be obvious to me, anyway).

My "Secret Santa Problem" is still open to anyone who wants to have a go - how can a group of people choose a derangement of themselves, in such a way that each person only knows the person to whom they are mapped, without wasting lots of time and without an outsider making the choices for them?

 

[CRGreathouse]

My "Secret Santa Problem" is still open to anyone who wants to have a go - how can a group of people choose a derangement of themselves, in such a way that each person only knows the person to whom they are mapped, without wasting lots of time and without an outsider making the choices for them?

First of all, the naive solution 'permute, have each person check if they're assigned to themself and start over if so' isn't actually that bad. It takes less than 1.6 attempts, on average: 1 + 1/e + 1/e^2 + ... ~= 1.582.

Depending on how many people you have, how honest they are, and what their field of vision is, having them go in a circle and choose the person, say, three people in front of them would be a possibility (using the fact that seeing behind you is harder than seeing in front of you).

 

[Pi]

I think it takes e attempts on average, doesn't it?

1/e + 2/e(1-1/e) + 3/e(1-1/e)^2 + ... = e

Which is still not that bad, I guess we were a bit unlucky not getting one after 5 attempts.

A circle might work in a large group, although I'm having trouble imagining how people could arrange themselves into a circle without at least some risk of being aware of who was behind them (blindfolded maybe?)! In a group of 5 or 6 it would be a non-starter. I'm wondering if the group could use markings on the names picked out of a hat, to calculate some sort of checksum that could give information about people needing to swap names around, without giving information about who had whom. Not sure if that's possible though.

 

[CRGreathouse]

I think it takes e attempts on average, doesn't it?

1/e + 2/e(1-1/e) + 3/e(1-1/e)^2 + ... = e

Yes, dumb mistake on my part. Or something.

Which is still not that bad, I guess we were a bit unlucky not getting one after 5 attempts.

10% chance, I suppose:
$$1/e\cdot\sum_{k=5}^{\infty}(1-1/e)^k\approx0.1009$$

I'm wondering if the group could use markings on the names picked out of a hat, to calculate some sort of checksum that could give information about people needing to swap names around, without giving information about who had whom. Not sure if that's possible though.

If you're minimizing total work, that's only advisable if calculating the checksum takes on average less than e times the work of permuting.

And it does open the door to all kinds of honesty-related attacks* and miscalculations.

* If you're choosing partners for the office Christmas party, it's not a big deal. But if you're pairing up gladiators it might just be worth someone's while to falsify their checksum as though they were assigned their own name if they were supposed to fight Maximus.