cp's OEIS Frontend

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

%I A019575 #38 Aug 14 2025 06:03:04
%S A019575 1,2,2,6,18,3,24,180,48,4,120,2100,800,100,5,720,28800,14700,2250,180,
%T A019575 6,5040,458640,301350,52920,5292,294,7,40320,8361360,6867840,1342600,
%U A019575 153664,10976,448,8,362880,172141200,172872000,36991080,4644864,387072,20736,648,9
%N A019575 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 A019575 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 A019575 Alois P. Heinz, <a href="/A019575/b019575.txt">Rows n = 1..141, flattened</a>
%F A019575 A019575(x, z) = Sum ( A049009(p)) where x = A036042(p), z = A049085(p) - _Alford Arnold_.
%F A019575 From _Robert Gerbicz_, Aug 19 2010: (Start)
%F A019575 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 A019575 f(n, k, b) = if(n=0, if(b=0, 1, 0), Sum_{i=0..min(k, b)} binomial(b, i)*f(n-1, k, b-i)).
%F A019575 T(n,k) = f(n,k,n) - f(n,k-1,n). (End)
%e A019575 Triangle begins:
%e A019575        1;
%e A019575        2,         2;
%e A019575        6,        18,         3;
%e A019575       24,       180,        48,        4;
%e A019575      120,      2100,       800,      100,       5;
%e A019575      720,     28800,     14700,     2250,     180,      6;
%e A019575     5040,    458640,    301350,    52920,    5292,    294,     7;
%e A019575    40320,   8361360,   6867840,  1342600,  153664,  10976,   448,   8;
%e A019575   362880, 172141200, 172872000, 36991080, 4644864, 387072, 20736, 648, 9;
%e A019575   ...
%p A019575 b:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1, 0,
%p A019575       add(b(n-j, i-1, k)/j!, j=0..min(k, n))))
%p A019575     end:
%p A019575 T:= (n, k)-> n!* (b(n$2, k) -b(n$2, k-1)):
%p A019575 seq(seq(T(n, k), k=1..n), n=1..12);  # _Alois P. Heinz_, Jul 29 2014
%t A019575 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 A019575 (PARI)
%o A019575 /*setup memoization table for args <= M. Could be done dynamically inside f() */
%o A019575 M=10;F=vector(M,i,vector(M,i,vector(M)));
%o A019575 f(n,k,b)={ (!n||!b||!k) & return(!b); F[n][k][b] & return(F[n][k][b]);
%o A019575 F[n][k][b]=sum(i=0,min(k,b),binomial(b,i)*f(n-1,k,b-i)) }
%o A019575 T(n,k)=f(n,k,n)-f(n,k-1,n)
%o A019575 for(n=1,9,print(vector(n,k,T(n,k))))
%o A019575 \\ _M. F. Hasler_, Aug 19 2010; Based on _Robert Gerbicz_'s code I suggest the following (very naively) memoized version of "f"
%Y A019575 Cf. A019576. See A180281 for the case when the balls are indistinguishable.
%Y A019575 Rows sums give A000312.
%Y A019575 Cf. A245687.
%K A019575 nonn,tabl,easy,nice
%O A019575 1,2
%A A019575 Lee Corbin (lcorbin(AT)tsoft.com)
%E A019575 Edited by _N. J. A. Sloane_, Sep 06 2010