[math-fun] Inverse factorial?
Suppose you place N things in N buckets. How many do expect the fullest bucket to contain? I know that the number of buckets containing k things, on average, is N/(k! e). So I can pretend to get the fullest bucket by setting this equal to 1 and solving for k: you expect around one bucket with "(N/e) un-factorial" items. (Surely this function has a name?) Any recommendations on a smarter approach? --Michael -- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.
On Thu, 25 Aug 2005, Michael Kleber wrote:
Suppose you place N things in N buckets. How many do expect the fullest bucket to contain?
My colleague Stephen Suen says: I believe I have a reference for it. Kolchin, Sevastyanov and Chistyakov, Random Allocations, Wiley, 1978. It is known that fullest urn has ln(n)/ln(ln(n)) balls (with probability tending to 1 as n goes to infinity). I think the exact answer is (1/n^n) ((n-1)n^n - \sum_{k\ge1} \sum_{i_1,...,i_n} n!/(i_1! ... i_n!) ) where the second sum is over all n-tuples (i_1,...,i_n) such that (1) \sum_j i_j = n, and (2) i_j <= k.
Excellent! Thanks very much. (For my own peace of mind, I suppose I'll have to figure out how that relates to the off-the-cuff inverse factorial heuristic...) --Michael Kleber On 8/26/05, Edwin Clark <eclark@math.usf.edu> wrote:
On Thu, 25 Aug 2005, Michael Kleber wrote:
Suppose you place N things in N buckets. How many do expect the fullest bucket to contain?
My colleague Stephen Suen says:
I believe I have a reference for it.
Kolchin, Sevastyanov and Chistyakov, Random Allocations, Wiley, 1978.
It is known that fullest urn has ln(n)/ln(ln(n)) balls (with probability tending to 1 as n goes to infinity).
I think the exact answer is
(1/n^n) ((n-1)n^n - \sum_{k\ge1} \sum_{i_1,...,i_n} n!/(i_1! ... i_n!) )
where the second sum is over all n-tuples (i_1,...,i_n) such that (1) \sum_j i_j = n, and (2) i_j <= k.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.
(For my own peace of mind, I suppose I'll have to figure out how that relates to the off-the-cuff inverse factorial heuristic...)
1: x! = N/e (yours) 2: x log x = log N (from 1, ignoring a lower-order term) 3: log x + log log x = log log N (log of 2) 4: x (log log N - log log x) = log N (substituting 3 into 2) 5: x log log N = log N (discarding a lower-order term) 6: x = log N / log log N (rearranging) -- g
participants (3)
-
Edwin Clark -
Gareth McCaughan -
Michael Kleber