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

64, 10, 4, 2, 2, 2, 2, 3, 5, 7, 11, 18, 31, 55, 100, 185, 348, 670, 1311, 2606, 5254, 10734, 22196, 46407, 98023, 209009, 449580, 974963, 2130442, 4688533, 10387113, 23156162, 51926745, 117090391, 265413053

Offset: 4

Author

Washington Bomfim, Mar 18 2012

Keywords

• nonn

Comments

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

Examples

			For n=4, there are 4^4 = 256 sequences on 4 symbols of length 4. Only 4 sequences have a unique symbol, so a(4) = floor(256/4) = 64.
		

References

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

Links

• Washington Bomfim, Table of n, a(n) for n = 4..100

Crossrefs

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

Formula

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