A089178 Triangle T(n,k) (n >= 0, 0 <= k <= 1+log_2(floor(n+1))) read by rows: row 0 = {1}, row 1 = {1 1}; for n >=2, row n = row n-1 + (row floor((n-1)/2) shifted one place right).

1, 1, 1, 1, 2, 1, 3, 1, 1, 4, 2, 1, 5, 4, 1, 6, 6, 1, 7, 9, 1, 1, 8, 12, 2, 1, 9, 16, 4, 1, 10, 20, 6, 1, 11, 25, 10, 1, 12, 30, 14, 1, 13, 36, 20, 1, 14, 42, 26, 1, 15, 49, 35, 1, 1, 16, 56, 44, 2, 1, 17, 64, 56, 4, 1, 18, 72, 68, 6, 1, 19, 81, 84, 10, 1, 20, 90, 100, 14, 1, 21, 100, 120, 20

Offset

0,5

Links

Alois P. Heinz, Rows n = 0..1094, flattened

N. J. A. Sloane and J. A. Sellers, On non-squashing partitions, Discrete Math., 294 (2005), 259-274.

Formula

G.f.: (1/(1-x))*(1+Sum(y^(k+1)*x^(2^(k+1)-1)/Product(1-x^(2^j), j=0..k), k=0..infinity)).

Example

Triangle begins:
1;
1, 1;
1, 2;
1, 3, 1;
1, 4, 2;
1, 5, 4;
1, 6, 6;
1, 7, 9, 1;

Maple

T:= proc(n) option remember; `if`(n=0, 1,
      zip((x, y)-> x+y, [T(n-1)], [0, T(floor((n-1)/2))], 0)[])
    end:
seq(T(n), n=0..25);  # Alois P. Heinz, Apr 01 2012

Mathematica

row[0] = {1}; row[n_] := row[n] = PadRight[{row[n-1], Join[{0}, row[Floor[(n-1)/2]]]}] // Total; Table[row[n], {n, 0, 25}] // Flatten (* Jean-François Alcover, Nov 27 2014 *)

Crossrefs

Also obtained by dividing rows of A089177 by "1 1".

Row sums give A033485.

Sequence in context: A210992 A220484 A174066 * A187489 A355145 A116599

Adjacent sequences: A089175 A089176 A089177 * A089179 A089180 A089181

Keyword

nonn,tabf,easy

Author

N. J. A. Sloane, Dec 08 2003

Extensions

More terms from Vladeta Jovovic, Dec 10 2003

Status

approved