A120986 Triangle read by rows: T(n,k) is the number of ternary trees with n edges and having k middle edges (n >= 0, k >= 0).

1, 2, 1, 5, 6, 1, 14, 28, 12, 1, 42, 120, 90, 20, 1, 132, 495, 550, 220, 30, 1, 429, 2002, 3003, 1820, 455, 42, 1, 1430, 8008, 15288, 12740, 4900, 840, 56, 1, 4862, 31824, 74256, 79968, 42840, 11424, 1428, 72, 1, 16796, 125970, 348840, 465120, 325584

Offset: 0

Author

Emeric Deutsch, Jul 21 2006

Keywords

• nonn
• tabl

Comments

A ternary tree is a rooted tree in which each vertex has at most three children and each child of a vertex is designated as its left or middle or right child.

T(n,k) is the number of Dyck paths of semilength 2n+2 with all descent runs of even length and n+1-k peaks. - Alexander Burstein, May 23 2020

T(n,k) is the number of Dyck paths of semilength 2n+2 with all descent runs of even length and k+1 peaks at even height. - Alexander Burstein, Jun 03 2020

T(n,k) is the number of Dyck paths of semilength 2n+2 with all descent runs of even length and k peaks at odd height. - Alexander Burstein, Jun 18 2020

An apparent refinement is A338135. - Tom Copeland, Oct 12 2020

Examples

			Triangle starts:
    1;
    2,   1;
    5,   6,   1;
   14,  28,  12,   1;
   42, 120,  90,  20,  1;
  132, 495, 550, 220, 30, 1;
  ...
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..1274
• Alexander Burstein, Distribution of peak heights modulo k and double descents on k-Dyck paths, arXiv:2009.00760 [math.CO], 2020.
• Alexander Burstein and Megan Martinez, Pattern classes equinumerous to the class of ternary forests, Permutation Patterns Virtual Workshop, Howard University (2020).
• Helmut Prodinger, Counting ternary trees according to the number of middle edges and factorizing into (3/2)-ary trees, arXiv:2009.06793 [math.CO], 2020.
• Helmut Prodinger, Counting edges according to edge-type in t-ary trees, arXiv:2205.13374 [math.CO], 2022.
• Chao-Jen Wang, Applications of the Goulden-Jackson cluster method to counting Dyck paths by occurrences of subwords, Dissertation, Brandeis University, 2011.

Crossrefs

Cf. A001764 (row sums), A000108, A108767, A013698, A110608.

Programs

Maple

T:=(n,k)->binomial(n+1,k)*binomial(2*(n+1),n-k)/(n+1): for n from 0 to 10 do seq(T(n,k),k=0..n) od; # yields sequence in triangular form

Mathematica

T[n_, k_] := Binomial[n+1, k]*Binomial[2*(n+1), n-k]/(n+1);
Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jul 06 2018 *)

PARI

T(n,k) = binomial(n+1,k)*binomial(2*(n+1),n-k)/(n+1); \\ Andrew Howroyd, Nov 06 2017

Python

from sympy import binomial
def T(n, k): return binomial(n + 1, k)*binomial(2*(n + 1), n - k)//(n + 1)
for n in range(21): print([T(n, k) for k in range(n + 1)]) # Indranil Ghosh, Nov 07 2017

Formula

T(n,k) = (1/(n+1))*binomial(n+1,k)*binomial(2*(n+1),n-k).

T(n,0) = A000108(n+1) (the Catalan numbers).

T(n,k) = A108767(n+1,n+1-k).

Sum_{k>=1} k*T(n,k) = binomial(3*n+2,n-1) = A013698(n).

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

O.g.f.: A(x,t) = 1 + (2 + t)*x + (5 + 6*t + t^2)*x^2 + ... satisfies 1 + x*d/dx(A(x,t))/A(x,t) = 1 + (2 + t)*x + (6 + 8*t + t^2)*x^2 + ..., which is the o.g.f. for A110608. - Peter Bala, Oct 13 2015