A003690 Number of spanning trees in K_3 X P_n.

3, 75, 1728, 39675, 910803, 20908800, 479991603, 11018898075, 252954664128, 5806938376875, 133306628004003, 3060245505715200, 70252340003445603, 1612743574573533675, 37022849875187828928, 849912803554746531675, 19510971631883982399603

Offset

1,1

Comments

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

References

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

Links

Vincenzo Librandi, Table of n, a(n) for n = 1..200

F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Preliminary version of paper that appeared in Ars Combin. 49 (1998), 129-154.

F. Faase, Counting Hamiltonian cycles in product graphs

F. Faase, Results from the counting program

P. Raff, Spanning Trees in Grid Graphs, arXiv:0809.2551 [math.CO], 2008. [From Paul Raff, Mar 06 2009]

P. Raff, Analysis of the Number of Spanning Trees of K_3 x P_n. Contains sequence, recurrence, generating function, and more. [From Paul Raff, Mar 06 2009] [broken link]

H. C. Williams and R. K. Guy, Some fourth-order linear divisibility sequences, Intl. J. Number Theory 7 (5) (2011) 1255-1277.

H. C. Williams and R. K. Guy, Some Monoapparitic Fourth Order Linear Divisibility Sequences, Integers, Volume 12A (2012) The John Selfridge Memorial Volume

Index entries for sequences related to trees

Index entries for linear recurrences with constant coefficients, signature (24,-24,1).

Formula

a(n) = (A090731(n)-2)/7.

a(n) = 24*a(n-1) - 24*a(n-2) + a(n-3), n>3.

G.f.: 3*x*(1+x)/((1-x)*(1-23*x+x^2)). - R. J. Mathar, Dec 16 2008

a(n) = 3*(A004254(n))^2. - R. K. Guy, seqfan list, Mar 28 2009, - R. J. Mathar, Jun 03 2009

From Peter Bala, Apr 27 2014: (Start)

Product {n >= 2} (1 - 3/a(n)) = 1/2 + sqrt(21)/10.

a(n) = (2/7)*( T(n,23/2) - 1), where T(n,x) is the Chebyshev polynomial of the first kind.

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].

a(n) = 3*U(n-1,5/2)^2, where U(n,x) is the Chebyshev polynomial of the second kind.

See the remarks in A100047 for the general connection between Chebyshev polynomials of the first kind and 4th-order linear divisibility sequences. (End)

a(n) = (-2+(2/(23+5*sqrt(21)))^n+(1/2*(23+5*sqrt(21)))^n)/7. - Colin Barker, Mar 06 2016

Mathematica

CoefficientList[Series[3 (1 + x)/((1 - x) (1 - 23 x + x^2)), {x, 0, 20}], x] (* Vincenzo Librandi, Apr 28 2014 *)

Prog

(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
(PARI) Vec(3*x*(1+x)/((1-x)*(1-23*x+x^2)) + O(x^25)) \\ Colin Barker, Mar 06 2016

Crossrefs

Cf. A100047, A173958 (column 3).

Sequence in context: A060869 A012491 A136328 * A230143 A228841 A361537

Adjacent sequences: A003687 A003688 A003689 * A003691 A003692 A003693

Keyword

nonn,easy

Author

Frans J. Faase

Status

approved