login
Largest period of a recurrence sequence of pairs of permutations of length n.
1

%I #33 Feb 14 2024 14:08:18

%S 1,3,8,18,96,216,2112,9720,39024,194256,1116240

%N Largest period of a recurrence sequence of pairs of permutations of length n.

%C The n! permutations (p) of the numbers 1,2,3..n may be paired (allowing duplication) in n!^2 ways. For a pair of permutations (p, p'), let p'' = p x p', p''' = p' x p'', and so on until the starting pair (p, p') is obtained. If p = p', this iterative process gives the Pisano periods. For most other pairs the periods have different lengths. The sequence gives the longest period that (p, p') generates for any p, p' of length n.

%C Period is invariant with respect to simultaneous conjugation of both p, p'. - _Max Alekseyev_, Feb 09 2024

%H Russell Walsmith, <a href="/A226593/a226593_1.pdf">An investigation of recursive sequences based on pairs of permutations of length n</a>.

%e For n = 4: 3142 x 2341 = 1423; 2341 x 1423 = 2134... the sequence thus generated is of period = 18.

%o (PARI) period(a,b)=my(n=matsize(a)[2], v=vector(n), aa=vector(n,i,a[i]), bb=vector(n,i,b[i]), id, nsteps); while(id!=n, for(i=1,n, v[i]=a[b[i]]); id=sum(i=1,n, b[i]==aa[i] && v[i]==bb[i]); for(i=1,n, a[i]=b[i]; b[i]=v[i]); nsteps++); nsteps

%o a(n)=my(a,b,m,p); for(k=1,n!, a=numtoperm(n,k); for(l=1,n!, b=numtoperm(n,l); p=period(a,b); if(p>m,m=p))); m \\ _Ralf Stephan_, Aug 13 2013

%Y Cf. A001175 (Pisano periods: period of Fibonacci numbers (A000045) mod n).

%Y Cf. A106291 (period of the Lucas sequence (A000032) mod n).

%K nonn,hard,more

%O 1,2

%A _Russell Walsmith_, Jun 13 2013

%E a(6) from _Ralf Stephan_, Aug 13 2013

%E Edited and a(7)-a(11) added by _Max Alekseyev_, Feb 13 2024