login
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.
3

%I #37 Sep 10 2021 02:05:26

%S 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,

%T 65,149,149,65,13,1,1,15,90,266,388,266,90,15,1,1,17,119,431,836,836,

%U 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

%N 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.

%C 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.

%C 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

%C Row sums gives A118649. - _Emanuele Munarini_, Feb 01 2017

%H G. C. Greubel, <a href="/A106597/b106597.txt">Rows n = 0..50 of the triangle, flattened</a>

%F 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

%e Triangle begins:

%e 1;

%e 1, 1;

%e 1, 3, 1;

%e 1, 5, 5, 1;

%e 1, 7, 14, 7, 1;

%e 1, 9, 27, 27, 9, 1;

%e 1, 11, 44, 72, 44, 11, 1;

%e 1, 13, 65, 149, 149, 65, 13, 1;

%e 1, 15, 90, 266, 388, 266, 90, 15, 1;

%e 1, 17, 119, 431, 836, 836, 431, 119, 17, 1;

%t 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_ *)

%o (PARI) /* same as in A092566, but last line (output) replaced by the following */

%o /* show as triangle T(n-k,k): */

%o { for(n=0,N-1, for(k=0,n, print1(T(n-k,k),", "); ); print(); ); }

%o /* _Joerg Arndt_, Jul 01 2011 */

%o (Sage)

%o @CachedFunction

%o def T(n, k):

%o if (k<0): return 0

%o elif (k==0 or k==n): return 1

%o 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)))

%o flatten([[T(n, k) for k in (0..n)] for n in (0..12)]) # _G. C. Greubel_, Sep 08 2021

%Y Cf. A007318, A118649.

%Y T(2n,n) gives A118650.

%K nonn,tabl,easy

%O 0,5

%A _N. J. A. Sloane_, May 30 2005

%E More terms from _Joshua Zucker_, May 10 2006

%E Definition corrected by _Emilie Hogan_, Oct 15 2009