A019575 - OEIS

%I #34 Jul 19 2024 03:13:32

%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