Liam Buttitta - cp's OEIS frontend

User: Liam Buttitta

Liam Buttitta has authored 2 sequences.

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

Liam Buttitta and Greg Dresden, Jul 15 2021

			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

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.

Cf. A108808, A346273, A000110.

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}]]

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

A346273 Number of compositions of graph C_3 X P_n.

Original entry on oeis.org

5, 114, 2712, 64518, 1534872, 36514338, 868669752, 20665502358, 491628707832, 11695761476178, 278240131889112, 6619284357957798, 157471623931541592, 3746222552567209218, 89121983141955313272, 2120196482644091472438, 50439105667748418772152

Offset: 1

Liam Buttitta and Greg Dresden, Jul 12 2021

			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.
    A        A      B      A        A
   / \      / \    / \    / \      / \
  A___A    B___A  A___A  A___B    B___C

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.
Index entries for linear recurrences with constant coefficients, signature (24,-5).

Cf. A108808.

a:= n-> ceil((<<0|1>, <-5|24>>^n. <<6/25, 24/5>>)[1$2]):
seq(a(n), n=1..21);  # Alois P. Heinz, Jul 14 2021

M = {{8, 6, 6, 6, 4}, {6, 4, 5, 5, 3}, {6, 5, 4, 5, 3}, {6, 5, 5, 4,
    3}, {4, 3, 3, 3, 2}}; w = {1, 1, 1, 1, 1}; Join[{5},Table[Transpose[w] . MatrixPower[M, n, w], {n, 1, 40}]]

a(n) = 24*a(n-1) - 5*a(n-2) for n >= 4.
G.f.: x*(5 - 6*x + x^2)/(1 - 24*x + 5*x^2).
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
   [[8, 6, 6, 6, 4],
    [6, 4, 5, 5, 3],
    [6, 5, 4, 5, 3],
    [6, 5, 5, 4, 3],
    [4, 3, 3, 3, 2]].

cp's OEIS Frontend

User: Liam Buttitta

A344638 Number of compositions of graph K_4 X P_n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula