A000238 -id:A000238 - cp's OEIS frontend

A174146 Partial sums of A000238.

1, 2, 5, 13, 40, 131, 481, 1857, 7600, 32235, 141203, 633383, 2899885, 13498337, 63734268, 304606922, 1471339736, 7173341171, 35262128485, 174617051093, 870425605393, 4364815662605, 22006511124267, 111501534635143, 567511427859428, 2900508758069868

Offset: 1

Jonathan Vos Post, Mar 09 2010

nonn

Partial sums of number of oriented trees with n nodes. The subsequence of primes in this partial sum begins: 2, 5, 13, 131, 633383, 870425605393, 55532683410408578237, 290078510058531496879, 26098901136734259174974296003.

			a(32) = 1 + 1 + 3 + 8 + 27 + 91 + 350 + 1376 + 5743 + 24635 + 108968 + 492180 + 2266502 + 10598452 + 50235931 + 240872654 + 1166732814 + 5702001435 + 28088787314 + 139354922608 + 695808554300 + 3494390057212 + 17641695461662 + 89495023510876 + 456009893224285 + 2332997330210440 + 11980753878699716 + 61739654323377296 + 319188605907760846 + 1655151350788152551 + 8606939469625111036 + 44874783067127406924.

Alois P. Heinz, Table of n, a(n) for n = 1..1000

Cf. A000238.

a(n) = Sum_{i=1..n} A000238(i).

A000151 Number of oriented rooted trees with n nodes. Also rooted trees with n nodes and 2-colored non-root nodes.

Original entry on oeis.org

1, 2, 7, 26, 107, 458, 2058, 9498, 44947, 216598, 1059952, 5251806, 26297238, 132856766, 676398395, 3466799104, 17873508798, 92630098886, 482292684506, 2521610175006, 13233573019372, 69687684810980, 368114512431638, 1950037285256658, 10357028326495097, 55140508518522726, 294219119815868952, 1573132563600386854, 8427354035116949486, 45226421721391554194

Offset: 1

N. J. A. Sloane

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Camb. 1998, p. 286.
S. R. Finch, Mathematical Constants, Cambridge, 2003, p. 307 and 564.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 60, R(x).
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 138.
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).

Vaclav Kotesovec, Table of n, a(n) for n = 1..1300 (terms 1..500 from N. J. A. Sloane)
Sølve Eidnes, Order theory for discrete gradient methods, arXiv:2003.08267 [math.NA], 2020.
L. Foissy, Algebraic structures on typed decorated rooted trees, arXiv:1811.07572 [math.RA], 2018.
Vsevolod Gubarev, Rota-Baxter operators on a sum of fields, arXiv:1811.08219 [math.RA], 2018.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 387
P. Leroux and B. Miloudi, Generalisations de la formule d'Otter, Ann. Sci. Math. Quebec 16 (1992), no 1, 53-80.
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)
R. J. Mathar, Topologically Distinct Sets of Non-intersecting Circles in the Plane, arXiv:1603.00077 [math.CO], 2016.
R. Simion, Trees with 1-factors and oriented trees, Discrete Math., 88 (1981), 97.
R. Simion, Trees with 1-factors and oriented trees, Discrete Math., 88 (1981), 97. (Annotated scanned copy)
S. G. Wagner, An identity for the cycle indices of rooted tree automorphism groups, Elec. J. Combinat., 13 (2006), #R00.
Index entries for sequences related to rooted trees
Index entries for sequences related to trees

Cf. A000238, A038055.
Also the self-convolution of A005750. - Paul D. Hanna, Aug 17 2002
Column k=2 of A242249.
Cf. A005751, A245870.

R:=series(x+2*x^2+7*x^3+26*x^4,x,5); M:=500;
for n from 5 to M do
series(add( subs(x=x^k,R)/k, k=1..n-1),x,n);
t4:=coeff(series(x*exp(%)^2,x,n+1),x,n);
R:=series(R+t4*x^n,x,n+1); od:
for n from 1 to M do lprint(n,coeff(R,x,n)); od: # N. J. A. Sloane, Mar 10 2007
with(combstruct):norootree:=[S, {B = Set(S), S = Prod(Z,B,B)}, unlabeled] :seq(count(norootree,size=i),i=1..30); # with Algolib (Pab Ter)

terms = 30; A[] = 0; Do[A[x] = x*Exp[2*Sum[A[x^k]/k, {k, 1, terms}]] + O[x]^(terms+1) // Normal, terms+1]; CoefficientList[A[x], x] // Rest
(* Jean-François Alcover, Jun 08 2011, updated Jan 11 2018 *)

seq(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} \\ Andrew Howroyd, May 13 2018

Generating function A(x) = x+2*x^2+7*x^3+26*x^4+... satisfies A(x)=x*exp( 2*sum_{k>=1}(A(x^k)/k) ) [Harary]. - Pab Ter (pabrlos2(AT)yahoo.com), Oct 12 2005
G.f.: x*Product_{n>=1} 1/(1 - x^n)^(2*a(n)) = Sum_{n>=1} a(n)*x^n.
a(n) ~ c * d^n / n^(3/2), where d = A245870 = 5.64654261623294971289271351621..., c = 0.2078615974229174213216534920508516879353537904602582293754027908931077971... - Vaclav Kotesovec, Aug 20 2014, updated Dec 26 2020

Extended with alternate description by Christian G. Bower, Apr 15 1998

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

A054733 Triangle of number of (weakly) connected unlabeled digraphs with n nodes and k arcs (n >=2, k >= 1).

Original entry on oeis.org

1, 1, 0, 3, 4, 4, 1, 1, 0, 0, 8, 22, 37, 47, 38, 27, 13, 5, 1, 1, 0, 0, 0, 27, 108, 326, 667, 1127, 1477, 1665, 1489, 1154, 707, 379, 154, 61, 16, 5, 1, 1, 0, 0, 0, 0, 91, 582, 2432, 7694, 19646, 42148, 77305, 122953, 170315, 206982, 220768, 207301, 171008

Offset: 2

Vladeta Jovovic, Apr 21 2000

			1,1;
0,3,4,4,1,1;
0,0,8,22,37,47,38,27,13,5,1,1;
the last batch giving the numbers of connected digraphs with 4 nodes and from 1 to 12 arcs.

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

Andrew Howroyd, Table of n, a(n) for n = 2..2661 (rows 2..20)
R. J. Mathar, Statistics on Small Graphs, arXiv:1709.09000 (2017) Table 75.

Cf. A000238 (leading diagonal), A003085 (row sums), A053454 (column sums), A062735 (labeled).

Cf. A052283 (not necessarily connected), A283753 (another version), A057276 (strongly connected), A350789 (transpose).

InvEulerMTS(p)={my(n=serprec(p,x)-1, q=log(p), vars=variables(p)); sum(i=1, n, moebius(i)*substvec(q + O(x*x^(n\i)), vars, apply(v->v^i,vars))/i)}
permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
edges(v, t) = {prod(i=2, #v, prod(j=1, i-1, my(g=gcd(v[i], v[j])); t(v[i]*v[j]/g)^(2*g) )) * prod(i=1, #v, my(c=v[i]); t(c)^(c-1))}
G(n, x)={my(s=0); forpart(p=n, s+=permcount(p)*edges(p, i->1+x^i)); s/n!}
row(n)={Vecrev(polcoef(InvEulerMTS(sum(i=0, n, G(i, y)*x^i, O(x*x^n))), n)/y)}
{ for(n=2, 6, print(row(n))) } \\ Andrew Howroyd, Jan 28 2022

A350449 Triangle read by rows: T(n,k) is the number of weakly connected acyclic digraphs on n unlabeled nodes with k arcs, n >= 1, k = 0..(n-1)*n/2.

Original entry on oeis.org

1, 0, 1, 0, 0, 3, 1, 0, 0, 0, 8, 9, 6, 1, 0, 0, 0, 0, 27, 54, 79, 63, 33, 10, 1, 0, 0, 0, 0, 0, 91, 320, 732, 1136, 1281, 1056, 649, 281, 85, 15, 1, 0, 0, 0, 0, 0, 0, 350, 1788, 6012, 14378, 26529, 38407, 44621, 41638, 31321, 18843, 8983, 3325, 920, 180, 21, 1

Offset: 1

Andrew Howroyd, Dec 31 2021

			Triangle begins:
  [1] 1;
  [2] 0, 1;
  [3] 0, 0, 3, 1;
  [4] 0, 0, 0, 8,  9,  6,  1;
  [5] 0, 0, 0, 0, 27, 54, 79, 63, 33, 10, 1;
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..1350 (rows 1..20)

Row sums are A101228.
Columns sums are A350451.
Leading diagonal is A000238.
Cf. A350447 (not necessarily connected), A350450 (transpose).

\\ See PARI link in A122078 for program code.
{ my(T=WeakAcyclicDigraphsByArcs(6)); for(n=1, #T, print(T[n])) }

A245870 Decimal expansion of a constant related to A000151.

Original entry on oeis.org

5, 6, 4, 6, 5, 4, 2, 6, 1, 6, 2, 3, 2, 9, 4, 9, 7, 1, 2, 8, 9, 2, 7, 1, 3, 5, 1, 6, 2, 1, 6, 9, 1, 3, 8, 3, 8, 1, 4, 9, 8, 2, 1, 9, 1, 1, 6, 0, 5, 3, 8, 4, 3, 9, 2, 3, 8, 5, 8, 1, 7, 0, 2, 8, 8, 5, 0, 0, 2, 1, 4, 3, 1, 1, 2, 2, 4, 9, 4, 3, 0, 7, 7, 0, 7, 4, 2, 7, 5, 5, 5, 1, 6, 1, 1, 7, 7, 8, 8, 3, 4, 0, 6, 6, 0

Offset: 1

Vaclav Kotesovec, Aug 25 2014

			5.646542616232949712892713516216913838149821911605384392385817...

Steven R. Finch, Mathematical Constants, Cambridge, 2003, p. 307 and 564.

Cf. A000151, A000238, A005750, A005751, A038055, A198760.

Equals lim n -> infinity A000151(n)^(1/n).
Equals lim n -> infinity A005751(n)^(1/n).
Equals lim n -> infinity A038055(n)^(1/n).
Equals lim n -> infinity A005750(n)^(1/n).
Equals lim n -> infinity A198760(n)^(1/n).

More terms from Vaclav Kotesovec, Sep 11 2014 and Dec 26 2020

A350450 Triangle read by rows: T(n,k) is the number of unlabeled weakly connected acyclic digraphs with n arcs and k vertices, n >= 0, k = 1..n+1.

Original entry on oeis.org

1, 0, 1, 0, 0, 3, 0, 0, 1, 8, 0, 0, 0, 9, 27, 0, 0, 0, 6, 54, 91, 0, 0, 0, 1, 79, 320, 350, 0, 0, 0, 0, 63, 732, 1788, 1376, 0, 0, 0, 0, 33, 1136, 6012, 9933, 5743, 0, 0, 0, 0, 10, 1281, 14378, 45225, 54502, 24635, 0, 0, 0, 0, 1, 1056, 26529, 151848, 322736, 298250, 108968

Offset: 0

Andrew Howroyd, Dec 31 2021

			Triangle begins:
  1;
  0, 1;
  0, 0, 3;
  0, 0, 1, 8;
  0, 0, 0, 9, 27;
  0, 0, 0, 6, 54,   91;
  0, 0, 0, 1, 79,  320,  350;
  0, 0, 0, 0, 63,  732, 1788, 1376;
  0, 0, 0, 0, 33, 1136, 6012, 9933, 5743;
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..860 (rows 0..40)

Main diagonal is A000238.
Row sums are A350451.
Column sums are A101228.
Cf. A122078, A350449 (transpose).

\\ See PARI link in A122078 for program code.
{ my(T=WeakAcyclicDigraphsTr(10)); for(n=1, #T, print(T[n])); }

A335362 Triangle T(n,d) read by rows: the number of mixed trees with n>=1 nodes and 0<=d

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 2, 5, 10, 8, 3, 12, 32, 40, 27, 6, 30, 99, 178, 187, 91, 11, 74, 298, 692, 1019, 854, 350, 23, 188, 890, 2538, 4751, 5692, 4074, 1376, 47, 478, 2627, 8886, 20260, 31188, 31856, 19602, 5743, 106, 1235, 7734, 30270, 81170, 152509, 200413, 177266, 96035, 24635

Offset: 1

R. J. Mathar, Jun 03 2020

			The triangle starts
1;
1, 1;
1, 2, 3;
2, 5,10, 8;
3,12,32,40,27;
There are T(3,1)=2 mixed trees on 3 nodes with one directed edge (the edge can point towards the middle node or away from it).

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (first 50 rows).
R. J. Mathar, Mixed Trees A335362
Index entries for sequences related to trees

Cf. A000055 (column d=0), A000238 (diagonal d=n-1), A000106 (column d=1), A006965 (row sums), A335601 (subdiagonal d=n-2).

\\ Here R(n) is rooted mixed trees as g.f.
EulerMTS(p)={my(n=serprec(p,x)-1,vars=variables(p)); exp(sum(i=1, n, substvec(p + O(x*x^(n\i)), vars, apply(v->v^i,vars))/i))}
R(n) = {my(p=x+O(x^2)); for(n=2, n, p=x*EulerMTS(2*y*p + p)); p}
T(n) = {my(p=R(n)); [Vecrev(p) | p<-Vec(p + (subst(subst(p + O(x*x^(n\2)), x, x^2), y, y^2) - (2*y+1)*p^2)/2)]}
{ my(A=T(10)); for(n=1, #A, print(A[n])) } \\ Andrew Howroyd, Mar 23 2023

Completed row n=9. - R. J. Mathar, Jun 11 2020

Terms a(46) and beyond from Andrew Howroyd, Mar 23 2023

A350734 Triangle read by rows: T(n,k) is the number of weakly connected oriented graphs on n unlabeled nodes with k arcs, n >= 1, k = 0..n*(n-1)/2.

Original entry on oeis.org

1, 0, 1, 0, 0, 3, 2, 0, 0, 0, 8, 12, 10, 4, 0, 0, 0, 0, 27, 68, 127, 144, 107, 50, 12, 0, 0, 0, 0, 0, 91, 395, 1144, 2393, 3767, 4500, 4112, 2740, 1274, 376, 56, 0, 0, 0, 0, 0, 0, 350, 2170, 9139, 28606, 71583, 145600, 244589, 339090, 387458, 361394, 271177, 159872, 71320, 22690, 4604, 456

Offset: 1

Andrew Howroyd, Jan 13 2022

			Triangle begins:
  [1] 1;
  [2] 0, 1;
  [3] 0, 0, 3, 2;
  [4] 0, 0, 0, 8, 12, 10,   4;
  [5] 0, 0, 0, 0, 27, 68, 127, 144, 107, 50, 12;
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..1350 (rows 1..20)

Row sums are A086345.
Column sums are A350915.
Leading diagonal is A000238.
The labeled version is A350732.
Cf. A054733, A350733, A350750, A350914 (transpose).

InvEulerMTS(p)={my(n=serprec(p,x)-1, q=log(p), vars=variables(p)); sum(i=1, n, moebius(i)*substvec(q + O(x*x^(n\i)), vars, apply(v->v^i,vars))/i)}
permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
edges(v, t) = {prod(i=2, #v, prod(j=1, i-1, my(g=gcd(v[i], v[j])); t(v[i]*v[j]/g)^g )) * prod(i=1, #v, my(c=v[i]); t(c)^((c-1)\2))}
G(n, x)={my(s=0); forpart(p=n, s+=permcount(p)*edges(p, i->1+2*x^i)); s/n!}
row(n)={Vecrev(polcoef(InvEulerMTS(sum(i=0, n, G(i, y)*x^i, O(x*x^n))), n))}
{ for(n=1, 6, print(row(n))) }

A139621 Triangle read by rows: T(n,k) is the number of connected directed multigraphs with loops and no vertex of degree 0, with n arcs and k vertices.

Original entry on oeis.org

1, 1, 1, 1, 4, 3, 1, 8, 15, 8, 1, 16, 57, 66, 27, 1, 25, 163, 353, 295, 91, 1, 40, 419, 1504, 2203, 1407, 350, 1, 56, 932, 5302, 12382, 13372, 6790, 1376, 1, 80, 1940, 16549, 58237, 96456, 80736, 33628, 5743, 1, 105, 3743, 46566, 237904, 573963, 717114, 482730, 168645, 24635

Offset: 0

Benoit Jubin, May 01 2008

Length of the n-th row: n+1.

			Triangle begins:
     1
     1     1
     1     4     3
     1     8    15     8
     1    16    57    66    27
     1    25   163   353   295    91
     1    40   419  1504  2203  1407   350
     1    56   932  5302 12382 13372  6790  1376
T(2 arcs, 2 vertices) = 4: one graph 1->1, 2->1; one graph with 1->1, 1->2; one graph with 2->1, 2->1, one graph with 1->2, 2->1.
T(2 arcs, 3 vertices) = 3: one graph 2->1, 3->1; one graph 2->1, 3->2; one graph 2->1, 2->3.

Andrew Howroyd, Table of n, a(n) for n = 0..1325
R. J. Mathar, Statistics on Small Graphs, arXiv:1709.09000 (2017) Table 71.

Cf. A129620, A136564, A139622, A137975 (row sums), A000238 (diagonal).

InvEulerMT(u)={my(n=#u, p=log(1+x*Ser(u)), vars=variables(p)); Vec(serchop( sum(i=1, n, moebius(i)*substvec(p + O(x*x^(n\i)), vars, apply(v->v^i,vars))/i), 1))}
permcount(v) = {my(m=1,s=0,k=0,t); for(i=1,#v,t=v[i]; k=if(i>1&&t==v[i-1],k+1,1); m*=t*k;s+=t); s!/m}
edges(v,t) = {prod(i=2, #v, prod(j=1, i-1, my(g=gcd(v[i],v[j])); t(v[i]*v[j]/g)^(2*g))) * prod(i=1, #v, t(v[i])^v[i])}
G(n, x)={my(s=0); forpart(p=n, s+=permcount(p)/edges(p,i->1-x^i)); s/n!}
T(n)={Mat([Col(p+O(y^n), -n) | p<-InvEulerMT(vector(n, k, G(k, y + O(y^n))))])}
{my(A=T(10)); for(n=1, #A, print(A[n,1..n]))} \\ Andrew Howroyd, Oct 22 2019

T(n,1) = 1.

T(n,2) = A136564(n,2) - floor(n/2).

Prepended a(0)=1 to have a regular triangle, Joerg Arndt, Apr 14 2013
More terms from R. J. Mathar, Jul 31 2017
Terms a(34) and beyond from Andrew Howroyd, Oct 22 2019

A350789 Triangle read by rows: T(n,k) is the number of unlabeled weakly connected digraphs with n arcs and k vertices, k = 1..n+1.

Original entry on oeis.org

1, 0, 1, 0, 1, 3, 0, 0, 4, 8, 0, 0, 4, 22, 27, 0, 0, 1, 37, 108, 91, 0, 0, 1, 47, 326, 582, 350, 0, 0, 0, 38, 667, 2432, 3024, 1376, 0, 0, 0, 27, 1127, 7694, 17314, 16008, 5743, 0, 0, 0, 13, 1477, 19646, 74676, 117312, 84494, 24635

Offset: 0

Andrew Howroyd, Jan 28 2022

			Triangle begins:
  1;
  0, 1;
  0, 1, 3;
  0, 0, 4,  8;
  0, 0, 4, 22,   27;
  0, 0, 1, 37,  108,   91;
  0, 0, 1, 47,  326,  582,   350;
  0, 0, 0, 38,  667, 2432,  3024,  1376;
  0, 0, 0, 27, 1127, 7694, 17314, 16008, 5743;
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (rows 0..50)

Row sums are A053454.
Column sums are A003085.
Main diagonal is A000238.
Cf. A054733 (transpose), A350450 (acyclic), A350753 (strongly connected).

\\ See A054733 for G, InvEulerMTS
T(n)={my(p=InvEulerMTS(sum(i=0, n, G(i, y+O(y^n))*x^i, O(x*x^n)))); vector(n, n, Vec(O(x^n)+polcoef(p,n-1,y)/x, -n))}
{ my(A=T(10)); for(n=1, #A, print(A[n])) }

cp's OEIS Frontend

A174146 Partial sums of A000238.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A000151 Number of oriented rooted trees with n nodes. Also rooted trees with n nodes and 2-colored non-root nodes.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A054733 Triangle of number of (weakly) connected unlabeled digraphs with n nodes and k arcs (n >=2, k >= 1).

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

PARI

A350449 Triangle read by rows: T(n,k) is the number of weakly connected acyclic digraphs on n unlabeled nodes with k arcs, n >= 1, k = 0..(n-1)*n/2.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

A245870 Decimal expansion of a constant related to A000151.

Views

Author

Keywords

Examples

References

Crossrefs

Formula

Extensions

A350450 Triangle read by rows: T(n,k) is the number of unlabeled weakly connected acyclic digraphs with n arcs and k vertices, n >= 0, k = 1..n+1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

A335362 Triangle T(n,d) read by rows: the number of mixed trees with n>=1 nodes and 0<=d

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Extensions

A350734 Triangle read by rows: T(n,k) is the number of weakly connected oriented graphs on n unlabeled nodes with k arcs, n >= 1, k = 0..n*(n-1)/2.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

A139621 Triangle read by rows: T(n,k) is the number of connected directed multigraphs with loops and no vertex of degree 0, with n arcs and k vertices.