A347913 - OEIS

%I #128 Jun 05 2022 13:19:25

%S 1,1,2,2,7,9,29,47,144,264,747,1531,4147,9063,23744,54522,140223,

%T 332033,845111,2045007,5176880,12713772,32115727,79676437,201227865,

%U 502852973

%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. Splitting is taking 2 occurrences of the same integer and incrementing one of them by 1 and decrementing the other occurrence by 1.

%C If the limit of a(n+1)/a(n) exists, then it is contained in the closed interval [2,6.75]. See Links for proof. Reverse splitting is defined in A348532.

%H Tejo Vrush, <a href="/A347913/a347913_3.pdf">Limiting ratio for consecutive terms (Upper bound)</a>

%H Tejo Vrush, <a href="/A347913/a347913_8.pdf">Limiting ratio for consecutive terms (Lower bound)</a>

%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   {{-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,-1,1,1,2}} {{-2,-1,-1,0,2,2}}

%e   {{-2,-1,-1,0,1,3}} {{-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}} {{-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,0,1,2,2}}  {{-3,-2,0,1,1,3}}

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

%e Therefore, a(6) = 29.

%p b:= proc(p) option remember; {p, seq(`if`(coeff(p, x, i)>1,

%p       b(expand((p-2*x^i+x^(i-1)+x^(i+1))*`if`(i=0, x, 1)

%p                )), [])[], i=0..degree(p))}

%p     end:

%p a:= n-> nops(b(n)):

%p seq(a(n), n=0..10);  # _Alois P. Heinz_, Oct 07 2021

%t b[p_] := b[p] = Union@Flatten@Join[{p}, Table[If[Coefficient[p, x, i] > 1, b[Expand[(p - 2*x^i + x^(i - 1) + x^(i + 1))*If[i == 0, x, 1]]]], {i, 0, Exponent[p, x]}]];

%t a[n_] := If[n == 0, 1, Length[b[n]] - 1];

%t Table[Print[n, " ", a[n]]; a[n], {n, 0, 14}] (* _Jean-François Alcover_, Jun 04 2022, after _Alois P. Heinz_ *)

%o (Python)

%o def nextq(q):

%o     used = 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 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                 if len(set(qq)) < len(qq):

%o                     expand.append(qq)

%o     return len(reach)

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

%Y Cf. A348532.

%K nonn,more

%O 0,3

%A _Tejo Vrush_, Oct 07 2021

%E a(15)-a(22) from _David A. Corneth_, Oct 08 2021

%E a(23)-a(25) from _Michael S. Branicky_, Oct 12 2021