On the average of the number of the Maximal (and Minimal) Number of Balls upon throwing, 2, balls into , 4, bins T times By Shalosh B. Ekhad Suppose you throw, uniformly at random,, 2, balls into , 4, boxes , T times Let , A(T), be the average of the Maximum number of balls minus , T/2 Then A(T) satisfies the following linear recurrence equation with polynomial\ coefficients 5 4 3 A(T) = -1/6 (28732838231 T - 735365890368 T + 5321371732254 T 2 / - 16158071261908 T + 22006502739649 T - 11060449920638) A(T - 1) / (%1 / 3 6 5 4 (T - 1) ) + 1/18 (705368438063 T - 9202200552550 T + 46241281439676 T 3 2 - 106389655603003 T + 84877469257815 T + 63832507149263 T / 3 - 107758489743716) A(T - 2) / ((T - 2) %1 (T - 1) ) + 1/54 ( / 6 5 4 778649420441 T - 16450843996378 T + 133266780528758 T 3 2 - 524909968930423 T + 1016029280481458 T - 784023799151440 T / 3 + 15464593977444) A(T - 3) / ((T - 2) %1 (T - 1) ) - 1/54 ( / 6 5 4 986366033287 T - 14041215172382 T + 73678561029800 T 3 2 - 157204980016036 T + 38317700932455 T + 299548147399032 T / 3 - 273962467455912) A(T - 4) / ((T - 2) %1 (T - 1) ) - 1/54 (T - 4) ( / 5 4 3 2 574645102821 T - 8816099624422 T + 50282765684963 T - 123675047907374 T / 3 + 100252158756490 T + 29152227244158) A(T - 5) / ((T - 2) %1 (T - 1) ) / 4 3 + 1/54 (T - 5) (T - 4) (10054744111 T + 303789343833 T 2 / - 2913101031660 T + 6220789968619 T - 1453298431647) A(T - 6) / ( / 3 (T - 2) %1 (T - 1) ) + 1/54 (T - 5) (T - 6) (T - 4) 3 2 (54591226459 T - 359850426441 T + 518457227354 T + 209648572587) A(T - 7) / 3 / ((T - 2) %1 (T - 1) ) + 1/54 (T - 4) (T - 5) (T - 6) (T - 7) / 2 / (8332406469 T - 23525611286 T - 4524668054) A(T - 8) / ((T - 2) %1 / 3 (T - 1) ) 2 %1 := 21261600583 T - 133290646614 T + 192745127537 Subject to the initial conditions 35 127 1675 1867 A(1) = 1/2, A(2) = 5/6, A(3) = --, A(4) = ---, A(5) = ----, A(6) = ----, 36 108 1296 1296 36043 116575 A(7) = -----, A(8) = ------ 23328 69984 and in Maple notation A(T) = -1/6*(28732838231*T^5-735365890368*T^4+5321371732254*T^3-16158071261908* T^2+22006502739649*T-11060449920638)/(21261600583*T^2-133290646614*T+ 192745127537)/(T-1)^3*A(T-1)+1/18*(705368438063*T^6-9202200552550*T^5+ 46241281439676*T^4-106389655603003*T^3+84877469257815*T^2+63832507149263*T-\ 107758489743716)/(T-2)/(21261600583*T^2-133290646614*T+192745127537)/(T-1)^3*A( T-2)+1/54*(778649420441*T^6-16450843996378*T^5+133266780528758*T^4-\ 524909968930423*T^3+1016029280481458*T^2-784023799151440*T+15464593977444)/(T-2 )/(21261600583*T^2-133290646614*T+192745127537)/(T-1)^3*A(T-3)-1/54*( 986366033287*T^6-14041215172382*T^5+73678561029800*T^4-157204980016036*T^3+ 38317700932455*T^2+299548147399032*T-273962467455912)/(T-2)/(21261600583*T^2-\ 133290646614*T+192745127537)/(T-1)^3*A(T-4)-1/54*(T-4)*(574645102821*T^5-\ 8816099624422*T^4+50282765684963*T^3-123675047907374*T^2+100252158756490*T+ 29152227244158)/(T-2)/(21261600583*T^2-133290646614*T+192745127537)/(T-1)^3*A(T -5)+1/54*(T-5)*(T-4)*(10054744111*T^4+303789343833*T^3-2913101031660*T^2+ 6220789968619*T-1453298431647)/(T-2)/(21261600583*T^2-133290646614*T+ 192745127537)/(T-1)^3*A(T-6)+1/54*(T-5)*(T-6)*(T-4)*(54591226459*T^3-\ 359850426441*T^2+518457227354*T+209648572587)/(T-2)/(21261600583*T^2-\ 133290646614*T+192745127537)/(T-1)^3*A(T-7)+1/54*(T-4)*(T-5)*(T-6)*(T-7)*( 8332406469*T^2-23525611286*T-4524668054)/(T-2)/(21261600583*T^2-133290646614*T+ 192745127537)/(T-1)^3*A(T-8) Using this recurrence we can compute many terms. 1/2 This enables us to estimate that A(T) is asympotically, C T where C is approximately, 0.59430 Suppose you throw, uniformly at random,, 2, balls into , 4, boxes , T times Let , A(T), be the average of the Minimum number of balls minus , T/2 Then A(T) satisfies the following linear recurrence equation with polynomial\ coefficients 5 4 3 A(T) = -1/6 (28732838231 T - 735365890368 T + 5321371732254 T 2 / - 16158071261908 T + 22006502739649 T - 11060449920638) A(T - 1) / (%1 / 3 6 5 4 (T - 1) ) + 1/18 (705368438063 T - 9202200552550 T + 46241281439676 T 3 2 - 106389655603003 T + 84877469257815 T + 63832507149263 T / 3 - 107758489743716) A(T - 2) / ((T - 2) %1 (T - 1) ) + 1/54 ( / 6 5 4 778649420441 T - 16450843996378 T + 133266780528758 T 3 2 - 524909968930423 T + 1016029280481458 T - 784023799151440 T / 3 + 15464593977444) A(T - 3) / ((T - 2) %1 (T - 1) ) - 1/54 ( / 6 5 4 986366033287 T - 14041215172382 T + 73678561029800 T 3 2 - 157204980016036 T + 38317700932455 T + 299548147399032 T / 3 - 273962467455912) A(T - 4) / ((T - 2) %1 (T - 1) ) - 1/54 (T - 4) ( / 5 4 3 2 574645102821 T - 8816099624422 T + 50282765684963 T - 123675047907374 T / 3 + 100252158756490 T + 29152227244158) A(T - 5) / ((T - 2) %1 (T - 1) ) / 4 3 + 1/54 (T - 5) (T - 4) (10054744111 T + 303789343833 T 2 / - 2913101031660 T + 6220789968619 T - 1453298431647) A(T - 6) / ( / 3 (T - 2) %1 (T - 1) ) + 1/54 (T - 5) (T - 6) (T - 4) 3 2 (54591226459 T - 359850426441 T + 518457227354 T + 209648572587) A(T - 7) / 3 / ((T - 2) %1 (T - 1) ) + 1/54 (T - 4) (T - 5) (T - 6) (T - 7) / 2 / (8332406469 T - 23525611286 T - 4524668054) A(T - 8) / ((T - 2) %1 / 3 (T - 1) ) 2 %1 := 21261600583 T - 133290646614 T + 192745127537 Subject to the initial conditions -35 -127 -1675 -1867 A(1) = -1/2, A(2) = -5/6, A(3) = ---, A(4) = ----, A(5) = -----, A(6) = -----, 36 108 1296 1296 -36043 -116575 A(7) = ------, A(8) = ------- 23328 69984 and in Maple notation A(T) = -1/6*(28732838231*T^5-735365890368*T^4+5321371732254*T^3-16158071261908* T^2+22006502739649*T-11060449920638)/(21261600583*T^2-133290646614*T+ 192745127537)/(T-1)^3*A(T-1)+1/18*(705368438063*T^6-9202200552550*T^5+ 46241281439676*T^4-106389655603003*T^3+84877469257815*T^2+63832507149263*T-\ 107758489743716)/(T-2)/(21261600583*T^2-133290646614*T+192745127537)/(T-1)^3*A( T-2)+1/54*(778649420441*T^6-16450843996378*T^5+133266780528758*T^4-\ 524909968930423*T^3+1016029280481458*T^2-784023799151440*T+15464593977444)/(T-2 )/(21261600583*T^2-133290646614*T+192745127537)/(T-1)^3*A(T-3)-1/54*( 986366033287*T^6-14041215172382*T^5+73678561029800*T^4-157204980016036*T^3+ 38317700932455*T^2+299548147399032*T-273962467455912)/(T-2)/(21261600583*T^2-\ 133290646614*T+192745127537)/(T-1)^3*A(T-4)-1/54*(T-4)*(574645102821*T^5-\ 8816099624422*T^4+50282765684963*T^3-123675047907374*T^2+100252158756490*T+ 29152227244158)/(T-2)/(21261600583*T^2-133290646614*T+192745127537)/(T-1)^3*A(T -5)+1/54*(T-5)*(T-4)*(10054744111*T^4+303789343833*T^3-2913101031660*T^2+ 6220789968619*T-1453298431647)/(T-2)/(21261600583*T^2-133290646614*T+ 192745127537)/(T-1)^3*A(T-6)+1/54*(T-5)*(T-6)*(T-4)*(54591226459*T^3-\ 359850426441*T^2+518457227354*T+209648572587)/(T-2)/(21261600583*T^2-\ 133290646614*T+192745127537)/(T-1)^3*A(T-7)+1/54*(T-4)*(T-5)*(T-6)*(T-7)*( 8332406469*T^2-23525611286*T-4524668054)/(T-2)/(21261600583*T^2-133290646614*T+ 192745127537)/(T-1)^3*A(T-8) Using this recurrence we can compute many terms. 1/2 This enables us to estimate that A(T) is asympotically, C T where C is approximately, -0.59430 -------------------------- This took, 108507.900, seconds.