A394153 G.f. A(x) satisfies (1-x)*A(x)^4+(5x-2)*A(x)^3+(1-5x)*A(x)^2+x^2*A(x)-x^2=0.

0, 1, 3, 15, 89, 579, 3995, 28721, 212847, 1614635, 12477185, 97877095, 777397703, 6239433601, 50526305419, 412314344295, 3387257518809, 27991418870939, 232523406281683, 1940567787973745, 16263132449945319, 136809398137470355, 1154813296781074241

Offset

0,3

Comments

Number of n-vertex planar rooted trees with vertices colored red, blue, and green with red root where red vertices can be followed by vertices of any colors, blue vertices can be followed red or green vertices, and green vertices can only be followed by blue vertices.

Links

Nathan Fox, Table of n, a(n) for n = 0..300

S. Dimitrov, N. Fox, K. Hadaway, A. Tharp, and S. Wagner, Counting Colored Trees, arXiv:2602.16055 [math.CO], 2026.

Robert Israel, Linear recurrence of order 15

Formula

D-finite with a recurrence of order 15 (see link). - Robert Israel, Jun 04 2026

Prog

(Python)
def A394153(n):
    A = [[1, 1, 1], [1, 0, 1], [0, 1, 0]]
    if n == 0:
        return 0
    m = len(A)
    output = [[1] for i in range(m)]
    for l in range(2, n + 1):
        for i in range(m):
            term = 0
            for k in range(1, l):
                for j in range(m):
                    term += A[i][j] * output[i][k - 1] * output[j][l - k - 1]
            output[i].append(term)
    return output[0][n - 1]

Crossrefs

Cf. A394154, A394155.

Sequence in context: A231257 A074541 A394141 * A368974 A394131 A074550

Adjacent sequences: A394150 A394151 A394152 * A394154 A394155 A394156

Keyword

nonn

Author

Nathan Fox, Mar 12 2026

Status

approved