A344638 Number of compositions of graph K_4 X P_n.

15, 1548, 168386, 18328142, 1994963186, 217145777610, 23635668646510, 2572671863723654, 280027640317060130, 30480171391948784938, 3317675523140039250350, 361119061152982241895174, 39306730094143339494849314, 4278420047285488959291378858, 465693230069569504343096792622

Offset

1,1

Links

Table of n, a(n) for n=1..15.

Liam Buttitta, On the Number of Compositions of Km X Pn, Journal of Integer Sequences, Vol. 25 (2022), Article 22.4.1.

J. N. Ridley and M. E. Mays, Compositions of unions of graphs, Fib. Quart. 42 (2004), 222-230.

Formula

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.

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).

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

[[16, 12, 12, 12, 12, 12, 12, 9, 9, 9, 8, 8, 8, 8, 5],

[12, 8, 10, 10, 9, 10, 10, 6, 8, 8, 6, 6, 7, 7, 4],

[12, 10, 8, 9, 10, 10, 10, 8, 6, 8, 6, 7, 6, 7, 4],

[12, 10, 9, 8, 10, 10, 10, 8, 6, 8, 7, 6, 7, 6, 4],

[12, 9, 10, 10, 8, 10, 10, 6, 8, 8, 7, 7, 6, 6, 4],

[12, 10, 10, 10, 10, 8, 9, 8, 8, 6, 7, 6, 6, 7, 4],

[12, 10, 10, 10, 10, 9, 8, 8, 8, 6, 6, 7, 7, 6, 4],

[ 9, 6, 8, 8, 6, 8, 8, 4, 7, 7, 5, 5, 5, 5, 3],

[ 9, 8, 6, 6, 8, 8, 8, 7, 4, 7, 5, 5, 5, 5, 3],

[ 9, 8, 8, 8, 8, 6, 6, 7, 7, 4, 5, 5, 5, 5, 3],

[ 8, 6, 6, 7, 7, 7, 6, 5, 5, 5, 4, 5, 5, 5, 3],

[ 8, 6, 7, 6, 7, 6, 7, 5, 5, 5, 5, 4, 5, 5, 3],

[ 8, 7, 6, 7, 6, 6, 7, 5, 5, 5, 5, 5, 4, 5, 3],

[ 8, 7, 7, 6, 6, 7, 6, 5, 5, 5, 5, 5, 5, 4, 3],

[ 5, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 2]].

Example

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:
   aa  aa aa ba ab   bb ab ab  aa ba cb ac   ab ba   ab
   aa  ab ba aa aa   aa ab ba  bc ca aa ab   ca ac   cd

Mathematica

M = {{16, 12, 12, 12, 12, 12, 12, 9, 9, 9, 8, 8, 8, 8, 5},
{12, 8, 10, 10, 9, 10, 10, 6, 8, 8, 6, 6, 7, 7, 4},
{12, 10, 8, 9, 10, 10, 10, 8, 6, 8, 6, 7, 6, 7, 4},
{12, 10, 9, 8, 10, 10, 10, 8, 6, 8, 7, 6, 7, 6, 4},
{12, 9, 10, 10, 8, 10, 10, 6, 8, 8, 7, 7, 6, 6, 4},
{12, 10, 10, 10, 10, 8, 9, 8, 8, 6, 7, 6, 6, 7, 4},
{12, 10, 10, 10, 10, 9, 8, 8, 8, 6, 6, 7, 7, 6, 4},
{9, 6, 8, 8, 6, 8, 8, 4, 7, 7, 5, 5, 5, 5, 3},
{9, 8, 6, 6, 8, 8, 8, 7, 4, 7, 5, 5, 5, 5, 3},
{9, 8, 8, 8, 8, 6, 6, 7, 7, 4, 5, 5, 5, 5, 3},
{8, 6, 6, 7, 7, 7, 6, 5, 5, 5, 4, 5, 5, 5, 3},
{8, 6, 7, 6, 7, 6, 7, 5, 5, 5, 5, 4, 5, 5, 3},
{8, 7, 6, 7, 6, 6, 7, 5, 5, 5, 5, 5, 4, 5, 3},
{8, 7, 7, 6, 6, 7, 6, 5, 5, 5, 5, 5, 5, 4, 3},
{5, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 2}};
w = Table[1, {15}]; Join[{15}, Table[Transpose[w] . MatrixPower[M, n, w], {n, 1, 40}]]

Crossrefs

Cf. A108808, A346273, A000110.

Sequence in context: A122469 A119784 A199228 * A209681 A209682 A209683

Adjacent sequences: A344635 A344636 A344637 * A344639 A344640 A344641

Keyword

nonn,easy

Author

Liam Buttitta and Greg Dresden, Jul 15 2021

Status

approved