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.

1, 0, 1, 0, 7, 0, 39, 0, 419, 0, 7208, 0, 226512, 0, 7885970, 0, 345718580, 0, 18478915794, 0

Offset: 3

Author

Zhi-Wei Sun, Sep 03 2013

Keywords

• nonn
• more

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.

Examples

			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.
		

Links

• Zhi-Wei Sun, Some new problems in additive combinatorics, arXiv preprint arXiv:1309.1679 [math.NT], 2013-2014.

Crossrefs

Cf. A185645, A228728, A228766.

Programs

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!}]

Extensions

a(9) and a(11) added by R. J. Mathar, Sep 03 2013

a(12)-a(22) from Robin Visser, Aug 26 2023