

A003690


Number of spanning trees in K_3 X P_n.


8



3, 75, 1728, 39675, 910803, 20908800, 479991603, 11018898075, 252954664128, 5806938376875, 133306628004003, 3060245505715200, 70252340003445603, 1612743574573533675, 37022849875187828928, 849912803554746531675, 19510971631883982399603
(list;
graph;
refs;
listen;
history;
text;
internal format)



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), 129154.


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), 129154.
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 fourthorder linear divisibility sequences, Intl. J. Number Theory 7 (5) (2011) 12551277.
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(n1)  24*a(n2) + a(n3), n>3.
G.f.: 3*x*(1+x)/((1x)*(123*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(n1,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 4thorder 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(n1)24*Self(n2)+Self(n3): n in [1..30]]; // Vincenzo Librandi, Apr 28 2014
(PARI) Vec(3*x*(1+x)/((1x)*(123*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 A249938
Adjacent sequences: A003687 A003688 A003689 * A003691 A003692 A003693


KEYWORD

nonn,easy


AUTHOR

Frans J. Faase


STATUS

approved



