A003769 - OEIS

%I #23 Jan 01 2019 06:31:05

%S 3,16,75,361,1728,8281,39675,190096,910803,4363921,20908800,100180081,

%T 479991603,2299777936,11018898075,52794712441,252954664128,

%U 1211978608201,5806938376875,27822713276176,133306628004003,638710426743841,3060245505715200

%N Number of perfect matchings (or domino tilings) in K_4 X P_n.

%D F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129-154.

%H Colin Barker, <a href="/A003769/b003769.txt">Table of n, a(n) for n = 1..1000</a>

%H F. Faase, <a href="http://www.iwriteiam.nl/Cpaper.zip">On the number of specific spanning subgraphs of the graphs G X P_n</a>, Preliminary version of paper that appeared in Ars Combin. 49 (1998), 129-154.

%H F. Faase, <a href="http://www.iwriteiam.nl/counting.html">Counting Hamiltonian cycles in product graphs</a>

%H F. Faase, <a href="http://www.iwriteiam.nl/Cresults.html">Results from the counting program</a>

%H <a href="/index/Do#domino">Index entries for sequences related to dominoes</a>

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (4,4,-1).

%F a(n) = 4a(n-1) + 4a(n-2) - a(n-3), n>3.

%F a(n) = (1/7)*(6*A030221(n) - A054477(n) + 2(-1)^n).

%F G.f.: x*(3+4*x-x^2)/((1+x)*(1-5*x+x^2)). - _R. J. Mathar_, Dec 16 2008

%F a(n) = 2^(-1-n)*((-1)^n*2^(2+n) + (5-sqrt(21))^(1+n) + (5+sqrt(21))^(1+n)) / 7. - _Colin Barker_, Dec 16 2017

%o (PARI) Vec(x*(3 + 4*x - x^2) / ((1 + x)*(1 - 5*x + x^2)) + O(x^40)) \\ _Colin Barker_, Dec 16 2017

%Y Essentially the same as A005386. First differences of A099025.

%K nonn,easy

%O 1,1

%A _Frans J. Faase_