A006235 Complexity of doubled cycle (regarding case n = 2 as a multigraph). (Formerly M4849)

1, 12, 75, 384, 1805, 8100, 35287, 150528, 632025, 2620860, 10759331, 43804800, 177105253, 711809364, 2846259375, 11330543616, 44929049777, 177540878700, 699402223099, 2747583822720, 10766828545725, 42095796462852, 164244726238343, 639620518118400

Offset

1,2

Comments

In plain English, a(n) is the number of spanning trees of the n-prism graph Y_n. - Eric W. Weisstein, Jul 15 2011

Also the number of spanning trees of the n-web graph. - Eric W. Weisstein, Jul 15 2011

Also the number of spanning trees of the n-dipyramidal graph. - Eric W. Weisstein, Jun 14 2018

Determinants of the spiral knots S(4,k,(1,-1,1)). a(k) = det(S(4,k,(1,-1,1))). These knots are also the weaving knots W(k,4) and the Turk's Head Links THK(4,k). - Ryan Stees, Dec 14 2014

References

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

T. D. Noe, Table of n, a(n) for n = 1..200

N. Brothers, S. Evans, L. Taalman, L. Van Wyk, D. Witczak, and C. Yarnall, Spiral knots, Missouri J. of Math. Sci., 22 (2010).

M. DeLong, M. Russell, and J. Schrock, Colorability and determinants of T(m,n,r,s) twisted torus knots for n equiv. +/-1(mod m), Involve, Vol. 8 (2015), No. 3, 361-384.

N. Dowdall, T. Mattman, K. Meek, and P. Solis, On the Harary-Kauffman conjecture and turk's head knots, arxiv 0811.0044 [math.GT], 2008.

A. A. Jagers, A note on the number of spanning trees in a prism graph, Int. J. Comput. Math., Vol. 24, 1988 (Issue 2), pp. 151-154.

Seong Ju Kim, R. Stees, L. Taalman, Sequences of Spiral Knot Determinants, Journal of Integer Sequences, Vol. 19 (2016), #16.1.4.

D. E. Knuth, Letter to N. J. A. Sloane, Oct. 1994

Germain Kreweras, Complexité et circuits Eulériens dans les sommes tensorielles de graphes, J. Combin. Theory, B 24 (1978), 202-212.

L. Oesper, p-Colorings of Weaving Knots, Undergraduate Thesis, Pomona College, 2005.

Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.

Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992

Ryan Stees, Sequences of Spiral Knot Determinants, Senior Honors Projects, Paper 84, James Madison Univ., May 2016.

Eric Weisstein's World of Mathematics, Dipyramidal Graph

Eric Weisstein's World of Mathematics, Prism Graph

Eric Weisstein's World of Mathematics, Spanning Tree

Eric Weisstein's World of Mathematics, Web Graph

Index entries for linear recurrences with constant coefficients, signature (10, -35, 52, -35, 10, -1).

Formula

a(n) = (1/2)*n*(-2 + (2 - sqrt(3))^n + (2 + Sqrt(3))^n) (Kreweras). - Eric W. Weisstein, Jul 15 2011

G.f.: x(1+2x-10x^2+2x^3+x^4)/((1-x)*(1-4x+x^2))^2.

a(n) = 10a(n-1)-35a(n-2)+52a(n-3)-35a(n-4)+10a(n-5)-a(n-6), n>5.

a(n) = (n/2)*A129743(n). - Woong Kook and Seung Kyoon Shin (andrewk(AT)math.uri.edu), Jan 13 2009

a(k) = det(S(4,k,(1,-1,1))) = k*b(k)^2, where b(1)=1, b(2)=sqrt(6), b(k)=sqrt(6)*b(k-1) - b(k-2) = b(2)*b(k-1) - b(k-2). - Ryan Stees, Dec 14 2014

a(n) = n*(A001075(n) - 1). - Eric W. Weisstein, Mar 30 2017

Example

For k=3, b(3)=sqrt(6)b(2)-b(1)=6-1=5, so det(S(4,3,(1,-1,1)))=3*5^2=75.

Maple

A006235:=(1+2*z-10*z**2+2*z**3+z**4)/(z-1)**2/(z**2-4*z+1)**2; # conjectured (correctly) by Simon Plouffe in his 1992 dissertation

Mathematica

LinearRecurrence[{10, -35, 52, -35, 10, -1}, {0, 1, 12, 75, 384, 1805}, 20]
Table[1/2 (-2 + (2 - Sqrt[3])^n + (2 + Sqrt[3])^n) n, {n, 0, 20}] // Expand
Table[n (ChebyshevT[n, 2] - 1), {n, 20}] (* Eric W. Weisstein, Mar 30 2017 *)

Prog

(PARI) a(n)=if(n<0, 0, polcoeff(x*(1+2*x-10*x^2+2*x^3+x^4)/((1-x)*(1-4*x+x^2))^2+x*O(x^n), n))

Crossrefs

Cf. A006237. Apart from a(2) coincides with A072373. A row or column of A173958.

Sequence in context: A292532 A053310 A368530 * A009642 A051104 A044199

Adjacent sequences: A006232 A006233 A006234 * A006236 A006237 A006238

Keyword

nonn

Author

N. J. A. Sloane

Extensions

More terms from Michael Somos, Jul 19 2002

Minor edits by N. J. A. Sloane, May 27 2012

Status

approved