A000368 -id:A000368 - cp's OEIS frontend

A217781 Triangular array read by rows: T(n,k) is the number of n-node connected graphs with exactly one cycle of length k (and no other cycles) for n >= 1 and 1 <= k <= n.

1, 1, 1, 2, 1, 1, 4, 3, 1, 1, 9, 6, 3, 1, 1, 20, 16, 7, 4, 1, 1, 48, 37, 18, 9, 4, 1, 1, 115, 96, 44, 28, 10, 5, 1, 1, 286, 239, 117, 71, 32, 13, 5, 1, 1, 719, 622, 299, 202, 89, 45, 14, 6, 1, 1, 1842, 1607, 793, 542, 264, 130, 52, 17, 6, 1, 1

Offset: 1

Geoffrey Critzer, Mar 24 2013

Note that the structures counted in columns 1 and 2 are not simple graphs as we are allowing a self loop (column 1) and a double edge (column 2).

			Triangle begins:
    1;
    1,   1;
    2,   1,   1;
    4,   3,   1,   1;
    9,   6,   3,   1,   1;
   20,  16,   7,   4,   1,   1;
   48,  37,  18,   9,   4,   1,   1;
  115,  96,  44,  28,  10,   5,   1,   1;
  286, 239, 117,  71,  32,  13,   5,   1,   1;
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (rows 1..50)
Washington G. Bomfim, A picture of the twenty one unicycles with 3, 4, 5 and 6 vertices.

Cf. A068051 (row sums), A001429 (row sums for columns >= 3).
Cf. A000081 (column 1), A027852 (column 2), A000226 (column 3), A000368 (column 4).
Cf. A339428 (directed cycle).

nn=15;f[list_]:=Select[list,#>0&];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[f,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]]//Grid

\\ 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(t=TreeGf(max(0,n+1-k))); my(g(e)=subst(t + O(x*x^(n\e)), x, x^e) + O(x*x^n)); Vec(sumdiv(k, d, eulerphi(d)*g(d)^(k/d))/k + if(k%2, g(1)*g(2)^(k\2), (g(1)^2+g(2))*g(2)^(k/2-1)/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])) } \\ Andrew Howroyd, Dec 03 2020

O.g.f. for column k is Z(D[k],A(x)). That is, we substitute for each variable s[i] in the cycle index of the dihedral group of order 2k the series A(x^i), where A(x) is the o.g.f. for A000081.

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

Original entry on oeis.org

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]

A339986 Decimal expansion of a constant related to the asymptotics of A339984.

Original entry on oeis.org

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

Offset: 0

Vaclav Kotesovec, Dec 25 2020

			0.057844678784856058922672857484093392503110392...

Vaclav Kotesovec, Table of n, a(n) for n = 0..1000

Cf. A000226, A000368, A187770, A339984, A339985.

Equals lim_{n->infinity} A339984(n) * n^(3/2) / A051491^n.

A058879 Triangle read by rows: T(n,k) = number of connected graphs with one cycle of length m = n - k + 1 and n nodes (n >= 3 and 1 <= k <= n - 2).

Original entry on oeis.org

1, 1, 1, 1, 1, 3, 1, 1, 4, 7, 1, 1, 4, 9, 18, 1, 1, 5, 10, 28, 44, 1, 1, 5, 13, 32, 71, 117, 1, 1, 6, 14, 45, 89, 202, 299, 1, 1, 6, 17, 52, 130, 264, 542, 793, 1, 1, 7, 19, 69, 163, 413, 751, 1507, 2095, 1, 1, 7, 22, 79, 224, 544, 1221, 2179, 4114, 5607

Offset: 3

N. J. A. Sloane, Jan 07 2001

Diagonals give A000226, A000368. Row sums give A001429.
From Washington Bomfim, Jul 06 2008: (Start)
T(n,3) = 2 + floor(m/2). When k = 3, n = m + 2, so we have unicyclic graphs of order m+2 with a cycle of length m. Only two nodes of those graphs belong to the rooted trees attached to the cycle, so the orders of those trees can be only 1, 2, or 3.
We can have only one tree of order 3 in those graphs. So the two different rooted trees of order 3 correspond to two unicycles.
We can have two trees of order 2 in those graphs. Those trees can be rooted at two points r_1, r_2 of the cycle in h = floor(m/2) ways. They can be neighbors, i.e., we have an edge of the cycle (r_1, r_2). They can be 2, 3, ..., h edges apart, but they cannot be h+1 edges away from each other. This is true because we obtain an isomorphic graph if r_1 and r_2 are h+1 (or more) edges apart, since there are also n - (h+1) edges between r_1 and r_2 and n-h-1 <= h. Note that there is only one rooted tree of order two.
The five unicyclic graphs of order 9 with a cycle of length 7 are depicted in the picture corresponding to the link.
T(n,4) = 4 + 2floor(m/2) + nearest integer to m^2/12.
We have unicyclic graphs of order m+3 with a cycle of length m. Only three nodes of those graphs belong to the rooted trees attached to the cycle, so the orders of those trees can be only 1, 2, 3, or 4. The set of unicycles can be divided in graphs with trees of orders
4,1,1,...,1
3,2,1,...,1
2,2,2,1,...,1.
Since there are 4 rooted trees of order 4, the orders 4,1,1,...,1 correspond to 4 unicycles.
The orders 3,2,1,...,1 correspond to 2floor(m/2) unicycles. For each one of the two rooted trees of order 3, we see above that there are floor(m/2) possibilities to choose a root for the tree of order 2.
The orders 2,2,2,1,...,1 correspond to i unicycles, i = nearest integer to m^2/12. This follows from the number of necklaces with n+3 beads 3 of which are red, that is equal to the nearest integer to (n+3)^2/12. See A001399. In our case we have necklaces with m beads. The 3 red beads are the roots of the trees of order 2. (End)

			Triangle begins:
  1;
  1,  1;
  1,  1,  3;
  1,  1,  4,  7;
  1,  1,  4,  9, 18;

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 69, (3.4.1).
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 150, Table 9.

Washington Bomfim, The five unicyclic graphs of order 9 with a cycle of length 7: T(9,3)=5.

Cf. A000081, A217781.

Needs["NumericalDifferentialEquationAnalysis`"];
t[n_, k_] := Block[{x}, Coefficient[CycleIndexPolynomial[DihedralGroup[n + 1 - k], Table[ButcherTreeCount[n].x^(p Range[n]), {p, n + 1 - k}]], x, n]];
Table[t[n, k], {n, 13}, {k, 1, n - 2}] // Flatten
(* requires Mathematica 9+; Andrey Zabolotskiy, May 12 2017 *)

T(n, k) = [x^n] Z(D_{n+1-k}; t(x)) where t(x) is the g.f. of A000081 and Z(D_m) is the cycle index of the dihedral group of order m. - Sean A. Irvine, Sep 03 2022

More terms from Washington Bomfim, May 12 2008
More terms from Washington Bomfim, Jul 06 2008
Rows n = 11 to 13 added, name and offset corrected by Andrey Zabolotskiy, May 12 2017

cp's OEIS Frontend

A217781 Triangular array read by rows: T(n,k) is the number of n-node connected graphs with exactly one cycle of length k (and no other cycles) for n >= 1 and 1 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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

A339986 Decimal expansion of a constant related to the asymptotics of A339984.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A058879 Triangle read by rows: T(n,k) = number of connected graphs with one cycle of length m = n - k + 1 and n nodes (n >= 3 and 1 <= k <= n - 2).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions