login
A373516
Number of sets that can be represented as a length-n combination of commas and braces, with elements possibly repeated.
0
0, 1, 0, 1, 0, 1, 1, 1, 2, 2, 4, 3, 7, 7, 11, 16, 18, 30, 34, 56, 65, 102, 134, 183, 275, 348, 544, 699, 1057, 1441, 2062, 2982, 4094, 6109, 8341, 12386, 17298, 25089, 36066, 51241, 75023, 105923, 155464, 221162, 321982, 464065, 669320, 974494, 1399818, 2044983
OFFSET
1,9
COMMENTS
Repeated elements can be in any combination at any point, so for instance the nested set {{{}}} has a representation {{{}},{{},{}}} and so counts at that length (n=14).
It is conjectured that there are only finitely many n such that a(n) > a(n+1), with n=11 being the last example.
A004111(n) is the number of sets that can be made with n pairs of braces. Notice how all sets with n braces use at most n-2 commas. If a set uses fewer, then one can add ",{}", without changing the set, until the number of characters used is either 3n-2, 3n-3, or 3n-4. This is sufficient to show that a(n) grows exponentially and that a(n+1)/a(n) > 1.36... This goes well with the empirical observation that 1.44 < a(n+1)/a(n) < 1.46.
Bounded above by A329691, the total number of length-n combinations of commas and braces that represents a set. - Michael S. Branicky, Jun 08 2024
FORMULA
a(n) < 3^n (trivial upper bound).
a(n) <= A329691(n). - Michael S. Branicky, Jun 08 2024
a(3n-2) + a(3n-3) + a(3n-4) > A004111(n) for n > 2. - Bryle Morga, Jun 09 2024
EXAMPLE
a(12) = 3. There are 3 sets representable with 12 of either commas, opening braces or closing braces, namely: {{{{{{}}}}}}, {{{}}} = {{{},{},{}}}, {{{}},{}} = {{{},{}},{}}.
PROG
(Python)
def tgen(n):
if n >= 2:
for i in range(2, (n+1)//2):
for S in sgen(i):
for T in tgen(n-i-1):
yield f"{S}, {T}"
for S in sgen(n):
yield S
def sgen(n):
if n == 2:
yield "frozenset({})"
else:
for T in tgen(n-2):
yield "frozenset({"+T+"})"
def a(n): return len(set(eval(p) for p in sgen(n)))
CROSSREFS
Sequence in context: A240010 A283502 A324756 * A324754 A174220 A334871
KEYWORD
nonn,hard
AUTHOR
Bryle Morga, Jun 08 2024
EXTENSIONS
a(45)-a(50) from Michael S. Branicky, Jun 08 2024
STATUS
approved