A036250 -id:A036250 - cp's OEIS frontend

A191646 Triangle read by rows: T(n,k) = number of connected multigraphs with n >= 0 edges and 1 <= k <= n+1 vertices, with no loops allowed.

1, 0, 1, 0, 1, 1, 0, 1, 2, 2, 0, 1, 3, 5, 3, 0, 1, 4, 11, 11, 6, 0, 1, 6, 22, 34, 29, 11, 0, 1, 7, 37, 85, 110, 70, 23, 0, 1, 9, 61, 193, 348, 339, 185, 47, 0, 1, 11, 95, 396, 969, 1318, 1067, 479, 106, 0, 1, 13, 141, 771, 2445, 4457, 4940, 3294, 1279, 235

Offset: 0

Alberto Tacchella, Jul 04 2011

			Triangle T(n,k) (with rows n >= 0 and columns k >= 1) begins as follows:
  1;
  0, 1;
  0, 1, 1;
  0, 1, 2,  2;
  0, 1, 3,  5,  3;
  0, 1, 4, 11, 11,  6;
  0, 1, 6, 22, 34, 29, 11;
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..1274 (terms 0..119 from R. J. Mathar)
R. J. Mathar, Statistics on Small Graphs, arXiv:1709.09000 [math.CO], 2017; see Section 4.
Brendan McKay and Adolfo Piperno, nauty and Traces. [nauty and Traces are programs for computing automorphism groups of graphs and digraphs.]
B. D. McKay and A. Piperno, Practical Graph Isomorphism, II, J. Symbolic Computation 60 (2013), 94-112.
Gordon Royle, Small Multigraphs.
Gus Wiseman, Illustration of the 33 connected multigraphs counted in row 5.

Row sums give A076864. Diagonal is A000055.
Cf. A034253, A054923, A192517, A253186 (column k=3), A290778 (column k=4).
Cf. A000664, A007718, A036250, A050535, A191646, A191970, A275421, A317672, A322114, A322133, A322152.

EulerT(v)={my(p=exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1); Vec(p/x,-#v)}
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,x)={sum(i=2, #v, sum(j=1, i-1, my(g=gcd(v[i],v[j])); g*x^(v[i]*v[j]/g))) + sum(i=1, #v, my(t=v[i]); ((t-1)\2)*x^t + if(t%2,0,x^(t/2)))}
G(n,m)={my(s=0); forpart(p=n, s+=permcount(p)*EulerT(Vec(edges(p,x) + O(x*x^m), -m))); s/n!}
R(n)={Mat(apply(p->Col(p+O(y^n),-n), InvEulerMT(vector(n, k, 1 + y*Ser(G(k,n-1), y)))))}
{ my(A=R(10)); for(n=1, #A, for(k=1, n, print1(A[n,k], ", "));print) } \\ Andrew Howroyd, May 14 2018

T(n,k=3) = A253186(n) = A034253(n,k=2) for n >= 1. - Petros Hadjicostas, Oct 02 2019

A038052 Number of labeled trees of nonempty sets with n points. (Each node is a set of 1 or more points.)

Original entry on oeis.org

1, 1, 2, 7, 42, 376, 4513, 68090, 1238968, 26416729, 646140364, 17837852044, 548713088399, 18612963873492, 690271321314292, 27785827303491579, 1206582732097720126, 56224025231569020724, 2798445211000659147033, 148178324442139816854902, 8317074395027724691495980

Offset: 0

Christian G. Bower, Jan 04 1999

Alois P. Heinz, Table of n, a(n) for n = 0..379 (first 101 terms from T. D. Noe)
Index entries for sequences related to trees

Cf. A036250, A048802.

b:= proc(n, m) option remember; `if`(n=0,
      m^max(0, m-2), m*b(n-1, m)+b(n-1, m+1))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..21);  # Alois P. Heinz, Jul 16 2022

a[0] = 1; a[n_] := Sum[StirlingS2[n, k]*k^(k - 2), {k, 1, n}]; Table[a[n], {n, 0, 18}] (* Jean-François Alcover, Sep 09 2013, after Vladeta Jovovic *)

E.g.f.: B(e^x-1) where B is e.g.f. of A000272.
a(n) = Sum_{k=1..n} Stirling2(n, k)*k^(k-2). - Vladeta Jovovic, Sep 20 2003
a(n) ~ (1+exp(1))^(3/2) * n^(n-2) / (exp(n) * (log(1+exp(-1)))^(n-3/2)). - Vaclav Kotesovec, Feb 17 2017

A303841 Triangle read by rows: T(s,n) (s>=1 and 1<=n<=s) = number of weighted trees with n nodes and positive integer node labels with label sum s.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 2, 4, 4, 3, 1, 3, 6, 10, 9, 6, 1, 3, 9, 17, 24, 20, 11, 1, 4, 12, 30, 50, 63, 48, 23, 1, 4, 16, 44, 96, 146, 164, 115, 47, 1, 5, 20, 67, 164, 315, 437, 444, 286, 106, 1, 5, 25, 91, 267, 592, 1022, 1300, 1204, 719, 235, 1, 6, 30, 126, 408, 1059, 2126, 3331, 3899, 3328, 1842, 551

Offset: 1

R. J. Mathar, May 01 2018

			The triangle starts
1;
1 1;
1 1  1;
1 2  2   2;
1 2  4   4    3;
1 3  6  10    9   6;
1 3  9  17   24   20    11;
1 4 12  30   50   63    48    23;
1 4 16  44   96  146   164   115    47;
1 5 20  67  164  315   437   444   286  106;
1 5 25  91  267  592  1022  1300  1204  719     235;
1 6 30 126  408 1059  2126  3331  3899 3328    1842    551;
1 6 36 163  603 1754  4098  7511 10781 11692   9233   4766  1301;
1 7 42 213  856 2805  7368 15619 26294 34844  35136  25865 12486  3159;
1 7 49 265 1186 4270 12590 30111 58485 91037 112036 105592 72734 32973 7741;

Andrew Howroyd, Table of n, a(n) for n = 1..1275
F. Harary, G. Prins, The number of homeomorphically irreducible trees and other species, Acta. Math. 101 (1959) 141, equation (9b).
R. J. Mathar, Labeled trees with fixed node label sum vixra:1805.0205 (2018).
Richard J. Mathar, Counting Connected Graphs without Overlapping Cycles, arXiv:1808.06264 [math.CO], 2018.

Cf. A036250 (row sums), A002620 (column 3), A301739 (column 4), A301740 (column 5), A000055 (diagonal), A000081 (subdiagonal), A303911 (rooted).

\\ here b is A303911
EulerMT(u)={my(n=#u, p=x*Ser(u), vars=variables(p)); Vec(exp(sum(i=1, n, substvec(p + O(x*x^(n\i)), vars, apply(v->v^i,vars))/i ))-1)}
b(n)={my(v=[1]); for(i=2, n, v=concat([1], v + EulerMT(y*v))); v}
seq(n)={my(g=x*Ser(y*b(n))); Vec(g - g^2/2 + substvec(g,[x,y],[x^2,y^2])/2)}
{my(A=seq(15)); for(n=1, #A, print(Vecrev(A[n]/y)))} \\ Andrew Howroyd, May 19 2018

A317722 Number of connected graphs with n nodes and no node a member of more than one cycle.

Original entry on oeis.org

1, 1, 2, 3, 8, 18, 56, 165, 563, 1937, 7086, 26396, 101383, 395821, 1573317, 6335511, 25825861, 106344587, 441919711, 1851114466, 7809848543, 33162241547, 141636863809, 608144007472, 2623832050460, 11370768445682, 49478287669666, 216109924932762, 947216963083175

Offset: 0

R. J. Mathar, Aug 05 2018

nonn

The sequence counts connected, loopless, undirected graphs with cycles that do not overlap (cycles have length >= 2), which means any pair of cycles does not have common edges or nodes.
Examples of these graphs are the trees (A000055), the unicyclic graphs (A001429, A002094), or the graphs with cycles without chords.
The concept is both narrower and wider than the concept for Husimi trees, because cycles in Husimi trees may share nodes (but not edges), and because cycles in Husimi trees need to have length >= 3.
There is a mapping/contraction of these graphs to trees: replace each cycle by a single node, attaching all edges that enter a node in the cycle to that node. That tree associated with the graph could be called the skeleton tree.
By reversing that surjection of the graphs to trees, we may generate our graphs with non-overlapping cycles by generating the set of weighted trees (A303841) and replacing the nodes by cycles of lengths that equals their weight.

Andrew Howroyd, Table of n, a(n) for n = 0..500
R. J. Mathar, Counting connected graphs without overlapping cycles, arXiv:1808.06264 [math.CO] (2018), series c(n).
R. J. Mathar, Illustration of the graphs up to n=6

Cf. A036250, A381468 (without 2-cycles).

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))}
raise(p,d) = {my(n=serprec(p,x)-1); substvec(p + O(x^(n\d+1)), [x, y], [x^d,y^d])}
R(n,y)={my(g=x+O(x^2)); for(n=2, n, my(p=x*EulerMTS(g), p2=raise(p,2)); g=p + p*y*(p/(1 - p) + (p + p2)/(1 - p2))/2); g}
G(n,y=1)={my(g=R(n,y), p = x*EulerMTS(g) + O(x*x^n));
  my( r=((1 + p)^2/(1 - raise(p,2)) - 1)/2 );
  my( c=-sum(d=1, n, eulerphi(d)/d*log(raise(1-p,d))) );
  1 + p + (raise(g,2) - g^2 + y*(r + c - 2*p))/2 }
{ Vec(G(30)) } \\ Andrew Howroyd, Feb 25 2025

a(n) >= A036250(n).

a(5) corrected. - R. J. Mathar, Aug 12 2018

A036251 Number of trees with 2-colored leaves.

Original entry on oeis.org

1, 2, 3, 3, 7, 14, 35, 85, 231, 633, 1845, 5461, 16707, 51945, 164695, 529077, 1722279, 5664794, 18813369, 62996850, 212533226, 721792761, 2466135375, 8471967938, 29249059293, 101440962296, 353289339927, 1235154230060

Offset: 0

Christian G. Bower, Nov 15 1998

nonn

Index entries for sequences related to trees

Essentially the same as A036250. Cf. A038054.

max = 30; B[] = 1; Do[B[x] = x*Exp[Sum[(B[x^k] + x^k)/k + O[x]^n, {k, 1, n}]] // Normal, {n, 1, max}]; A[x_] = 1 + x + x^2 + B[x] - B[x]^2/2 + B[x^2]/2; CoefficientList[A[x] + O[x]^max, x] (* Jean-François Alcover, Jan 28 2019 *)

G.f.: B(x) + B(x)^2/2 + B(x^2)/2 - B(x)*(B(x)-x), where B(x) is g.f. for A029856.

cp's OEIS Frontend

A191646 Triangle read by rows: T(n,k) = number of connected multigraphs with n >= 0 edges and 1 <= k <= n+1 vertices, with no loops allowed.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A038052 Number of labeled trees of nonempty sets with n points. (Each node is a set of 1 or more points.)

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A303841 Triangle read by rows: T(s,n) (s>=1 and 1<=n<=s) = number of weighted trees with n nodes and positive integer node labels with label sum s.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

A317722 Number of connected graphs with n nodes and no node a member of more than one cycle.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

Extensions

A036251 Number of trees with 2-colored leaves.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula