A002985 Number of trees in an n-node wheel.

1, 1, 1, 2, 3, 6, 11, 20, 36, 64, 108, 179, 292, 464, 727, 1124, 1714, 2585, 3866, 5724, 8418, 12290, 17830, 25713, 36898, 52664, 74837, 105873, 149178, 209364, 292793, 407990, 566668, 784521, 1082848, 1490197, 2045093, 2798895, 3820629, 5202085

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn

Comments

This is the number of nonequivalent spanning trees of the n-wheel graph up to isomorphism of the trees.

Examples

			All trees that span a wheel on 5 nodes are equivalent to one of the following:
      o         o         o
      |         | \     /   \
   o--o--o   o--o  o   o--o  o
      |         |           /
      o         o         o
		

References

• F. Harary, P. E. O'Neil, R. C. Read and A. J. Schwenk, The number of trees in a wheel, in D. J. A. Welsh and D. R. Woodall, editors, Combinatorics. Institute of Mathematics and Its Applications. Southend-on-Sea, England, 1972, pp. 155-163.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..200
• Andrew Howroyd, Derivation of formula.
• Eric Weisstein's World of Mathematics, Wheel Graph.
• Index entries for sequences related to trees

Crossrefs

Cf. A003293, A004146, A008804.

Programs

Mathematica

terms = 40;
A003293[n_] := SeriesCoefficient[Product[(1-x^k)^(-Ceiling[k/2]), {k, 1, terms}], {x, 0, n}];
A008804[n_] := SeriesCoefficient[1/((1-x)^4 (1+x)^2 (1+x^2)), {x, 0, n}];
a[n_] := A003293[n-1] - A008804[n-3];
Array[a, terms] (* Jean-François Alcover, Sep 02 2019 *)

PARI

\\ here b(n) is A003293 and d(n) is A008804.
b(n)={polcoeff( prod(k=1, n, (1-x^k+x*O(x^n))^-ceil(k/2)), n)}
d(n)={(84+12*(-1)^n+6*I*((-I)^n-I^n)+(85+3*(-1)^n)*n+24*n^2+2*n^3)/96}
a(n)=b(n-1)-d(n-3); \\ Andrew Howroyd, Oct 09 2017

Formula

a(n) = A003293(n-1) - A008804(n-3). - Andrew Howroyd, Oct 09 2017

Extensions

Terms a(32) and beyond from Andrew Howroyd, Oct 09 2017