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, 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

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

Links

Table of n, a(n) for n=1..78.

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

Sequence in context: A342985 A278094 A245487 * A174956 A124182 A188429

Adjacent sequences: A074731 A074732 A074733 * A074735 A074736 A074737

Keyword

nonn,tabl

Author

Wouter Meeussen, Sep 05 2002

Status

approved