A131106 - OEIS

The OEIS is supported by the many generous donors to the OEIS Foundation.

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

Other ways to Give

A131106

Rectangular array read by antidiagonals: k objects are each put into one of n boxes, independently with equal probability. a(n, k) is the expected number of boxes with exactly one object (n, k >= 1). Sequence gives the numerators.

1, 1, 0, 1, 1, 0, 1, 4, 3, 0, 1, 3, 4, 1, 0, 1, 8, 27, 32, 5, 0, 1, 5, 48, 27, 80, 3, 0, 1, 12, 25, 256, 405, 64, 7, 0, 1, 7, 108, 125, 256, 729, 448, 1, 0, 1, 16, 147, 864, 3125, 6144, 5103, 1024, 9, 0, 1, 9, 64, 343, 6480, 3125, 28672, 2187, 256, 5, 0, 1, 20, 243, 2048, 12005

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

1,8

COMMENTS

Problem suggested by Brandon Zeidler. To motivate this sequence, suppose that when objects are placed in the same box, they mix and the information they contain is lost. The sequence tells us how much information we can expect to recover.

LINKS

Table of n, a(n) for n=1..71.

FORMULA

a(n, k) = k*(1 - 1/n)^(k - 1). Let f(n, k, i) be the number of assignments such that exactly i boxes have exactly one object. For i > n, f(n, k, i) = 0. For i = k <= n, f(n, k, i) = n!/(n-k)!. Otherwise, f(n, k, i) = sum_{j = 1..min(floor((k-i)/2), n-i) A008299(k-i, j)*n!*binomial(k, i)/(n-i-j)!. Then a(n, k) = sum_{i=1..min(n, k)} i*f(n, k, i)/n^k.

EXAMPLE

Array begins:

1 0 0 0 0 0

1 1 3/4 1/2 5/16 3/16

1 4/3 4/3 32/27 80/81 64/81

CROSSREFS

Cf. A131107 gives the denominators. A131103, A131104 and A131105 give f(n, k, 0), f(n, k, 1) and f(n, k, 2).

Sequence in context: A106646 A056969 A335532 * A298739 A346366 A325011

Adjacent sequences: A131103 A131104 A131105 * A131107 A131108 A131109

KEYWORD

easy,frac,nonn,tabl

AUTHOR

David Wasserman, Jun 15 2007

STATUS

approved