[seqfan] Re: A019575 challenge

Robert Gerbicz robert.gerbicz at gmail.com
Thu Aug 19 23:01:55 CEST 2010


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).



More information about the SeqFan mailing list