A026780 Triangular array T read by rows: T(n,0)=T(n,n)=1 for n >= 0; for n >= 2 and 1 <= k <= n-1, T(n,k) = T(n-1,k-1) + T(n-2,k-1) + T(n-1,k) if 1 <= k <= floor(n/2), else T(n,k) = T(n-1,k-1) + T(n-1,k).

1, 1, 1, 1, 3, 1, 1, 5, 4, 1, 1, 7, 12, 5, 1, 1, 9, 24, 17, 6, 1, 1, 11, 40, 53, 23, 7, 1, 1, 13, 60, 117, 76, 30, 8, 1, 1, 15, 84, 217, 246, 106, 38, 9, 1, 1, 17, 112, 361, 580, 352, 144, 47, 10, 1, 1, 19, 144, 557, 1158, 1178, 496, 191, 57, 11, 1

Offset

0,5

Comments

T(n,k) is the number of paths from (0,0) to (k,n-k) in the directed graph having vertices (i,j) and edges (i,j)-to-(i+1,j) and (i,j)-to-(i,j+1) for i,j>= 0 and edges (i,i+h)-to-(i+1,i+h+1) for i>=0, h>=0.

Also, square array R read by antidiagonals with R(i,j) = T(i+j,i) equal number of paths from (0,0) to (i,j). - Max Alekseyev, Jan 13 2015

Links

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

M. A. Alekseyev, On Enumeration of Dyck-Schroeder Paths, Journal of Combinatorial Mathematics and Combinatorial Computing 106 (2018), 59-68; arXiv:1601.06158 [math.CO], 2016-2018.

Formula

For n>=2*k, T(n,k) = coefficient of x^k in F(x)*S(x)^(n-2*k). For n<=2*k, T(n,k) = coefficient of x^(n-k) in F(x)*C(x)^(2*k-n). Here C(x) = (1 - sqrt(1-4x))/(2*x) is o.g.f. for A000108, S(x) = (1 - x - sqrt(1-6*x+x^2))/(2*x) is o.g.f. for A006318, and F(x) = S(x)/(1 - x*C(x)*S(x)) is o.g.f. for A026781. - Max Alekseyev, Jan 13 2015

Example

The array T(n,k) starts with:
n=0: 1;
n=1: 1,  1;
n=2: 1,  3,  1;
n=3: 1,  5,  4,  1;
n=4: 1,  7, 12,  5,  1;
n=5: 1,  9, 24, 17,  6, 1;
n=6: 1, 11, 40, 53, 23, 7, 1;
...

Maple

T:= proc(n, k) option remember;
    if n<0 then 0;
    elif k=0 or k =n then 1;
    elif k <= n/2 then
        procname(n-1, k-1)+procname(n-2, k-1)+procname(n-1, k) ;
    else
        procname(n-1, k-1)+procname(n-1, k) ;
    fi ;
end proc:
seq(seq(T(n, k), k=0..n), n=0..12); # G. C. Greubel, Nov 01 2019

Mathematica

T[n_, k_]:= T[n, k]= If[n<0, 0, If[k==0 || k==n, 1, If[k<=n/2, T[n-1, k-1] + T[n-2, k-1] + T[n-1, k], T[n-1, k-1] + T[n-1, k] ]]];
Table[T[n, k], {n, 0, 10}, {k, 0, n}]//Flatten (* G. C. Greubel, Nov 01 2019 *)

Prog

(PARI) T(n, k) = if(n<0, 0, if(k==0 || k==n, 1, if( k<=n/2, T(n-1, k-1) + T(n-2, k-1) + T(n-1, k), T(n-1, k-1) + T(n-1, k) )); )
for(n=0, 12, for(k=0, n, print1(T(n, k), ", "))) \\ G. C. Greubel, Oct 31 2019
(Sage)
@CachedFunction
def T(n, k):
    if (n<0): return 0
    elif (k==0 or k==n): return 1
    elif (k<=n/2): return T(n-1, k-1) + T(n-2, k-1) + T(n-1, k)
    else: return T(n-1, k-1) + T(n-1, k)
[[T(n, k) for k in (0..n)] for n in (0..12)] # G. C. Greubel, Oct 31 2019
(GAP)
T:= function(n, k)
    if n<0 then return 0;
    elif k=0 or k=n then return 1;
    elif (k <= Int(n/2)) then return T(n-1, k-1)+T(n-2, k-1) +T(n-1, k);
    else return T(n-1, k-1) + T(n-1, k);
    fi;
  end;
Flat(List([0..12], n-> List([0..n], k-> T(n, k) ))); # G. C. Greubel, Oct 31 2019

Crossrefs

Cf. A026787 (row sums), A026781 (center elements), A249488 (row-reversed version).

Cf. A026782, A026783, A026784, A026785, A026786, A026787, A026788, A026789, A026790.

Sequence in context: A285409 A208510 A131767 * A209421 A320435 A275421

Adjacent sequences: A026777 A026778 A026779 * A026781 A026782 A026783

Keyword

nonn,tabl

Author

Clark Kimberling

Extensions

Edited by Max Alekseyev, Dec 02 2015

Status

approved