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

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

Offset

1,2

Comments

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

Links

Alois P. Heinz, Rows n = 1..141, flattened

Formula

A019575(x, z) = Sum ( A049009(p)) where x = A036042(p), z = A049085(p) - Alford Arnold.

From Robert Gerbicz, Aug 19 2010: (Start)

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

(end)

Example

Triangle begins:
       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;
  ...

Maple

b:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(b(n-j, i-1, k)/j!, j=0..min(k, n))))
    end:
T:= (n, k)-> n!* (b(n$2, k) -b(n$2, k-1)):
seq(seq(T(n, k), k=1..n), n=1..12);  # Alois P. Heinz, Jul 29 2014

Mathematica

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

Prog

(PARI)
/*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))))
\\ M. F. Hasler, Aug 19 2010; Based on Robert Gerbicz's code I suggest the following (very naively) memoized version of "f"

Crossrefs

Cf. A019576. See A180281 for the case when the balls are indistinguishable.

Rows sums give A000312.

Cf. A245687.

Sequence in context: A006250 A006249 A216971 * A178882 A186195 A256215

Adjacent sequences: A019572 A019573 A019574 * A019576 A019577 A019578

Keyword

nonn,tabl,easy,nice

Author

Lee Corbin (lcorbin(AT)tsoft.com)

Extensions

Edited by N. J. A. Sloane, Sep 06 2010

Status

approved