A303841 -id:A303841 - cp's OEIS frontend

A303911 Triangle T(w>=1,1<=n<=w) read by rows: the number of rooted weighted trees with n nodes and weight w.

1, 1, 1, 1, 2, 2, 1, 3, 5, 4, 1, 4, 10, 13, 9, 1, 5, 16, 31, 35, 20, 1, 6, 24, 60, 98, 95, 48, 1, 7, 33, 103, 217, 304, 262, 115, 1, 8, 44, 162, 423, 764, 945, 727, 286, 1, 9, 56, 241, 743, 1658, 2643, 2916, 2033, 719, 1, 10, 70, 341, 1221, 3224, 6319, 8996, 8984, 5714, 1842, 1, 11, 85, 466, 1893

Offset: 1

R. J. Mathar, May 02 2018

Weights are positive integer labels on the nodes. The weight of the tree is the sum of the weights of its nodes.

			The triangle starts
1 ;
1  1 ;
1  2  2 ;
1  3  5   4 ;
1  4 10  13    9 ;
1  5 16  31   35    20 ;
1  6 24  60   98    95    48 ;
1  7 33 103  217   304   262   115 ;
The first column (for a single node n=1) is 1, because all the weight is on that node.

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-162, W(x,y) equation (9a)

Cf. A000081 (diagonal), A000107 (subdiagonal), A036249 (row sums), A303841 (not rooted).

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)}
seq(n)={my(v=[1]); for(i=2, n, v=concat([1], v + EulerMT(y*v))); v}
{my(A=seq(10)); for(n=1, #A, print(Vecrev(A[n])))} \\ 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

A301739 The number of trees with 4 nodes labeled by positive integers, where each tree's label sum is n.

Original entry on oeis.org

2, 4, 10, 17, 30, 44, 67, 91, 126, 163, 213, 265, 333, 403, 491, 582, 693, 807, 944, 1084, 1249, 1418, 1614, 1814, 2044, 2278, 2544, 2815, 3120, 3430, 3777, 4129, 4520, 4917, 5355, 5799, 6287, 6781, 7321, 7868, 8463, 9065, 9718, 10378, 11091, 11812, 12588, 13372, 14214, 15064

Offset: 4

R. J. Mathar, Mar 26 2018

Computed by the sum over the A000055(4)=2 shapes of the trees: the linear graph of the n-Butane, and the star graph of (1)-Methyl-Propane.

			a(4)=2 because there is a linear tree with all labels equal 1 and the star tree with all labels equal to 1.

Index entries for linear recurrences with constant coefficients, signature (1,2,-1,-2,-1,2,1,-1).

4th column of A303841.

x^4*(2+2*x+2*x^2+x^3+x^4)/(1+x)^2/(x-1)^4/(1+x+x^2) ;
taylor(%,x=0,80) ;
gfun[seriestolist](%) ;

a(n) = A005993(n-4)+A000601(n-4).

G.f.: x^4*(2+2*x+2*x^2+x^3+x^4)/((1+x)^2*(x-1)^4*(1+x+x^2) ).

A303842 Triangle read by rows: T(s,n) (s>=1 and 2<=n<=s+1) = number of trees with n nodes and positive integer edge labels with label sum s.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 2, 3, 3, 1, 2, 6, 6, 6, 1, 3, 9, 15, 16, 11, 1, 3, 13, 26, 43, 37, 23, 1, 4, 17, 46, 88, 116, 96, 47, 1, 4, 23, 68, 169, 273, 329, 239, 106, 1, 5, 28, 103, 287, 585, 869, 918, 622, 235, 1, 5, 35, 141, 467, 1104, 2031, 2695, 2609, 1607, 551

Offset: 1

R. J. Mathar, May 01 2018

			The triangle starts
1;
1   1;
1   1   2;
1   2   3    3;
1   2   6    6    6;
1   3   9    15   16    11;
1   3   13   26   43    37     23;
1   4   17   46   88    116    96    47;
1   4   23   68   169   273    329   239  106;
1   5   28   103  287   585    869   918  622    235;
1   5   35   141  467   1104   2031  2695 2609   1607   551;
1   6   42   195  711   1972   4211  6882 8399   ...    4235  1301;
1   6   50   253  1051  3270   8108 15513 23152  ...    ... ;
1   7   58   330  1489  5222  14552 32191 56291  ...    ... ;
1   7   68   412  2063  7958  24846 62014 124958  ...    ... ;

Andrew Howroyd, Table of n, a(n) for n = 1..1275
R. J. Mathar, Labeled Trees with fixed node label sum, vixra:1805.0205 (2018).

Cf. A303841 (labeled nodes), A000055 (diagonal), A027852 (subdiagonal), A303833 (subdiagonal), A304914 (row sums).

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=1, n, v=concat([1], v + EulerMT(y*v))); Ser(v)*y*(1-x)}
seq(n)={my(g=b(n)); Vec(g + (substvec(g, [x,y], [x^2,y^2]) - g^2)*x/(2*(1-x)) - y)}
{my(A=seq(15)); for(n=1, #A, print(Vecrev(A[n]/y^2)))} \\ Andrew Howroyd, May 20 2018

cp's OEIS Frontend

A303911 Triangle T(w>=1,1<=n<=w) read by rows: the number of rooted weighted trees with n nodes and weight w.

Views

Author

Keywords

Comments

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

A301739 The number of trees with 4 nodes labeled by positive integers, where each tree's label sum is n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A303842 Triangle read by rows: T(s,n) (s>=1 and 2<=n<=s+1) = number of trees with n nodes and positive integer edge labels with label sum s.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI