

A108808


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


5



4, 74, 1434, 27780, 538150, 10424872, 201947094, 3912050356, 75782907270, 1468040672696, 28438383992230, 550898690444420, 10671821831261942, 206730898391393192, 4004720564629102582, 77578083032366404308, 1502816206487087179878, 29112043791259796460440
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


REFERENCES

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: AddisonWesley, pp. 147148, 1990. [Background]


LINKS

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


FORMULA

From Brian Kell, Oct 20 2008: (Start)
a(n) = z * M^(n1) * 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*(x2)*(x^36*x^2+4*x1) / (4*x^56*x^491*x^3+75*x^223*x+1).  Colin Barker, May 14 2013


MAPLE

z:= <111111>: 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


CROSSREFS

Cf. A078469, A110476, A221157 (Grid graph G_{4,n}).
Sequence in context: A232371 A114878 A131359 * A139112 A100865 A007157
Adjacent sequences: A108805 A108806 A108807 * A108809 A108810 A108811


KEYWORD

nonn,easy


AUTHOR

N. J. A. Sloane, Jul 09 2005


EXTENSIONS

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


STATUS

approved



