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
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
Comments