|
Search: id:A131106
|
|
|
| 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. |
|
+0
5
|
|
| 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; listen)
|
|
|
OFFSET
|
1,8
|
|
|
COMMENT
|
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.
|
|
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).
Adjacent sequences: A131103 A131104 A131105 this_sequence A131107 A131108 A131109
Sequence in context: A019983 A019984 A056969 this_sequence A016697 A086466 A021703
|
|
KEYWORD
|
easy,frac,nonn,tabl
|
|
AUTHOR
|
David Wasserman (dwasserm(AT)earthlink.net), Jun 15 2007
|
|
|
Search completed in 0.002 seconds
|
