|
Search: id:A102081
|
|
|
| A102081 |
|
Number of perfect matchings in the C_n X P_2 graph (C_n is the cycle graph on n vertices and P_2 is the path graph on 2 vertices). |
|
+0
5
|
|
| 5, 4, 9, 11, 20, 29, 49, 76, 125, 199, 324, 521, 845, 1364, 2209, 3571, 5780, 9349, 15129, 24476, 39605, 64079, 103684, 167761, 271445, 439204, 710649, 1149851, 1860500, 3010349, 4870849, 7881196, 12752045, 20633239, 33385284, 54018521
(list; graph; listen)
|
|
|
OFFSET
|
2,1
|
|
|
COMMENT
|
a(n)=A102079(n,n).
Apart from initial term, identical to A068397. - Creighton Dement (creighton.k.dement(AT)uni-oldenburg.de), Jun 03 2006
|
|
REFERENCES
|
H. Hosoya and A. Motoyama, An effective algorithm for obtaining polynomials for dimer statistics. Application of operator technique on the topological index to two- and three-dimensional rectangular and torus lattices, J. Math. Physics 26 (1985) 157-167 (eq. (21) and Table IV).
|
|
FORMULA
|
G.f.=z^2*(5-z-5z^2-z^3)/[(1+z)(1-2z+z^3)]. a(n)=a(n-1)+2a(n-2)-a(n-3)-a(n-4) for n >= 6.
|
|
EXAMPLE
|
Example: a(3)=4 because in the graph with vertex set {A,B,C,A',B',C'} and edge set {AB,AC,BC, A'B',A'C',B'C',AA',BB',CC'} we have the following perfect matchings: {AA',BC,B'C'},{BB',AC,A'C'}, {CC',AB,A'B'}} and {AA',BB',CC'}.
|
|
MAPLE
|
a[2]:=5: a[3]:=4: a[4]:=9: a[5]:=11: for n from 6 to 45 do a[n]:=a[n-1]+2*a[n-2]-a[n-3]-a[n-4] od:seq(a[n], n=2..40);
|
|
CROSSREFS
|
Cf. A102079.
Sequence in context: A057763 A054508 A110617 this_sequence A068397 A022344 A046588
Adjacent sequences: A102078 A102079 A102080 this_sequence A102082 A102083 A102084
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Emeric Deutsch (deutsch(AT)duke.poly.eduandgessel(AT)brandeis.edu), Dec 29 2004
|
|
|
Search completed in 0.002 seconds
|
