login
A002985
Number of trees in an n-node wheel.
(Formerly M0783)
1
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, Derivation of formula.
Eric Weisstein's World of Mathematics, Wheel Graph.
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
KEYWORD
nonn
EXTENSIONS
Terms a(32) and beyond from Andrew Howroyd, Oct 09 2017
STATUS
approved