login
A228762
Number of undirected circular permutations i_1,...,i_{n-1} of 1,...,n-1 with i_1-i_2, ..., i_{n-2}-i_{n-1}, i_{n-1}-i_1 pairwise distinct modulo n.
4
1, 0, 1, 0, 7, 0, 39, 0, 419, 0, 7208, 0, 226512, 0, 7885970, 0, 345718580, 0, 18478915794, 0
OFFSET
3,5
COMMENTS
If i_1,...,i_{n-1} is a permutation of 1,...,n-1 with i_1-i_2, ..., i_{n-2}-i_{n-1}, i_{n-1}-i_1 pairwise distinct modulo n, then 0 = (i_1-i_2)+...+(i_{n-1}-i_1) == 1+2+...+(n-1) = n(n-1)/2 (mod n) and hence n is odd. So a(n) = 0 for every n = 4,6,8,...
If g is a primitive root modulo an odd prime p, then 1-g, g-g^2, g^2-g^3, ..., g^{p-3}-g^{p-2},g^{p-2}-1 are pairwise distinct modulo p. Therefore a(p) > 0 for any odd prime p.
Conjecture: a(n) > 0 for any odd number n > 1. In general, if G is an additive abelian group with |G| = n odd and greater than one, then there is a permutation a_1,...,a_{n-1} of all the nonzero elements of G such that a_1-a_2, a_2-a_3, ..., a_{n-2}-a_{n-1}, a_{n-1}-a_1 are pairwise distinct.
For any integer n > 1, the author has showed that there is a permutation i_1, ..., i_n of 1, ..., n such that i_1-i_2, i_2-i_3, ..., i_{n-1}-i_n are pairwise distinct if and only if n is even.
LINKS
Zhi-Wei Sun, Some new problems in additive combinatorics, arXiv preprint arXiv:1309.1679 [math.NT], 2013-2014.
EXAMPLE
a(3) = 1 since the circular permutation (1,2) of 1,2 meets the requirement.
a(5) = 1 due to the circular permutation (1,2,4,3).
a(7) = 7 due to the following circular permutations:
(1,2,5,4,6,3), (1,2,6,4,3,5), (1,3,2,5,6,4), (1,3,2,6,4,5),
(1,3,4,2,6,5), (1,4,5,3,2,6), (1,5,4,2,3,6).
a(9) > 0 due to the circular permutation (1,2,5,3,7,6,8,4).
a(15) > 0 due to the circular permutation
(1,3,14,7,4,11,5,10,9,12,13,2,8,6).
a(21) > 0 due to the circular permutation
(1,2,11,8,19,15,9,4,10,3,6,13,18,7,5,17,16,20,12,14).
Permutations for n = 15, 21 were produced by Qing-Hu Hou at Nankai Univ. after the author told him the conjecture.
MAPLE
A228762 := proc(n)
local a, pL, p, mset, per, i ;
a := 0 ;
pL := combinat[permute](n-2) ;
for p in pL do
mset := {} ;
per := [1, seq(op(i, p)+1, i=1..nops(p))] ;
# only directed
if op(2, per) <= op(-1, per) then
for i from 1 to nops(per) do
if i = nops(per) then
mset := mset union { modp(n+op(i, per)-op(1, per), n) } ;
else
mset := mset union { modp(n+op(i, per)-op(i+1, per), n) } ;
end if;
end do:
if nops(mset) = n-1 then
a := a+1 ;
end if;
end if;
end do:
return a;
end proc:
for n from 3 do
A228762(n) ;
end do; # R. J. Mathar, Sep 03 2013
MATHEMATICA
A program to compute required circular permutations of 1, ..., 7 (beginning with 1). To get undirected circular permutations, we should identify one such a permutation with the one of the opposite direction; for example, (1, 3, 6, 4, 5, 2) is identical to (1, 2, 5, 4, 6, 3).
V[i_]:=Part[Permutations[{2, 3, 4, 5, 6}], i]
m=0
Do[If[Length[Union[{Mod[1-Part[V[i], 1], 7]}, Table[Mod[Part[V[i], j]-If[j<5, Part[V[i], j+1], 1], 7], {j, 1, 5}]]]<6, Goto[aa]];
m=m+1; Print[m, ":", " ", 1, " ", Part[V[i], 1], " ", Part[V[i], 2], " ", Part[V[i], 3], " ", Part[V[i], 4], " ", Part[V[i], 5]]; Label[aa]; Continue, {i, 1, 5!}]
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Zhi-Wei Sun, Sep 03 2013
EXTENSIONS
a(9) and a(11) added by R. J. Mathar, Sep 03 2013
a(12)-a(22) from Robin Visser, Aug 26 2023
STATUS
approved