login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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), 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 Hamilton 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 A249938

Adjacent sequences:  A003687 A003688 A003689 * A003691 A003692 A003693

KEYWORD

nonn,easy

AUTHOR

Frans J. Faase

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified November 21 16:27 EST 2017. Contains 295003 sequences.