login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 multi-choose 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 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.

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

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(n-1);

    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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 25 04:28 EDT 2021. Contains 348237 sequences. (Running on oeis4.)