A006237 Number of spanning trees of n-cube. (Formerly M3725)

1, 1, 4, 384, 42467328, 20776019874734407680, 1657509127047778993870601546036901052416000000, 153850844349814660487100539994381178281567942393055761257560677644718869248475136000000000000000000000

Offset

0,3

Comments

Kreweras calls this the complexity of the tensor sum of n 1-edge graphs.

References

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

R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Example 5.6.10.

Links

Alois P. Heinz, Table of n, a(n) for n = 0..10

Aaron R. Bagheri, Classifying the Jacobian Groups of Adinkras, (2017), HMC Senior Theses.

Frank Harary, John P. Hayes, and Horng-Jyh Wu, A survey of the theory of hypercube graphs, Comput. Math. Appl., 15(4) (1988), 277-289.

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. See p. 210, Parag. 4.

Eric Weisstein's World of Mathematics, Hypercube Graph

Eric Weisstein's World of Mathematics, Spanning Tree

Index entries for sequences related to trees

Formula

a(n) = 2^(2^n-1-n)*1^binomial(n, 1)*2^binomial(n, 2)*...*n^binomial(n, n).

Mathematica

Table[2^(2^n - 1 - n) Product[k^Binomial[n, k], {k, n}], {n, 0, 10}]

Prog

(PARI) a(n)=2^(2^n-n-1)*prod(k=1, n, k^binomial(n, k))

Crossrefs

Cf. A006235, A193130.

Sequence in context: A279525 A003753 A193130 * A181044 A339449 A116031

Adjacent sequences: A006234 A006235 A006236 * A006238 A006239 A006240

Keyword

nonn,easy,nice

Author

N. J. A. Sloane, Don Knuth

Extensions

Description expanded July 1995

Name edited by Andrei Zabolotskii, May 11 2026

Status

approved