|
%I M0904 N0340 #50 Aug 30 2023 07:28:13
%S 1,2,3,10,27,98,350,1402,5743,24742,108968,492638,2266502,10600510,
%T 50235931,240882152,1166732814,5702046382,28088787314,139355139206,
%U 695808554300,3494391117164,17641695461662,89495028762682,456009893224285,2332997356507678,11980753878699716,61739654456234062,319188605907760846
%N Number of signed trees with n nodes.
%C If only trees with a degree of each node <= 2 (linear chains) are counted, we obtain A005418. If only trees with a degree of each node <= 3 are counted, we obtain 1, 2, 3, 10, 22, 76, 237, 856, ... If the degree is restricted to <= 4 we obtain 1, 2, 3, 10, 27, 92, 323, 1260, ... - _R. J. Mathar_, Feb 26 2018
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H T. D. Noe, <a href="/A000060/b000060.txt">Table of n, a(n) for n = 1..500</a>
%H F. Harary and G. Prins, <a href="http://dx.doi.org/10.1007/BF02559543">The number of homeomorphically irreducible trees and other species</a>, Acta Math., 101 (1959), 141-162.
%H P. Leroux and B. Miloudi, <a href="http://www.labmath.uqam.ca/~annales/volumes/16-1/PDF/053-080.pdf">Généralisations de la formule d'Otter</a>, Ann. Sci. Math. Québec, Vol. 16, No. 1, pp. 53-80, 1992.
%H P. Leroux and B. Miloudi, <a href="/A000081/a000081_2.pdf">Généralisations de la formule d'Otter</a>, Ann. Sci. Math. Québec, Vol. 16, No. 1, pp. 53-80, 1992. (Annotated scanned copy)
%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%F G.f.: S(x) + S(x^2) - S(x)^2, where S(x) is the generating function for A000151. - Pab Ter (pabrlos2(AT)yahoo.com), Oct 12 2005
%F a(n) = A000238(n) + A000151(n/2), where A000151(.) is zero for non-integer arguments. - _R. J. Mathar_, Apr 16 2018
%e For n=4 nodes and 3 edges, the unsigned tree has two forms: the star and the linear chain. The star has 4 ways of signing its 3 edges: without plus (3 minus'), with one plus (2 minus'), with two plusses (1 minus) and with three plusses (no minus). The linear chain has 6 ways of signing the edges: +++, ---, +-- (equivalent to --+), -++ (equivalent to ++-), -+- and +-+. The total number of ways is a(4) = 4+6=10. - _R. J. Mathar_, Feb 26 2018
%p unassign('x'): with(combstruct): norootree:=[S, {B = Set(S), S = Prod(Z,B,B)}, unlabeled]: S:=x->add(count(norootree,size=i)*x^i,i=1..30): seq(coeff(S(x)+S(x^2)-S(x)^2,x,i),i=1..29); # with Algolib (Pab Ter)
%t b[M_] := Module[{A}, A = Table[1, {M}]; For[n = 1, n <= M-1, n++, A[[n+1]] = 2/n*Sum[Sum[d*A[[d]], {d, Divisors[i]}]*A[[n-i+1]], {i, 1, n}]]; A];
%t seq[n_] := Module[{g}, g = x*(b[n].x^Range[0, n-1]); CoefficientList[g + (g /. x -> x^2) - g^2, x]][[2 ;; n+1]];
%t seq[29] (* _Jean-François Alcover_, Sep 04 2019, after _Andrew Howroyd_ *)
%o (PARI) \\ here b(N) is A000151 as vector
%o b(N) = {my(A=vector(N, j, 1)); for (n=1, N-1, A[n+1] = 2/n * sum(i=1, n, sumdiv(i, d, d*A[d]) * A[n-i+1] ) ); A}
%o seq(n) = {my(g=x*Ser(b(n))); Vec(g + subst(g, x, x^2) - g^2)} \\ _Andrew Howroyd_, May 13 2018
%Y Cf. A000151, A000238.
%Y Row sums of A302939.
%K nonn,nice
%O 1,2
%A _N. J. A. Sloane_
%E More terms from Pab Ter (pabrlos2(AT)yahoo.com), Oct 12 2005
|
