Search All of the Math Forum:

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

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Replies: 6   Last Post: Aug 10, 2013 11:20 PM

 Messages: [ Previous | Next ]
 Vladimir Zajic Posts: 319 Registered: 12/3/04
Posted: Nov 24, 2004 5:48 PM

On Wed, 24 Nov 2004 07:49:18 -0500, Jerry Grossman wrote:
&gt;This problem has been floating around for a few years. I heard
&gt;it from Gary Thompson, Grove City College (Pennsylvania).
&gt;I don't think anyone has the general solution (with n people).
&gt;You can use a computer to brute force your way to the answer
&gt;for small values of n. In particular, the answer for n=10 is
&gt;
&gt;If anyone has any information about solutions, I'd very much
&gt;
&gt;Jerry Grossman
&gt;Oakland University
&gt;

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 &gt; 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

&gt;---- Original message ----
&gt;&gt;Date: 23 Nov 04 20:51:41 -0500 (EST)
&gt;&gt;From: John &lt;sternitj@uwplatt.edu&gt;
&gt;&gt;To: discretemath@mathforum.org
&gt;&gt;
&gt;&gt;Ten friends organize a gift exchange. The ten names are put in a
&gt;&gt;hat, and the first person draws one. If they pick their own name,
&gt;&gt;they return it to the bag and draw again, until they have a name
&gt;&gt;that is not their own. Then the second person draws, again
&gt;&gt;returning their own name if they draw it. This continues down the
&gt;&gt;line. What is the probability that when the 10th person draws, only
&gt;&gt;their own name will be left in the bag?
&gt;&gt;
&gt;&gt;Any help!!!

Date Subject Author
11/23/04 John
11/24/04 Jerry Grossman