login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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+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.

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 A217204

Adjacent sequences:  A120983 A120984 A120985 * A120987 A120988 A120989

KEYWORD

nonn,tabl

AUTHOR

Emeric Deutsch, Jul 21 2006

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 2 19:18 EST 2021. Contains 341756 sequences. (Running on oeis4.)