I was wondering about this, as you do around this time of year, and couldn’t work it out or find a solution on the net.

For a given number, n, of people in a Secret Santa*, how many possible sets of combinations of loops can there be?

There can be one leftover, in the case where the last person to pick a name picks their own name, but there can only ever be one one.

For example, for 4 people the sets of combinations are:

4 (a single loop with four)

3, 1

2, 2

So there are three sets. s=3

For 5 people:

5

4, 1

3, 2

2, 2, 2

Four sets. s=4

For 7 people:

7

6, 1

5, 2

4, 3

3, 2, 2

2, 2, 2, 1

3, 3, 1

Seven sets. s=7

and so on.

What is the relationship between n and s.

The closest thing I can find is the partition function P(n), which does not take into account the case where there is a left over person.

There has been a similar threadon this recently, but was a question about probabilities.

*A Secret Santa is where a group of people put names together (in a hat) and the names are distributed randomly back to each person in the group. You buy a present for the person you are given. If you pick your own name then you put it back and pick again. If you pick your name and there are no other names to pick, tough.