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

%I #41 Feb 26 2021 02:12:47

%S 4,74,1434,27780,538150,10424872,201947094,3912050356,75782907270,

%T 1468040672696,28438383992230,550898690444420,10671821831261942,

%U 206730898391393192,4004720564629102582,77578083032366404308,1502816206487087179878,29112043791259796460440

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

%D 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]

%D 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]

%H Robert Israel, <a href="/A108808/b108808.txt">Table of n, a(n) for n = 1..769</a>

%H J. N. Ridley and M. E. Mays, <a href="https://www.fq.math.ca/Papers1/42-3/Ridley-Mays-scanned.pdf">Compositions of unions of graphs</a>, Fib. Quart. 42 (2004), 222-230.

%H Frank Simon, <a href="https://nbn-resolving.org/urn:nbn:de:bsz:14-qucosa-101154">Algebraic Methods for Computing the Reliability of Networks</a>, 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

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/GridGraph.html">Grid Graph</a>. [Background]

%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (23,-75,91,6,-4).

%F From _Brian Kell_, Oct 20 2008: (Start)

%F a(n) = z * M^(n-1) * w,

%F where

%F z is the 1 x 6 row vector [ 1 ... 1 ],

%F M is the 6 x 6 matrix

%F [[ 2, 3, 3, 3, 4, 5 ],

%F [ 3, 4, 5, 5, 6, 6 ],

%F [ 1, 0, 2, 0, 0, 0 ],

%F [ 3, 5, 5, 4, 6, 6 ],

%F [ 2, 1, 4, 1, 2, 0 ],

%F [ 2, 5, 2, 5, 6, 8 ]],

%F and w is the 6 x 1 column vector

%F [[ 1 ],

%F [ 1 ],

%F [ 0 ],

%F [ 1 ],

%F [ 0 ],

%F [ 1 ]] (End)

%F 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

%p z:= <1|1|1|1|1|1>: w:= <1,1,0,1,0,1>:

%p M:= Matrix([[ 2, 3, 3, 3, 4, 5 ],

%p [ 3, 4, 5, 5, 6, 6 ],

%p [ 1, 0, 2, 0, 0, 0 ],

%p [ 3, 5, 5, 4, 6, 6 ],

%p [ 2, 1, 4, 1, 2, 0 ],

%p [ 2, 5, 2, 5, 6, 8 ]]):

%p seq(z . M^i . w, i=0..31); # _Robert Israel_, Dec 03 2015

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

%K nonn,easy

%O 1,1

%A _N. J. A. Sloane_, Jul 09 2005

%E a(4) corrected and a(5)-a(7) computed by _Brian Kell_, May 20 2008

%E a(8) - a(11) from _Brian Kell_, Oct 20 2008

%E a(12)-a(18) added from Frank Simon's thesis by _N. J. A. Sloane_, Jan 04 2013