login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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). 7
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 (list; table; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified November 24 00:27 EST 2017. Contains 295164 sequences.