A182041 Number of independent sets of nodes in C_5 X C_n (n >= 1).

11, 1, 81, 391, 3561, 25531, 199821, 1511931, 11589281, 88389661, 675443291, 5157630831, 39394699881, 300868345701, 2297915763861, 17550293888221, 134040955378561, 1023739686467981, 7818833928607761, 59716490127924211, 456085875187977011, 3483364700645591901

Offset: 0

Author

Cesar Bautista, Apr 07 2012

Keywords

• nonn
• easy

References

• M. Golin, Y. C. Leung, Y. J. Wang and X. R. Yong, Counting structures in grid-graphs, cylinders and tori using transfer matrices: Survey and new results. In: Demetrescu, C., Sedgewick, R., Tamassia, R., (eds.) The Proceedings of the Second Workshop on Analytic Algorithmics and Combinatorics (ANALCO05), SIAM, Philadelphia, (2005), 250-258.

Links

• Cesar Bautista, Table of n, a(n) for n = 0..399
• C. Bautista-Ramos and C. Guillen-Galvan, Fibonacci numbers of generalized Zykov sums, J. Integer Seq., 15 (2012), #12.7.8.
• Eric Weisstein's World of Mathematics, Independent Vertex Set
• Eric Weisstein's World of Mathematics, Torus Grid Graph
• Index entries for linear recurrences with constant coefficients, signature (4,27,10,-30,-7,8,-1).

Programs

Mathematica

LinearRecurrence[{4,27,10,-30,-7,8,-1},{11,1,81,391,3561,25531,199821},30] (* Harvey P. Dale, Mar 06 2013 *)

Formula

a(n)=4*a(n-1)+27*a(n-2)+10*a(n-3)-30*a(n-4)-7*a(n-5)+8*a(n-6)-a(n-7) with a(0)=11, a(1)=1, a[2]=81, a(3)=391, a(4)=3561, a(5)=25531, a(6)=199821.

G.f.: (-11*x^6+27*x^5+130*x^4-70*x^3-220*x^2-43*x+11)/((x^3-5*x^2-7*x+1)*(x^4-3*x^3-x^2+3*x+1)).