[seqfan] Re: A019575 challenge

Maximilian Hasler maximilian.hasler at gmail.com
Fri Aug 20 04:39:26 CEST 2010


Based on Robert's code I suggest the following (very naively) memoized
version of "f" which gives the table T up to n=9 in 0.03s instead of
7.7s (on my netbook...).

/*setup memoization table for args <= M. Could be done dynamically inside f() */
M=10;F=vector(M,i,vector(M,i,vector(M)));

f(n,k,b)={ (!n|!b|!k) & return(!b); F[n][k][b] & return(F[n][k][b]);
F[n][k][b]=sum(i=0,min(k,b),binomial(b,i)*f(n-1,k,b-i)) }

T(n,k)=f(n,k,n)-f(n,k-1,n)
for(n=1,9,print(vector(n,k,T(n,k))))
[1]
[2, 2]
[6, 18, 3]
[24, 180, 48, 4]
[120, 2100, 800, 100, 5]
[720, 28800, 14700, 2250, 180, 6]
[5040, 458640, 301350, 52920, 5292, 294, 7]
[40320, 8361360, 6867840, 1342600, 153664, 10976, 448, 8]
[362880, 172141200, 172872000, 36991080, 4644864, 387072, 20736, 648, 9]
time = 31 ms.

Maximilian
PS: in PARI/gp, loop variables should not be declared as local
variable (which creates a duplicate, unused instance).

On Thu, Aug 19, 2010 at 3:01 PM, Robert Gerbicz
<robert.gerbicz at gmail.com> wrote:
> 2010/8/19 Charles Greathouse <charles.greathouse at case.edu>
>
>> A019575 is:
>> Place n distinguishable balls in n boxes (in n^n ways); let T(n,k) =
>> number of ways that max in any box is k, for 1<=k<=n; sequence gives
>> triangle of numbers T(n,k).
>>
>> It strikes me as a useful sequence that comes up in many applications.
>>  For example, I recently found someone asking (not in these terms) for
>> a weighted sum over T(16, k) for the purpose of estimating the number
>> of cache misses in a GPU.
>>
>> The formula, as listed, is confusing.  Can anyone determine a better
>> (ideally, an efficient) formula or gf?  Also, a b-file might be nice,
>> though at the moment there's no good way to visualize large triangular
>> arrays.
>>
>> Charles Greathouse
>> Analyst/Programmer
>> Case Western Reserve University
>>
>>
>> _______________________________________________
>>
>> Seqfan Mailing list - http://list.seqfan.eu/
>>
>
> Here it is my version:
> f(n,k,b)=local(i);if(n==0,return(b==0));return(sum(i=0,min(k,b),binomial(b,i)*f(n-1,k,b-i)))
> T(n,k)=f(n,k,n)-f(n,k-1,n)
>
> where f(n,k,b)=is the number of ways to place b balls to n boxes, where the
> max in any box is not larger than k. Obviously T(n,k)=f(n,k,n)-f(n,k-1,n).
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>




More information about the SeqFan mailing list