A347913 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.

1, 1, 2, 2, 7, 9, 29, 47, 144, 264, 747, 1531, 4147, 9063, 23744, 54522, 140223, 332033, 845111, 2045007, 5176880, 12713772, 32115727, 79676437, 201227865, 502852973

Offset: 0

Author

Tejo Vrush, Oct 07 2021

Keywords

• nonn
• more

Comments

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.

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}}
  {{-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,-1,1,1,2}} {{-2,-1,-1,0,2,2}}
  {{-2,-1,-1,0,1,3}} {{-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}} {{-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,0,1,2,2}}  {{-3,-2,0,1,1,3}}
  {{-3,-2,0,0,2,3}}  {{-3,-2,-1,1,2,3}}
Therefore, a(6) = 29.
		

Links

• Tejo Vrush, Limiting ratio for consecutive terms (Upper bound)
• Tejo Vrush, Limiting ratio for consecutive terms (Lower bound)

Crossrefs

Cf. A348532.

Programs

Maple

b:= proc(p) option remember; {p, seq(`if`(coeff(p, x, i)>1,
      b(expand((p-2*x^i+x^(i-1)+x^(i+1))*`if`(i=0, x, 1)
               )), [])[], i=0..degree(p))}
    end:
a:= n-> nops(b(n)):
seq(a(n), n=0..10);  # Alois P. Heinz, Oct 07 2021

Mathematica

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]}]];
a[n_] := If[n == 0, 1, Length[b[n]] - 1];
Table[Print[n, " ", a[n]]; a[n], {n, 0, 14}] (* Jean-François Alcover, Jun 04 2022, after Alois P. Heinz *)

Python

def nextq(q):
    used = 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))
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)
                if len(set(qq)) < len(qq):
                    expand.append(qq)
    return len(reach)
print([a(n) for n in range(17)]) # Michael S. Branicky, Oct 10 2021

Extensions

a(15)-a(22) from David A. Corneth, Oct 08 2021

a(23)-a(25) from Michael S. Branicky, Oct 12 2021