

A237585


Number of structures of size n in class A = o x (o + MSET(A)) where o is a neutral structure of size 1.


1



0, 1, 2, 3, 6, 15, 36, 94, 245, 663, 1815, 5062, 14269, 40706, 117103, 339673, 991834, 2913869, 8605576, 25536300, 76096896, 227634717, 683296679, 2057540487, 6213495745, 18813535942, 57103173296, 173710272584, 529534793886, 1617347972250, 4948744120771
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

MSET(A) is the multichoose function: pick any number of unlabeled structures in A with repetition allowed.
Interpreting the neutral structure of size 1 as a single pointer dereference, A is the class of Apointers either to null pointers or to a multiset of unlabeled Apointers, where the size of a pointer is the number of dereferences required to resolve the entire structure, so a null pointer has size 1 and an Apointer to a null pointer has size 2 and an Apointer to {Apointer(null), Apointer(null), Apointer({Apointer(null)})} has size 1+((1+1)+(1+1)+(1+(1+1)))=8.
a(n) is the number of rooted trees of weight n where leaves can have either weight 1 or 2 and nonleaves have weight 1.  Andrew Howroyd, Mar 02 2020


LINKS

Andrew Howroyd, Table of n, a(n) for n = 0..200
Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge Univ. Press, 2009
Guy P. Srinivasan, C# program to generate sequence


FORMULA

G.f. A(x) satisfies: A(x) = x * (x + exp(A(x) + A(x^2)/2 + A(x^3)/3 + A(x^4)/4 + ...)).  Ilya Gutkovskiy, Jun 11 2021


EXAMPLE

For n = 3 the a(3)=3 pointers are the pointer to the multiset of exactly the pointer to the null pointer, the pointer to the multiset of twice the pointer to the empty multiset, and the pointer to the multiset of exactly the pointer to the multiset of the pointer to the empty multiset.
From Andrew Howroyd, Mar 02 2020: (Start)
The a(2) = 2 trees are: 2, (1).
The a(3) = 3 trees are: (2), (11), ((1)).
The a(4) = 6 trees are: ((2)), (12), (111), ((11)), (1(1)), (((1))).
(End)


PROG

(C#) (see linked code for GetPartitions, Choose, and invoking this)
private static Func<int, long> A237585() {
Func<int, long> A = null;
Func<int, long> B = null;
Func<int, long> C = null;
A = (n) => n == 0 ? 0 : B(n1);
B = (n) => C(n) + (n == 1 ? 1 : 0);
C = (n) =>
{
if (n == 0) return 1;
long sum = 0;
foreach (var partition in GetPartitions(n))
{
long product = 1;
for (int k = 1; k < partition.Count; k++)
{
var N = A(k);
var K = partition[k];
product *= Choose(N + K  1, K);
}
sum += product;
}
return sum;
};
return A;
}
(PARI)
EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))1, #v)}
seq(n)={my(v=[1]); for(n=2, n, v=concat([1], EulerT(v)); v[2]++); concat([0], v)} \\ Andrew Howroyd, Mar 02 2020


CROSSREFS

Sequence in context: A182240 A052102 A053561 * A147773 A006403 A129960
Adjacent sequences: A237582 A237583 A237584 * A237586 A237587 A237588


KEYWORD

nonn


AUTHOR

Guy P. Srinivasan, Feb 09 2014


EXTENSIONS

Terms a(21) and beyond from Andrew Howroyd, Mar 02 2020


STATUS

approved



