Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl-Sensitive Sunglasses
 
PerlMonks  

Re: A bad shuffle

by QM (Vicar)
on Mar 24, 2005 at 00:28 UTC ( #441927=note: print w/ replies, xml ) Need Help??


in reply to A bad shuffle

The size of this sample space is NN. To each element of this space corresponds a permutation, but the size of the space of all possible permutations is N! , which is not only smaller than NN for any N > 1, but more importantly, it is not a divisor of NN, which means that it is impossible for the algorithm to give equal weight to all the permutations.
If I'm not mistaken, N! | NN, as N! = 1*2*...*N, and NN = N*N*...*N. Therefore, NN/N! = NN-1/(N-1)!

How does this affect your comment?

Update: Oops, I was mistaken.

-QM
--
Quantum Mechanics: The dreams stuff is made of


Comment on Re: A bad shuffle
Re^2: A bad shuffle
by runrig (Abbot) on Mar 24, 2005 at 00:38 UTC
    How does this affect your comment?

    It doesn't. The important point is that (N**N mod N!) != 0 for N > 2, i.e., N**N balls can not be evenly distributed among N! buckets.

Re^2: A bad shuffle
by tlm (Prior) on Mar 24, 2005 at 00:45 UTC

    NN-1/(N-1)! is not an integer for any integer N > 2, so it is not the case that N! | NN, except for N=1 and N=2.

    the lowliest monk

    Update: Here's a proof of the assertion made above. I'm sure there are better proofs of it, but this is the best I could come up with.

    Assume that N > 2, and let p be the largest prime in the prime factorization of N. There are three cases to consider. Suppose first that p is 2. Then, by assumption, N is a power of 2 greater than or equal to 4. Therefore, 3 is a factor of N!, and consequently N! does not divide NN. Next, suppose that p > 2. If N = pk for some nonnegative integer k, then N is odd and not divisible by N! whose prime factorization includes 2. This leaves the case in which p > 2, and is not the sole prime factor of N. In this case N >= 2 p. By Bertrand's postulate there exists a prime q such that p < q < 2 p <= N. Therefore, there is a factor of N!, namely q, that does not divide Ns, for any positive integer s. Therefore, N! does not divide NN, for all N > 2.

Re^2: A bad shuffle
by Anonymous Monk on Mar 24, 2005 at 10:01 UTC
    If I'm not mistaken, N! | NN, as N! = 1*2*...*N, and NN = N*N*...*N. Therefore, NN/N! = NN-1/(N-1)!
    The fact that NN and N! share a factor doesn't mean that N! is a divisor of NN, as the following table shows:
     N                 NN                 N!             NN % N!
     1                  1                  1                  0
     2                  4                  2                  0
     3                 27                  6                  3
     4                256                 24                 16
     5               3125                120                  5
     6              46656                720                576
     7             823543               5040               2023
     8           16777216              40320               4096
     9          387420489             362880             227529
    10        10000000000            3628800            2656000
    11       285311670611           39916800           26301011
    12      8916100448256          479001600          443667456
    13    302875106592253         6227020800         5268921853
    14  11112006825558016        87178291200          294332416
    15 437893890380859375      1307674368000       820814907375
    
      My bad. Somehow the coffee fairy didn't stop by me, and I'm confusing "share a factor" with "evenly divides".

      -QM
      --
      Quantum Mechanics: The dreams stuff is made of

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://441927]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others contemplating the Monastery: (10)
As of 2014-07-28 18:27 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite superfluous repetitious redundant duplicative phrase is:









    Results (205 votes), past polls