A373516 - OEIS

%I #67 Jul 05 2024 21:43:46

%S 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,

%T 544,699,1057,1441,2062,2982,4094,6109,8341,12386,17298,25089,36066,

%U 51241,75023,105923,155464,221162,321982,464065,669320,974494,1399818,2044983

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

%C 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).

%C It is conjectured that there are only finitely many n such that a(n) > a(n+1), with n=11 being the last example.

%C 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.

%C 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

%F a(n) < 3^n (trivial upper bound).

%F a(n) <= A329691(n). - _Michael S. Branicky_, Jun 08 2024

%F a(3n-2) + a(3n-3) + a(3n-4) > A004111(n) for n > 2. - _Bryle Morga_, Jun 09 2024

%e a(12) = 3. There are 3 sets representable with 12 of either commas, opening braces or closing braces, namely: {{{{{{}}}}}}, {{{}}} = {{{},{},{}}}, {{{}},{}} = {{{},{}},{}}.

%o (Python)

%o def tgen(n):

%o     if n >= 2:

%o         for i in range(2, (n+1)//2):

%o             for S in sgen(i):

%o                 for T in tgen(n-i-1):

%o                     yield f"{S},{T}"

%o         for S in sgen(n):

%o             yield S

%o def sgen(n):

%o     if n == 2:

%o         yield "frozenset({})"

%o     else:

%o         for T in tgen(n-2):

%o             yield "frozenset({"+T+"})"

%o def a(n): return len(set(eval(p) for p in sgen(n)))

%Y Cf. A004111, A329691.

%K nonn,hard

%O 1,9

%A _Bryle Morga_, Jun 08 2024

%E a(45)-a(50) from _Michael S. Branicky_, Jun 08 2024