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!)
A026769 Triangular array T read by rows: T(n,0)=T(n,n)=1 for n >= 0; T(2,1)=2; for n >= 3 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<=(n-1)/2, else T(n,k) = T(n-1,k-1) + T(n-1,k). 30
1, 1, 1, 1, 2, 1, 1, 4, 3, 1, 1, 6, 7, 4, 1, 1, 8, 17, 11, 5, 1, 1, 10, 31, 28, 16, 6, 1, 1, 12, 49, 76, 44, 22, 7, 1, 1, 14, 71, 156, 120, 66, 29, 8, 1, 1, 16, 97, 276, 352, 186, 95, 37, 9, 1, 1, 18, 127, 444, 784, 538, 281, 132, 46, 10, 1, 1, 20, 161, 668, 1504, 1674, 819, 413, 178, 56, 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 (i and j in range [0,n]) 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>=1.

Also, square array R read by antidiagonals where R(i,j) = T(i+j,i), which is equal to the number of paths from (0,0) to (i,j) in the above graph. - Max Alekseyev, Dec 02 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 G(x)*S(x)^(n-2*k). For n<=2*k, T(n,k) = coefficient of x^(n-k) in G(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 G(x)=1/(1-x*(C(x)+S(x))) is o.g.f. for A026770. - Max Alekseyev, Dec 02 2015

EXAMPLE

Triangle begins as:

  1;

  1,  1;

  1,  2,   1;

  1,  4,   3,   1;

  1,  6,   7,   4,   1;

  1,  8,  17,  11,   5,   1;

  1, 10,  31,  28,  16,   6,   1;

  1, 12,  49,  76,  44,  22,   7,   1;

  1, 14,  71, 156, 120,  66,  29,   8,  1;

  1, 16,  97, 276, 352, 186,  95,  37,  9,  1;

  1, 18, 127, 444, 784, 538, 281, 132, 46, 10, 1;

MAPLE

A026769 := proc(n, k)

    option remember;

    if k= 0 or k =n then

        1;

    elif n= 2 and k= 1 then

        2;

    elif k <= (n-1)/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: # R. J. Mathar, Jun 15 2014

MATHEMATICA

T[n_, k_] := T[n, k] = Which[k==0 || k==n, 1, n==2 && k==1, 2, k <= (n-1)/2, T[n-1, k-1] + T[n-2, k-1] + T[n-1, k], True, T[n-1, k-1] + T[n-1, k]];

Table[T[n, k], {n, 0, 11}, {k, 0, n}] // Flatten (* Jean-François Alcover, Dec 10 2017, from Maple *)

PROG

(PARI) T(n, k) = if(k==0 || k==n, 1, if(n==2 && k==1, 2, if( k<=(n-1)/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 (k==0 or k==n): return 1

    elif (n==2 and k==1): return 2

    elif (k<=(n-1)/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 k=0 or k=n then return 1;

    elif (n=2 and k=1) then return 2;

    elif (k <= Int((n-1)/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. A026770, A026771, A026772, A026773, A026774, A026775, A026776, A026777, A026779

Cf. A026780 (a variant with h>=0)

Sequence in context: A026758 A130523 A034363 * A257365 A230858 A060098

Adjacent sequences:  A026766 A026767 A026768 * A026770 A026771 A026772

KEYWORD

nonn,tabl

AUTHOR

Clark Kimberling

EXTENSIONS

Offset corrected by R. J. Mathar, Jun 15 2014

More terms added by G. C. Greubel, Oct 31 2019

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 July 14 03:42 EDT 2020. Contains 335716 sequences. (Running on oeis4.)