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

Author

N. J. A. Sloane, Dec 08 2003

Keywords

• nonn
• tabf
• easy

Examples

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

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.

Crossrefs

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

Row sums give A033485.

Programs

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 *)

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)).

Extensions

More terms from Vladeta Jovovic, Dec 10 2003