On the average of the number of the Maximal (and Minimal) Number of Balls upon throwing, 1, balls into , 3, bins T times By Shalosh B. Ekhad Suppose you throw, uniformly at random,, 1, balls into , 3, boxes , T times Let , A(T), be the average of the Maximum number of balls minus , T/3 Then A(T) satisfies the following linear recurrence equation with polynomial\ coefficients 4 3 2 (7 T - 32 T + 36 T + 19 T - 36) A(T - 1) A(T) = 2/3 ------------------------------------------- 2 %1 (T - 1) 5 4 3 2 (7 T - 53 T + 131 T - 55 T - 206 T + 200) A(T - 2) + 1/3 ------------------------------------------------------ 2 (T - 2) %1 (T - 1) 4 3 2 (21 T - 180 T + 519 T - 544 T + 160) A(T - 3) + 1/3 ------------------------------------------------ 2 %1 (T - 1) 3 2 (T - 3) (7 T - 32 T + 29 T + 2) A(T - 4) - 2/3 ------------------------------------------ 2 %1 (T - 1) 2 (T - 3) (T - 4) (7 T - 11 T + 2) A(T - 5) - 1/3 ------------------------------------------ 2 %1 (T - 1) 2 %1 := 7 T - 25 T + 20 Subject to the initial conditions 28 A(1) = 2/3, A(2) = 2/3, A(3) = 8/9, A(4) = --, A(5) = 10/9 27 and in Maple notation A(T) = 2/3*(7*T^4-32*T^3+36*T^2+19*T-36)/(7*T^2-25*T+20)/(T-1)^2*A(T-1)+1/3*(7* T^5-53*T^4+131*T^3-55*T^2-206*T+200)/(T-2)/(7*T^2-25*T+20)/(T-1)^2*A(T-2)+1/3*( 21*T^4-180*T^3+519*T^2-544*T+160)/(7*T^2-25*T+20)/(T-1)^2*A(T-3)-2/3*(T-3)*(7*T ^3-32*T^2+29*T+2)/(7*T^2-25*T+20)/(T-1)^2*A(T-4)-1/3*(T-3)*(T-4)*(7*T^2-11*T+2) /(7*T^2-25*T+20)/(T-1)^2*A(T-5) 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.489 Suppose you throw, uniformly at random,, 1, balls into , 3, boxes , T times Let , A(T), be the average of the Minimum number of balls minus , T/3 Then A(T) satisfies the following linear recurrence equation with polynomial\ coefficients 4 3 2 (7 T - 32 T + 36 T + 19 T - 36) A(T - 1) A(T) = 2/3 ------------------------------------------- 2 %1 (T - 1) 5 4 3 2 (7 T - 53 T + 131 T - 55 T - 206 T + 200) A(T - 2) + 1/3 ------------------------------------------------------ 2 (T - 2) %1 (T - 1) 4 3 2 (21 T - 180 T + 519 T - 544 T + 160) A(T - 3) + 1/3 ------------------------------------------------ 2 %1 (T - 1) 3 2 (T - 3) (7 T - 32 T + 29 T + 2) A(T - 4) - 2/3 ------------------------------------------ 2 %1 (T - 1) 2 (T - 3) (T - 4) (7 T - 11 T + 2) A(T - 5) - 1/3 ------------------------------------------ 2 %1 (T - 1) 2 %1 := 7 T - 25 T + 20 Subject to the initial conditions -85 A(1) = -1/3, A(2) = -2/3, A(3) = -7/9, A(4) = -8/9, A(5) = --- 81 and in Maple notation A(T) = 2/3*(7*T^4-32*T^3+36*T^2+19*T-36)/(7*T^2-25*T+20)/(T-1)^2*A(T-1)+1/3*(7* T^5-53*T^4+131*T^3-55*T^2-206*T+200)/(T-2)/(7*T^2-25*T+20)/(T-1)^2*A(T-2)+1/3*( 21*T^4-180*T^3+519*T^2-544*T+160)/(7*T^2-25*T+20)/(T-1)^2*A(T-3)-2/3*(T-3)*(7*T ^3-32*T^2+29*T+2)/(7*T^2-25*T+20)/(T-1)^2*A(T-4)-1/3*(T-3)*(T-4)*(7*T^2-11*T+2) /(7*T^2-25*T+20)/(T-1)^2*A(T-5) 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.488 -------------------------- This took, 14.915, seconds.