login
Number of perfect matchings in the graph C_10 X C_n.
6

%I #20 Feb 22 2021 10:34:28

%S 5054,537636,2540032,114557000,1034315998,33898728836,400448833106,

%T 11203604497408,152849502772958,3876306765700644,58099728840105682,

%U 1375359477482867528,22057225099289357824,496348449090698237956,8370856315868909044082,181385918483215101487880

%N Number of perfect matchings in the graph C_10 X C_n.

%C For even values of m the order of recurrence relation for the number of perfect matchings in C_m X C_n graph does not exceed (3^delta(m/2) + 2*(3/5)^(1 - delta(m/2)))*5^floor(m/4) + 1. Here delta(k) equals 1 for odd values of k and 0 otherwise. If m=10 the above estimate gives 126 for the order of recurrence relation while the exact value equals 118.

%H Seiichi Manyama, <a href="/A281679/b281679.txt">Table of n, a(n) for n = 3..500</a>

%H S. N. Perepechko, <a href="http://www.jip.ru/2016/333-361-2016.pdf"> The number of perfect matchings on C_m X C_n graphs</a>, (in Russian), Information Processes, 2016, V. 16, No. 4, pp. 333-361.

%H Sergey Perepechko, <a href="/A281679/a281679.pdf">Generating function</a>, in Maple notation.

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

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

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PerfectMatching.html">Perfect Matching</a>

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

%Y Row n=5 of A341741.

%Y Cf. A220864, A230033, A231087, A231485, A232804, A253678, A281583.

%K nonn

%O 3,1

%A _Sergey Perepechko_, Jan 26 2017