A390130 - OEIS

A390130

Number of 4-partitions of the fan graph F_{1,n} where every triangle uses exactly 2 parts.

1, 5, 19, 61, 180, 500, 1335, 3459, 8767, 21839, 53674, 130492, 314493, 752537, 1790139, 4237593, 9990280, 23471780, 54986827, 128501527, 299678439, 697644539, 1621649262, 3764596716, 8729693569, 20223978269, 46814365891, 108289428757, 250339614588, 578423423444

(list; graph; refs; listen; history; text; internal format)

OFFSET

6,2

COMMENTS

A partition is an unlabeled vertex coloring into indistinguishable color classes (parts). A k-partition is valid if it satisfies the duo-triangle constraint: every triangle must use exactly 2 parts. This forbids both monochromatic triangles (all three vertices in the same part) and rainbow triangles (all three vertices in different parts).

The fan graph Phi_n = F_{1,n} is the join K_1 + P_n; i.e., one "apex" vertex adjacent to all vertices of a path of length n.

This sequence counts the number of ways to partition the vertices into exactly 4 nonempty parts satisfying the duo-triangle constraint.

LINKS

Table of n, a(n) for n=6..35.

Julian Allagan and Vitaly Voloshin, Coloring k-trees with forbidden monochrome and rainbow triangles, Australas. J. Combin. 65(2) (2016), 137-151.

Eric Weisstein's World of Mathematics, Fan Graph.

FORMULA

a(n) = (1/2)(A_{n-1,3} - 2A_{n-1,2} + A_{n-1,1}) where A_{m,r} = F_m(r) + 2F_{m-1}(r) + F_{m-2}(r), and F_m(r) is the m-th Fibonacci polynomial evaluated at r, defined by F_0(r)=0, F_1(r)=1, F_{m+1}(r) = F_m(r) + r*F_{m-1}(r).

Using known sequences: A_{m,1} = F_{m+2} (A000045 shifted), A_{m,2} = 3*2^m (A007283).

For n>=6, a(n) = (1404*(703*sqrt(5)-1225) * (1-sqrt(5))^n + 2808*(221*sqrt(5)-40) * (sqrt(5)+1)^n + 5*(229*sqrt(5)-261) * ((182-46*sqrt(13)) * (1-sqrt(13))^n - 1053*4^n + 2*(23*sqrt(13)+91) * (sqrt(13)+1)^n)) / (1755*(229*sqrt(5)-261) * 2^(n+3)). - Vaclav Kotesovec, Nov 10 2025

EXAMPLE

For n < 6, a(n) = 0 since a 4-partition requires at least 6 vertices under the duo-triangle constraint.

For n=6, we have m=5. Computing A_{5,1} = F_7 = 13, A_{5,2} = 32^5 = 96, A_{5,3} = 37. Then a(6) = (1/2)(37 - 224 + 13) = (1/2)(2) = 1.

For n=7, a(7) = 5 valid 4-partitions exist.

For n=8, a(8) = 19 valid 4-partitions exist.

MATHEMATICA

FibPoly[m_, r_] := Module[{F}, F[0] = 0; F[1] = 1;

F[k_] := F[k] = F[k-1] + r*F[k-2]; F[m]];

A[m_, r_] := FibPoly[m, r] + 2*FibPoly[m-1, r] + FibPoly[m-2, r];

Table[(1/2)(A[n-1, 3] - 2*A[n-1, 2] + A[n-1, 1]), {n, 6, 35}]

CROSSREFS

Cf. A083856 (Fibonacci polynomials F_m(r), the building blocks of this formula), A000045, A001045, A006130, A007283 (3*2^m, equals A_{m,2}).