[seqfan] Set of sets using minimal number of braces

[Joshua Zucker]

Hi folks,
I was working with some 5th graders today on an introduction to set
theory and we came up with a question whose answer doesn't appear to
be in the OEIS.

The question is, what's the minimal number of braces required to make
an n-element set?

For a zero-element set, {} is one set of braces.
For a one-element set, {{}} is two sets of braces.
For a two-element set, {{},{{}}} is four sets of braces.
For a three-element set, {{},{{}},{{{}}}} is seven sets of braces.
You might think from this pattern that we're on the usual 1, 2, 4, 7,
11, but then it's 15 next, not 16, because there are two different
four-sets-of-braces objects you can put in, so the five-element set is
{{}, {{}}, {{{}}}, {{{{}}}}, {{},{{}}}} and you save one set of
braces.

This leaves me pretty sure that the sequence is 1, 2, 4, 7, 11, 15,
20, 25, 31, 37, ... but I'm not sure how to create more terms.
The first differences of this sequence are also interesting.
And, the sequence of how many different sets can be produced with n
sets of braces also looks good.

Any ideas about how to automate the calculation of a bunch of terms of
these things?  Or even better, a pointer to a known formula?

Thanks,
--Joshua Zucker