A002985 - OEIS

%I M0783 #27 Oct 20 2023 22:04:55

%S 1,1,1,2,3,6,11,20,36,64,108,179,292,464,727,1124,1714,2585,3866,5724,

%T 8418,12290,17830,25713,36898,52664,74837,105873,149178,209364,292793,

%U 407990,566668,784521,1082848,1490197,2045093,2798895,3820629,5202085

%N Number of trees in an n-node wheel.

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

%D 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.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Andrew Howroyd, <a href="/A002985/b002985.txt">Table of n, a(n) for n = 1..200</a>

%H Andrew Howroyd, <a href="/A002985/a002985.txt">Derivation of formula</a>.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/WheelGraph.html">Wheel Graph</a>.

%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>

%F a(n) = A003293(n-1) - A008804(n-3). - _Andrew Howroyd_, Oct 09 2017

%e All trees that span a wheel on 5 nodes are equivalent to one of the following:

%e       o         o         o

%e       |         | \     /   \

%e    o--o--o   o--o  o   o--o  o

%e       |         |           /

%e       o         o         o

%t terms = 40;

%t A003293[n_] := SeriesCoefficient[Product[(1-x^k)^(-Ceiling[k/2]), {k, 1, terms}], {x, 0, n}];

%t A008804[n_] := SeriesCoefficient[1/((1-x)^4 (1+x)^2 (1+x^2)), {x, 0, n}];

%t a[n_] := A003293[n-1] - A008804[n-3];

%t Array[a, terms] (* _Jean-François Alcover_, Sep 02 2019 *)

%o (PARI) \\ here b(n) is A003293 and d(n) is A008804.

%o b(n)={polcoeff( prod(k=1, n, (1-x^k+x*O(x^n))^-ceil(k/2)), n)}

%o d(n)={(84+12*(-1)^n+6*I*((-I)^n-I^n)+(85+3*(-1)^n)*n+24*n^2+2*n^3)/96}

%o a(n)=b(n-1)-d(n-3); \\ _Andrew Howroyd_, Oct 09 2017

%Y Cf. A003293, A004146, A008804.

%K nonn

%O 1,4

%A _N. J. A. Sloane_

%E Terms a(32) and beyond from _Andrew Howroyd_, Oct 09 2017