cp's OEIS Frontend

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

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