A373516 Number of sets that can be represented as a length-n combination of commas and braces, with elements possibly repeated.

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

Links

Table of n, a(n) for n=1..50.

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

Cf. A004111, A329691.

Sequence in context: A240010 A283502 A324756 * A324754 A174220 A334871

Adjacent sequences: A373513 A373514 A373515 * A373517 A373518 A373519

Keyword

nonn,hard

Author

Bryle Morga, Jun 08 2024

Extensions

a(45)-a(50) from Michael S. Branicky, Jun 08 2024

Status

approved