A317875 Number of achiral free pure multifunctions with n unlabeled leaves.

1, 1, 3, 9, 30, 102, 369, 1362, 5181, 20064, 79035, 315366, 1272789, 5185080, 21296196, 88083993, 366584253, 1533953100, 6449904138, 27238006971, 115475933202, 491293053093, 2096930378415, 8976370298886, 38528771056425, 165784567505325

Offset

1,3

Comments

An achiral free pure multifunction is either (case 1) the leaf symbol "o", or (case 2) a nonempty expression of the form h[g, ..., g], where h and g are both achiral free pure multifunctions.

Links

Andrew Howroyd, Table of n, a(n) for n = 1..200

Formula

a(1) = 1; a(n > 1) = Sum_{0 < k < n} a(n - k) * Sum_{d|k} a(d).

From Ilya Gutkovskiy, Apr 30 2019: (Start)

G.f. A(x) satisfies: A(x) = x + A(x) * Sum_{k>=1} A(x^k).

G.f.: A(x) = Sum_{n>=1} a(n)*x^n = x + (Sum_{n>=1} a(n)*x^n) * (Sum_{n>=1} a(n)*x^n/(1 - x^n)). (End)

Example

The first 4 terms count the following multifunctions.
o,
o[o],
o[o,o], o[o[o]], o[o][o],
o[o,o,o], o[o[o][o]], o[o[o[o]]], o[o[o,o]], o[o][o,o], o[o][o[o]], o[o][o][o], o[o,o][o], o[o[o]][o].

Mathematica

a[n_]:=If[n==1, 1, Sum[a[n-k]*Sum[a[d], {d, Divisors[k]}], {k, n-1}]];
Array[a, 12]

Prog

(PARI) seq(n)={my(p=O(x)); for(n=1, n, p = x + p*(sum(k=1, n-1, subst(p + O(x^(n\k+1)), x, x^k)) ) + O(x*x^n)); Vec(p)} \\ Andrew Howroyd, Aug 19 2018
(PARI) seq(n)={my(v=vector(n)); v[1]=1; for(n=2, #v, v[n]=sum(i=1, n-1, v[i]*sumdiv(n-i, d, v[d]))); v} \\ Andrew Howroyd, Aug 19 2018

Crossrefs

Cf. A001003, A001678, A002033, A003238, A052893, A053492, A067824, A167865, A214577, A277996, A280000, A317853.

Cf. A317876, A317877, A317878, A317879, A317880, A317881.

Cf. A317882, A317883, A317884, A317885.

Sequence in context: A257641 A048119 A304823 * A056333 A148948 A148949

Adjacent sequences: A317872 A317873 A317874 * A317876 A317877 A317878

Keyword

nonn

Author

Gus Wiseman, Aug 09 2018

Status

approved