A121445 -id:A121445 - cp's OEIS frontend

A120988 Triangle read by rows: T(n,k) is the number of binary trees with n edges and such that the first leaf in the preorder traversal is at level k (1<=k<=n). A binary tree is a rooted tree in which each vertex has at most two children and each child of a vertex is designated as its left or right child.

2, 1, 4, 2, 4, 8, 5, 9, 12, 16, 14, 24, 30, 32, 32, 42, 70, 85, 88, 80, 64, 132, 216, 258, 264, 240, 192, 128, 429, 693, 819, 833, 760, 624, 448, 256, 1430, 2288, 2684, 2720, 2490, 2080, 1568, 1024, 512, 4862, 7722, 9009, 9108, 8361, 7068, 5488, 3840, 2304, 1024

Offset: 1

Emeric Deutsch, Jul 30 2006

Row sums are the Catalan numbers (A000108). T(n,1)=A000108(n-1) for n>=2 (the Catalan numbers). T(n,n)=2^n. Sum(k*T(n,k),k=1..n)=A120989(n).

			T(2,1)=1 because we have the tree /\.
Triangle starts:
2;
1;4;
2,4,8;
5,9,12,16;
14,24,30,32,32;

Cf. A000108, A120989, A121445.

Maple
```
T:=proc(n,k) if k
				
```

T(n,k)=Sum(j*binomial(k,j)*binomial(2n-2k+j,n-k)/(2n-2k+j), j=0..k). G.f.=1/[1-tz(1+C)], where C=[1-sqrt(1-4z)]/(2z) is the Catalan function.

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

Original entry on oeis.org

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

Emeric Deutsch, Jul 30 2006

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.

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

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.

Cf. A007226, A001764, A006013, A006632.

Column 1 of A121445.

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

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

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)

A121447 Level of the first leaf (in preorder traversal) of a ternary tree, summed over all ternary trees with n edges. 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.

Original entry on oeis.org

3, 21, 127, 747, 4386, 25897, 154077, 923910, 5581485, 33949836, 207787668, 1278900412, 7911394686, 49165322241, 306809507561, 1921849861260, 12079999018605, 76170034283805, 481680300300255, 3054157623774495

Offset: 1

Emeric Deutsch, Jul 30 2006

nonn

a(n) = Sum_{k=1..n} k*A121445(n,k).

			a(1)=3 because each of the trees /, | and \ contributes 1 to the sum.

Cf. A121445.

a:=n->3*n*(23*n^2+78*n+67)*binomial(3*n+2,n+2)/4/(n+3)/(2*n+1)/(2*n+3)/(2*n+5): seq(a(n),n=1..23);

a(n)=3n(23n^2+78n+67)binomial(3n+2,n+2)/[4(n+3)(2n+1)(2n+3)(2n+5)].
G.f.= (h-1-z)(h-1)/z^2, where h=1+zh^3=2sin(arcsin(sqrt(27z/4))/3)/sqrt(3z).
D-finite with recurrence -2*(2*n+5)*(n+3)*(1951*n-2094)*a(n) +(43553*n^3+142716*n^2+115045*n-10338)*a(n-1) +3*(2281*n+1723)*(3*n-1)*(3*n-2)*a(n-2)=0. - R. J. Mathar, Jul 24 2022

cp's OEIS Frontend

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A121447 Level of the first leaf (in preorder traversal) of a ternary tree, summed over all ternary trees with n edges. 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.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Formula