login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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). 32
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 (list; table; graph; refs; listen; history; text; internal format)
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

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 19 19:21 EST 2020. Contains 332047 sequences. (Running on oeis4.)