cp's OEIS Frontend

A346273 Number of compositions of graph C_3 X P_n.

%I A346273 #23 Jan 05 2025 19:51:42
%S A346273 5,114,2712,64518,1534872,36514338,868669752,20665502358,491628707832,
%T A346273 11695761476178,278240131889112,6619284357957798,157471623931541592,
%U A346273 3746222552567209218,89121983141955313272,2120196482644091472438,50439105667748418772152
%N A346273 Number of compositions of graph C_3 X P_n.
%H A346273 Liam Buttitta, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL25/Buttitta/but3.html">On the Number of Compositions of Km X Pn</a>, Journal of Integer Sequences, Vol. 25 (2022), Article 22.4.1.
%H A346273 J. N. Ridley and M. E. Mays, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Papers1/42-3/Ridley-Mays-scanned.pdf">Compositions of unions of graphs</a>, Fib. Quart. 42 (2004), 222-230.
%H A346273 <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (24,-5).
%F A346273 a(n) = 24*a(n-1) - 5*a(n-2) for n >= 4.
%F A346273 G.f.: x*(5 - 6*x + x^2)/(1 - 24*x + 5*x^2).
%F A346273 For n>1, a(n) = z * M^(n-1) * z^T, where z is the 1 X 5 row vector [1,1,1,1,1], z^T is its transpose (a 5 X 1 column vector of 1's), and M is the 5 X 5 matrix
%F A346273    [[8, 6, 6, 6, 4],
%F A346273     [6, 4, 5, 5, 3],
%F A346273     [6, 5, 4, 5, 3],
%F A346273     [6, 5, 5, 4, 3],
%F A346273     [4, 3, 3, 3, 2]].
%e A346273 For n=1 the a(1)=5 solutions are given here, where the first picture has all three vertices in the same partition (called A), the next three pictures have two vertices in the partition A and one in the partition B, and the last picture has all three vertices in their own partitions.
%e A346273     A        A      B      A        A
%e A346273    / \      / \    / \    / \      / \
%e A346273   A___A    B___A  A___A  A___B    B___C
%p A346273 a:= n-> ceil((<<0|1>, <-5|24>>^n. <<6/25, 24/5>>)[1$2]):
%p A346273 seq(a(n), n=1..21);  # _Alois P. Heinz_, Jul 14 2021
%t A346273 M = {{8, 6, 6, 6, 4}, {6, 4, 5, 5, 3}, {6, 5, 4, 5, 3}, {6, 5, 5, 4,
%t A346273     3}, {4, 3, 3, 3, 2}}; w = {1, 1, 1, 1, 1}; Join[{5},Table[Transpose[w] . MatrixPower[M, n, w], {n, 1, 40}]]
%Y A346273 Cf. A108808.
%K A346273 nonn,easy
%O A346273 1,1
%A A346273 _Liam Buttitta_ and _Greg Dresden_, Jul 12 2021