1
$\begingroup$

Let $a(n)$ be the number of sets that can be built using length-$n$ combination of either a commas and braces. Here's a manual calculation of $a(n)$ for $0<n<13$ (duplicate sets have been removed)

a(1) = 0
a(2) = 1 {}
a(3) = 0
a(4) = 1 {{}}
a(5) = 0
a(6) = 1 {{{}}}
a(7) = 1 {{},{}}
a(8) = 1 {{{{}}}}
a(9) =  2 {{{},{}}} {{{}},{}}
a(10) = 2  {{{{{}}}}} {{},{},{}}
a(11) =  4 {{{{}}},{}}  {{{{},{}}}} {{{{}},{}}} {{{}}, {{}}}
a(12) =  3 {{...}}   {{{},{},{}}} {{{},{}},{}}

With the help of some crappy Python program I wrote, I extended the sequence further:

a(13) = 7
a(14) = 7
a(15) = 11
a(16) = 16
a(17) = 18
a(18) = 30
a(19) = 34
a(20) = 56
a(21) = 65
a(22) = 102
a(23) = 134
a(24) = 183
a(25) = 275
a(26) = 348
a(27) = 544
a(28) = 699
a(29) = 1057
a(30) = 1441
a(31) = 2062
a(32) = 2982

As of the time of writing, there's no OEIS page for this sequence. Is there a closed-form formula for $a(n)$? If not, is there at least some good approximation?

$\endgroup$
7
  • $\begingroup$ The rules are not clear to me. Why is $a(1) = 0$, couldn't a comma be there ? Why is $a(3) = 0$, what is wrong with $\{ , \}$ ? $\endgroup$
    – true blue anil
    Commented Jun 8 at 4:33
  • $\begingroup$ A set must be a "list" enclosed by braces. A list must either be empty, a set, or a set followed by a comma and a list. $\endgroup$
    – Bryle Morga
    Commented Jun 8 at 5:11
  • 1
    $\begingroup$ The symbolic method gives the OGF equation $A(z)=z^2 \exp\left( \sum_{j=1}^\infty \frac{A(z^j)}{j} (-z)^{j-1} \right)$ which looks hard. I don't know about approximations. It would be easier if we considered lists instead of sets: then the OGF would be $A(z) = \frac{1+2z-z^2+z^3 - \sqrt{1-2z^2-2z^3+z^4-2z^5+z^6}}{2z}$. $\endgroup$
    – ploosu2
    Commented Jun 8 at 9:23
  • 1
    $\begingroup$ Sometimes you give a set with repeated elements listed. For example, in your set for $a(7)=1$, you give $\{ \{ \}, \{ \}\}$. But this set is the same set as $\{\{ \}\}$, since it is the same element twice in the set. Is that ok according to the rules you want to use? $\endgroup$
    – paw88789
    Commented Jun 8 at 12:49
  • 2
    $\begingroup$ But repeating items in a set leads to the headache: is { {},{} } different from { {},{} }? That is, what happens to permutations of the set? $\endgroup$
    – Carl Witthoft
    Commented Jun 8 at 23:00

0

Reset to default

You must log in to answer this question.