A348532 a(n) is the number of multisets of integers that are possible to reach by starting with n occurrences of 0 and by splitting and reverse splitting.
1, 1, 2, 2, 7, 9, 43, 59, 338, 490, 3097, 4639, 31283, 48107, 338553, 531469, 3857036, 6157068, 45713546, 73996100
Offset: 0
Examples
For n = 5, the multisets are as follows:
{{0,0,0,0,0}} {{-1,0,0,0,1}} {{-1,-1,0,1,1}}
{{-1,-1,0,0,2}} {{-1,-1,-1,1,2}} {{-2,0,0,1,1}}
{{-2,0,0,0,2}} {{-2,-1,1,1,1}} {{-2,-1,0,1,2}}.
Therefore, a(5) = 9.
For n = 6, the multisets are as follows:
{{0,0,0,0,0,0}} {{-1,0,0,0,0,1}} {{-1,-1,0,0,1,1}}
{{-1,-1,0,0,0,2}} {{-1,-1,-1,1,1,1}} {{-1,-1,-1,0,1,2}}
{{-1,-1,-1,0,0,3}}* {{-1,-1,-1,-1,2,2}}* {{-1,-1,-1,-1,1,3}}*
{{-2,0,0,0,1,1}} {{-2,0,0,0,0,2}} {{-2,-1,0,1,1,1}}
{{-2,-1,0,0,1,2}} {{-2,-1,0,0,0,3}}* {{-2,-1,-1,1,1,2}}
{{-2,-1,-1,0,2,2}} {{-2,-1,-1,0,1,3}} {{-2,-1,-1,-1,2,3}}*
{{-2,-2,1,1,1,1}}* {{-2,-2,0,1,1,2}} {{-2,-2,0,0,2,2}}
{{-2,-2,0,0,1,3}} {{-2,-2,-1,1,2,2}} {{-2,-2,-1,1,1,3}}
{{-2,-2,-1,0,2,3}} {{-2,-2,-2,2,2,2}}* {{-2,-2,-2,1,2,3}}*
{{-3,0,0,0,0,3}}* {{-3,0,0,0,1,2}}* {{-3,0,0,1,1,1}}*
{{-3,-1,1,1,1,1}}* {{-3,-1,0,1,1,2}} {{-3,-1,0,0,2,2}}
{{-3,-1,0,0,1,3}} {{-3,-1,-1,1,2,2}} {{-3,-1,-1,1,1,3}}
{{-3,-1,-1,0,2,3}} {{-3,-2,1,1,1,2}}* {{-3,-2,0,1,2,2}}
{{-3,-2,0,1,1,3}} {{-3,-2,0,0,2,3}} {{-3,-2,-1,2,2,2}}*
{{-3,-2,-1,1,2,3}}.
Therefore, a(6) = 43.
The ones marked with an asterisk are the ones that need reverse splitting
to be reached. They are not produced using the rules of A347913.
Programs
-
Python
def nextq(q): used, used2 = set(), set() for i in range(len(q)-1): for j in range(i+1, len(q)): if q[i] == q[j]: if q[i] in used: continue used.add(q[i]) qc = list(q); qc[i] -= 1; qc[j] += 1 yield tuple(sorted(qc)) elif q[j] - q[i] == 2: # assumes q is sorted if q[i] in used2: continue used2.add(q[i]) qc = list(q); qc[i] += 1; qc[j] -= 1 yield tuple(sorted(qc)) def a(n): s = tuple(0 for i in range(n)); reach = {s}; expand = list(reach) while len(expand) > 0: q = expand.pop() for qq in nextq(q): if qq not in reach: reach.add(qq) expand.append(qq) return len(reach) print([a(n) for n in range(13)]) # Michael S. Branicky, Oct 21 2021
Formula
It appears that a(n) = A000571(n) for odd n.
Extensions
a(6)-a(19) from Michael S. Branicky, Oct 21 2021
Comments