|
%I #49 Mar 21 2023 12:52:09
%S 3,75,1728,39675,910803,20908800,479991603,11018898075,252954664128,
%T 5806938376875,133306628004003,3060245505715200,70252340003445603,
%U 1612743574573533675,37022849875187828928,849912803554746531675,19510971631883982399603
%N Number of spanning trees in K_3 X P_n.
%C Column 3 of A173958. The sequence a(n)/3 is linear divisibility sequence of the fourth order; it is the case P1 = 25, P2 = 46, Q = 1 of the three parameter family of divisibility sequences found by Williams and Guy. - _Peter Bala_, Apr 27 2014
%D F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129-154.
%H Vincenzo Librandi, <a href="/A003690/b003690.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="http://arxiv.org/abs/0809.2551">Spanning Trees in Grid Graphs</a>, arXiv:0809.2551 [math.CO], 2008. [From _Paul Raff_, Mar 06 2009]
%H 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 K_3 x P_n</a>. Contains sequence, recurrence, generating function, and more. [From _Paul Raff_, Mar 06 2009] [broken link]
%H H. C. Williams and R. K. Guy, <a href="http://dx.doi.org/10.1142/S1793042111004587">Some fourth-order linear divisibility sequences</a>, Intl. J. Number Theory 7 (5) (2011) 1255-1277.
%H H. C. Williams and R. K. Guy, <a href="http://www.emis.de/journals/INTEGERS/papers/a17self/a17self.Abstract.html">Some Monoapparitic Fourth Order Linear Divisibility Sequences</a>, Integers, Volume 12A (2012) The John Selfridge Memorial Volume
%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (24,-24,1).
%F a(n) = (A090731(n)-2)/7.
%F a(n) = 24*a(n-1) - 24*a(n-2) + a(n-3), n>3.
%F G.f.: 3*x*(1+x)/((1-x)*(1-23*x+x^2)). - _R. J. Mathar_, Dec 16 2008
%F a(n) = 3*(A004254(n))^2. - _R. K. Guy_, seqfan list, Mar 28 2009, - _R. J. Mathar_, Jun 03 2009
%F From _Peter Bala_, Apr 27 2014: (Start)
%F Product {n >= 2} (1 - 3/a(n)) = 1/2 + sqrt(21)/10.
%F a(n) = (2/7)*( T(n,23/2) - 1), where T(n,x) is the Chebyshev polynomial of the first kind.
%F a(n) = 3 * the bottom left entry of the 2 X 2 matrix T(n,M), where M is the 2 X 2 matrix [0, -23/2; 1, 25/2].
%F a(n) = 3*U(n-1,5/2)^2, where U(n,x) is the Chebyshev polynomial of the second kind.
%F See the remarks in A100047 for the general connection between Chebyshev polynomials of the first kind and 4th-order linear divisibility sequences. (End)
%F a(n) = (-2+(2/(23+5*sqrt(21)))^n+(1/2*(23+5*sqrt(21)))^n)/7. - _Colin Barker_, Mar 06 2016
%t CoefficientList[Series[3 (1 + x)/((1 - x) (1 - 23 x + x^2)), {x, 0, 20}], x] (* _Vincenzo Librandi_, Apr 28 2014 *)
%o (Magma) I:=[3,75,1728]; [n le 3 select I[n] else 24*Self(n-1)-24*Self(n-2)+Self(n-3): n in [1..30]]; // _Vincenzo Librandi_, Apr 28 2014
%o (PARI) Vec(3*x*(1+x)/((1-x)*(1-23*x+x^2)) + O(x^25)) \\ _Colin Barker_, Mar 06 2016
%Y Cf. A100047, A173958 (column 3).
%K nonn,easy
%O 1,1
%A _Frans J. Faase_
| 