A338110 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 vertices.

1, 128, 139968, 536870912, 5000000000000, 92442129447518208, 2988151979474457198592, 154742504910672534362390528, 12044329605471552321957641846784, 1342177280000000000000000000000000000, 206097683218942123873399068932507659403264, 42281678783395138381516145098915043145456549888

Offset

1,2

Comments

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

These graphs are cographs.

Links

Table of n, a(n) for n=1..12.

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*(2*n)^(3*(n - 1)).

a(n) = A193131(n)/3.

Example

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

Mathematica

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

Crossrefs

Cf. A011655, A193131, A204437, A338104.

Sequence in context: A330486 A016795 A222054 * A283926 A016831 A103348

Adjacent sequences: A338107 A338108 A338109 * A338111 A338112 A338113

Keyword

nonn

Author

Rigoberto Florez, Oct 10 2020

Status

approved