login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A117670 Triangle read by rows: partial sums of the Pascal triangle minus 1. 2
1, 2, 3, 3, 6, 7, 4, 10, 14, 15, 5, 15, 25, 30, 31, 6, 21, 41, 56, 62, 63, 7, 28, 63, 98, 119, 126, 127, 8, 36, 92, 162, 218, 246, 254, 255, 9, 45, 129, 255, 381, 465, 501, 510, 511, 10, 55, 175, 385, 637, 847, 967, 1012, 1022, 1023 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

Imagine that you are in a building with floors starting at floor 1, the lowest floor and you have a large number of eggs. For each floor in the building, you want to know whether or not an egg dropped from that floor will break.

If an egg breaks when dropped from floor i, then all eggs are guaranteed to break when dropped from any floor j > i. Likewise, if an egg doesn't break when dropped from floor i, then all eggs are guaranteed to never break when dropped from any floor j <= i.

a(n,k) is the maximum number of floors where you can determine whether or not an egg will break when dropped from any floor, with the following restrictions: you may drop a maximum of n eggs (one at a time, from any floors of your choosing) and you may break a maximum of k eggs.

Each row of the triangle is the running sum of the corresponding row with the first 1 omitted of Pascal's triangle (A007318), see A008949, A054143, A193820.

The k-th entry in the n-th row is the number of possible combinations of on/off switches after k attempts to turn on a switch in a set of n distinguishable switches. An attempt to turn on the same switch twice does not result in a new combination. See example. - Sergei Viznyuk, Jun 24 2012

T(n,k) is the number of nonempty subsets of the n-set with at most k elements, see example. - Joerg Arndt, May 04 2014

LINKS

Susanne Wienand, Table of n, a(n) for n = 1..1830

Google code.jam, Problem C. Egg Drop

Sergei Viznyuk, C-Program

Sergei Viznyuk, Local copy of C-Program

FORMULA

a(n,1) = n ; a(n,n) = 2^n-1; a(n+1,k+1) = 1 + a(n,k) + a(n,k-1), 0 < k < n.

a(n,k) = sum(binomial(n,m),m=1..k), 1 <= k <= n. (see the running sum comment above). - Wolfdieter Lang, Feb 07 2013

EXAMPLE

Triangle a(n,k) begins:

n\k  1   2    3    4    5    6    7     8     9    10 ...

1:   1

2:   2   3

3:   3   6    7

4:   4  10   14   15

5:   5  15   25   30   31

6:   6  21   41   56   62   63

7:   7  28   63   98  119  126  127

8:   8  36   92  162  218  246  254   255

9:   9  45  129  255  381  465  501   510   511

10: 10  55  175  385  637  847  967  1012  1022  1023

...  Reformatted and extended by Wolfdieter Lang, Feb 07 2013

From Sergei Viznyuk, Jun 24 2012: (Start)

For example, we have n=3 distinguishable switches A,B,C (third row above). We attempt k=2 times to turn on a switch at random. The possible resulting combinations are:

A=on, B=off, C=off (the same A switch was turned on 2 times)

A=off, B=on, C=off (the same B switch was turned on 2 times)

A=off, B=off, C=on (the same C switch was turned on 2 times)

A=on, B=on, C=off  (switches A and B were turned on)

A=on, B=off, C=on  (switches A and C were turned on)

A=off, B=on, C=on  (switches B and C were turned on)

Thus, we have 6 different combinations, which is the number 6 at row n=3 column k=2 in the sequence above.

(End)

From Joerg Arndt, May 04 2014: (Start)

There are T(4,2) = 10 subsets of {0, 1, 2, 3}:

01:    1...    { 0 }

02:    11..    { 0, 1 }

03:    111.    { 0, 1, 2 }

04:    11.1    { 0, 1, 3 }

05:    1.1.    { 0, 2 }

06:    1.11    { 0, 2, 3 }

07:    1..1    { 0, 3 }

08:    .1..    { 1 }

09:    .11.    { 1, 2 }

10:    .111    { 1, 2, 3 }

11:    .1.1    { 1, 3 }

12:    ..1.    { 2 }

13:    ..11    { 2, 3 }

14:    ...1    { 3 }

(End)

MATHEMATICA

Table[Sum[Binomial[n, m], {m, k}], {n, 10}, {k, n}] // Flatten (* Michael De Vlieger, Nov 25 2015 *)

PROG

(PARI) tabl(nrows) = {for (n=1, nrows, for (k=1, n, print1(sum(m=1, k, binomial(n, m)), ", "); ); print(); ); } \\ Michel Marcus, May 21 2013

CROSSREFS

Sequence in context: A251729 A187763 A187262 * A181695 A184830 A025499

Adjacent sequences:  A117667 A117668 A117669 * A117671 A117672 A117673

KEYWORD

nonn,tabl

AUTHOR

Arie Bos, Jul 06 2008, Jul 08 2008

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified April 24 00:59 EDT 2017. Contains 285338 sequences.