A338109 a(n)/A002939(n+1) is the Kirchhoff index of the join of the disjoint union of two complete graphs on n vertices with the empty graph on n+1 vertices.

1, 60, 289, 796, 1689, 3076, 5065, 7764, 11281, 15724, 21201, 27820, 35689, 44916, 55609, 67876, 81825, 97564, 115201, 134844, 156601, 180580, 206889, 235636, 266929, 300876, 337585, 377164, 419721, 465364, 514201, 566340, 621889, 680956, 743649, 810076, 880345

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.

The initial term a(0) = 1 has been included to agree with the formula. For the graph, it should be 0.

Links

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

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, Kirchhoff Index

Index entries for linear recurrences with constant coefficients, signature (4,-6,4,-1).

Formula

a(n) = 1 + 10*n + 31*n^2 + 18*n^3.

From Stefano Spezia, Oct 10 2020: (Start)

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

a(n) = 4*a(n-1) - 6*a(n-2) + 4*a(n-3) - a(n-4) for n >= 4. (End)

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) = 289 because the Kirchhoff index of the graph is 289/30 = 289/A002939(3).
The first few Kirchhoff indices (n >= 1) as reduced fractions are 5, 289/30, 199/14, 563/30, 769/33, 5065/182, 647/20, 11281/306, 3931/95, 7067/154, 6955/138, 35689/650.

Mathematica

Table[1+10n+31n^2+18n^3, {n, 30}]

Prog

(PARI) a(n)=1+10*n+31*n^2+18*n^3 \\ Charles R Greathouse IV, Oct 18 2022

Crossrefs

Cf. A002939, A011655, A204437, A338104.

Sequence in context: A246230 A100148 A100151 * A179811 A268805 A146750

Adjacent sequences: A338106 A338107 A338108 * A338110 A338111 A338112

Keyword

nonn,easy

Author

Rigoberto Florez, Oct 10 2020

Status

approved