A121446 Number of ternary trees with n edges and such that the first leaf in the preorder traversal is at level 1.

3, 3, 10, 42, 198, 1001, 5304, 29070, 163438, 937365, 5462730, 32256120, 192565800, 1160346492, 7048030544, 43108428198, 265276342782, 1641229898525, 10202773534590, 63698396932170, 399223286267190, 2510857763851185, 15842014607109600, 100244747986099080

Offset

1,1

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.

Links

Table of n, a(n) for n=1..24.

Ira Gessel and Guoce Xin, The generating function of ternary trees and continued fractions, arXiv:math/0505217 [math.CO], 2005.

Ira Gessel and Guoce Xin, The generating function of ternary trees and continued fractions, Electronic Journal of Combinatorics, 13(1) (2006), #R53.

Formula

a(n) = A007226(n-1) for n >= 2.

a(1) = 3 and a(n) = (2/n)*binomial(3*n-3, n-1) for n >= 2.

G.f.: (h - 1 - z)/(h - 1), where h = 1 + z*h^3 = 2*sin(arcsin(sqrt(27*z/4))/3)/sqrt(3*z).

D-finite with recurrence 2*n*(2*n - 3)*a(n) - 3*(3*n - 4)*(3*n - 5)*a(n-1) = 0 for n >= 3. - R. J. Mathar, Jun 22 2016

G.f.: 1-(1-(4*sin(arcsin((3^(3/2)*sqrt(x))/2)/3)^2)/3)^3. - Vladimir Kruchinin, Oct 04 2022

Example

a(1) = 3 because we have the trees /, | and \.
a(2) = 3 because we have the trees /|, /\ and |\.

Maple

a:=proc(n) if n=1 then 3 else (2/n)*binomial(3*n-3, n-1) fi end: seq(a(n), n=1..25);

Mathematica

a[1] = 3; a[n_] := (2/n) Binomial[3 n - 3, n - 1];
Array[a, 22] (* Jean-François Alcover, Nov 28 2017 *)

Crossrefs

Cf. A007226.

Column 1 of A121445.

Sequence in context: A107299 A298899 A205388 * A302196 A340598 A258193

Adjacent sequences: A121443 A121444 A121445 * A121447 A121448 A121449

Keyword

nonn

Author

Emeric Deutsch, Jul 30 2006

Status

approved