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

0, 1, 3, 16, 103, 732, 5534, 43654, 355219, 2959796, 25127182, 216566228, 1889981702, 16667677502, 148309034228, 1329840823598, 12004376548231, 109001991366916, 994928157018222, 9123606773971816, 84014017887712710, 776551886860725700, 7202290010661477580

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 by red or blue vertices, and green vertices can be followed by red or green 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.

Prog

(Python)
def A394135(n):
    A = [[1, 1, 1], [1, 1, 0], [1, 0, 1]]
    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

Sequence in context: A394156 A394149 A341320 * A394152 A365752 A207434

Adjacent sequences: A394132 A394133 A394134 * A394136 A394137 A394138

Keyword

nonn

Author

Nathan Fox, Mar 11 2026

Status

approved