A106580 Triangle T(n, k) = T(n, k-1) + Sum_{i >= 1} T(n-2i, k-i) with T(n,0)=1, read by rows.

1, 1, 1, 1, 2, 2, 1, 2, 3, 3, 1, 2, 5, 7, 7, 1, 2, 5, 9, 12, 12, 1, 2, 5, 13, 22, 29, 29, 1, 2, 5, 13, 26, 41, 53, 53, 1, 2, 5, 13, 34, 65, 101, 130, 130, 1, 2, 5, 13, 34, 73, 129, 194, 247, 247, 1, 2, 5, 13, 34, 89, 185, 322, 481, 611, 611, 1, 2, 5, 13, 34, 89, 201, 386, 645, 945, 1192, 1192, 1, 2, 5, 13, 34, 89, 233, 514, 973, 1613, 2354, 2965, 2965

Offset: 0

Author

N. J. A. Sloane, May 30 2005

Keywords

• nonn
• tabl
• easy

Comments

Next term is previous term + terms directly above you on a vertical line.

An intermingling of two independent triangles, A106595 and A106596.

Examples

			Triangle begins as:
  1;
  1, 1;
  1, 2, 2;
  1, 2, 3,  3;
  1, 2, 5,  7,  7;
  1, 2, 5,  9, 12, 12;
  1, 2, 5, 13, 22, 29,  29;
  1, 2, 5, 13, 26, 41,  53,  53;
  1, 2, 5, 13, 34, 65, 101, 130, 130;
		

Links

• G. C. Greubel, Rows n = 0..50 of the triangle, flattened

Crossrefs

Cf. A106595, A106596.

Programs

Maple

A106580:= proc(n,k) option remember; if k=0 then 1; else A106580(n,k-1) + add(A106580(n-2*i, k-i), i=1..min(k, floor(n/2), n-k)); fi ; end: for n from 0 to 12 do for k from 0 to n do printf("%d, ", A106580(n,k)); od; od; # R. J. Mathar, May 02 2007

Mathematica

t[, 0]= 1; t[n, k_]:= t[n, k] = t[n, k-1] + Sum[t[n-2j, k-j], {j, 1, Min[k, Floor[n/2], n-k]}]; Table[t[n, k], {n, 0, 12}, {k, 0, n}]//Flatten (* Jean-François Alcover, Jan 08 2014, after Maple *)

Sage

@CachedFunction
def T(n, k):
    if (k<0): return 0
    elif (k==0): return 1
    else: return T(n, k-1) + sum( T(n-2*j, k-j) for j in (1..min(k, n//2, n-k)))
flatten([[T(n,k) for k in (0..n)] for n in (0..10)]) # G. C. Greubel, Sep 07 2021

Formula

T(n, k) = T(n, k-1) + Sum_{i>=1} T(n-2*i, k-i), with T(n, 0) = 1.

Extensions

More terms from R. J. Mathar, May 02 2007