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 [math.CO], 2016-2018.
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
KEYWORD
nonn,tabl
AUTHOR
EXTENSIONS
Offset corrected by R. J. Mathar, Jun 15 2014
More terms added by G. C. Greubel, Oct 31 2019
STATUS
approved