login
T(n,k)= count of differences between standard sort and 'modular sort' over all subsets of k integers chosen from n. Modular Sort considers the integers 1..n to lie on a circle and rotates them to exclude the largest interval.
0

%I #5 Mar 30 2012 18:37:42

%S 0,0,0,0,1,0,0,1,2,0,0,3,3,3,0,0,3,8,6,4,0,0,6,13,16,10,5,0,0,6,22,33,

%T 28,15,6,0,0,10,31,60,67,45,21,7,0,0,10,48,97,136,120,68,28,8,0,0,15,

%U 62,158,244,271,198,98,36,9,0,0,15,86,234,424,535,492,308,136,45,10,0

%N T(n,k)= count of differences between standard sort and 'modular sort' over all subsets of k integers chosen from n. Modular Sort considers the integers 1..n to lie on a circle and rotates them to exclude the largest interval.

%C for modulo 24, imagine you need to be present at work at 23:00 and at 04:00, then you only have to be there for 5 hours, not 19 (=23-4).

%e T(4,3)=2 because modsort mod 4 on {{1,2,3},{1,2,4},{1,3,4},{2,3,4}} produces {{1,2,3},{4,1,2},{3,4,1},{2,3,4}} with 2 changes. modsort on {1,2,4} gives {4,1,2} since it has intervals (4 to 1 gives 1) and (1 to 2 gives 1), while (2 to 4 gives 2) is excluded.

%t modsort[li_List, n_] := Block[{temp}, RotateRight[Sort[li], Length[li]-Position[temp=Mod[ #2-#1, n, 0]& @@@ Partition[Sort[li], 2, 1, {1, 1}], Max[temp]][[ -1, 1]] ]]; << DiscreteMath`Combinatorica`; Table[Count[modsort[ #, n]& /@ KSubsets[Range[n], k], _?(!OrderedQ[ # ]&)], {n, 16}, {k, n}]

%K nonn,tabl

%O 1,9

%A _Wouter Meeussen_, Sep 05 2002