|
%I #38 Jun 25 2023 20:12:48
%S 1,54,2240,89964,3596725,143700480,5740732439,229334969304,
%T 9161621922880,365994298083150,14620972301965259,584087869159280640,
%U 23333512405041243469,932141942728566562746,37237797134599264280000,1487599121840339002010544,59427552583207598523644161
%N Number of spanning trees in S_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 Alois P. Heinz, <a href="/A003755/b003755.txt">Table of n, a(n) for n = 1..200</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 P. Raff, <a href="https://arxiv.org/abs/0809.2551">Spanning Trees in Grid Graphs</a>. arXiv:0809.2551 [math.CO], 2008.
%H P. Raff, <a href="http://www.math.rutgers.edu/~praff/span/4/12-13-14/index.xml">Analysis of the Number of Spanning Trees of S_4 x P_n</a>. Contains sequence, recurrence, generating function, and more.
%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%H <a href="/index/Rec#order_06">Index entries for linear recurrences with constant coefficients</a>, signature (48, -336, 582, -336, 48, -1).
%F a(1) = 1,
%F a(2) = 54,
%F a(3) = 2240,
%F a(4) = 89964,
%F a(5) = 3596725,
%F a(6) = 143700480 and
%F a(n) = 48a(n-1) - 336a(n-2) + 582a(n-3) - 336a(n-4) + 48a(n-5) - a(n-6).
%F G.f.: x*(x^4+6*x^3-16*x^2+6*x+1)/ ((x^2-6*x+1)*(x^4-42*x^3+83*x^2-42*x+1)). - _Paul Raff_, Mar 06 2009
%F a(n) = A001109(n)*A049684(n). [R. Guy, seqfan list, Mar 28 2009] - _R. J. Mathar_, Jun 03 2009
%p a:= n-> (Matrix([[1, 0, -1, -54, -2240, -89964]]). Matrix(6, (i,j)-> if (i=j-1) then 1 elif j=1 then [48,-336,582,-336,48,-1][i] else 0 fi)^(n-1))[1,1]: seq(a(n), n=1..14); # _Alois P. Heinz_, Aug 01 2008
%t LinearRecurrence[{48, -336, 582, -336, 48, -1}, {1, 54, 2240, 89964, 3596725, 143700480}, 17] (* _Jean-François Alcover_, Aug 06 2018 *)
%K nonn
%O 1,2
%A _Frans J. Faase_
%E Added recurrence from Faase's web page. - _N. J. A. Sloane_, Feb 03 2009
|
