login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

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

%I #81 Nov 19 2021 07:44:42

%S 1,1,2,2,7,9,43,59,338,490,3097,4639,31283,48107,338553,531469,

%T 3857036,6157068,45713546,73996100

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

%C Splitting is taking 2 occurrences of the same integer and incrementing one of them by 1 and decrementing the other occurrence by 1.

%C Reverse splitting is taking two elements with a difference of 2 and incrementing the smaller one by 1 and decrementing the larger one by 1. It is the opposite of splitting.

%F It appears that a(n) = A000571(n) for odd n.

%e For n = 5, the multisets are as follows:

%e {{0,0,0,0,0}} {{-1,0,0,0,1}} {{-1,-1,0,1,1}}

%e {{-1,-1,0,0,2}} {{-1,-1,-1,1,2}} {{-2,0,0,1,1}}

%e {{-2,0,0,0,2}} {{-2,-1,1,1,1}} {{-2,-1,0,1,2}}.

%e Therefore, a(5) = 9.

%e For n = 6, the multisets are as follows:

%e {{0,0,0,0,0,0}} {{-1,0,0,0,0,1}} {{-1,-1,0,0,1,1}}

%e {{-1,-1,0,0,0,2}} {{-1,-1,-1,1,1,1}} {{-1,-1,-1,0,1,2}}

%e {{-1,-1,-1,0,0,3}}* {{-1,-1,-1,-1,2,2}}* {{-1,-1,-1,-1,1,3}}*

%e {{-2,0,0,0,1,1}} {{-2,0,0,0,0,2}} {{-2,-1,0,1,1,1}}

%e {{-2,-1,0,0,1,2}} {{-2,-1,0,0,0,3}}* {{-2,-1,-1,1,1,2}}

%e {{-2,-1,-1,0,2,2}} {{-2,-1,-1,0,1,3}} {{-2,-1,-1,-1,2,3}}*

%e {{-2,-2,1,1,1,1}}* {{-2,-2,0,1,1,2}} {{-2,-2,0,0,2,2}}

%e {{-2,-2,0,0,1,3}} {{-2,-2,-1,1,2,2}} {{-2,-2,-1,1,1,3}}

%e {{-2,-2,-1,0,2,3}} {{-2,-2,-2,2,2,2}}* {{-2,-2,-2,1,2,3}}*

%e {{-3,0,0,0,0,3}}* {{-3,0,0,0,1,2}}* {{-3,0,0,1,1,1}}*

%e {{-3,-1,1,1,1,1}}* {{-3,-1,0,1,1,2}} {{-3,-1,0,0,2,2}}

%e {{-3,-1,0,0,1,3}} {{-3,-1,-1,1,2,2}} {{-3,-1,-1,1,1,3}}

%e {{-3,-1,-1,0,2,3}} {{-3,-2,1,1,1,2}}* {{-3,-2,0,1,2,2}}

%e {{-3,-2,0,1,1,3}} {{-3,-2,0,0,2,3}} {{-3,-2,-1,2,2,2}}*

%e {{-3,-2,-1,1,2,3}}.

%e Therefore, a(6) = 43.

%e The ones marked with an asterisk are the ones that need reverse splitting

%e to be reached. They are not produced using the rules of A347913.

%o (Python)

%o def nextq(q):

%o used, used2 = set(), set()

%o for i in range(len(q)-1):

%o for j in range(i+1, len(q)):

%o if q[i] == q[j]:

%o if q[i] in used: continue

%o used.add(q[i])

%o qc = list(q); qc[i] -= 1; qc[j] += 1

%o yield tuple(sorted(qc))

%o elif q[j] - q[i] == 2: # assumes q is sorted

%o if q[i] in used2: continue

%o used2.add(q[i])

%o qc = list(q); qc[i] += 1; qc[j] -= 1

%o yield tuple(sorted(qc))

%o def a(n):

%o s = tuple(0 for i in range(n)); reach = {s}; expand = list(reach)

%o while len(expand) > 0:

%o q = expand.pop()

%o for qq in nextq(q):

%o if qq not in reach:

%o reach.add(qq)

%o expand.append(qq)

%o return len(reach)

%o print([a(n) for n in range(13)]) # _Michael S. Branicky_, Oct 21 2021

%Y Cf. A000571, A347913.

%K nonn,more

%O 0,3

%A _Tejo Vrush_, Oct 21 2021

%E a(6)-a(19) from _Michael S. Branicky_, Oct 21 2021