A180975 Array of the "egg-drop" numbers, read by downwards antidiagonals.
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, 15, 30, 41, 28, 8, 1, 3, 7, 15, 31, 56, 63, 36, 9, 1, 3, 7, 15, 31, 62, 98, 92, 45, 10
Offset: 1
Examples
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. 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. The square array starts in row n=1 with columns k >= 1: 1: 1 1 1 1 1 1 1 1 1 2: 2 3 3 3 3 3 3 3 3 3: 3 6 7 7 7 7 7 7 7 4: 4 10 14 15 15 15 15 15 15 5: 5 15 25 30 31 31 31 31 31 6: 6 21 41 56 62 63 63 63 63
References
- J. Kleinberg and E. Tardos, "Algorithm Design", Addison-Wesley Longman Publishing Co. Inc., 2005. Problem 2.8.
- 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.
Links
- G. C. Greubel, Antidiagonals n = 1..100 of array, flattened
- Michael Boardman, The Egg-Drop Numbers, Mathematics Magazine, 77 (2004), 368-372.
Programs
-
GAP
nmax:=11;; T:=List([1..nmax],n->List([1..nmax],k->Sum([1..k],j->Binomial(n,j))));; b:=List([2..nmax],n->OrderedPartitions(n,2));; 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
-
Magma
[[(&+[Binomial(k,j): j in [1..n-k]]): k in [1..n-1]]: n in [2..15]]; // G. C. Greubel, Oct 09 2018
-
Maple
T:= proc(n,k) option remember; if n = 0 or k = 0 then 0 else T(n-1,k-1) + 1 + T(n-1,k) fi end proc: seq(seq(T(i,m-i),i=1..m-1),m=1..20); # Robert Israel, Jan 20 2015
-
Mathematica
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 *) -
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
-
Python
from functools import lru_cache @lru_cache(maxsize=None) def T(n, k): return 0 if n*k == 0 else T(n-1, k-1) + 1 + T(n-1, k) print([T(k, n-k) for n in range(1, 12) for k in range(1, n)]) # Michael S. Branicky, Apr 04 2021
Formula
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.
T(n,k) = Sum_{j=1..k} binomial(n,j).
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).
G.f.: x*y/((1-y)*(1-x)*(1-x-x*y)). - Vladimir Kruchinin, Oct 09 2018
Comments