P is for Practical PerlMonks

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

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

Replies are listed 'Best First'.
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.

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

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.

Create A New User
Node Status?
node history
Node Type: note [id://441927]
help
Chatterbox?
 [marto]: A bit late for cookies here :)

How do I use this? | Other CB clients
Other Users?
Others exploiting the Monastery: (10)
As of 2017-07-27 21:10 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
I came, I saw, I ...

Results (422 votes). Check out past polls.