login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A346273 Number of compositions of graph C_3 X P_n. 1
5, 114, 2712, 64518, 1534872, 36514338, 868669752, 20665502358, 491628707832, 11695761476178, 278240131889112, 6619284357957798, 157471623931541592, 3746222552567209218, 89121983141955313272, 2120196482644091472438, 50439105667748418772152 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

LINKS

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

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

FORMULA

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

EXAMPLE

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

MAPLE

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

MATHEMATICA

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

CROSSREFS

Cf. A108808.

Sequence in context: A053712 A325914 A091026 * A216342 A207999 A223057

Adjacent sequences:  A346270 A346271 A346272 * A346274 A346275 A346276

KEYWORD

nonn,easy

AUTHOR

Liam Buttitta and Greg Dresden, Jul 12 2021

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 17 00:01 EDT 2022. Contains 356180 sequences. (Running on oeis4.)