A221157 -id:A221157 - 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

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

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