A338104 Number of spanning trees in the join of the disjoint union of two complete graphs each on n vertices with the empty graph on n+1 vertices.

1, 4, 1200, 2074464, 10883911680, 128615328600000, 2881502756476710912, 109416128865750000000000, 6508595325997684722663161856, 572150341080161420030586961966080, 71062412455566037275496151040000000000

Offset

0,2

Comments

Equivalently, the graph can be described as the graph on 3*n + 1 vertices with labels 0..3*n and with i and j adjacent iff A011655(i + j) = 1.

These graphs are cographs.

Links

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

H-Y. Ching, R. Florez, and A. Mukherjee, Families of Integral Cographs within a Triangular Arrays, arXiv:2009.02770 [math.CO], 2020.

Eric Weisstein's World of Mathematics, Spanning Tree

Formula

a(n) = (n + 1)*(2*n)^n*(2*n + 1)^(2*(n - 1)).

Example

The adjacency matrix of the graph associated with n = 2 is: (compare A204437)
  [0, 1, 1, 0, 1, 1, 0]
  [1, 0, 0, 1, 1, 0, 1]
  [1, 0, 0, 1, 0, 1, 1]
  [0, 1, 1, 0, 1, 1, 0]
  [1, 1, 0, 1, 0, 0, 1]
  [1, 0, 1, 1, 0, 0, 1]
  [0, 1, 1, 0, 1, 1, 0]
a(2) = 1200 because the graph has 1200 spanning trees.

Mathematica

Table[(n + 1)*(2 n)^n*(2 n + 1)^(2 (n - 1)), {n, 1, 10}]

Crossrefs

Cf. A011655, A204437, A338109.

Sequence in context: A357512 A309979 A221383 * A198899 A350341 A253168

Adjacent sequences: A338101 A338102 A338103 * A338105 A338106 A338107

Keyword

nonn

Author

Rigoberto Florez, Oct 10 2020

Status

approved