A390491 Array of Fibonacci polynomial linear combinations read by antidiagonals: T(m,r) = F_m(r) + 2*F_{m-1}(r) + F_{m-2}(r) where F_k(r) is the k-th Fibonacci polynomial evaluated at r (m >= 2, r >= 1).

3, 3, 5, 3, 6, 8, 3, 7, 12, 13, 3, 8, 16, 24, 21, 3, 9, 20, 37, 48, 34, 3, 10, 24, 52, 85, 96, 55, 3, 11, 28, 69, 132, 196, 192, 89, 3, 12, 32, 88, 189, 340, 451, 384, 144, 3, 13, 36, 109, 256, 534, 868, 1039, 768, 233, 3, 14, 40, 132, 333, 784, 1479, 2228

Offset

2,1

Comments

Array T(m,r) with rows indexed by m >= 2 and columns indexed by r >= 1.

Antidiagonal n (for n >= 1) contains the terms T(2,n), T(3,n-1), T(4,n-2), ..., T(n+1,1) in that order.

F_k(r) denotes the k-th Fibonacci polynomial (A083856, row r), defined by the recurrence F_0(r) = 0, F_1(r) = 1, and F_{k+1}(r) = F_k(r) + r*F_{k-1}(r) for k >= 1.

These values are the building blocks for closed formulas of proper k-partitions of fan graphs Phi_n under the duo/bichromatic triangle constraint, where each triangle must use exactly two colors (forbidding both monochromatic and rainbow triangles).

For fan graph Phi_n with n vertices, the number of proper k-partitions is given by r_k(Phi_n) = Sum_{t=k-1..n-1} a(n-1,t) * S(t,k-1), where a(m,t) are coefficients from A129718 and S(t,k-1) denotes Stirling numbers of the second kind. This general formula yields explicit closed forms:

r_4(Phi_n) = (1/2)*(T(n-1,3) - 2*T(n-1,2) + T(n-1,1))

r_5(Phi_n) = (1/6)*(T(n-1,4) - 3*T(n-1,3) + 3*T(n-1,2) - T(n-1,1)).

Links

Table of n, a(n) for n=2..64.

Julian Allagan, Gabrielle Morgan, Shawn Langley, Rogelio Lopez-Bonilla, and Vladimir Deriglazov, Chromatic Feature Vectors for 2-Trees: Exact Formulas for Partition Enumeration with Network Applications, arXiv:2512.07120 [cs.DS], 2025. See p. 14.

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

Formula

T(m,r) = F_m(r) + 2*F_{m-1}(r) + F_{m-2}(r) where F_k(r) is the k-th Fibonacci polynomial evaluated at r.

F_k(r) satisfies the recurrence: F_0(r) = 0, F_1(r) = 1, F_{k+1}(r) = F_k(r) + r*F_{k-1}(r).

Column r=1: T(m,1) = F_{m+2}, the (m+2)-th Fibonacci number.

Column r=2: T(m,2) = 3*2^{m-2} for m >= 2.

Example

m\r   |  1    2    3    4    5    6    7     8     9    10   11   12   13   14   15
  ----+----------------------------------------------------------------------------
  2   |  3    3    3    3    3    3    3     3     3     3    3    3    3    3    3
  3   |  5    6    7    8    9   10   11    12    13    14   15   16   17   18   19
  4   |  8   12   16   20   24   28   32    36    40    44   48   52   56   60   64
  5   | 13   24   37   52   69   88  109   132   157   184  213  244  277  312  349
  6   | 21   48   85  132  189  256  333   420   517   624  741  868 1005 1152 1309
  7   | 34   96  196  340  534  784 1096  1476  1930  2464 3084 3796 4606 5520 6544
  8   | 55  192  451  868 1479 2320 3427  4836  6583  8704 ...
  9   | 89  384 1039 2228 4149 7024 11099 16644 23953 33344 ...
Application to fan graph proper 4-partitions: For the fan graph Phi_8 (8 vertices), we compute r_4(Phi_8), the number of ways to partition vertices into exactly 4 parts, where each triangle uses exactly two colors.
Using n=8, so m=n-1=7, the formula is: r_4(Phi_8) = (1/2)*(T(7,3) - 2*T(7,2) + T(7,1))
From the array: T(7,1) = 34, T(7,2) = 96, T(7,3) = 196; therefore r_4(Phi_8) = (1/2)*(196 - 2*96 + 34) = 19 proper 4-partitions.

Mathematica

Clear[FibPoly, T]
FibPoly[m_, r_] := Module[{F},
  F[0] = 0;
  F[1] = 1;
  F[k_] := F[k] = F[k - 1] + r * F[k - 2];
  F[m]
];
T[m_, r_] := FibPoly[m, r] + 2 * FibPoly[m - 1, r] + FibPoly[m - 2, r];
antidiagonalData = Flatten[Table[T[m, n + 2 - m], {n, 1, 15}, {m, 2, n + 1}]];
Print[Take[antidiagonalData, 55]];

Crossrefs

Column r=1: A000045 (Fibonacci numbers, specifically F_{m+2} for m >= 2).

Column r=2: A007283 (3*2^n, here 3*2^{m-2} for m >= 2).

Sequence in context: A015971 A163167 A243729 * A200810 A365710 A114003

Adjacent sequences: A390488 A390489 A390490 * A390492 A390493 A390494

Keyword

nonn,tabl

Author

Julian Allagan, Nov 07 2025

Status

approved