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,2

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

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.

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

Example

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

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

Prog

(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

Crossrefs

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

Sequence in context: A179457 A107783 A047887 * A095801 A128567 A345394

Adjacent sequences: A120983 A120984 A120985 * A120987 A120988 A120989

Keyword

nonn,tabl

Author

Emeric Deutsch, Jul 21 2006

Status

approved