login
Number of permutations p of {1,2,...,n} such that p(x) is a polynomial in x, modulo n, of degree at most 2, for x=1,2,3,...,n.
1

%I #13 May 21 2015 20:10:31

%S 1,2,6,8,20,12,42,64,162,40,110,48,156,84,120,512,272,324,342,160,252,

%T 220,506,384,2500,312,4374,336,812,240,930,4096,660,544,840,1296,1332,

%U 684,936,1280

%N Number of permutations p of {1,2,...,n} such that p(x) is a polynomial in x, modulo n, of degree at most 2, for x=1,2,3,...,n.

%C For n > 1, a(n) is a multiple of n less than n^3. - _Charles R Greathouse IV_, May 21 2015

%e For n=4, the permutation (1,2,3,4) is clearly given by the polynomial p(x)=x, for any modulus and the permutation (1,4,3,2) is found to be given by p(x)=2x^2+x+2 (modulo 4), since 2+1+2=5=1(mod 4), 2*4+2+2=12=0 (mod 4), 2*9+3+2=23=3 (mod 4) and 2*16+4+2=38=2 (mod 4). Among the other 22 permutations of (1,2,3,4) six are found to have the desired property, for a total of 8, so a(4)=8.

%t f = Function[n, arg = Range[n]; Length[Union[Select[Flatten[ Table[Mod[a*arg^2 + b*arg + c, n], {a, n}, {b, n}, {c, n}], 2], Sort[#] == arg - 1 &]]]]; Table[f[n], {n, 40}] (* _Ivan Neretin_, May 21 2015 *)

%o (PARI) a(n)=my(u=List(),v); for(a=1,n-1,for(b=0,n-1, v=vector(n,x,a*x^2+b*x)%n; if(#Set(v)==n, listput(u,v)))); for(a=1,n, v=vector(n,x,a*x%n); if(#Set(v)==n,listput(u,v))); n*#Set(u) \\ _Charles R Greathouse IV_, May 21 2015

%Y Cf. A002618 (analog with linear polynomials).

%K nonn

%O 1,2

%A _John W. Layman_, Feb 28 2008

%E More terms from _Ivan Neretin_, May 21 2015