A027852 -id:A027852 - cp's OEIS frontend

A068051 Number of n-node connected graphs with one cycle, possibly of length 1 or 2.

1, 2, 4, 9, 20, 49, 118, 300, 765, 1998, 5255, 14027, 37670, 102095, 278262, 763022, 2101905, 5816142, 16153148, 45017423, 125836711, 352723949, 991143727, 2791422887, 7877935985, 22275473767, 63096075118, 179012076933

Offset: 1

Christian G. Bower, Feb 12 2002

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..200
C. G. Bower, Transforms (2)

Cf. A217781.

nn=20;t[x_]:=Sum[a[n]x^n,{n,0,nn}];sol=SolveAlways[0==Series[t[x]-x Product[1/(1-x^i)^a[i],{i,1,nn}],{x,0,nn}],x];b=Table[a[n],{n,1,nn}]/.sol//Flatten;Map[Total,Drop[Transpose[Table[Take[CoefficientList[CycleIndex[DihedralGroup[n],s]/.Table[s[j]->Table[Sum[b[[i]]x^(i*k),{i,1,nn}],{k,1,nn}][[j]],{j,1,n}],x],nn],{n,1,nn}]],1]]  (* Geoffrey Critzer, Mar 24 2013 *)

\\ TreeGf gives gf of A000081
TreeGf(N)={my(A=vector(N, j, 1)); for(n=1, N-1, A[n+1] = 1/n * sum(k=1, n, sumdiv(k, d, d*A[d]) * A[n-k+1] ) ); x*Ser(A)}
seq(n)={my(t=TreeGf(n)); my(g(e)=subst(t + O(x*x^(n\e)), x, x^e) + O(x*x^n)); Vec((sum(d=1, n, eulerphi(d)/d*log(1/(1-g(d)))) + ((1+g(1))^2/(1-g(2))-1)/2)/2)} \\ Andrew Howroyd, Jun 20 2018

"DIK" transform of A000081.

a(n) = A000081(n) + A027852(n) + A000226(n) + A000368(n) + ... [Geoffrey Critzer, Mar 24 2013]

A302939 Number of signed trees with n nodes and p positive edges. Triangle T(n,p) read by rows, 0<=p

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 2, 3, 3, 2, 3, 6, 9, 6, 3, 6, 16, 27, 27, 16, 6, 11, 37, 79, 96, 79, 37, 11, 23, 96, 233, 349, 349, 233, 96, 23, 47, 239, 679, 1187, 1439, 1187, 679, 239, 47, 106, 622, 1987, 4017, 5639, 5639, 4017, 1987, 622, 106, 235, 1607, 5784, 13216, 21263, 24758, 21263, 13216, 5784, 1607, 235

Offset: 1

R. J. Mathar, Apr 16 2018

			T(2,0)=T(2,1)=1: the tree on 2 nodes (one edge) has one variant with no positive edge and one variant with one positive edge.
T(4,1)=3: the 2 trees on 4 nodes (three edges) have two variants from the linear tree with a positive edge (edge in the middle or at the end) and one variant from the star graph with one positive edge.
T(5,0)=3: there are 3 trees on 5 nodes (4 edges) where all edges are negative.
The triangle starts
    1;
    1,   1;
    1,   1,   1;
    2,   3,   3,    2;
    3,   6,   9,    6,    3;
    6,  16,  27,   27,   16,    6;
   11,  37,  79,   96,   79,   37,  11;
   23,  96, 233,  349,  349,  233,  96,  23;
   47, 239, 679, 1187, 1439, 1187, 679, 239, 47;
  106, 622,...

Andrew Howroyd, Table of n, a(n) for n = 1..1275
Index entries for sequences related to trees

Cf. A000060 (row sums), A000055 (diagonal and 1st column), A027852 (subdiagonal and 2nd column), A304489 (rooted), A331113 (central coefficients).

R(n, y)={my(v=vector(n)); v[1]=1; for(k=1, n-1, my(p=(1+y)*v[k]); my(q=Vec(prod(j=0, poldegree(p, y), (1/(1-x*y^j) + O(x*x^(n\k)))^polcoeff(p, j)))); v=vector(n, j, v[j] + sum(i=1, (j-1)\k, v[j-i*k] * q[i+1]))); v; }
M(n)={my(B=x*Ser(R(n, y))); B - (1+y)*(B^2 - substvec(B, [x, y], [x^2, y^2]))/2}
{ my(A=Vec(M(10))); for(n=1, #A, print(Vecrev(A[n]))) } \\ Andrew Howroyd, May 13 2018

T(n,p) = T(n,n-p-1), flipping all edge signs.

Completed row 10. - R. J. Mathar, Apr 29 2018

Terms a(58) and beyond from Andrew Howroyd, May 13 2018

A000631 Number of ethylene derivatives with n carbon atoms.

Original entry on oeis.org

1, 1, 3, 5, 13, 27, 66, 153, 377, 914, 2281, 5690, 14397, 36564, 93650, 240916, 623338, 1619346, 4224993, 11062046, 29062341, 76581151, 202365823, 536113477, 1423665699, 3788843391, 10103901486, 26995498151, 72253682560, 193706542776

Offset: 2

N. J. A. Sloane

nonn

Number of structural isomers of alkenes C_n H_{2n} with n carbon atoms.
Number of unicyclic graphs of n nodes where a double-edge replaces the cycle, [A217781], end-points of the double-edge of out-degrees <= 2, other nodes having out-degrees <= 3.
Number of rooted trees on n+1 nodes where the root has degree 2, the 2 children of the root have out-degrees <= 2, and the other nodes have out-degrees <= 3.
See illustration of initial terms. - Washington Bomfim, Nov 30 2020

J. L. Faulon, D. Visco and D. Roe, Enumerating Molecules, In: Reviews in Computational Chemistry Vol. 21, Ed. K. Lipkowitz, Wiley-VCH, 2005.
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).

Andrew Howroyd, Table of n, a(n) for n = 2..500
Washington Bomfim, Illustration of initial terms
J. L. Faulon, D. Visco and D. Roe, Enumerating Molecules, In: Reviews in Computational Chemistry Vol. 21, Ed. K. Lipkowitz, Wiley-VCH, 2005.
H. R. Henze and C. M. Blair, The number of structurally isomeric Hydrocarbons of the Ethylene Series, J. Amer. Chem. Soc., 55 (2) (1933), 680-686.
H. R. Henze and C. M. Blair, The number of structurally isomeric Hydrocarbons of the Ethylene Series, J. Amer. Chem. Soc., 55 (2) (1933), 680-685. (Annotated scanned copy)
H. R. Henze and C. M. Blair, The number of structural isomers of the more important types of aliphatic compounds, J. Amer. Chem. Soc., 56 (1) (1934), 157-157.
C.-W. Lam, A Mathematical Relationship between the Number of Isomers of Alkenes and Alkynes: A Result Established from the Enumeration of Isomers of Alkenes from Alky Biradicals, J. Math. Chem., 23, 421 (1998).
R. J. Mathar, Illustration for graphs up to 6 carbons
R. C. Read, Some recent results in chemical enumeration, Lect. Notes Math. 303 (1972), 243-259.
R. C. Read, Some recent results in chemical enumeration, Preprint, circa 1972. (Annotated scanned copy)
R. C. Read, The Enumeration of Acyclic Chemical Compounds, pp. 25-61 of A. T. Balaban, ed., Chemical Applications of Graph Theory, Ac. Press, 1976. [Annotated scanned copy] See p. 28.
N. Trinajstich, Z. Jerievi, J. V. Knop, W. R. Muller and K. Szymanski, Computer Generation of Isomeric Structures, Pure & Appl. Chem., Vol. 55, No. 2, pp. 379-390, 1983.
Index entries for sequences related to rooted trees

Cf. A000642, A000598, A027852 (out-degrees of nodes not limited).

\\ Here G(n) is A000598 as g.f., h is A000642.
seq(n)={my(g=G(n), h=(subst(g, x, x^2) + g^2)/2); Vec(subst(h, x, x^2) + h^2)/2} \\ Andrew Howroyd, Dec 01 2020

a(n) = b(1)b(n-1) + b(2)b(n-2) + b(3)b(n-3) + ... + b(n/2)(b(n/2) + 1)/2 when n is even or b(1)b(n-1) + b(2)b(n-2) + b(3)b(n-3) + ... + b((n-1)/2)b((n + 1)/2) when n is odd, where b(n) = A000642(n). - Herman Jamke (hermanjamke(AT)fastmail.fm), Feb 24 2008
a(n) = Sum_{k=1..(n-1)/2}( f(k) * f(n-k) ) + [n mod 2 = 0] * ( f(n/2)^2 + f(n/2) ) / 2 where f(n) = A000642(n+1). - Washington Bomfim, Nov 29 2020
G.f.: (g(x^2) + g(x)^2)/2 where x*g(x) is the g.f. of A000642. - Andrew Howroyd, Dec 01 2020

More terms from Herman Jamke (hermanjamke(AT)fastmail.fm), Feb 24 2008

A280786 Number of topologically distinct sets of n circles with one pair intersecting.

Original entry on oeis.org

1, 4, 15, 50, 162, 506, 1558, 4727, 14227, 42521, 126506, 374969, 1108476, 3269902, 9630631, 28328999, 83251569, 244471484, 717486860, 2104777227, 6172357873, 18096097750, 53044095421, 155464365080, 455601800970, 1335107222743, 3912330438784, 11464463809180, 33595343643160

Offset: 2

N. J. A. Sloane, Jan 20 2017

nonn

R. J. Mathar, Topologically Distinct Sets of Non-intersecting Circles in the Plane, arXiv:1603.00077 [math.CO], 2016, row sums Table 7.

Row sums of A280787.

Column k=1 of A261070.

A280786 := proc(N)
    if N < 2 then
        0;
    else
        add(A280787(N,f),f=1..N-1) ;
    end if;
end proc:
A280787 := proc(N,f)
    option remember ;
    local Npr,ct ;
    if f = N then
        return 0;
    elif f = N-1 then
        return 1;
    elif f = 1 then
        A280786(N-1)+A280788(N-2) ;
    else
        ct := 0 ;
        for Npr from 1 to N-1 do
            ct := ct+procname(Npr,1)*A033185(N-Npr,f-1) ;
        end do:
        ct ;
    end if;
end proc:
seq(A280786(n),n=2..30) ; # R. J. Mathar, Mar 06 2017

a81[n_] := a81[n] = If[n <= 1, n, Sum[a81[n - j]*DivisorSum[j, #1*a81[#1] &], {j, n - 1}]/(n - 1)];
A027852[n_] := Module[{dh = 0, np}, For[np = 0, np <= n, np++, dh = a81[np]*a81[n - np] + dh]; If[EvenQ[n], dh = a81[n/2] + dh]; dh/2];
A280788[n_] := If[n == 0, 1, Sum[a81[np + 1]*A027852[n - np + 2], {np, 0, n}]];
t[n_] := t[n] = Module[{d, j}, If[n == 1, 1, Sum[Sum[d*t[d], {d, Divisors[j]}]*t[n - j], {j, 1, n - 1}]/(n - 1)]];
b[1, 1, 1] = 1;
b[n_, i_, p_] := b[n, i, p] = If[p > n, 0, If[n == 0, 1, If[Min[i, p] < 1, 0, Sum[b[n - i*j, i - 1, p - j]*Binomial[t[i] + j - 1, j], {j, 0, Min[n/i, p]}]]]]; A033185[n_, k_] := b[n, n, k];
A280786[n_] := If[n < 2, 0, Sum[A280787[n, f], {f, 1, n - 1}]];
A280787[n_, f_] := A280787[n, f] = Module[{ct}, Which[f == n, Return[0], f == n - 1, Return[1], f == 1, Return[A280786[n - 1] + A280788[n - 2]], True, ct = 0; Do[ct += A280787[np, 1]*A033185[n - np, f - 1], {np, 1, n - 1}]]; ct];
Table[A280786[n], {n, 2, 30}] (* Jean-François Alcover, Nov 23 2017, after R. J. Mathar and Alois P. Heinz *)

A339303 Triangle read by rows: T(n,k) is the number of unoriented linear forests with n nodes and k rooted trees.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 4, 3, 2, 1, 9, 6, 6, 2, 1, 20, 16, 15, 8, 3, 1, 48, 37, 41, 22, 12, 3, 1, 115, 96, 106, 69, 38, 15, 4, 1, 286, 239, 284, 194, 124, 52, 20, 4, 1, 719, 622, 750, 564, 377, 189, 77, 24, 5, 1, 1842, 1607, 2010, 1584, 1144, 618, 292, 100, 30, 5, 1

Offset: 1

Andrew Howroyd, Dec 04 2020

Linear forests (A339067) are considered up to reversal of the linear order.

T(n,k) is the number of unlabeled trees on n nodes rooted at two indistinguishable nodes at distance k-1 from each other.

			Triangle read by rows:
    1;
    1,   1;
    2,   1,   1;
    4,   3,   2,   1;
    9,   6,   6,   2,   1;
   20,  16,  15,   8,   3,   1;
   48,  37,  41,  22,  12,   3,  1;
  115,  96, 106,  69,  38,  15,  4,  1;
  286, 239, 284, 194, 124,  52, 20,  4, 1;
  719, 622, 750, 564, 377, 189, 77, 24, 5, 1;
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (rows 1..50)

Columns 1..4 are A000081, A027852, A280788(n-3), A339302.
Row sums are A303840(n+2).
Row sums excluding the first column are A303833.
Cf. A339067.

\\ TreeGf is A000081 as g.f.
TreeGf(N) = {my(A=vector(N, j, 1)); for (n=1, N-1, A[n+1] = 1/n * sum(k=1, n, sumdiv(k, d, d*A[d]) * A[n-k+1] ) ); x*Ser(A)}
ColSeq(n,k)={my(r=TreeGf(max(0,n+1-k))); Vec(r^k + r^(k%2)*subst(r, x, x^2)^(k\2), -n)/2}
M(n, m=n)=Mat(vector(m, k, ColSeq(n,k)~))
{ my(T=M(12)); for(n=1, #T~, print(T[n,1..n])) }

G.f of column k: (r(x)^k + r(x)^(k mod 2)*r(x^2)^floor(k/2))/2 where r(x) is the g.f. of A000081.

A280787 Triangle read by rows: number of topologically distinct sets of n circles with one pair intersecting, by number of factors.

Original entry on oeis.org

1, 3, 1, 10, 4, 1, 30, 15, 4, 1, 91, 50, 16, 4, 1, 268, 162, 55, 16, 4, 1, 790, 506, 185, 56, 16, 4, 1, 2308, 1558, 594, 190, 56, 16, 4, 1, 6737, 4727, 1878, 617, 191, 56, 16, 4, 1, 19609, 14227, 5825, 1970, 622, 191, 56, 16, 4, 1

Offset: 2

N. J. A. Sloane, Jan 20 2017

			Triangle begins:
     1;
     3,    1;
    10,    4,   1;
    30,   15,   4,   1;
    91,   50,  16,   4,  1;
   268,  162,  55,  16,  4,  1;
   790,  506, 185,  56, 16,  4, 1;
  2308, 1558, 594, 190, 56, 16, 4, 1;
...

R. J. Mathar, Topologically Distinct Sets of Non-intersecting Circles in the Plane, arXiv:1603.00077 [math.CO], 2016.

Row sums give A280786.

a81[n_] := a81[n] = If[n <= 1, n, Sum[a81[n - j]*DivisorSum[j, #1*a81[#1] &], {j, n - 1}]/(n - 1)];
A027852[n_] := Module[{dh = 0, np}, For[np = 0, np <= n, np++, dh = a81[np]*a81[n - np] + dh]; If[EvenQ[n], dh = a81[n/2] + dh]; dh/2];
A280788[n_] := If[n == 0, 1, Sum[a81[np+1]*A027852[n-np+2], {np, 0, n}]];
t[n_] := t[n] = Module[{d, j}, If[n == 1, 1, Sum[Sum[d*t[d], {d, Divisors[j]}]*t[n - j], {j, 1, n - 1}]/(n - 1)]];
b[1, 1, 1] = 1;
b[n_, i_, p_] := b[n, i, p] = If[p > n, 0, If[n == 0, 1, If[Min[i, p] < 1, 0, Sum[b[n - i*j, i - 1, p - j]*Binomial[t[i] + j - 1, j], {j, 0, Min[n/i, p]}]]]]; A033185[n_, k_] := b[n, n, k];
A280786[n_] := If[n < 2, 0, Sum[A280787[n, f], {f, 1, n - 1}]];
A280787[n_, f_] := A280787[n, f] = Module[{ct}, Which[f == n, Return[0], f == n - 1, Return[1], f == 1, Return[A280786[n - 1] + A280788[n - 2]], True, ct = 0; Do[ct += A280787[np, 1]*A033185[n - np, f - 1], {np, 1, n - 1}]]; ct];
Table[A280787[n, f], {n, 2, 11}, {f, 1, n - 1}] // Flatten (* Jean-François Alcover, Nov 23 2017, after R. J. Mathar and Alois P. Heinz *)

A370772 Triangle read by rows: T(n,k) is the number of k-trees with n unlabeled nodes rooted at a hedron.

Original entry on oeis.org

0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 3, 1, 1, 0, 1, 6, 3, 1, 1, 0, 1, 16, 10, 3, 1, 1, 0, 1, 37, 39, 10, 3, 1, 1, 0, 1, 96, 164, 48, 10, 3, 1, 1, 0, 1, 239, 746, 253, 48, 10, 3, 1, 1, 0, 1, 622, 3474, 1584, 273, 48, 10, 3, 1, 1, 0, 1, 1607, 16658, 10500, 1913, 273, 48, 10, 3, 1, 1, 0

Offset: 0

Andrew Howroyd, Mar 01 2024

A hedron is a (k+1)-clique.

			Triangle begins:
  0;
  1,   0;
  1,   1,    0;
  1,   1,    1,    0;
  1,   3,    1,    1,   0;
  1,   6,    3,    1,   1,  0;
  1,  16,   10,    3,   1,  1,  0;
  1,  37,   39,   10,   3,  1,  1, 0;
  1,  96,  164,   48,  10,  3,  1, 1, 0;
  1, 239,  746,  253,  48, 10,  3, 1, 1, 0;
  1, 622, 3474, 1584, 273, 48, 10, 3, 1, 1, 0;
  ...

Andrew Gainer-Dewar, Gamma-Species and the Enumeration of k-Trees, Electronic Journal of Combinatorics, Volume 19 (2012), #P45.

Columns k=1..2 are A027852, A063688(n-2).

Cf. A370770 (unrooted), A370771, A370773.

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

A304067 Number of trees with n vertices rooted at a non-edge.

Original entry on oeis.org

0, 0, 1, 3, 9, 27, 79, 233, 679, 1987, 5784, 16864, 49063, 142821, 415439, 1208761, 3516475, 10232428, 29778138, 86682119, 252382445, 735040515, 2141319946, 6239913801, 18188637903, 53033228465, 154674931182, 451247206423

Offset: 1

Brendan McKay, May 05 2018

nonn

			a(3)=1: the non-edge joins two leaves. a(4)=3: The non-edge joins two leaves of the star graph; or the non-edge joins the two leaves of the linear graph; or the non-edge joins a leaf with the node at distance 2.

Cf. A000055 (not rooted), A027852 (rooted at an edge), A304068 (rooted at an oriented non-edge).

a(n) + A027852(n) = A303833(n).

A339524 Number of unordered pairs of rooted trees with a total of n nodes and an even total of leaves.

Original entry on oeis.org

0, 1, 1, 2, 3, 8, 18, 49, 120, 313, 802, 2120, 5591, 14942, 40033, 108108, 293094, 798839, 2185341, 6002085, 16538599, 45716952, 126727195, 352215812, 981268481, 2739930091, 7666333161, 21491833976, 60358490615, 169798048026, 478420333601

Offset: 1

Washington Bomfim, Dec 08 2020

nonn

Equivalently, the number of rooted trees on n+1 nodes, where the root has degree 2, and the number of leaves is even.

Washington Bomfim, Illustration of initial terms
Index entries for sequences related to rooted trees

Cf. A027852, A339525.

a(n) = A027852(n) - A339525(n).

cp's OEIS Frontend

A068051 Number of n-node connected graphs with one cycle, possibly of length 1 or 2.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A302939 Number of signed trees with n nodes and p positive edges. Triangle T(n,p) read by rows, 0<=p

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A000631 Number of ethylene derivatives with n carbon atoms.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Formula

Extensions

A280786 Number of topologically distinct sets of n circles with one pair intersecting.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

A339303 Triangle read by rows: T(n,k) is the number of unoriented linear forests with n nodes and k rooted trees.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A280787 Triangle read by rows: number of topologically distinct sets of n circles with one pair intersecting, by number of factors.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

A370772 Triangle read by rows: T(n,k) is the number of k-trees with n unlabeled nodes rooted at a hedron.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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