login
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.
2
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,3
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.
EXAMPLE
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.
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 *)
PROG
(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
CROSSREFS
Cf. A348532.
Sequence in context: A267214 A107386 A095021 * A348532 A275282 A307633
KEYWORD
nonn,more
AUTHOR
Tejo Vrush, Oct 07 2021
EXTENSIONS
a(15)-a(22) from David A. Corneth, Oct 08 2021
a(23)-a(25) from Michael S. Branicky, Oct 12 2021
STATUS
approved