A052843 A simple grammar.

1, 1, 2, 3, 6, 10, 20, 38, 79, 162, 348, 751, 1661, 3695, 8335, 18919, 43310, 99664, 230700, 536327, 1252298, 2934508, 6900046, 16272771, 38484608, 91243851, 216839820, 516423974, 1232376315, 2946354649, 7056335478, 16926813939, 40665822366, 97836595223, 235697108115, 568531616730

Offset

0,3

Comments

a(n) is the number of forests of rooted unlabeled identity trees. Euler transform of A004111. - Geoffrey Critzer, Oct 13 2012

References

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 64, Eq. (3.3.15); p. 80, Problem 3.10.

Links

Alois P. Heinz, Table of n, a(n) for n = 0..1000

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 811

Formula

O.g.f.: prod(n>=1, 1/(1 - x^n)^A004111(n) ). - Geoffrey Critzer, Oct 13 2012

Maple

spec := [S, {C=Prod(Z, B), B=PowerSet(C), S=Set(C)}, unlabeled]: seq(combstruct[count](spec, size=n), n=0..20);
# second Maple program:
with(numtheory):
b:= proc(n) option remember; `if`(n<2, n, add(b(n-k)*add(d*
       b(d)*(-1)^(k/d+1), d=divisors(k)), k=1..n-1)/(n-1))
    end:
a:= proc(n) option remember; `if`(n=0, 1, add(add(d*b(d),
       d=divisors(j)) *a(n-j), j=1..n)/n)
    end:
seq(a(n), n=0..40);  # Alois P. Heinz, Mar 06 2015

Mathematica

nn=35; 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); it=Table[a[i], {i, 1, nn}]; CoefficientList[Series[Product[1/(1-x^i)^it[[i]], {i, 1, nn}], {x, 0, nn}], x]  (* after code given by Robert A. Russell in A004111 *)
(* Geoffrey Critzer, Oct 13 2012 *)

Crossrefs

Cf. A004111.

Sequence in context: A123423 A005195 A228835 * A120707 A047111 A106741

Adjacent sequences: A052840 A052841 A052842 * A052844 A052845 A052846

Keyword

easy,nonn

Author

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

Extensions

Added more terms, Geoffrey Critzer, Oct 13 2012

Status

approved