|
|
A333468
|
|
Length of the largest disjoint cycle of the permutation that results from the composition of first n circular shifts.
|
|
1
|
|
|
1, 2, 2, 3, 5, 6, 3, 4, 9, 4, 7, 10, 9, 14, 4, 5, 7, 18, 8, 10, 7, 7, 14, 11, 6, 26, 12, 9, 29, 30, 5, 6, 33, 11, 21, 6, 11, 15, 22, 27, 41, 6, 17, 8, 8, 7, 22, 24, 15, 50, 28, 8, 53, 18, 22, 14, 25, 9, 15, 55, 14, 50, 6, 7, 65, 11, 19, 34, 69, 23, 35, 14, 22, 74, 10
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
Size of the largest part of the partition of n that is associated with the cycle structure of the permutation given by the permutation product (1)*(1,2)*(1,2,3)*...*(1,2,3,...n) after the product is rewritten as the product of disjoint cycles, where * means functional composition, and the permutations are written in cycle form.
Also see Circular shift on Wikipedia.
For n>1, a(n) is always greater than 1, since the given product can never be the identity permutation on the set {1,2,...,n}, which is the only permutation associated with the partition <1,1,...,1> (1 repeated n times).
Connections: The image of 1 in each resulting permutation appears to be the same as the numbers in A003602. The number of parts in the partition associated with each resulting permutation appear to match the numbers in A006694.
|
|
LINKS
|
|
|
FORMULA
|
|
|
EXAMPLE
|
For n=3, the permutation (1)*(1,2)*(1,2,3)=(1)*(2,3), which is associated with the partition <2,1> of 3. The size of the largest part is 2, so a(3)=2.
For n=11, the permutation (1)*(1,2)*..*(1,2,..11)=(1,2,7,5)*(3,4,8,10,11,6,9) when rewritten as the product of disjoint cycles, which is associated with the partition <7,4> of 11. The size of the largest part is 7, so a(11)=7.
|
|
PROG
|
(PARI)
Follow(s, f)={my(t=f(s), k=1); while(t>s, k++; t=f(t)); if(s==t, k, 0)}
mkp(n)={my(v=vector(n, i, i)); for(k=1, n, my(t=v[1]); for(i=1, k-1, v[i]=v[i+1]); v[k]=t); v}
a(n)={my(v=mkp(n), m=0); for(i=1, n, m=max(m, Follow(i, j->v[j]))); m} \\ Andrew Howroyd, Mar 27 2020
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|