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 10:13 PM


This is all very nice but invalid for solving our problem. The permutations in the situation given are NOT equally likely. jerry
On Wed, 24 Nov 2004, Vladimir wrote:
> 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!!!



