cp's OEIS Frontend

A003696 Number of spanning trees in P_4 X P_n.

%I A003696 #63 Mar 03 2024 10:06:09
%S A003696 1,56,2415,100352,4140081,170537640,7022359583,289143013376,
%T A003696 11905151192865,490179860527896,20182531537581071,830989874753525760,
%U A003696 34214941811800329425,1408756312731277540744
%N A003696 Number of spanning trees in P_4 X P_n.
%C A003696 Also number of domino tilings of the 7 X (2n-1) rectangle with upper left corner removed. - _Alois P. Heinz_, Apr 14 2011
%C A003696 A linear divisibility sequence of order 8; a(n) divides a(m) whenever n divides m. It is the product of a 2nd-order Lucas sequence and a 4th-order linear divisibility sequence. - _Peter Bala_, Apr 27 2014
%D A003696 F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129-154.
%H A003696 T. D. Noe, <a href="/A003696/b003696.txt">Table of n, a(n) for n = 1..200</a>
%H A003696 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 A003696 F. Faase, <a href="http://www.iwriteiam.nl/counting.html">Counting Hamiltonian cycles in product graphs</a>
%H A003696 F. Faase, <a href="http://www.iwriteiam.nl/Cresults.html">Results from the counting program</a>
%H A003696 P. Raff, <a href="http://arxiv.org/abs/0809.2551">Spanning Trees in Grid Graphs</a>, arXiv:0809.2551 [math.CO], 2008.
%H A003696 P. Raff, <a href="http://www.math.rutgers.edu/~praff/span/3/12-13-23/index.xml">Analysis of the Number of Spanning Trees of P_4 x P_n</a>. Contains sequence, recurrence, generating function, and more.
%H A003696 Roettger, E. L.; Williams, H. C.; Guy, R. K., <a href="https://doi.org/10.1007/978-1-4614-6642-0_15">Some extensions of the Lucas functions</a>, Springer Proceedings in Mathematics & Statistics 43, 271-311 (2013), chapter 5.
%H A003696 <a href="/index/Di#divseq">Index to divisibility sequences</a>
%H A003696 <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%H A003696 <a href="/index/Rec#order_08">Index entries for linear recurrences with constant coefficients</a>, signature (56, -672, 2632, -4094, 2632, -672, 56, -1).
%F A003696 a(1) = 1,
%F A003696 a(2) = 56,
%F A003696 a(3) = 2415,
%F A003696 a(4) = 100352,
%F A003696 a(5) = 4140081,
%F A003696 a(6) = 170537640,
%F A003696 a(7) = 7022359583,
%F A003696 a(8) = 289143013376 and
%F A003696 a(n) = 56a(n-1) - 672a(n-2) + 2632a(n-3) - 4094a(n-4) + 2632a(n-5) - 672a(n-6) + 56a(n-7) - a(n-8).
%F A003696 G.f.: x(x^6-49x^4+112x^3-49x^2+1) / (x^8-56x^7 +672x^6-2632x^5 +4094x^4 -2632x^3 +672x^2-56x+1). - _Paul Raff_, Mar 06 2009
%F A003696 From _Peter Bala_, Apr 27 2014: (Start)
%F A003696 a(n) = Resultant( U(3,(x-4)/2),U(n-1,x/2) ), where U(n,x) denotes the Chebyshev polynomial of the second kind. The polynomial U(3,(x-4)/2) = x^3 - 12*x^2 + 46*x - 56 (see A159764) has zeros z_1 = 4, z_2 = 4 + sqrt(2) and z_3 = 4 - sqrt(2). Hence a(n) = U(n-1,2)*U(n-1,1/2*(4 + sqrt(2)))*U(n-1,1/2*(4 - sqrt(2))).
%F A003696 a(n) = A001353(n)*A161158(n-1). (End)
%F A003696 a(n) = (9/3968)*(A028469(n+3)-A028469(n-4)) - (497/3968)*(A028469(n+2)-A028469(n-3)) + (5687/3968)*(A028469(n+1)-A028469(n-2)) - (19983/3968)*(A028469(n)-A028469(n-1)), n>3. - _Sergey Perepechko_, May 02 2016
%F A003696 a(n) = -a(-n) for all n in Z. - _Michael Somos_, Oct 31 2022
%p A003696 seq(resultant(simplify(ChebyshevU(3, (x-4)*(1/2))), simplify(ChebyshevU(n-1, (1/2)*x)), x), n = 1 .. 14); # _Peter Bala_, Apr 27 2014
%t A003696 LinearRecurrence[{56, -672, 2632, -4094, 2632, -672, 56, -1}, {1, 56, 2415, 100352, 4140081, 170537640, 7022359583, 289143013376}, 20] (* _Jean-François Alcover_, Feb 28 2020 *)
%o A003696 (PARI) {a(n) = polresultant((x-4)*(x^2-8*x+14), polchebyshev(n-1, 2, x/2))}; /* _Michael Somos_, Oct 31 2022 */
%Y A003696 A row of A116469. - _N. J. A. Sloane_, May 27 2012
%Y A003696 Bisection of A189004. - _Alois P. Heinz_, Sep 20 2012
%Y A003696 A001353, A161158, A159764.
%K A003696 nonn,easy
%O A003696 1,2
%A A003696 _Frans J. Faase_
%E A003696 Added recurrence from Faase's web page. - _N. J. A. Sloane_, Feb 03 2009