A002985 Number of trees in an n-node wheel. (Formerly M0783)

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,4

Comments

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

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

Formula

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

Example

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

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 *)

Prog

(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

Crossrefs

Cf. A003293, A004146, A008804.

Sequence in context: A358027 A090167 A352500 * A239342 A093608 A320328

Adjacent sequences: A002982 A002983 A002984 * A002986 A002987 A002988

Keyword

nonn

Author

N. J. A. Sloane

Extensions

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

Status

approved