

A074734


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



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, 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, 62, 158, 244, 271, 198, 98, 36, 9, 0, 0, 15, 86, 234, 424, 535, 492, 308, 136, 45, 10, 0
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,9


COMMENTS

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 (=234).


LINKS



EXAMPLE

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.


MATHEMATICA

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


CROSSREFS



KEYWORD



AUTHOR



STATUS

approved



