A000238 -id:A000238 - cp's OEIS frontend

A000060 Number of signed trees with n nodes.

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

Offset: 1

N. J. A. Sloane

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

			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

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

T. D. Noe, Table of n, a(n) for n = 1..500
F. Harary and G. Prins, The number of homeomorphically irreducible trees and other species, Acta Math., 101 (1959), 141-162.
P. Leroux and B. Miloudi, Généralisations de la formule d'Otter, Ann. Sci. Math. Québec, Vol. 16, No. 1, pp. 53-80, 1992.
P. Leroux and B. Miloudi, Généralisations de la formule d'Otter, Ann. Sci. Math. Québec, Vol. 16, No. 1, pp. 53-80, 1992. (Annotated scanned copy)
Index entries for sequences related to trees

Cf. A000151, A000238.

Row sums of A302939.

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)

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]];
seq[29] (* Jean-François Alcover, Sep 04 2019, after Andrew Howroyd *)

\\ 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

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

a(n) = A000238(n) + A000151(n/2), where A000151(.) is zero for non-integer arguments. - R. J. Mathar, Apr 16 2018

More terms from Pab Ter (pabrlos2(AT)yahoo.com), Oct 12 2005

A283753 Irregular triangular array read by rows: T(n,k) is the number of non-isomorphic unlabeled weakly connected digraphs on n nodes and with k arcs.

Original entry on oeis.org

1, 1, 1, 3, 4, 4, 1, 1, 8, 22, 37, 47, 38, 27, 13, 5, 1, 1, 27, 108, 326, 667, 1127, 1477, 1665, 1489, 1154, 707, 379, 154, 61, 16, 5, 1, 1, 91, 582, 2432, 7694, 19646, 42148, 77305, 122953, 170315, 206982, 220768, 207301, 171008, 124110, 78813, 43862, 21209, 8951, 3242, 1043, 288, 76, 17, 5, 1, 1, 350, 3024, 17314, 74676, 266364, 808620, 2144407

Offset: 1

Marko Riedel, Mar 15 2017

The range for the subindex k is from n-1 to n(n-1).

Obtained from A054733 by removing leading zeros.

			First rows are:
1;
1,    1;
3,    4,   4,   1,    1;
8,   22,  37,  47,   38,   27,   13,    5,    1,   1;
27, 108, 326, 667, 1127, 1477, 1665, 1489, 1154, 707, 379, ...

E. Palmer and F. Harary, Graphical Enumeration, Academic Press, 1973.

Marko R. Riedel, Number of distinct connected digraphs
Marko Riedel, Maple code for sequences A052283, A283753.

Cf. A000273, A000238, A003085, A052283.

\\ See A054733 for G, InvEulerMTS.
row(n)={Vecrev(polcoef(InvEulerMTS(sum(i=0, n, G(i, y)*x^i, O(x*x^n))), n)/y^(n-1))}
{ for(n=1, 6, print(row(n))) } \\ Andrew Howroyd, Jan 28 2022

A007748 Number of self-converse oriented trees with n nodes.

Original entry on oeis.org

1, 1, 1, 2, 3, 7, 10, 26, 39, 107, 160, 458, 702, 2058, 3177, 9498, 14830, 44947, 70678, 216598, 342860, 1059952, 1686486, 5251806, 8393681, 26297238, 42187148, 132856766, 213828802, 676398395, 1091711076

Offset: 1

N. J. A. Sloane

R. Simion, Trees with 1-factors and oriented trees, Discrete Math., 88 (1991), 93-104.
R. Simion, Trees with 1-factors and oriented trees, Discrete Math., 88 (1981), 97. (Annotated scanned copy)
Index entries for sequences related to trees

Cf. A000238.

max = 15; A[n_, k_] := A[n, k] = If[n<2, n, Sum[Sum[d*A[d, k], {d, Divisors[j]}] * A[n-j, k]*k, {j, 1, n-1}]/(n-1)]; a[n_] := A[n, 2]; A000151 = Table[a[n], {n, 1, max}]; etr[p_] := Module[{b}, b[n_] := b[n] = If[n==0, 1, Sum[Sum[d*p[d], {d, Divisors[j]}]*b[n-j], {j, 1, n}]/n]; b]; A005750 = Table[etr[a][n], {n, 0, max}] ; A007748 = Riffle[A005750, A000151] (* Jean-François Alcover, Jul 16 2015 *)

a(2n)=A000151(n). a(2n-1)=A005750(n). - Christian G. Bower, Dec 15 1999

A007835 Number of unordered sets of pairs (in-degree, out-degree) for nodes of directed trees on n unlabeled nodes (the edges are directed in arbitrary directions, the tree is unrooted).

Original entry on oeis.org

1, 1, 3, 8, 21, 52, 124, 284, 629, 1352, 2829, 5777, 11544

Offset: 1

Philippe Aubry (philippe.aubry(AT)oncfs.gouv.fr), Oct 02 1994

The trees in question might also be called unlabeled acyclic connected digraphs, totally acyclic digraphs or acyclic posets.
Comments from Dean Hickerson, May 17 2006: For each directed tree with n nodes, write down the set of pairs (in-degree, out-degree) that occur in the tree. Then count how many different sets you get that way.
For n=3 there are 3 such sets, namely: O-->O-->O {(0,1), (1,0), (1,1)}, O-->O<--O {(0,1), (2,0)}, O<--O-->O {(1,0), (0,2)}.
For n=4 there are 8 directed trees:
O->-O->-O->-O, O->-O->-O-<-O, O-<-O-<-O->-O, O->-O-<-O->-O,
......................
O .... O .... O .... O
| .... | .... | .... |
V .... ^ .... V .... ^
| .... | .... | .... |
O-<--O O->--O O-<--O O->--O
| .... | .... | .... |
^ .... V .... V .... ^
| .... | .... | .... |
O .... O .... O .... O
(see A000238 for the number of them with n nodes). It turns out that all of these give different sets, so a(4)=8.
For n=5 there are 27 directed trees. The following groups of trees give the same set:
O-->O<--O<--O<--O {(0,1), (0,1), (2,0), (1,1), (1,1)}
O-->O-->O<--O<--O {(0,1), (0,1), (2,0), (1,1), (1,1)}
------------------------------------------------------------
O<--O-->O-->O-->O {(1,0), (1,0), (0,2), (1,1), (1,1)}
O<--O<--O-->O-->O {(1,0), (1,0), (0,2), (1,1), (1,1)}
------------------------------------------------------------
O-->O<--O<--O-->O {(0,1), (1,0), (2,0), (1,1), (0,2)}
O-->O-->O<--O-->O {(0,1), (1,0), (2,0), (1,1), (0,2)}
O-->O<--O-->O-->O {(0,1), (1,0), (2,0), (1,1), (0,2)}
------------------------------------------------------------
............O
............|
............v
....O<--O<--O-->O {(0,1), (1,0), (1,0), (1,1), (1,2)}
.............
............O
............^
............|
....O-->O-->O-->O {(0,1), (1,0), (1,0), (1,1), (1,2)}
------------------------------------------------------------
............O
............^
............|
....O-->O-->O<--O {(0,1), (0,1), (1,0), (1,1), (2,1)}
.............
............O
............|
............v
....O<--O<--O<--O {(0,1), (0,1), (1,0), (1,1), (2,1)}
------------------------------------------------------------
There are no other duplications, so a(5)=23, as claimed.

Cf. A000238.

Edited by N. J. A. Sloane, May 17 2006

a(12)-a(13) from and example in comment clarified by Sean A. Irvine, Feb 04 2018

A063881 Number of oriented trees rooted at an arc.

Original entry on oeis.org

1, 4, 18, 80, 367, 1708, 8122, 39204, 191963, 950984, 4759626, 24030736, 122258314, 626162464, 3225926450, 16706775984, 86928097451, 454203897192, 2382255252398, 12537764465072, 66193294753768, 350472816969976, 1860542261745782, 9901018433270812

Offset: 2

Vladeta Jovovic, Aug 27 2001

nonn

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 61, (3.3.7).

Vincenzo Librandi, Table of n, a(n) for n = 2..100

Cf. A000151, A000238.

B:= proc(n) option remember; if n<=1 then unapply(x,x) else unapply(convert(series(x*exp(2*sum(B(n-1)(x^k)/k, k=1..n-1)), x,n+1), polynom),x) fi end: a:= proc(n) local T; T:=B(n-1)(x); add(coeff(T,x,k)* coeff(T,x,n-k), k=1..n-1) end: seq(a(n), n=2..23); # Alois P. Heinz, Aug 23 2008

B[n_ /; n <= 1] = Identity; B[n_] := B[n] = Function[x, Evaluate[Normal[Series[x*Exp[2*Sum[B[n-1][x^k]/k, {k, 1, n-1}]], {x, 0, n+1}]]]]; a[n_] := Module[{T}, T = B[n-1][x]; Sum[Coefficient[T, x, k]*Coefficient[T, x, n-k], {k, 1, n-1}]]; Table[a[n], {n, 2, 23}] (* Jean-François Alcover, Feb 17 2014, after Alois P. Heinz *)

a(n) = A000151(n)- A000238(n). G.f.: A(x) = B(x)^2, where B(x) is g.f. for A000151.

A334827 The number of oriented star-like and star trees with n arcs.

Original entry on oeis.org

4, 17, 66, 221, 688, 2034, 5788, 15998, 43192, 114496, 298712, 769340, 1959064, 4940761, 12354210, 30660947, 75583868, 185208833, 451356846, 1094522547, 2642121008, 6351335083, 15208854510, 36288478177, 86295204732, 204571273167, 483532711338, 1139738858221

Offset: 3

R. J. Mathar, Jun 09 2020

nonn

			a(6)=221 counts 132 oriented star-like trees with 3 rays and 6 arcs, 62 with 4 rays and 6 arcs, 20 with 5 rays and 6 arcs, and 7 star trees. In the illustrations in A000238 [Mathar] this is the same as 48 (shape 2) + 64 (shape 3) + 20 (shape 4) +32 (shape 7) + 30 (shape 8) +20 (shape 10) + 7 (shape 11).

Wikipedia, Starlike Tree
Index entries for sequences related to trees

Cf. A000238 (oriented trees), A051437 (linear oriented trees), A209406 (star-like oriented by number of arcs and rays), A004250 (undirected edges).

a(n) = A034899(n) -2^(n+1) = Sum_{k>=3} A209406(n,k).

cp's OEIS Frontend

A000060 Number of signed trees with n nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A283753 Irregular triangular array read by rows: T(n,k) is the number of non-isomorphic unlabeled weakly connected digraphs on n nodes and with k arcs.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

A007748 Number of self-converse oriented trees with n nodes.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A007835 Number of unordered sets of pairs (in-degree, out-degree) for nodes of directed trees on n unlabeled nodes (the edges are directed in arbitrary directions, the tree is unrooted).

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A063881 Number of oriented trees rooted at an arc.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A334827 The number of oriented star-like and star trees with n arcs.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula