p_1, ..., p_n;   k рекордов        f (n, k)
где последний рекорд?
переберём позицию s последнего рекорда
p_1, ..., p_{s-1};   k-1 рекорд    f (s - 1, k - 1)
последний рекорд в перестановке длины n всегда равен n

ещё нужно разбить числа на две группы:
     группа 1                     группа 2
-----------------   --------------------------------------
p_1, ..., p_{s-1} n (оставшиеся n-s чисел в любом порядке)
  f (s - 1, k - 1)  *   (n - s)!

  choose (n - 1, n - s)  =  (n - 1)! / (n - s)! / (s - 1)!
= choose (n - 1, s - 1)             * (n - s)!
                         =  (n - 1)! / (s - 1)!