|
|
A000060
|
|
Number of signed trees with n nodes.
(Formerly M0904 N0340)
|
|
4
|
|
|
1, 2, 3, 10, 27, 98, 350, 1402, 5743, 24742, 108968, 492638, 2266502, 10600510, 50235931, 240882152, 1166732814, 5702046382, 28088787314, 139355139206, 695808554300, 3494391117164, 17641695461662, 89495028762682, 456009893224285, 2332997356507678, 11980753878699716, 61739654456234062, 319188605907760846
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
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
|
|
REFERENCES
|
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
|
|
FORMULA
|
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
|
|
EXAMPLE
|
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
|
|
MAPLE
|
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)
|
|
MATHEMATICA
|
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];
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]];
|
|
PROG
|
(PARI) \\ here b(N) is A000151 as vector
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}
seq(n) = {my(g=x*Ser(b(n))); Vec(g + subst(g, x, x^2) - g^2)} \\ Andrew Howroyd, May 13 2018
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
More terms from Pab Ter (pabrlos2(AT)yahoo.com), Oct 12 2005
|
|
STATUS
|
approved
|
|
|
|