[seqfan] Re: A208250 and growth of the expected largest bucket

[Charles Greathouse]

b(n) should be about log n/log log n. More precisely, b(n) = IGamma(n) -
3/2 + o(1) where IGamma is the inverse gamma function, see

G. H. Gonnet. Expected length of the longest probe sequence in hash code
searching. Journal of the ACM, 28(2):289-304, 1981.

Charles Greathouse
Analyst/Programmer
Case Western Reserve University


On Wed, Feb 20, 2013 at 3:09 AM, <hv at crypt.org> wrote:

> Could someone help me consider how to calculate more values of A208250,
> or to approximate them? I'd like to find values for rather larger n,
> but I'm struggling to think of an approach that will make it practical
> to calculate for n substantially greater than the 19 already listed.
>
> Working a(4) by hand, for example, I get:
>
> (4,0,0,0) has largest bucket 4; can appear 4 ways; can be constructed in
> only one order; contribution is 4 * 4 * 1 => 16.
> (3,1,0,0) => largest bucket 3; 12 ways; 4 orders => 144.
> (2,2,0,0) => 2 * 6 * 6 => 72.
> (2,1,1,0) => 2 * 12 * 12 => 288.
> (1,1,1,1) => 1 * 1 * 24 => 24.
>   total 16+144+72+288+24 = 544
> .. but an approach iterating over all partitions of n is not going to scale
> very far.
>
> Motivation: for a programming-related issue I need to get a clearer picture
> of how the expected size of largest bucket b(n) = A208250(n) / n^n will
> grow,
> particularly for n = 2^m. From the current values I get:
>
> b(2^0) = 1
> b(2^1) = 1.5
> b(2^2) = 2.125
> b(2^3) = 2.597 (approx)
> b(2^4) = 3.078 (approx)
>
> Hugo
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>