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 ]
Vladimir Zajic

Posts: 319
Registered: 12/3/04
Re: a gift exchange
Posted: Nov 24, 2004 5:48 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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.