A108808 -id:A108808 - cp's OEIS frontend

A131359 Erroneous version of A108808.

4, 74, 1434, 27080

Offset: 1

dead

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

A078469 Number of different compositions of the ladder graph L_n.

1, 2, 12, 74, 456, 2810, 17316, 106706, 657552, 4052018, 24969660, 153869978, 948189528, 5843007146, 36006232404, 221880401570, 1367288641824, 8425612252514, 51920962156908, 319951385193962, 1971629273320680

Offset: 0

Ralf Stephan, Jan 02 2003

This is equally the number of partitions of a 2 x n rectangle into connected pieces consisting of unit squares cut along lattice lines, like a 2-d analog of a partition into integers. - Hugo van der Sanden, Mar 23 2009

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Liam Buttitta, On the Number of Compositions of Km X Pn, Journal of Integer Sequences, Vol. 25 (2022), Article 22.4.1.
Tomislav Došlić and Luka Podrug, Sweet division problems: from chocolate bars to honeycomb strips and back, arXiv:2304.12121 [math.CO], 2023.
Tanya Khovanova, Recursive Sequences
A. Knopfmacher and M. E. Mays, Graph Compositions. I: Basic Enumeration, Integers 1(2001), #A04.
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 (6,1).

Cf. A108808, A110476. - Brian Kell, Oct 21 2008

Cf. A152113, A152124.

I:=[1, 2, 12]; [n le 3 select I[n] else 6*Self(n-1)+Self(n-2): n in [1..30]]; // Vincenzo Librandi, May 17 2013

Join[{1},LinearRecurrence[{6,1},{2,12},30]] (* Harvey P. Dale, Jul 22 2013 *)

a(n) = 6*a(n-1) + a(n-2).
G.f.: 1 + 2*x/(1 - 6*x - x^2).
a(n) = ((3 + s)^n - (3 - s)^n)/s, where s = sqrt(10) (assumes a(0) = 0).
Asymptotic to (3 + sqrt(10))^n/sqrt(10). - Ralf Stephan, Jan 03 2003
Let p[i] = Fibonacci(3*i) and A be the Hessenberg matrix of order n defined by: A[i,j] = p[j-i+1], if i <= j; A[i,j] = -1, if i = j + 1; and A[i,j] = 0, otherwise. Then, for n >= 1, a(n) = det(A). - Milan Janjic, May 08 2010
a(n) = 2*A005668(n), n > 0. - R. J. Mathar, Nov 29 2015
a(n) >= A116694(2,n). - R. J. Mathar, Nov 29 2015

a(0) changed from 0 to 1 by N. J. A. Sloane, Sep 21 2009, at the suggestion of Hugo van der Sanden

A110476 Table of number of partitions of an m X n rectangle, read by descending antidiagonals.

Original entry on oeis.org

1, 2, 2, 4, 12, 4, 8, 74, 74, 8, 16, 456, 1434, 456, 16, 32, 2810, 27780, 27780, 2810, 32, 64, 17316, 538150, 1691690, 538150, 17316, 64, 128, 106706, 10424872, 103015508, 103015508, 10424872, 106706, 128, 256, 657552, 201947094, 6273056950

Offset: 1

Hugo van der Sanden, Sep 08 2005

We count the partitions of the rectangle into regions of orthogonally connected unit squares. a(2, 2) = 12 comprising one partition of the 2 X 2 region; 4 partitions into a 3-square 'L' shape and an isolated corner; 2 partitions into two 1 X 2 bricks; 4 partitions into a 1 X 2 brick and two isolated squares; and 1 partition into four isolated squares.

			Array A(m,n) (with rows m >= 1 and columns n >= 1) begins
    1,      2,        4,         8,        16,       32,     64, 128, ...
    2,     12,       74,       456,      2810,    17316, 106706, ...
    4,     74,     1434,     27780,    538150, 10424872, ...
    8,    456,    27780,   1691690, 103015508, ...
   16,   2810,   538150, 103015508, ...
   32,  17316, 10424872, ...
   64, 106706, ...
  128, ...
  ...

Walter Trump, Table of n, a(n) for n = 1..220 (first 40 terms from Hugo van der Sanden).
Brian Kell, Values for m+n < 16 [except (7,7), (7,8) and (8,7)]
A. Knopfmacher and M. E. Mays, Graph compositions I: Basic enumeration, Integers, 1 (2001), 1-11. [From _Brian Kell_, Oct 21 2008]
Yulka Lipkova, Miso Forisek, Tom Zathurecky, and Davidko Pal, Delicious cake. [From _Brian Kell_, Oct 21 2008]
J. N. Ridley and M. E. Mays, Compositions of unions of graphs, Fib. Quart., 42 (2004), 222-230. [From _Brian Kell_, Oct 21 2008]
Frank Simon, Algebraic Methods for Computing the Reliability of Networks, Dissertation, Doctor Rerum Naturalium (Dr. rer. nat.), Fakultät Mathematik und Naturwissenschaften der Technischen Universität Dresden, 2012. - From _N. J. A. Sloane_, Jan 04 2013
F. Simon, P. Tittmann and M. Trinks, Counting Connected Set Partitions of Graphs, Electron. J. Combin., 18(1) (2010), #P14, 12pp.

Cf. A000041, A000079, A078469, A221157.

Cf. A108808, A145835. - Brian Kell, Oct 21 2008

a(m,n) = a(n,m).
a(1,n) = 2^(n-1) = a(n,1).
a(2,n) = A078469(n) = a(n,2).
From Petros Hadjicostas, Feb 27 2021: (Start)
The following two equations seem to follow from the work of Brian Kell and Frank Simon:
a(3,n) = A108808(n) = a(n,3).
a(4,n) = A221157(n) = a(n,4). (End)

Corrected by Chuck Carroll (chuck(AT)chuckcarroll.org), Jun 06 2006

Name edited by Michel Marcus, Jul 02 2020

A221157 Number of compositions of the grid graph G_{4,n}.

Original entry on oeis.org

8, 456, 27780, 1691690, 103015508, 6273056950, 381992581548, 23261112447444, 1416465537909008, 86254456382365422, 5252391281433321840, 319839870650458477666, 19476375116903366115612, 1185997189541765630381252, 72220283556802506132778356, 4397792341346509099717980618, 267799799794395524429805470412, 16307439552264147863293668460374

Offset: 1

N. J. A. Sloane, Jan 04 2013

nonn

Frank Simon, Algebraic Methods for Computing the Reliability of Networks, Dissertation, Doctor Rerum Naturalium (Dr. rer. nat.), Fakultät Mathematik und Naturwissenschaften der Technischen Universität Dresden, 2012.

Cf. A108808, A145835.

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

A344638 Number of compositions of graph K_4 X P_n.

Original entry on oeis.org

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

cp's OEIS Frontend

A131359 Erroneous version of A108808.

Views

Author

Keywords

References

A078469 Number of different compositions of the ladder graph L_n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

Formula

Extensions

A110476 Table of number of partitions of an m X n rectangle, read by descending antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A221157 Number of compositions of the grid graph G_{4,n}.

Views

Author

Keywords

Links

Crossrefs

A346273 Number of compositions of graph C_3 X P_n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A344638 Number of compositions of graph K_4 X P_n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula