A380761 Number of rooted ordered trees with n internal nodes where each node has out-degree 0, 2, or 6.

1, 2, 16, 192, 2720, 42224, 694848, 11907648, 210240256, 3797869056, 69859601920, 1304037291008, 24639504760832, 470342682171392, 9057003542405120, 175721074857734144, 3431733070223491072, 67407828276358119424, 1330851767254309142528, 26395675263287212834816

Offset: 0

Author

Ahmat Mahamat, Feb 02 2025

Keywords

• nonn
• easy

Comments

a(n) is the number of paths that start at (0,0), never go below the x-axis and end on the x-axis with n ascending steps, where ascending steps are (1,1) and (1,5) and descending steps are (1,-1).

Examples

			The a(0) = 1 tree with 0 internal nodes is simply a single leaf node.
The a(1) = 2 trees are those with 1 internal node and either 2 or 6 leaves.
		

Links

• Ahmat Mahamat, Github repo

Crossrefs

Cf. A001764 (number of complete ternary trees with n internal nodes).

Programs

Maple

a:= n-> if n = 0 then 1 else add(binomial(n, k) * binomial(2*n + 4*k, n + 4*k + 1), k=0..n)/n end if:
seq(a(n), n = 0..19);

Mathematica

a[n_] := If[n == 0, 1, Sum[Binomial[n, k] * Binomial[2 n + 4 k, n + 4 k + 1], {k, 0, n}]/n]

Python

import math
def a(n):
    return 1 if n == 0 else sum(math.comb(n, k) * math.comb(2 * n + 4 * k, n + 4 * k + 1) for k in range(n + 1)) // n
print([a(n) for n in range(20)])

Formula

G.f. satisfies: A(z) = 1 + z*A(z)^2 + z*A(z)^6.

a(n) = (1/n) * Sum_{k=0..n} binomial(n, k) * binomial(2*n + 4*k, n + 4*k + 1) for n >= 1.