

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


4



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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



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+1k 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 kDyck 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.
ChaoJen Wang, Applications of the GouldenJackson 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),nk).
T(n,0) = A000108(n+1) (the Catalan numbers).
T(n,k) = A108767(n+1,n+1k).
Sum_{k>=1} k*T(n,k) = binomial(3*n+2,n1) = 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), nk)/(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), nk]/(n+1);
Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* JeanFrançois Alcover, Jul 06 2018 *)


PROG

(PARI) T(n, k) = binomial(n+1, k)*binomial(2*(n+1), nk)/(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 A217204
Adjacent sequences: A120983 A120984 A120985 * A120987 A120988 A120989


KEYWORD

nonn,tabl


AUTHOR

Emeric Deutsch, Jul 21 2006


STATUS

approved



