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,5

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

Links

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

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

Example

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;

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

Prog

(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

Crossrefs

Cf. A007318, A118649.

T(2n,n) gives A118650.

Sequence in context: A302997 A326792 A144461 * A108359 A100936 A086620

Adjacent sequences: A106594 A106595 A106596 * A106598 A106599 A106600

Keyword

nonn,tabl,easy

Author

N. J. A. Sloane, May 30 2005

Extensions

More terms from Joshua Zucker, May 10 2006

Definition corrected by Emilie Hogan, Oct 15 2009

Status

approved