cp's OEIS Frontend

A180975 Array of the "egg-drop" numbers, read by downwards antidiagonals.

%I A180975 #52 Jun 26 2022 03:09:35
%S A180975 1,1,2,1,3,3,1,3,6,4,1,3,7,10,5,1,3,7,14,15,6,1,3,7,15,25,21,7,1,3,7,
%T A180975 15,30,41,28,8,1,3,7,15,31,56,63,36,9,1,3,7,15,31,62,98,92,45,10
%N A180975 Array of the "egg-drop" numbers, read by downwards antidiagonals.
%C A180975 The egg-drop problem is as follows. We wish to determine the highest floor in a building such that an egg dropped from that floor will not shatter. We have a set of k identical eggs for dropping; note that an egg that does not shatter can be reused to test higher floors. Then T(n,k) is the largest number of floors that can be tested using at most n drops and k eggs.
%C A180975 Suppose one is given k eggs and a building of f floors. Then the worst-case number of drops WC(k,f) to test all the floors satisfies the dynamic programming equation
%C A180975 . WC(k,f) = 1 + max_{g in 1..f} { WC(k-1, g-1), WC(k, f-g) }
%C A180975 with boundary conditions
%C A180975 . WC(1,f) = f and WC(k,0) = 0
%C A180975 where g is the floor chosen for the next drop. One can substitute f -> T(n,k) and g -> T(n-1,k-1)+1 = f-T(k-1,j). Then by an inductive argument, it is verified that WC(j,T(n,j)) = n as expected.
%C A180975 T(n,2) = n(n+1)/2. This leads to the commonly-used heuristic solution for 2 eggs of dropping from the sqrt(f), 2*sqrt(f), 3*sqrt(f) etc. floors until the first egg breaks. T(n,j) is a j-th order polynomial in n, and so this heuristic may be generalized: drop from multiples of f^((j-1)/j) until the j-th egg breaks.
%D A180975 J. Kleinberg and E. Tardos, "Algorithm Design", Addison-Wesley Longman Publishing Co. Inc., 2005. Problem 2.8.
%D A180975 D. Velleman, "Which Way Did The Bicycle Go? And Other Intriguing Mathematical Mysteries (Dolciani Mathematical Expositions)", The Mathematical Association of America, 1996, "166. An Egg-Drop Experiment" pages 53 and 204-205.
%H A180975 G. C. Greubel, <a href="/A180975/b180975.txt">Antidiagonals n = 1..100 of array, flattened</a>
%H A180975 Michael Boardman, <a href="http://www.jstor.org/stable/3219201">The Egg-Drop Numbers</a>, Mathematics Magazine, 77 (2004), 368-372.
%F A180975 Recursive formula: T(n,k) = T(n-1,k-1) + 1 + T(n-1,k) with boundary conditions T(0,k) = T(n,0) = 0.
%F A180975 T(n,k) = Sum_{j=1..k} binomial(n,j).
%F A180975 From the journal article by Boardman, the generating function for a fixed value of n is g_n(x) = ((1+x)^n - 1) / (1-x).
%F A180975 G.f.: x*y/((1-y)*(1-x)*(1-x-x*y)). - _Vladimir Kruchinin_, Oct 09 2018
%e A180975 T(n,1) = n. With only a single egg, one must drop the egg from the first floor, then the second, and so on until it finally breaks. At most n floors may be tested this way.
%e A180975 If one is allowed fewer drops than eggs, a simple binary search is optimal. Hence T(n,k) = 2^n-1 for n <= k. Note that one cannot test 2^n floors in this case. For example, suppose one had 2 drops and a 4-story building; dropping from either the second or third floor could leave another two floors to test, but only one drop remaining.
%e A180975 The square array starts in row n=1 with columns k >= 1:
%e A180975   1:  1  1  1  1  1  1  1  1  1
%e A180975   2:  2  3  3  3  3  3  3  3  3
%e A180975   3:  3  6  7  7  7  7  7  7  7
%e A180975   4:  4 10 14 15 15 15 15 15 15
%e A180975   5:  5 15 25 30 31 31 31 31 31
%e A180975   6:  6 21 41 56 62 63 63 63 63
%p A180975 T:= proc(n,k) option remember;
%p A180975 if n = 0 or k = 0 then 0
%p A180975 else T(n-1,k-1) + 1 + T(n-1,k)
%p A180975 fi
%p A180975 end proc:
%p A180975 seq(seq(T(i,m-i),i=1..m-1),m=1..20); # _Robert Israel_, Jan 20 2015
%t A180975 T[n,k] = Sum[Binomial[n, j], {j, 1, k}]; Table[T[k, n-k], {n, 2, 15}, {k, 1, n-1}]//Flatten (* modified by _G. C. Greubel_, Oct 09 2018 *)
%o A180975 (PARI) for(n=2, 15, for(k=1,n-1, print1(sum(j=1, n-k, binomial(k,j)), ", "))) \\ _G. C. Greubel_, Oct 09 2018
%o A180975 (Magma) [[(&+[Binomial(k,j): j in [1..n-k]]): k in [1..n-1]]: n in [2..15]]; // _G. C. Greubel_, Oct 09 2018
%o A180975 (GAP) nmax:=11;; T:=List([1..nmax],n->List([1..nmax],k->Sum([1..k],j->Binomial(n,j))));;
%o A180975 b:=List([2..nmax],n->OrderedPartitions(n,2));;
%o A180975 a:=Flat(List([1..Length(b)],i->List([1..Length(b[i])],j->T[b[i][j][1]][b[i][j][2]]))); # _Muniru A Asiru_, Oct 09 2018
%o A180975 (Python)
%o A180975 from functools import lru_cache
%o A180975 @lru_cache(maxsize=None)
%o A180975 def T(n, k): return 0 if n*k == 0 else T(n-1, k-1) + 1 + T(n-1, k)
%o A180975 print([T(k, n-k) for n in range(1, 12) for k in range(1, n)]) # _Michael S. Branicky_, Apr 04 2021
%Y A180975 Cf. A004070, A117670.
%Y A180975 Cf. A131251 (transpose).
%Y A180975 Cf. A001924 (antidiagonal sums).
%K A180975 easy,nice,nonn,tabl
%O A180975 1,3
%A A180975 Francis Carr (fcarr(AT)alum.mit.edu), Sep 30 2010