login
This site is supported by donations to The OEIS Foundation.

 

Logo

The October issue of the Notices of the Amer. Math. Soc. has an article about the OEIS.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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: Addison-Wesley, pp. 147-148, 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), 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).

FORMULA

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

MAPLE

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

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

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 22 20:30 EDT 2018. Contains 315270 sequences. (Running on oeis4.)