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

 

Logo


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

(From M. F. Hasler, Aug 19 2010: Based on Robert Gerbicz's code I suggest the following (very naively) memoized version of "f")

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

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 March 22 22:17 EDT 2017. Contains 283901 sequences.