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

1, 1, 1, 1, 3, 1, 1, 5, 5, 1, 1, 7, 14, 7, 1, 1, 9, 27, 27, 9, 1, 1, 11, 44, 72, 44, 11, 1, 1, 13, 65, 149, 149, 65, 13, 1, 1, 15, 90, 266, 388, 266, 90, 15, 1, 1, 17, 119, 431, 836, 836, 431, 119, 17, 1, 1, 19, 152, 652, 1585, 2150, 1585, 652, 152, 19, 1, 1, 21, 189, 937, 2743, 4753, 4753, 2743, 937, 189, 21, 1

Offset: 0

Author

N. J. A. Sloane, May 30 2005

Keywords

• nonn
• tabl
• easy

Comments

Next term is sum of two terms above you in previous row (as in Pascal's triangle A007318) plus sum of terms directly above you on a vertical line.

T(n,n-k) is the number of lattice paths from (0,0) to (n,k) using steps (1,0), (0,1), and (s,s) for s>=1. - Joerg Arndt, Jul 01 2011

Row sums gives A118649. - Emanuele Munarini, Feb 01 2017

Examples

			Triangle begins:
  1;
  1,  1;
  1,  3,   1;
  1,  5,   5,   1;
  1,  7,  14,   7,   1;
  1,  9,  27,  27,   9,   1;
  1, 11,  44,  72,  44,  11,   1;
  1, 13,  65, 149, 149,  65,  13,   1;
  1, 15,  90, 266, 388, 266,  90,  15,  1;
  1, 17, 119, 431, 836, 836, 431, 119, 17, 1;
		

Links

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

Crossrefs

Cf. A007318, A118649.

T(2n,n) gives A118650.

Programs

Mathematica

CoefficientList[#, y]& /@ CoefficientList[(1 -x^2*y)/(1 -x -x*y -2x^2*y +x^3*y + x^3*y^2) + O[x]^12, x]//Flatten (* Jean-François Alcover, Oct 30 2018, after Emanuele Munarini *)

PARI

/* same as in A092566, but last line (output) replaced by the following */
/* show as triangle T(n-k,k): */
{ for(n=0,N-1, for(k=0,n, print1(T(n-k,k),", "); ); print(); ); }
/* Joerg Arndt, Jul 01 2011 */

Sage

@CachedFunction
def T(n, k):
    if (k<0): return 0
    elif (k==0 or k==n): return 1
    else: return + T(n-1, k-1) + T(n-1, k) + 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..12)]) # G. C. Greubel, Sep 08 2021

Formula

G.f.: (1-x^2*y)/(1-x-x*y-2*x^2*y+x^3*y+x^3*y^2). - Emanuele Munarini, Feb 01 2017

Extensions

More terms from Joshua Zucker, May 10 2006

Definition corrected by Emilie Hogan, Oct 15 2009