The OEIS is supported by the many generous donors to the OEIS Foundation.
%I #22 Jan 05 2025 19:51:42
%S 15,1548,168386,18328142,1994963186,217145777610,23635668646510,
%T 2572671863723654,280027640317060130,30480171391948784938,
%U 3317675523140039250350,361119061152982241895174,39306730094143339494849314,4278420047285488959291378858,465693230069569504343096792622
%N Number of compositions of graph K_4 X P_n.
%H 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 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.
%F a(n) = 112*a(n-1) - 346*a(n-2) + 306*a(n-3) - 57*a(n-4) + 2*a(n-5) for n >= 6.
%F G.f.: (-15 + 132*x - 200*x^2 + 72*x^3 - 5*x^4)/(-1 + 112*x - 346*x^2 + 306*x^3 - 57*x^4 + 2*x^5).
%F For n>1, a(n) = z * M^(n-1) * z^T, where z is the 1 X 15 row vector [1,1,1,...,1], z^T is its transpose (a 15 X 1 column vector of 1's), and M is the 15 X 15 matrix
%F [[16, 12, 12, 12, 12, 12, 12, 9, 9, 9, 8, 8, 8, 8, 5],
%F [12, 8, 10, 10, 9, 10, 10, 6, 8, 8, 6, 6, 7, 7, 4],
%F [12, 10, 8, 9, 10, 10, 10, 8, 6, 8, 6, 7, 6, 7, 4],
%F [12, 10, 9, 8, 10, 10, 10, 8, 6, 8, 7, 6, 7, 6, 4],
%F [12, 9, 10, 10, 8, 10, 10, 6, 8, 8, 7, 7, 6, 6, 4],
%F [12, 10, 10, 10, 10, 8, 9, 8, 8, 6, 7, 6, 6, 7, 4],
%F [12, 10, 10, 10, 10, 9, 8, 8, 8, 6, 6, 7, 7, 6, 4],
%F [ 9, 6, 8, 8, 6, 8, 8, 4, 7, 7, 5, 5, 5, 5, 3],
%F [ 9, 8, 6, 6, 8, 8, 8, 7, 4, 7, 5, 5, 5, 5, 3],
%F [ 9, 8, 8, 8, 8, 6, 6, 7, 7, 4, 5, 5, 5, 5, 3],
%F [ 8, 6, 6, 7, 7, 7, 6, 5, 5, 5, 4, 5, 5, 5, 3],
%F [ 8, 6, 7, 6, 7, 6, 7, 5, 5, 5, 5, 4, 5, 5, 3],
%F [ 8, 7, 6, 7, 6, 6, 7, 5, 5, 5, 5, 5, 4, 5, 3],
%F [ 8, 7, 7, 6, 6, 7, 6, 5, 5, 5, 5, 5, 5, 4, 3],
%F [ 5, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 2]].
%e Here are the a(1) = 15 compositions of the graph K_4 x P_1 = K_4, where the first block represents all four vertices of K_4 in the same partition (called "a"), the second block shows three vertices in partition "a" and the fourth vertex in its own partition (called "b"), and so on, up to the last block which shows all four vertices each in its own partition:
%e aa aa aa ba ab bb ab ab aa ba cb ac ab ba ab
%e aa ab ba aa aa aa ab ba bc ca aa ab ca ac cd
%t M = {{16, 12, 12, 12, 12, 12, 12, 9, 9, 9, 8, 8, 8, 8, 5},
%t {12, 8, 10, 10, 9, 10, 10, 6, 8, 8, 6, 6, 7, 7, 4},
%t {12, 10, 8, 9, 10, 10, 10, 8, 6, 8, 6, 7, 6, 7, 4},
%t {12, 10, 9, 8, 10, 10, 10, 8, 6, 8, 7, 6, 7, 6, 4},
%t {12, 9, 10, 10, 8, 10, 10, 6, 8, 8, 7, 7, 6, 6, 4},
%t {12, 10, 10, 10, 10, 8, 9, 8, 8, 6, 7, 6, 6, 7, 4},
%t {12, 10, 10, 10, 10, 9, 8, 8, 8, 6, 6, 7, 7, 6, 4},
%t {9, 6, 8, 8, 6, 8, 8, 4, 7, 7, 5, 5, 5, 5, 3},
%t {9, 8, 6, 6, 8, 8, 8, 7, 4, 7, 5, 5, 5, 5, 3},
%t {9, 8, 8, 8, 8, 6, 6, 7, 7, 4, 5, 5, 5, 5, 3},
%t {8, 6, 6, 7, 7, 7, 6, 5, 5, 5, 4, 5, 5, 5, 3},
%t {8, 6, 7, 6, 7, 6, 7, 5, 5, 5, 5, 4, 5, 5, 3},
%t {8, 7, 6, 7, 6, 6, 7, 5, 5, 5, 5, 5, 4, 5, 3},
%t {8, 7, 7, 6, 6, 7, 6, 5, 5, 5, 5, 5, 5, 4, 3},
%t {5, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 2}};
%t w = Table[1, {15}]; Join[{15}, Table[Transpose[w] . MatrixPower[M, n, w], {n, 1, 40}]]
%Y Cf. A108808, A346273, A000110.
%K nonn,easy
%O 1,1
%A _Liam Buttitta_ and _Greg Dresden_, Jul 15 2021