Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Re: a gift exchange
Posted:
Nov 24, 2004 5:48 PM


On Wed, 24 Nov 2004 07:49:18 0500, Jerry Grossman wrote: >This problem has been floating around for a few years. I heard >it from Gary Thompson, Grove City College (Pennsylvania). >I don't think anyone has the general solution (with n people). >You can use a computer to brute force your way to the answer >for small values of n. In particular, the answer for n=10 is >160127/2116800, which is about 0.075645786. > >If anyone has any information about solutions, I'd very much >like to hear about it. > >Jerry Grossman >Oakland University >
Let's denote n? the number of true shuffles from n elements, i.e., the number of permutations from n elements, in which no element sits in its original place.
1? = 0 obviously
2? = 1 12 not OK 21 OK
3? = 2 123 132 213 231 OK 312 OK 321 4? = 9 1234 1243 1324 1342 1423 1432 2134 2143 OK 2314 2341 OK 2413 OK 2431 3124 3142 OK 3214 3241 3412 OK 3421 OK 4123 OK 4132 4213 4231 4312 OK 4321 OK
In general,
n? = n!  C(n,1)*(n1)?  C(n,2)*(n2)?  ...   C(n,n1)*1?  1
where C(n,k) is the number of combinations of k elements out of n. For example,
4? = 4!  C(4,1)*3?  C(4,2)*2?  C(4,3)*1?  C(4,4)*0? = 24  4*2  6*1  6*0  1 = 24  15 = 9
Take all permutations and subtract the unacceptable permutations, when exactly 1 element sits in its place: C(4,1) = 4 possibilities multiplied by the number of possibilities, when remaining 3 elements make a true shuffle, i.e., 3?. Then subtract the unacceptable permutations, when exactly 2 elements sit in their places: C(4,2) = 6 possibilities multiplied by the number of possibilities, when remaining 2 elements make a true shuffle, i.e., 2?. Then subtract the unacceptable permutations, when exactly 3 elements sit in their places: C(4,3) = 4 possibilities multiplied by the number of possibilities, when remaining 1 element makes a true shuffle, i.e., 1?. Obviously zero. When 3 elements sit in their places, the 4th element must also sit in its place, i.e., no acceptable possibilities. Then subtract the one unacceptable possibility, when all elements sit in their original places.
If we define 0? = 1 (just like 0! = 1, by vacuity), then we can write
n! = C(n,0)*n? + C(n,1)*(n1)? + C(n,0)*(n2)? + ... + + C(n,n2)*2? + C(n,n1)*1? + C(n,n1)*0?
or, using C(n,k) = C(n,nk),
n! = C(n,n)*n? + C(n,n1)*(n1)? + C(n,n2)*(n2)? + ... + + C(n,2)*2? + C(n,1)*1? + C(n,0)*0?
Calculating n! and n? for n up to 11:
0! = 1 0? = 1 1! = 1 1? = 0 2! = 2 2? = 1 3! = 6 3? = 2 4! = 24 4? = 9 5! = 120 5? = 44 6! = 720 6? = 265 7! = 5040 7? = 1854 8! = 40320 8? = 14833 9! = 362880 9? = 133496 10! = 3628800 10? = 1334961 11! = 39916800 11? = 14684570
and taking their ratios, 0!/0? = 0.367879441... 1!/1? = undefined 2!/2? = 2 3!/3? = 3 4!/4? = 2.666666667... 5!/5? = 2.727272727... 6!/6? = 2.716981132... 7!/7? = 2.718446602... 8!/8? = 2.718263332... 9!/9? = 2.718283694... 10!/10? = 2.718281658... 11!/11? = 2.718281843... e = 2.718281828...
n!/n? approaches e very fast. In fact, for all n > 0, we can write n? = [n!/e + 0.5], where [x] is the integer part of x. [x + 0.5] obviously means rounding x to the nearest integer. We also have the recurrence formulas
n? = n*(n1)? + (1)^n with the seed 0? = 1
or n? = (n1)*[(n1)? + (n2)?] with the seed 0? = 1 and 1? = 0
0? = 1 1? = 0 = 1 * 1  1 2? = 1 = 2 * 0 + 1 = 1 * (0 + 1) 3? = 2 = 3 * 1  1 = 2 * (1 + 0) 4? = 9 = 4 * 2 + 1 = 3 * (2 + 1) 5? = 44 = 5 * 9  1 = 4 * (9 + 2) 6? = 265 = 6 * 44 + 1 = 5 * (44 + 9) 7? = 1854 = 7 * 265  1 = 6 * (265 + 44) 8? = 14833 = 8 * 1854 + 1 = 7 * (1854 + 265) 9? = 133496 = 9 * 14833  1 = 8 * (14833 + 1854) 10? = 1334961 = 10 * 133496 + 1 = 9 * (133496 + 14833) 11? = 14684570 = 11 * 1334961  1 = 10 * (1334961 + 133496) By the condition of the problem, either the last (10th) element sits in its original place and the other 9 elements make a true shuffle (9? possibilities) or it does not sit in its original place and then all 10 elements make a true shuffle (10? possibilities). The desired probability is then
P = 9?/(9? + 10?) = 133496/(133496 + 1334961) = = 133496/(11*133496 + 1) = = 133496/1468457 = 0.090909029001... ~ 1/11
Perhaps your ratio is for a similar problem. For example, you can ask, if 10 people randomly draw from a hat containing their names, what is the probability that nobody will draw his own name?
P = 10?/10! = 1334961/3628800 = 0.367879464... ~ 1/e
Vladimir > Original message  >>Date: 23 Nov 04 20:51:41 0500 (EST) >>From: John <sternitj@uwplatt.edu> >>Subject: a gift exchange >>To: discretemath@mathforum.org >> >>Ten friends organize a gift exchange. The ten names are put in a >>hat, and the first person draws one. If they pick their own name, >>they return it to the bag and draw again, until they have a name >>that is not their own. Then the second person draws, again >>returning their own name if they draw it. This continues down the >>line. What is the probability that when the 10th person draws, only >>their own name will be left in the bag? >> >>Any help!!!



