A180975 - OEIS

%I #52 Jun 26 2022 03:09:35

%S 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 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 Array of the "egg-drop" numbers, read by downwards antidiagonals.

%C 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 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 . WC(k,f) = 1 + max_{g in 1..f} { WC(k-1, g-1), WC(k, f-g) }

%C with boundary conditions

%C . WC(1,f) = f and WC(k,0) = 0

%C 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 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 J. Kleinberg and E. Tardos, "Algorithm Design", Addison-Wesley Longman Publishing Co. Inc., 2005. Problem 2.8.

%D 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 G. C. Greubel, <a href="/A180975/b180975.txt">Antidiagonals n = 1..100 of array, flattened</a>

%H Michael Boardman, <a href="http://www.jstor.org/stable/3219201">The Egg-Drop Numbers</a>, Mathematics Magazine, 77 (2004), 368-372.

%F 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 T(n,k) = Sum_{j=1..k} binomial(n,j).

%F 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 G.f.: x*y/((1-y)*(1-x)*(1-x-x*y)). - _Vladimir Kruchinin_, Oct 09 2018

%e 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 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 The square array starts in row n=1 with columns k >= 1:

%e   1:  1  1  1  1  1  1  1  1  1

%e   2:  2  3  3  3  3  3  3  3  3

%e   3:  3  6  7  7  7  7  7  7  7

%e   4:  4 10 14 15 15 15 15 15 15

%e   5:  5 15 25 30 31 31 31 31 31

%e   6:  6 21 41 56 62 63 63 63 63

%p T:= proc(n,k) option remember;

%p if n = 0 or k = 0 then 0

%p else T(n-1,k-1) + 1 + T(n-1,k)

%p fi

%p end proc:

%p seq(seq(T(i,m-i),i=1..m-1),m=1..20); # _Robert Israel_, Jan 20 2015

%t 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 (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 (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 (GAP) nmax:=11;; T:=List([1..nmax],n->List([1..nmax],k->Sum([1..k],j->Binomial(n,j))));;

%o b:=List([2..nmax],n->OrderedPartitions(n,2));;

%o 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 (Python)

%o from functools import lru_cache

%o @lru_cache(maxsize=None)

%o def T(n, k): return 0 if n*k == 0 else T(n-1, k-1) + 1 + T(n-1, k)

%o print([T(k, n-k) for n in range(1, 12) for k in range(1, n)]) # _Michael S. Branicky_, Apr 04 2021

%Y Cf. A004070, A117670.

%Y Cf. A131251 (transpose).

%Y Cf. A001924 (antidiagonal sums).

%K easy,nice,nonn,tabl

%O 1,3

%A Francis Carr (fcarr(AT)alum.mit.edu), Sep 30 2010