Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » Math Topics » discretemath

Topic: a gift exchange
Replies: 6   Last Post: Aug 10, 2013 11:20 PM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Jerry Grossman

Posts: 27
Registered: 12/6/04
Re: a gift exchange
Posted: Nov 24, 2004 10:13 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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)*(n-1)?
> - C(n,2)*(n-2)? - ... -
> - C(n,n-1)*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)*(n-1)? + C(n,0)*(n-2)? + ... +
> + C(n,n-2)*2? + C(n,n-1)*1? + C(n,n-1)*0?
>
> or, using C(n,k) = C(n,n-k),
>
> n! = C(n,n)*n? + C(n,n-1)*(n-1)? + C(n,n-2)*(n-2)? + ... +
> + 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*(n-1)? + (-1)^n with the seed 0? = 1
>
> or
>
> n? = (n-1)*[(n-1)? + (n-2)?] 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!!!




Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.