A210115 Floor of the expected value of number of trials until exactly four cells are empty in a random distribution of n balls in n cells.

625, 50, 13, 5, 3, 2, 2, 2, 3, 4, 5, 7, 11, 17, 28, 46, 78, 136, 242, 441, 815, 1533, 2927, 5669, 11123, 22090, 44363, 90027, 184482, 381499, 795686, 1672914, 3543925, 7561129, 16240832, 35106812, 76346759, 166982782, 367206632, 811693449

Offset: 5

Author

Washington Bomfim, Mar 18 2012

Keywords

• nonn

Comments

Also floor of the expected value of number of trials until we have n-4 distinct symbols in a random sequence on n symbols of length n. A055775 corresponds to zero cells empty.

Examples

			For n=5, there are 5^5 = 3125 sequences on 5 symbols of length 5. Only 5 sequences has a unique symbol, so a(5) = floor(3125/5) = 625.
		

References

• W. Feller, An Introduction to Probability Theory and its Applications, 2nd ed, Wiley, New York, 1965, (2.4) p. 92. (Occupancy problems)

Links

• W. Bomfim, Table of n, a(n) for n = 5..100

Crossrefs

Cf. A055775, A209899, A209900, A210112, A210113, A210114, A210116.

Formula

With m = 4, a(n) = floor(n^n/(binomial(n,m)*_Sum{v=0..n-m-1}((-1)^v*binomial(n-m,v)*(n-m-v)^n)))