A110476 -id:A110476 - cp's OEIS frontend

A108808 Number of compositions of grid graph G_{3,n} = P_3 X P_n.

4, 74, 1434, 27780, 538150, 10424872, 201947094, 3912050356, 75782907270, 1468040672696, 28438383992230, 550898690444420, 10671821831261942, 206730898391393192, 4004720564629102582, 77578083032366404308, 1502816206487087179878, 29112043791259796460440

Offset: 1

N. J. A. Sloane, Jul 09 2005

Reddy, V. and Skiena, S. "Frequencies of Large Distances in Integer Lattices." Technical Report, Department of Computer Science. Stony Brook, NY: State University of New York, Stony Brook, 1989. [Background]
Skiena, S. "Grid Graphs." Section 4.2.4 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 147-148, 1990. [Background]

Robert Israel, Table of n, a(n) for n = 1..769
J. N. Ridley and M. E. Mays, Compositions of unions of graphs, Fib. Quart. 42 (2004), 222-230.
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, Table 6.12. - From _N. J. A. Sloane_, Jan 04 2013
Eric Weisstein's World of Mathematics, Grid Graph. [Background]
Index entries for linear recurrences with constant coefficients, signature (23,-75,91,6,-4).

Cf. A078469, A110476, A221157 (Grid graph G_{4,n}).

z:= <1|1|1|1|1|1>: w:= <1,1,0,1,0,1>:
M:= Matrix([[ 2, 3, 3, 3, 4, 5 ],
[ 3, 4, 5, 5, 6, 6 ],
[ 1, 0, 2, 0, 0, 0 ],
[ 3, 5, 5, 4, 6, 6 ],
[ 2, 1, 4, 1, 2, 0 ],
[ 2, 5, 2, 5, 6, 8 ]]):
seq(z . M^i . w, i=0..31); # Robert Israel, Dec 03 2015

From Brian Kell, Oct 20 2008: (Start)
a(n) = z * M^(n-1) * w,
where
z is the 1 x 6 row vector [ 1 ... 1 ],
M is the 6 x 6 matrix
[[ 2, 3, 3, 3, 4, 5 ],
[ 3, 4, 5, 5, 6, 6 ],
[ 1, 0, 2, 0, 0, 0 ],
[ 3, 5, 5, 4, 6, 6 ],
[ 2, 1, 4, 1, 2, 0 ],
[ 2, 5, 2, 5, 6, 8 ]],
and w is the 6 x 1 column vector
[[ 1 ],
[ 1 ],
[ 0 ],
[ 1 ],
[ 0 ],
[ 1 ]] (End)
G.f.: 2*x*(x-2)*(x^3-6*x^2+4*x-1) / (4*x^5-6*x^4-91*x^3+75*x^2-23*x+1). - Colin Barker, May 14 2013

a(4) corrected and a(5)-a(7) computed by Brian Kell, May 20 2008
a(8) - a(11) from Brian Kell, Oct 20 2008
a(12)-a(18) added from Frank Simon's thesis by N. J. A. Sloane, Jan 04 2013

A078469 Number of different compositions of the ladder graph L_n.

Original entry on oeis.org

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

A145835 Number of compositions of the n X n grid graph.

Original entry on oeis.org

1, 12, 1434, 1691690, 19719299768, 2271230282824746, 2584855762327078145444, 29068227444022728740767607050, 3230042572278849047360048508956727420, 3546545075986984198328715750838554116235343894

Offset: 1

Brian Kell, Oct 21 2008

The number of compositions of the n X n grid graph is the number of partitions of an n X n square into regions of orthogonally connected unit squares.

			For n=2 the a(2)=12 partitions of a 2x2 square are: 1 partition into a single 2x2 region; 4 partitions into a 3-square 'L' shape and an isolated corner; 2 partitions into 2 1x2 bricks; 4 partitions into a 1x2 brick and 2 isolated squares; and 1 partition into 4 isolated squares.

A. Knopfmacher and M. E. Mays, Graph compositions I: Basic enumeration, Integers, 1 (2001), #A4.
J. N. Ridley and M. E. Mays, Compositions of unions of graphs, Fib. Quart., 42 (2004), 222-230.
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

Cf. A110476.

Terms for n=7,8,9 from Frank Simon, Oct 25 2011

a(10) from Frank Simon's thesis added by N. J. A. Sloane, Jan 04 2013

cp's OEIS Frontend

A108808 Number of compositions of grid graph G_{3,n} = P_3 X P_n.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Formula

Extensions

A078469 Number of different compositions of the ladder graph L_n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

Formula

Extensions

A145835 Number of compositions of the n X n grid graph.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions