|
%I #19 Apr 04 2024 10:56:44
%S 0,1,2,3,6,15,36,94,245,663,1815,5062,14269,40706,117103,339673,
%T 991834,2913869,8605576,25536300,76096896,227634717,683296679,
%U 2057540487,6213495745,18813535942,57103173296,173710272584,529534793886,1617347972250,4948744120771
%N Number of structures of size n in class A = o x (o + MSET(A)) where o is a neutral structure of size 1.
%C MSET(A) is the multi-choose function: pick any number of unlabeled structures in A with repetition allowed.
%C Interpreting the neutral structure of size 1 as a single pointer dereference, A is the class of A-pointers either to null pointers or to a multiset of unlabeled A-pointers, 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 A-pointer to a null pointer has size 2 and an A-pointer to {A-pointer(null), A-pointer(null), A-pointer({A-pointer(null)})} has size 1+((1+1)+(1+1)+(1+(1+1)))=8.
%C a(n) is the number of rooted trees of weight n where leaves can have either weight 1 or 2 and non-leaves have weight 1. - _Andrew Howroyd_, Mar 02 2020
%H Andrew Howroyd, <a href="/A237585/b237585.txt">Table of n, a(n) for n = 0..200</a>
%H Philippe Flajolet and Robert Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/AnaCombi/anacombi.html">Analytic Combinatorics</a>, Cambridge Univ. Press, 2009
%H Guy P. Srinivasan, <a href="/A237585/a237585.txt">C# program to generate sequence</a>
%F 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
%e 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.
%e From _Andrew Howroyd_, Mar 02 2020: (Start)
%e The a(2) = 2 trees are: 2, (1).
%e The a(3) = 3 trees are: (2), (11), ((1)).
%e The a(4) = 6 trees are: ((2)), (12), (111), ((11)), (1(1)), (((1))).
%e (End)
%o (C#) // See linked code for GetPartitions, Choose, and invoking this.
%o private static Func<int, long> A237585() {
%o Func<int, long> A = null;
%o Func<int, long> B = null;
%o Func<int, long> C = null;
%o A = (n) => n == 0 ? 0 : B(n-1);
%o B = (n) => C(n) + (n == 1 ? 1 : 0);
%o C = (n) =>
%o {
%o if (n == 0) return 1;
%o long sum = 0;
%o foreach (var partition in GetPartitions(n))
%o {
%o long product = 1;
%o for (int k = 1; k < partition.Count; k++)
%o {
%o var N = A(k);
%o var K = partition[k];
%o product *= Choose(N + K - 1, K);
%o }
%o sum += product;
%o }
%o return sum;
%o };
%o return A;
%o }
%o (PARI)
%o EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
%o seq(n)={my(v=[1]); for(n=2, n, v=concat([1], EulerT(v)); v[2]++); concat([0],v)} \\ _Andrew Howroyd_, Mar 02 2020
%K nonn
%O 0,3
%A _Guy P. Srinivasan_, Feb 09 2014
%E Terms a(21) and beyond from _Andrew Howroyd_, Mar 02 2020
| 