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,4

Comments

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).

Links

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.

Formula

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.

Example

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;
  ...

Mathematica

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

Prog

(PARI) \\ 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

Crossrefs

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).

Sequence in context: A103574 A112682 A033185 * A339428 A204849 A105632

Adjacent sequences: A217778 A217779 A217780 * A217782 A217783 A217784

Keyword

nonn,tabl

Author

Geoffrey Critzer, Mar 24 2013

Status

approved