

A364237


a(n) is the number of nonequivalent permutations of {1,2,...,2n1} such that no subset of consecutive terms from the permutation sums to 0 modulo 2n, where two permutations are equivalent if one can be obtained from the other by multiplying every entry with an integer relatively prime to 2n and/or reversing the permutation.


1




OFFSET

1,3


COMMENTS

If we consider all permutations of {1,2,...,2n1} such that no subset of consecutive terms from the permutation sums to 0 modulo 2n, then the number of such permutations is given by the number of constructive orderings mentioned in A141599. For example, given the permutation 14325 that satisfies the given conditions, observe that the partial sums modulo 6, namely 1=1, 1+4=5, 1+4+3=2, 1+4+3+2=4, and 1+4+3+2+5=3, are distinct.


LINKS



EXAMPLE

When n=3, there are four permutations of {1,2,3,4,5} such that no subset of consecutive terms from the permutation sums to 0 modulo 6, namely 14325, 25314, 41352, and 52341. Note that 14325 and 52341 are equivalent by reversing the permutations. Furthermore multiplication by 5 on every entry also yields the same equivalence. Additionally, 25314 and 41352 are analogously equivalent. Hence a(3)=2.
When n=4, 6142573 and 3752416 are equivalent by reversing the permutations but not by multiplying any integer relatively prime to 8, whereas 6142573 and 2346751 are equivalent by multiplication of 3 on every entry.


PROG

(SageMath)
n = 3 #the index for the sequence a(n)
orbits = {} #dictionary of permutations that are consecutive zerosumfree
seen = [] #list of seen permutations that are consecutive zerosumfree
a = 0 #the value of a(n)
for labeling in Permutations(range(1, 2*n)):
if labeling not in seen:
sums = [labeling[0]]
for i in range(1, 2*n1):
nextsum = (labeling[i] + sums[i1]) % (2*n)
if any([nextsum == 0, nextsum in sums]):
break
sums.append(nextsum)
if len(sums) == (2*n)1:
a += 1
orbits[a] = []
for m in [x for x in range(1, 2*n) if gcd(x, 2*n) == 1]:
equiv = [(m*labeling[i]) % (2*n) for i in range(2*n1)]
if equiv not in orbits[a]:
orbits[a].append(equiv)
seen.append(equiv)
equiv = [equiv[2*n2i] for i in range(2*n1)]
if equiv not in orbits[a]:
orbits[a].append(equiv)
seen.append(equiv)
print(f"a({n}) = {a}\n")
print("Equivalencies:")
for i in range(1, a+1):
print(f"{i}.")
for x in orbits[i]:
print(x)
print('\n')


CROSSREFS



KEYWORD

nonn,hard,more


AUTHOR



EXTENSIONS



STATUS

approved



