A000226 -id:A000226 - cp's OEIS frontend

A033185 Rooted tree triangle read by rows: a(n,k) = number of forests with n nodes and k rooted trees.

1, 1, 1, 2, 1, 1, 4, 3, 1, 1, 9, 6, 3, 1, 1, 20, 16, 7, 3, 1, 1, 48, 37, 18, 7, 3, 1, 1, 115, 96, 44, 19, 7, 3, 1, 1, 286, 239, 117, 46, 19, 7, 3, 1, 1, 719, 622, 299, 124, 47, 19, 7, 3, 1, 1, 1842, 1607, 793, 320, 126, 47, 19, 7, 3, 1, 1, 4766, 4235, 2095, 858, 327, 127, 47, 19, 7, 3, 1, 1

Offset: 1

Christian G. Bower

Leading column: A000081, rows sums: A000081 shifted.
Also, number of multigraphs of k components, n nodes, and no cycles except one loop in each component. See link below to have a picture showing the bijection between rooted forests and multigraphs of this kind. - Washington Bomfim, Sep 04 2010
Number of rooted trees with n+1 nodes and degree of the root is k.- Michael Somos, Aug 20 2018

			Triangle begins:
     1;
     1,    1;
     2,    1,   1;
     4,    3,   1,   1;
     9,    6,   3,   1,   1;
    20,   16,   7,   3,   1,  1;
    48,   37,  18,   7,   3,  1,  1;
   115,   96,  44,  19,   7,  3,  1,  1;
   286,  239, 117,  46,  19,  7,  3,  1,  1;
   719,  622, 299, 124,  47, 19,  7,  3,  1,  1;
  1842, 1607, 793, 320, 126, 47, 19,  7,  3,  1,  1;

Alois P. Heinz, Rows n = 1..141, flattened
W. Bomfim, Bijection between rooted forests and multigraphs without cycles except one loop in each connected component.
R. J. Mathar, Topologically distinct sets of non-intersecting circles in the plane, arXiv:1603.00077 [math.CO] (2016), Table 2.
Index entries for sequences related to rooted trees
Index entries for sequences related to trees

Cf. A000081, A005197, A106240, A181360, A027852 (2nd column), A000226 (3rd column), A029855 (4th column), A336087.

with(numtheory):
t:= proc(n) option remember; local d, j; `if` (n<=1, n,
      (add(add(d*t(d), d=divisors(j))*t(n-j), j=1..n-1))/(n-1))
    end:
b:= proc(n, i, p) option remember; `if`(p>n, 0, `if`(n=0, 1,
      `if`(min(i, p)<1, 0, add(b(n-i*j, i-1, p-j) *
       binomial(t(i)+j-1, j), j=0..min(n/i, p)))))
    end:
a:= (n, k)-> b(n, n, k):
seq(seq(a(n, k), k=1..n), n=1..14);  # Alois P. Heinz, Aug 20 2012

nn=10;f[x_]:=Sum[a[n]x^n,{n,0,nn}];sol=SolveAlways[0 == Series[f[x]-x Product[1/(1-x^i)^a[i],{i,1,nn}],{x,0,nn}],x];a[0]=0;g=Table[a[n],{n,1,nn}]/.sol//Flatten;h[list_]:=Select[list,#>0&];Map[h,Drop[CoefficientList[Series[x Product[1/(1-y x^i)^g[[i]],{i,1,nn}],{x,0,nn}],{x,y}],2]]//Grid  (* Geoffrey Critzer, Nov 17 2012 *)
t[1] = 1; t[n_] := t[n] = Module[{d, j}, 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]}]]]]; a[n_, k_] := b[n, n, k]; Table[a[n, k], {n, 1, 14}, {k, 1, n}] // Flatten (* Jean-François Alcover, Mar 13 2014, after Alois P. Heinz *)

G.f.: 1/Product_{i>=1} (1-x*y^i)^A000081(i). - Vladeta Jovovic, Apr 28 2005

a(n, k) = sum over the partitions of n, 1M1 + 2M2 + ... + nMn, with exactly k parts, of Product_{i=1..n} binomial(A000081(i)+Mi-1, Mi). - Washington Bomfim, May 12 2005

A027852 Number of connected functions on n points with a loop of length 2.

Original entry on oeis.org

0, 1, 1, 3, 6, 16, 37, 96, 239, 622, 1607, 4235, 11185, 29862, 80070, 216176, 586218, 1597578, 4370721, 12003882, 33077327, 91433267, 253454781, 704429853, 1962537755, 5479855546, 15332668869, 42983656210, 120716987723, 339596063606, 956840683968

Offset: 1

Christian G. Bower, Dec 14 1997

nonn

Number of unordered pairs of rooted trees with a total of n nodes.
Equivalently, the number of rooted trees on n+1 nodes where the root has degree 2.
Number of trees on n nodes rooted at an edge. - Washington Bomfim, Jul 06 2012
Guy (1988) calls these tadpole graphs. - N. J. A. Sloane, Nov 04 2014
Number of unicyclic graphs of n nodes with a cycle length of two (in other words, a double edge). - Washington Bomfim, Dec 02 2020

Alois P. Heinz, Table of n, a(n) for n = 1..2136
Washington Bomfim, Illustration of initial terms
R. K. Guy, Letter to N. J. A. Sloane, 1988-04-12 (annotated scanned copy) Includes illustrations for n <= 6.
R. J. Mathar, Topologically distinct sets of non-intersecting circles in the plane, arXiv:1603.00077 [math.CO] (2016), Eq. (75).
Index entries for sequences related to rooted trees

Column 2 of A033185 (forests of rooted trees), A217781 (unicyclic graphs), A339303 (unoriented linear forests) and A339428 (connected functions).

Cf. A000081, A000106, A000226, A000631, A001372, A002861.

with(numtheory): b:= proc(n) option remember; local d, j; `if`(n<=1, n, (add(add(d*b(d), d=divisors(j)) *b(n-j), j=1..n-1))/ (n-1)) end: a:= n-> (add(b(i) *b(n-i), i=0..n) +`if`(irem(n, 2)=0, b(n/2), 0))/2: seq(a(n), n=1..50);  # Alois P. Heinz, Aug 22 2008, revised Oct 07 2011
# second, re-usable version
A027852 := proc(N::integer)
    local dh, Nprime;
    dh := 0 ;
    for Nprime from 0 to N do
        dh := dh+A000081(Nprime)*A000081(N-Nprime) ;
    end do:
    if type(N,'even') then
        dh := dh+A000081(N/2) ;
    end if;
    dh/2 ;
end proc: # R. J. Mathar, Mar 06 2017

Needs["Combinatorica`"];nn = 30; s[n_, k_] := s[n, k] = a[n + 1 - k] + If[n < 2 k, 0, s[n - k, k]]; a[1] = 1; a[n_] := a[n] = Sum[a[i] s[n - 1, i] i, {i, 1, n - 1}]/(n - 1); rt = Table[a[i], {i, 1, nn}]; Take[CoefficientList[CycleIndex[DihedralGroup[2], s] /. Table[s[j] -> Table[Sum[rt[[i]] x^(k*i), {i, 1, nn}], {k, 1, nn}][[j]], {j, 1, nn}], x], {2, nn}]  (* Geoffrey Critzer, Oct 12 2012, after code given by Robert A. Russell in A000081 *)
b[n_] := b[n] = If[n <= 1, n, (Sum[Sum[d b[d], {d, Divisors[j]}] b[n-j], {j, 1, n-1}])/(n-1)];
a[n_] := (Sum[b[i] b[n-i], {i, 0, n}] + If[Mod[n, 2] == 0, b[n/2], 0])/2;
Table[a[n], {n, 1, 50}] (* Jean-François Alcover, Oct 30 2018, after Alois P. Heinz *)

seq(max_n)= { my(V = f = vector(max_n), i=1,s); f[1]=1;
for(j=1, max_n - 1, f[j+1] = 1/j * sum(k=1, j, sumdiv(k,d, d * f[d]) * f[j-k+1]));
for(n = 1, max_n, s = sum(k = 1, (n-1)/2, ( f[k] * f[n-k] ));
if(n % 2 == 1, V[i] = s, V[i] = s + (f[n/2]^2 + f[n/2])/2); i++); V };
\\ Washington Bomfim, Jul 06 2012 and Dec 01 2020

G.f.: A(x) = (B(x)^2 + B(x^2))/2 where B(x) is g.f. of A000081.
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) = A000081(n). - Washington Bomfim, Jul 06 2012 and Dec 01 2020
a(n) ~ c * d^n / n^(3/2), where d = A051491 = 2.9557652856519949747148..., c = A187770 = 0.43992401257102530404090339... . - Vaclav Kotesovec, Sep 12 2014
2*a(n) = A000106(n) + A000081(n/2), where A(.)=0 if the argument is non-integer. - R. J. Mathar, Jun 04 2020

Edited by Christian G. Bower, Feb 12 2002

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.

Original entry on oeis.org

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.

A000368 Number of connected graphs with one cycle of length 4.

Original entry on oeis.org

1, 1, 4, 9, 28, 71, 202, 542, 1507, 4114, 11381, 31349, 86845, 240567, 668553, 1860361, 5188767, 14495502, 40572216, 113743293, 319405695, 898288484, 2530058013, 7135848125, 20152898513, 56986883801

Offset: 4

N. J. A. Sloane

nonn

F. Harary and E. Palmer, Graphical Enumeration, Academic Press, 1973, page 69.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 150.
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).

Vaclav Kotesovec, Table of n, a(n) for n = 4..2000 (terms 4..43 from Sean A. Irvine, 44..200 from Washington Bomfim)
Washington Bomfim, Illustration of initial terms

Column k=4 of A217781.
Cf. A000081, A000226, A001429, A005703.
Second diagonal of A058879.

Needs["Combinatorica`"]; nn = 30; s[n_, k_] := s[n, k] = a[n + 1 - k] + If[n < 2 k, 0, s[n - k, k]]; a[1] = 1; a[n_] := a[n] = Sum[a[i] s[n - 1, i] i, {i, 1, n - 1}]/(n - 1); rt = Table[a[i], {i, 1, nn}]; Take[CoefficientList[CycleIndex[DihedralGroup[4], s] /. Table[s[j] -> Table[Sum[rt[[i]] x^(k*i), {i, 1, nn}], {k, 1, nn}][[j]], {j, 1, nn}], x], {5, nn}]  (* Geoffrey Critzer, Oct 12 2012, after code given by Robert A. Russell in A000081 *)
A000081 = Rest[Cases[ Import["https://oeis.org/A000081/b000081.txt", "Table"], {, }][[All, 2]]]; max = 30; g81 = Sum[A000081[[k]]*x^k, {k, 1, max}]; g81x2 = Sum[A000081[[k]]*x^(2 k), {k, 1, max}]; g81x4 = Sum[A000081[[k]]*x^(4 k), {k, 1, max}]; Drop[CoefficientList[ Series[(2*g81x4 + 3*g81x2^2 + 2*g81^2*g81x2 + g81^4)/8, {x, 0, max}], x], 4] (* Vaclav Kotesovec, Dec 25 2020 *)

g(Q)={my(V=Vec(Q),D=Set(V),d=#D); if(d==4,return(3*f[D[1]]*f[D[2]]*f[D[3]]*f[D[4]]));
if(d==1, return((f[D[1]]^4+2*f[D[1]]^3+3*f[D[1]]^2+2*f[D[1]])/8));
my(k=1, m = #select(x->x == D[k],V), t); while(m==1, k++; m = #select(x->x == D[k], V)); t = D[1]; D[1] = D[k]; D[k] = t;
if(d == 3, return( f[D[1]] * f[D[2]] * f[D[3]] * (3 * f[D[1]] + 1)/2 ) );
if(m==3, return(f[D[1]]^2 * f[D[2]] * (f[D[1]] + 1)/2));
((3*f[D[2]]^2 + f[D[2]])*f[D[1]]^2 + (f[D[2]]^2 + 3*f[D[2]])*f[D[1]])/4 };
seq(max_n) = { my(s, a = vector(max_n), U); f = vector(max_n); f[1] = 1;
for(j=1, max_n - 1, if(j%100==0,print(j)); f[j+1] = 1/j * sum(k=1, j, sumdiv(k,d, d * f[d]) * f[j-k+1]));
for(n=4, max_n, s=0; forpart(Q = n, if( (Q[4] > Q[3]) && (Q[3]-1 > Q[2]),
      U = U / (f[Q[4] + 1] * f[Q[3] - 1]) * f[Q[4]] * f[Q[3]],  U = g(Q)); s += U,
[1,n],[4,4]); a[n] = s; if(n % 100 == 0, print(n": " s))); a[4..max_n] };
\\ Washington Bomfim, Jul 19 2012 and Dec 22 2020

From Washington Bomfim, Jul 19 2012 and Dec 22 2020: (Start)
a(n) = Sum_{P}( g(Q) ), where P is the set of the partitions Q of n with 4 parts, Q with distinct parts D[1]..D[d], D[1] the part of maximum multiplicity m in Q, f(n) = A000081(n), and g(Q) given by,
       | 3 * f(D[1]) * f(D[2]) * f(D[3]) * f(D[4]),              if d = 4,
       | (f(D[1])^4 + 2*f(D[1])^3 + 3*f(D[1])^2 + 2*f(D[1]))/8,  if d = 1,
g(Q) = | f(D[1]) * f(D[2]) * f(D[3]) * (3 * f(D[1]) + 1)/2,      if d = 3,
       | ((3*f(D[2])^2+f(D[2]))*f(D[1])^2+(f(D[2])^2+3*f(D[2]))*f(D[1]))/4,
       |                                                   if d=2, and m=2,
       | f(D[1])^2 * f(D[2]) * (f(D[1]) + 1)/2,            if d=2, and m=3.
(End)
G.f.: (2*t(x^4) + 3*t(x^2)^2 + 2*t(x)^2*t(x^2) + t(x)^4)/8 where t(x) is the g.f. of A000081. - Andrew Howroyd, Dec 03 2020
a(n) ~ (A187770 + A339986) * A051491^n / (2 * n^(3/2)). - Vaclav Kotesovec, Dec 25 2020

More terms from Vladeta Jovovic, Apr 20 2000
Definition improved by Franklin T. Adams-Watters, May 16 2006
More terms from Sean A. Irvine, Nov 14 2010

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

A029855 Number of rooted trees where root has degree 4.

Original entry on oeis.org

1, 1, 3, 7, 19, 46, 124, 320, 858, 2282, 6161, 16647, 45352, 123861, 340000, 936098, 2586518, 7166394, 19911638, 55456892, 154814055, 433081632, 1213901668, 3408659401, 9587879987, 27011564035, 76212078500

Offset: 5

Christian G. Bower

nonn

Fourth column of A033185. - Michael Somos, Aug 20 2018

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 53.

Washington Bomfim, Table of n, a(n) for n = 5..200
Frank Ruskey, Combinatorial Generation Algorithm 4.26, p. 96
Eric Weisstein's World of Mathematics, Frequency Representation
Eric Weisstein's World of Mathematics, Rooted Tree
Index entries for sequences related to rooted trees

Cf. A000226 (root degree 3), A000081, A033185.

Needs["Combinatorica`"];
nn=30;s[n_,k_]:=s[n,k]=a[n+1-k]+If[n<2k,0,s[n-k,k]];a[1]=1;a[n_]:=a[n]=Sum[a[i]s[n-1,i]i,{i,1,n-1}]/(n-1);rt=Table[a[i],{i,1,nn}];Drop[Take[CoefficientList[CycleIndex[SymmetricGroup[4],s]/.Table[s[j]->Table[Sum[rt[[i]]x^(k*i),{i,1,nn}],{k,1,nn}][[j]],{j,1,nn}],x],nn],4]  (* Geoffrey Critzer, Oct 14 2012, after code by Robert A. Russell in A000081 *)

max_n = 200; f=vector(max_n);            \\ f[n] = A000081[n], n=1..max_n
sum2(k) = {local(s); s=0; fordiv(k, d, s += d*f[d]); return(s)};
Init_f()={f[1]=1;
for(n =1, max_n -2, s=0; for(k=1, n, s+=sum2(k)*f[n-k+1]); f[n+1]=s/n)};
S=0; P=[0,1,1,1,1,0];
visit4() = {i = 3; k = 2; p = P[2]; Pr = 1;
while(1, while(P[i]==p, i++);c=i-k;Pr*=binomial(f[P[k]]+c-1, c);
if(P[i] == 0, S += Pr; return); p = P[i]; k = i; i++)};
                                         \\ F. Ruskey partition generator
Part(n, k, s, t) = { P[t] = s;
if((k == 1) || (n == k), visit4(), L = max(1, ceil((n - s)/(k - 1)));
for(j = L, min(s, n-s-k+2), Part(n-s, k-1, j, t+1))); P[t] = 1;};
\\
a(n) = {S=0; n--; Part(2*n,4+1,n,1); return(S)}
Init_f(); for(n=5, max_n, print(n, " ", a(n)))           \\ b-file format
\\ # Washington Bomfim, Jul 10 2012

a(n)= Sum_(P){ Prod_(1^a1 2^a2 3^a3 ...){ binomial(f(i)+a_i -1, a_i) } }, where P is the set of the partitions of n with four parts, and f = A000081. - Washington Bomfim, Jul 10 2012

a(n) ~ c * A051491^n / n^(3/2), where c = 0.036592912312268101787903577... - Vaclav Kotesovec, Dec 26 2020

cp's OEIS Frontend

A033185 Rooted tree triangle read by rows: a(n,k) = number of forests with n nodes and k rooted trees.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A027852 Number of connected functions on n points with a loop of length 2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

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

A000368 Number of connected graphs with one cycle of length 4.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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