login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000060 Number of signed trees with n nodes.
(Formerly M0904 N0340)
7

%I M0904 N0340

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

%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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 21 04:59 EDT 2019. Contains 321364 sequences. (Running on oeis4.)