Probability Puzzle!!?

if the kids must be split into these subgroups, then we have two scenarios to look at:

1.) 2 groups of 3 and 1 group of 2; this can be arranged in

(8 C 3)*(5 C 3)*(2 C 2) = 560 ways. Each group of 3 can be arranged in 2 ways, i.e.,

child 1 --> child 2 --> child 3 ---> child 1, or child 1 --> child 3 ---> child 2 ---> child 1.

The group of 2 can only be arranged in 1 way, so the total number of Secret Santa

arrangements in this case is 560*2*2 = 2240.

2.) 2 groups of 2 and 1 group of 4; this can be arranged in

(8 C 2)*(6 C 2)*(4 C 4) = 420 ways. Each group of 2 can be arranged in only 1 way.

The group of 4 is a bit trickier. I'll use a shorthand notation where if child 1 is

Secret Santa to child 2 I will write 1 -> 2. So some possible arrangements within

the group of 4 are:

(1 -> 2, 2 ->1, 3 -> 4. 4 -> 3)

(1 -> 2, 2 -> 3, 3 -> 4, 4 -> 1)

(1 -> 2, 2 -> 4, 3 -> 1, 4 -> 3)

We can do the same starting with 1 -> 3 and 1 -> 4, giving us 9 possible Secret

Santa arrangements within the group of 4. This results in a total of

420*9 = 3780 arrangements.

So adding the results from the 2 cases gives us 2240 + 3780 = 6020 possible

Secret Santa arrangements.

Edit: I just realized that there are many more groupings to consider, i.e.,

4 groups of 2, 2 groups of 4, 1 group each of 5 and 3 and 1 group each of 2 and 6.

You're right, this is a bit of a monster. I don't know why I looked at just splitting

the 8 into 3 groups: I think I'm just tired. I'll try again in the morning. As for

finding an expression for n in general - I'm not hopeful, but I'll try. :)

Edit: O.k., I'll look at the other cases now.

- 4 groups of 2: There are (8 C 2)*(6 C 2)*(4 C 2)*(2 C 2) = 2520 groupings, where

each group can be arranged in just 1 way, giving us 2520 arrangements in total.

- 2 groups of 4: There are (8 C 4)*(4 C 4) = 70 groupings possible, and as found

before there are 9 ways of arranging each group, giving us 70*9*9 = 5671 more

arrangements.

- 1 group each of 5 and 3: There are (8 C 5)*(3 C 3) = 56 groupings possible.

The group of 3 can be arranged in 2 ways, as found before. The group of 5

I'm still working on.

- 1 group each of 6 and 2: There are (8 C 6)*(2 C 2) = 28 groupings possible.

The group of 2 can be arranged in 1 way. The group of 6 I'm still working on.

I'm sorry that this is still a work in progress. Good question, though. :)

Edit #2: This has turned into a derangement problem. My answer is getting

long so I'm just going to give you a link rather than explain the concept myself.

http://en.wikipedia.org/wiki/Derangement

So from this article we have the number of 'derangements' of a group of 5 kids

as 44, and for a group of 6 kids there are 265 derangements.

Thus for the 5-3 grouping we end up with 56*2*44 = 4928 possible arrangements,

and for the 6-2 grouping we end up with 28*265 = 7420 possible arrangements.

So the final tally is 6020 + 2520 + 5671 + 4928 + 7420 = 26559 possible

Secret Santa arrangements where the kids are split into groups of 2 or more.

If the kids aren't sub-grouped, then the number of derangements of a group of 8 is

14833, so if this scenario is allowed as well then there would be 41392 arrangements.

As for dealing with n kids in general, the combination/derangement approach I've

used can be used for any n and for any sub-grouping scenario, but to establish

an actual expression would be messy and depend on the specific scenario.

For large n, note that the number of derangements of n objects will go to infinity

as n goes to infinity.

I got 8960. There 16 ways to arrange 2 groups of 3 and 1 group of 2. 8C3 or 56 for first group of 3 times 5C3 or 10 times 2C2 or 1 all times 16= 8960.