A114709 Triangle read by rows: T(n,k) is the number of hill-free Schroeder paths of length 2n that have k horizontal steps on the x-axis (0<=k<=n). A Schroeder path of length 2n is a lattice path from (0,0) to (2n,0) consisting of U=(1,1), D=(1,-1) and H=(2,0) steps and never going below the x-axis. A hill is a peak at height 1.

1, 0, 1, 2, 0, 1, 6, 4, 0, 1, 26, 12, 6, 0, 1, 114, 56, 18, 8, 0, 1, 526, 252, 90, 24, 10, 0, 1, 2502, 1192, 414, 128, 30, 12, 0, 1, 12194, 5772, 2006, 600, 170, 36, 14, 0, 1, 60570, 28536, 9882, 2976, 810, 216, 42, 16, 0, 1, 305526, 143388, 49554, 14904, 4110, 1044

Offset

0,4

Comments

Row sums are the little Schroeder numbers (A001003). Column 0 is A114710. Sum(k*T(n,k),k=0..n)=A010683(n-1).

Riordan array ((1+3x-sqrt(1-6x+x^2))/(2x(2x+3)),(1+3x-sqrt(1-6x+x^2))/(2(2x+3))), inverse of the Riordan array ((1-3x)/((1-x)(1-2x)), (x(1-3x)/((1-x)(1-2x))). - Paul Barry, Mar 01 2011

Links

Michael De Vlieger, Table of n, a(n) for n = 0..11475 (assuming the Kruchinin formula, rows 0 <= n <= 150, flattened.)

E. Deutsch, L. Ferrari and S. Rinaldi, Production Matrices, Advances in Applied Mathematics, 34 (2005) pp. 101-122.

Shishuo Fu, Yaling Wang, Bijective recurrences concerning two Schröder triangles, arXiv:1908.03912 [math.CO], 2019.

Formula

G.f.: 1/(1+z-t*z-z*R), where R=(1-z-sqrt(1-6*z+z^2))/(2*z) is the g.f. of the large Schroeder numbers (A006318).

T(n,k) = Sum_{i=0..n-k}((i+1)*binomial(k+i+1,k)*Sum_{j=0..n-k-i}((-1)^(j+i)*2^(n-k-j-i)*binomial(n+1,j)*binomial(2*n-k-j-i,n)))/(n+1). - Vladimir Kruchinin, Feb 29 2016

Example

T(4,2)=6 because we have (HH)UHD,(HH)UUDD,(H)UHD(H),(H)UUDD(H),UHD(HH) and
UUDD(HH), where U=(1,1), D=(1,-1) and H=(2,0) (the H's on the x-axis are shown between parentheses).
Triangle starts:
1;
0,1;
2,0,1;
6,4,0,1;
26,12,6,0,1;
Production matrix is
0, 1,
2, 0, 1,
6, 2, 0, 1,
18, 6, 2, 0, 1,
54, 18, 6, 2, 0, 1,
162, 54, 18, 6, 2, 0, 1,
486, 162, 54, 18, 6, 2, 0, 1,
1458, 486, 162, 54, 18, 6, 2, 0, 1
where the columns have generator ((1-x)(1-2x))/(1-3x).

Maple

R:=(1-z-sqrt(1-6*z+z^2))/2/z: G:=1/(1+z-t*z-z*R): Gser:=simplify(series(G, z=0, 14)): P[0]:=1: for n from 1 to 10 do P[n]:=coeff(Gser, z^n) od: for n from 0 to 10 do seq(coeff(t*P[n], t^j), j=1..n+1) od; # yields sequence in triangular form

Mathematica

Table[Sum[(i + 1) Binomial[k + i + 1, k] Sum[(-1)^(j + i)*2^(n - k - j - i)* Binomial[n + 1, j] Binomial[2 n - k - j - i, n], {j, 0, n - k - i}], {i, 0, n - k}]/(n + 1), {n, 0, 10}, {k, 0, n}] // Flatten (* Michael De Vlieger, Oct 30 2019 *)

Prog

(Maxima)
T(n, k):=sum((i+1)*binomial(k+i+1, k)*sum((-1)^(j+i)*2^(n-k-j-i)*binomial(n+1, j)*binomial(2*n-k-j-i, n), j, 0, n-k-i), i, 0, n-k)/(n+1); /* Vladimir Kruchinin, Feb 29 2016 */

Crossrefs

Cf. A001003, A114710, A010683.

Sequence in context: A304485 A289537 A323837 * A293147 A331047 A264550

Adjacent sequences: A114706 A114707 A114708 * A114710 A114711 A114712

Keyword

nonn,tabl

Author

Emeric Deutsch, Dec 26 2005

Status

approved