login
Number of independent vertex sets of the n X n torus grid graph.
21

%I #46 Jun 08 2023 06:03:56

%S 1,7,34,743,25531,2406862,464483559,213256442503,215560806324388,

%T 498819827260367617,2590618817013278596997,30496896080418683388380966,

%U 809724336154415150287031740151,48609694845429192825410114233405807,6589876632329358971395398453738256596574,2018670118781080042934952855192359574137313799

%N Number of independent vertex sets of the n X n torus grid graph.

%H Rintaro Matsuo, <a href="/A027683/b027683.txt">Table of n, a(n) for n = 1..32</a>

%H Vaclav Kotesovec, <a href="https://oeis.org/wiki/User:Vaclav_Kotesovec">Non-attacking chess pieces</a>, 6ed, 2013, p. 73, 405.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/IndependentVertexSet.html">Independent Vertex Set</a>

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

%t a[n_] := With[{sets = Select[Tuples[{0, 1}, n], Count[#*RotateLeft[#], 1] == 0 &]}, Tr[MatrixPower[Table[Boole[Count[s1*s2, 1] == 0], {s1, sets}, {s2, sets}], n]]];

%t Table[a[n], {n, 1, 10}] (* _Pjotr Buys_, Jun 07 2023 *)

%Y Cf. A006506 for flat version.

%Y Cf. A067960, A201626, A212270.

%K nonn,nice,hard

%O 1,2

%A _R. H. Hardin_

%E Terms a(14)-a(16) from _Vaclav Kotesovec_, Dec 02 2011