|
%I #30 Oct 07 2017 02:40:53
%S 1,2,2,6,18,3,24,180,48,4,120,2100,800,100,5,720,28800,14700,2250,180,
%T 6,5040,458640,301350,52920,5292,294,7,40320,8361360,6867840,1342600,
%U 153664,10976,448,8,362880,172141200,172872000,36991080,4644864,387072,20736,648,9
%N Place n distinguishable balls in n boxes (in n^n ways); let T(n,k) = number of ways that the maximum in any box is k, for 1 <= k <= n; sequence gives triangle of numbers T(n,k).
%C T(n,k) is the number of endofunctions on [n] such that the maximal cardinality of the nonempty preimages equals k. - _Alois P. Heinz_, Jul 31 2014
%H Alois P. Heinz, <a href="/A019575/b019575.txt">Rows n = 1..141, flattened</a>
%F A019575(x, z) = Sum ( A049009(p)) where x = A036042(p), z = A049085(p) - _Alford Arnold_.
%F From _Robert Gerbicz_, Aug 19 2010: (Start)
%F Let f(n,k,b) = number of ways to place b balls to n boxes, where the max in any box is not larger than k. Then T(n,k) = f(n,k,n) - f(n,k-1,n). We have:
%F 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))).
%F T(n,k) = f(n,k,n) - f(n,k-1,n).
%F (end)
%e Triangle begins:
%e 1;
%e 2, 2;
%e 6, 18, 3;
%e 24, 180, 48, 4;
%e 120, 2100, 800, 100, 5;
%e 720, 28800, 14700, 2250, 180, 6;
%e 5040, 458640, 301350, 52920, 5292, 294, 7;
%e 40320, 8361360, 6867840, 1342600, 153664, 10976, 448, 8;
%e 362880, 172141200, 172872000, 36991080, 4644864, 387072, 20736, 648, 9;
%e ...
%p b:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1, 0,
%p add(b(n-j, i-1, k)/j!, j=0..min(k, n))))
%p end:
%p T:= (n, k)-> n!* (b(n$2, k) -b(n$2, k-1)):
%p seq(seq(T(n, k), k=1..n), n=1..12); # _Alois P. Heinz_, Jul 29 2014
%t f[0, _, b_] := Boole[b == 0]; f[n_, k_, b_] := f[n, k, b] = Sum[ Binomial[b, i]*f[n - 1, k, b - i], {i, 0, Min[k, b]}]; t[n_, k_] := f[n, k, n] - f[n, k - 1, n]; Flatten[ Table[ t[n, k], {n, 1, 9}, {k, 1, n}]] (* _Jean-François Alcover_, Mar 09 2012, after _Robert Gerbicz_ *)
%o (PARI)
%o /*setup memoization table for args <= M. Could be done dynamically inside f() */
%o M=10;F=vector(M,i,vector(M,i,vector(M)));
%o f(n,k,b)={ (!n|!b|!k) & return(!b); F[n][k][b] & return(F[n][k][b]);
%o F[n][k][b]=sum(i=0,min(k,b),binomial(b,i)*f(n-1,k,b-i)) }
%o T(n,k)=f(n,k,n)-f(n,k-1,n)
%o for(n=1,9,print(vector(n,k,T(n,k))))
%o \\ _M. F. Hasler_, Aug 19 2010; Based on _Robert Gerbicz_'s code I suggest the following (very naively) memoized version of "f"
%Y Cf. A019576. See A180281 for the case when the balls are indistinguishable.
%Y Rows sums give A000312.
%Y Cf. A245687.
%K nonn,tabl,easy,nice
%O 1,2
%A Lee Corbin (lcorbin(AT)tsoft.com)
%E Edited by _N. J. A. Sloane_, Sep 06 2010
|
