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

Author

Emeric Deutsch, Jul 30 2006

Keywords

• nonn
• easy

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.

Examples

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

Links

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

Crossrefs

Cf. A007226, A001764, A006013, A006632.

Column 1 of A121445.

Programs

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

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

From Peter Bala, Jul 24 2025: (Start)

The g.f. A(x) = 3*x + 3*x^2 + 10*x^3 + ... satisfies the algebraic equation A(x)^3 - (3*x + 2)*A(x)^2 + (3*x^2 + 6*x + 1)*A(x) - (x^3 + 3*x^2 + 3*x) = 0.

1 + x/(1 - A(x)) = 1 + x + 3*x^2 + 12*x^3 + 55*x^4 + ... is the g.f. of A001764.

The g.f. A(x) satisfies (and is uniquely determined by) the conditions [x^n] (A(x) - 1)^n = 3 for n >= 1. (End)