A006237 -id:A006237 - cp's OEIS frontend

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

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

Offset: 1

N. J. A. Sloane

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

			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.

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

T. D. Noe, Table of n, a(n) for n = 1..200
Zbigniew R. Bogdanowicz, The number of spanning trees in a superprism, Discrete Math. Lett. 13 (2024) 66-73. See p. 66.
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, and 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).

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

Cf. A001075, A129743.

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

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 *)

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))

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+2*x-10*x^2+2*x^3+x^4)/((1-x)*(1-4*x+x^2))^2.
a(n) = 10*a(n-1)-35*a(n-2)+52*a(n-3)-35*a(n-4)+10*a(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
E.g.f.: exp(x)*x*(exp(x)*(2*cosh(sqrt(3)*x) + sqrt(3)*sinh(sqrt(3)*x)) - 1). - Stefano Spezia, May 05 2024

More terms from Michael Somos, Jul 19 2002

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

A372705 Number of connected spanning subgraphs of the n-dimensional hypercube graph.

Original entry on oeis.org

1, 1, 5, 1083, 1239326145

Offset: 0

Pontus von Brömssen, May 11 2024

a(n)/A061301(n) is the probability that the n-dimensional hypercube graph is still connected after each edge has been independently deleted with probability 1/2.

Cf. A006237, A061301, A290758, A359992, A373034, A373035.

A337083 Number of spanning trees of the 1-skeleton of the (n-1)-dimensional permutohedron.

Original entry on oeis.org

1, 1, 6, 101154816, 6187732257761496793412385090375984958331031826464768000000000

Offset: 1

Richard Stanley, Aug 14 2020

nonn

We have the factorizations:
a(4) = 2^15 * 3^2 * 7^3.
a(5) = 2^59 * 3^15 * 5^9 * 7^5 * 11^6 * 23^5 * 29^4 * 41^4.
a(6) = 2^215 * 3^178 * 5^47 * 7^15 * 11^39 * 13^10 * 19^16 * 23^15 * 29^16 * 41^16 * 61^5 * 67^9 * 71^5 * 1931^16 * 3253^9.

			For n=3 the permutohedron is a hexagon, which has six spanning trees.

Richard Stanley, Table of n, a(n) for n = 1..6
Eric Weisstein's World of Mathematics, Bruhat Graph
Wikipedia, Permutohedron

Cf. A006237.

import sympy,itertools
def A337083(n):
  p=tuple(itertools.permutations(range(n)))
  m=len(p)
  q={p[i]:i for i in range(m)}
  Q=sympy.diag(*[n-1]*m)
  for i in range(m):
    for k in range(n-1):
      Q[i,q[p[i][:k]+tuple(reversed(p[i][k:k+2]))+p[i][k+2:]]]=-1
  return Q[:m-1,:m-1].det() # Pontus von Brömssen, Jan 18 2021

a(1) prepended by Pontus von Brömssen, Jan 19 2021

A338832 Number of spanning trees in the k_1 X ... X k_j grid graph, where (k_1 - 1, ..., k_j - 1) is the partition with Heinz number n.

Original entry on oeis.org

1, 1, 1, 4, 1, 15, 1, 384, 192, 56, 1, 31500, 1, 209, 2415, 42467328, 1, 49766400, 1, 2558976, 30305, 780, 1, 3500658000000, 100352, 2911, 8193540096000, 207746836, 1, 76752081000, 1, 20776019874734407680, 380160, 10864, 4140081, 242716067758080000000, 1

Offset: 1

Pontus von Brömssen, Nov 11 2020

nonn

a(n) > 1 precisely when n is composite.

			The partition (2, 2, 1) has Heinz number 18 and the 3 X 3 X 2 grid graph has a(18) = 49766400 spanning trees.

Pontus von Brömssen, Table of n, a(n) for n = 1..1151
Germain Kreweras, Complexité et circuits Eulériens dans les sommes tensorielles de graphes, J. Combin. Theory B 24 (1978), 202-212.
Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Spanning Tree
Index entries for sequences related to trees

X n grid: A001353(n) = a(2*prime(n-1))
X n grid: A006238(n) = a(3*prime(n-1))
X n grid: A003696(n) = a(5*prime(n-1))
X n grid: A003779(n) = a(7*prime(n-1))
X n grid: A139400(n) = a(11*prime(n-1))
X n grid: A334002(n) = a(13*prime(n-1))
X n grid: A334003(n) = a(17*prime(n-1))
X n grid: A334004(n) = a(19*prime(n-1))
X n grid: A334005(n) = a(23*prime(n-1))
n X n grid: A007341(n) = a(prime(n-1)^2)
m X n grid: A116469(m,n) = a(prime(m-1)*prime(n-1))
X 2 X n grid: A003753(n) = a(4*prime(n-1))
X n X n grid: A067518(n) = a(2*prime(n-1)^2)
n X n X n grid: A071763(n) = a(prime(n-1)^3)
X ... X 2 grid: A006237(n) = a(2^n)

a(n) = Product_{n_1=0..k_1-1, ..., n_j=0..k_j-1; not all n_i=0} Sum_{i=1..j} (2*(1 - cos(n_i*Pi/k_i))) / Product_{i=1..j} k_i, where (k_1 - 1, ..., k_j - 1) is the partition with Heinz number n.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A372705 Number of connected spanning subgraphs of the n-dimensional hypercube graph.

Views

Author

Keywords

Comments

Crossrefs

A337083 Number of spanning trees of the 1-skeleton of the (n-1)-dimensional permutohedron.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Extensions

A338832 Number of spanning trees in the k_1 X ... X k_j grid graph, where (k_1 - 1, ..., k_j - 1) is the partition with Heinz number n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula