Present combinations

Here's a problem which seems simple enough but quickly becomes complicated.

Quote:

---

Suppose I have 3 friends and assign a different present to each friend. Purely for whimsical reasons, I then decide to give each friend the wrong present so that no one present is given to it's respective assigned recipient. How many ways can this be achieved? What if had 4 friends? What if i had 'n' friends?

---

I've been working on this problem for a few days and have realised that the problem requires combinatorials and/or permutations but cannot directly see how they are used in a general formula for 'n' friends.

So far i have found the following for 2, 3, 4, 5 and 6 friends where n is the number of friends and X is the number of combinations possible.

N = 2 3 4 5 6
X = 1 2 9 44 280

I also noticed, whilst writing my tables for each combination that it appears that we get certain groups whereby we can split all combinations in to n-1 groups of combinations where each combination in a group begins with the same present being given to the friend. Each group comprises of the same amount of combinations. This leads me to at least assume the formula X=(n-1)*f(n) where f(n) gives the number of combinations in a group.

This leads to the data now looking as follows:

N = 2 3 4 5 6
X = 1 2 9 44 280
f(n) = 1 2 3 11 56

I'm afraid to say that at this point my investigation slowed and I am unable to find any method of denoting f(n). As I stated previously, I believe that combinatorials are the answer but my knowledge of combination/permutation theory is very limited and doesn't surpass my College studies of nCr and nPr.

I would greatly appreciate any help with this problem as I have been working on it for a few days now and don't seem to be getting anywhere.

Bump!
I wonder if Marilyn vos Savant could handle this one. Perhaps we should ask her. I'm stumped, and here's a warning: it's contagious to try to work this one out. :eek:

First, I'll point out an error Talithin's counts by giving accurate results for N up to 10. These were found using brute force - I wrote a simple recursive subroutine to create all N! permutations, and counted the number that were valid for this function. Note that each is a multiple (N-1) of the sum of the previous two.

Code:

---

1        0
 2        1
 3        2 = 2(0+1)
 4        9 = 3(1+2)
 5        44 = 4(2+9)
 6      265 = 5(9+44)
 7      1854 = 6(44+265)
 8    14833 = 7(265+1854)
 9    133496 = 8(1854+14833)
10  1334961 = 9(14833+133496)

---

If Talithin had correctly counted 265 for N=6, he may have noticed 2+9=11 and 9+44=53 and figured this out himself.

Good job, Logophobic. I figured if anyone could solve it, you could.:thumb:

And the math formula for X as a function of N is...:confused: