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
KEYWORD
nonn,tabl
AUTHOR
Emeric Deutsch, Jul 21 2006
STATUS
approved