[seqfan] Re: Set of sets using minimal number of braces

[franktaw at netscape.net]

The number of sets that can be made with n braces is A004111. This 
sequence has differences which are n repeated A004111(n) times. This 
means that it is actually:

1, 2, 4, 7, 11, 15, 20, 25, 30, 36, ...

More terms (billions of them) can easily be calculated using the values 
in A004111.

This sequence can also be described as the minimum number of nodes in a 
rooted identity tree where the root has n children.

You should submit it.

Franklin T. Adams-Watters

-----Original Message-----
From: Joshua Zucker <joshua.zucker at gmail.com>

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

_______________________________________________

Seqfan Mailing list - http://list.seqfan.eu/