login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 11
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 (list; table; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 11 16:42 EDT 2021. Contains 342888 sequences. (Running on oeis4.)