A026376 -id:A026376 - cp's OEIS frontend

A101895 Triangle read by rows: T(n,k) is the number of Schroeder paths of length 2n and having k peaks at even height.

2, 5, 1, 15, 6, 1, 51, 30, 8, 1, 188, 144, 51, 10, 1, 731, 685, 300, 77, 12, 1, 2950, 3258, 1695, 532, 108, 14, 1, 12235, 15533, 9348, 3455, 854, 144, 16, 1, 51822, 74280, 50729, 21538, 6245, 1280, 185, 18, 1, 223191, 356283, 272128, 130375, 43278, 10387, 1824

Offset: 1

Emeric Deutsch, Dec 20 2004

A Schroeder path of length 2n is a lattice path starting from (0,0), ending at (2n,0), consisting only of steps U=(1,1) (up steps), D=(1,-1) (down steps) and H=(2,0) (level steps) and never going below the x-axis. Schroeder paths are counted by the large Schroeder numbers (A006318). Row sums are the large Schroeder numbers (A006318). Column 0 yields A007317. Column 1 yields A026376.

			T(3,1)=6 because we have HU(UD)D, U(UD)DH, UH(UD)D, U(UD)HD, UDU(UD)D and
U(UD)DUD, the peaks at even height being shown between parentheses.
Triangle begins:
2;
5,1;
15,6,1;
51,30,8,1;
188,144,51,10,1;

Cf. A006318, A007317, A026376, A101894.

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

G.f.=G=G(t, z) satisfies z(1-z)G^2-(1-z)(1-tz)G+1-tz=0.

A126181 Triangle read by rows, T(n,k) = C(n,k)*Catalan(n-k+1), n >= 0, 0 <= k <= n.

Original entry on oeis.org

1, 2, 1, 5, 4, 1, 14, 15, 6, 1, 42, 56, 30, 8, 1, 132, 210, 140, 50, 10, 1, 429, 792, 630, 280, 75, 12, 1, 1430, 3003, 2772, 1470, 490, 105, 14, 1, 4862, 11440, 12012, 7392, 2940, 784, 140, 16, 1, 16796, 43758, 51480, 36036, 16632, 5292, 1176, 180, 18, 1, 58786

Offset: 0

Emeric Deutsch, Dec 19 2006, Mar 30 2007

T(n,k) is the number of hex trees with n edges and k nodes having median children (i.e., k vertical edges; 0 <= k <= n). A hex tree is a rooted tree where each vertex has 0, 1, or 2 children and, when only one child is present, it is either a left child, or a median child, or a right child (name due to an obvious bijection with certain tree-like polyhexes; see the Harary-Read paper).
Also, with offset 1, triangle read by rows: T(n,k) is the number of skew Dyck paths of semilength n and having k left steps (n >= 1; 0 <= k <= n-1). A skew Dyck path is a path in the first quadrant which begins at the origin, ends on the x-axis, consists of steps U=(1,1)(up), D=(1,-1)(down) and L=(-1,-1)(left) so that up and left steps do not overlap. The length of a path is defined to be the number of its steps. For example, T(4,2)=6 because we have UDUUUDLL, UUUUDLLD, UUDUUDLL, UUUUDLDL, UUUDUDLL and UUUUDDLL.
Also, with offset 1, number of skew Dyck paths of semilength and having k UDU's. Example: T(3,1)=4 because we have (UDU)UDD, (UDU)UDL, U(UDU)DD and U(UDU)DL (the UDU's are shown between parentheses).

			Triangle starts:
   1;
   2,  1;
   5,  4,  1;
  14, 15,  6,  1;
  42, 56, 30,  8,  1;

F. Harary and R. C. Read, The enumeration of tree-like polyhexes, Proc. Edinburgh Math. Soc. (2) 17 (1970), 1-13.

Mirror image of A108198.

Cf. A002212, A000108, A026376.

c:=n->binomial(2*n,n)/(n+1): T:=proc(n,k) if k<=n then binomial(n,k)*c(n-k+1) else 0 fi end: for n from 0 to 10 do seq(T(n,k),k=1..n) od; # yields sequence in triangular form
# Second implementation:
h := n -> simplify(hypergeom([3/2,-n],[3],-x)):
T := (n,k) -> 4^(n-k)*coeff(h(n), x, n-k):
seq(print(seq(T(n,k), k=0..n)), n=0..9); # Peter Luschny, Feb 04 2015

T[n_, k_] := Binomial[n, k]*CatalanNumber[n-k+1]; Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Feb 04 2015 *)

T(n,k) = binomial(n,k)*c(n-k+1), where c(m) = binomial(2m,m)/(m+1) is a Catalan number (A000108). Proof: There are c(n-k+1) binary trees with n-k edges. We can insert k vertical edges at the n-k+1 vertices (repetitions possible) in binomial(n-k+1+k-1,k) = binomial(n,k) ways.
G.f.: G = G(t,z) satisfies G = 1 + (2+t)*z*G + z^2*G^2.
Sum of terms in row n is A002212(n+1).
T(n,0) = A000108(n+1) (the Catalan numbers).
Sum_{k=0..n} k*T(n,k) = A026376(n) for n >= 1.
1/(1 - xy - 2x - x^2/(1 - xy - 2x - x^2/(1 - xy - 2x - x^2/(1 - xy - 2x - x^2/(1 - ... (continued fraction). - Paul Barry, Jan 28 2009
T(n,k) = 4^(n-k)*[x^(n-k)]hypergeom([3/2,-n],[3],-x). - Peter Luschny, Feb 04 2015

Edited by N. J. A. Sloane at the suggestion of Andrew S. Plewe, Jun 13 2007

Edited and previous name moved to comments by Peter Luschny, Feb 03 2015

A126178 Triangle read by rows: T(n,k) is number of hex trees with n edges and k vertices of outdegree 1 (0<=k<=n).

Original entry on oeis.org

1, 0, 3, 1, 0, 9, 0, 9, 0, 27, 2, 0, 54, 0, 81, 0, 30, 0, 270, 0, 243, 5, 0, 270, 0, 1215, 0, 729, 0, 105, 0, 1890, 0, 5103, 0, 2187, 14, 0, 1260, 0, 11340, 0, 20412, 0, 6561, 0, 378, 0, 11340, 0, 61236, 0, 78732, 0, 19683, 42, 0, 5670, 0, 85050, 0, 306180, 0, 295245, 0

Offset: 0

Emeric Deutsch, Dec 19 2006

A hex tree is a rooted tree where each vertex has 0, 1, or 2 children and, when only one child is present, it is either a left child, or a median child, or a right child (name due to an obvious bijection with certain tree-like polyhexes; see the Harary-Read paper).
Sum of terms in row n = A002212(n+1).
Column 0 yields the aerated Catalan numbers (1,0,1,0,2,0,5,0,14,...).
T(n,n) = 3^n (see A000244).
Sum_{k=0..n} k*T(n,k) = 3*A026376(n) (n>=1).

			Triangle starts:
  1;
  0,  3;
  1,  0,  9;
  0,  9,  0, 27;
  2,  0, 54,  0, 81;

F. Harary and R. C. Read, The enumeration of tree-like polyhexes, Proc. Edinburgh Math. Soc. (2) 17 (1970), 1-13.

Cf. A000244, A002212, A026376.

T:=proc(n,k) if n-k mod 2 = 0 then 3^k*binomial(n+1,k)*binomial(n+1-k,(n-k)/2)/(n+1) else 0 fi end: for n from 0 to 11 do seq(T(n,k),k=0..n) od; # yields sequence in triangular form

T(n,k) = [3^k/(n+1)]binomial(n+1,k)*binomial(n+1-k,(n-k)/2) (0<=k<=n).

G.f.: G=G(t,z) satisfies G=1+3tzG+z^2*G^2.

A128753 Triangle read by rows: T(n,k) is the number of skew Dyck paths of semilength n and having k UDUDU's (n >= 0; 0 <= k <= n-2 for n >= 2).

Original entry on oeis.org

1, 1, 3, 9, 1, 31, 4, 1, 113, 19, 4, 1, 431, 86, 21, 4, 1, 1697, 393, 101, 23, 4, 1, 6847, 1800, 492, 116, 25, 4, 1, 28161, 8279, 2388, 596, 131, 27, 4, 1, 117631, 38218, 11603, 3032, 705, 146, 29, 4, 1, 497665, 177013, 56407, 15403, 3732, 819, 161, 31, 4, 1

Offset: 0

Emeric Deutsch, Apr 01 2007

A skew Dyck path is a path in the first quadrant which begins at the origin, ends on the x-axis, consists of steps U=(1,1)(up), D=(1,-1)(down) and L=(-1,-1)(left) so that up and left steps do not overlap. The length of a path is defined to be the number of its steps.
Rows 0 and 1 have one term each; row n has n-1 terms (n >= 2).
Row sums yield A002212.

			T(4,1)=4 because we have (UDUDU)UDD, (UDUDU)UDL, U(UDUDU)DD and U(UDUDU)DL (the subwords UDUDU are shown between parentheses).
Triangle starts
    1;
    1;
    3;
    9,  1;
   31,  4,  1;
  113, 19,  4,  1;

E. Deutsch, E. Munarini, S. Rinaldi, Skew Dyck paths, J. Stat. Plann. Infer. 140 (8) (2010) 2191-2203.

Cf. A002212, A052709, A026376.

C:=z->(1-sqrt(1-4*z))/2/z: G:=C(z*(1+z-t*z)/(1-t*z)): Gser:=simplify(series(G,z=0,15)): for n from 0 to 12 do P[n]:=sort(coeff(Gser,z,n)) od: 1; 1; for n from 2 to 12 do seq(coeff(P[n],t,j),j=0..n-2) od; # yields sequence in triangular form

T(n,0) = A052709(n+1).
Sum_{k=0..n-2} k*T(n,k) = A026376(n-2).
G.f.: G = G(t,z) satisfies z(1 + z - tz)G^2 - (1 - tz)G + 1 - tz = 0. G = C((1+z-tz)/(1-tz)), where C(z) = (1 - sqrt(1 - 4z))/(2z) is the Catalan function.

cp's OEIS Frontend

A101895 Triangle read by rows: T(n,k) is the number of Schroeder paths of length 2n and having k peaks at even height.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Formula

A126181 Triangle read by rows, T(n,k) = C(n,k)*Catalan(n-k+1), n >= 0, 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A126178 Triangle read by rows: T(n,k) is number of hex trees with n edges and k vertices of outdegree 1 (0<=k<=n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A128753 Triangle read by rows: T(n,k) is the number of skew Dyck paths of semilength n and having k UDUDU's (n >= 0; 0 <= k <= n-2 for n >= 2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula