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

Author

Emeric Deutsch, Dec 26 2005

Keywords

• nonn
• tabl

Comments

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

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

Examples

			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-2*x)/(1-3*x).
		

Links

• Michael De Vlieger, Table of n, a(n) for n = 0..11475 (assuming the Kruchinin formula, rows 0 <= n <= 150, flattened.)
• Emeric Deutsch, L. Ferrari, and S. Rinaldi, Production Matrices, Advances in Applied Mathematics, 34 (2005) pp. 101-122.
• Shishuo Fu and Yaling Wang, Bijective recurrences concerning two Schröder triangles, arXiv:1908.03912 [math.CO], 2019.

Crossrefs

Cf. A001003, A114710, A010683.

Programs

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 *)

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 */

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