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 ]
 Jerry Grossman Posts: 27 Registered: 12/6/04
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:

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

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