The problem: given numbers n and k, find the number of functions such that for each x with 1 ≤ x ≤ k there is a number r with f^[r](x) = 1 and for each x with k < x ≤ n there is no such number r.

First, observe that f(x) with x > k can be set to anything in {k + 1... n}, independently to what f is in {1... k}. This means that we can just calculate the number of such functions f restricted to {1, ... k} and multiply by (n - k)^n - k by the multiplication principle.

But how do we find how many functions there are that come back to 1 after sufficiently many iterations? If you draw some pictures, you may think about labeled trees: there are k(k - 2) labeled trees on n vertices by [Caley's theorem](http://en.wikipedia.org/wiki/Tree_(graph_theory)#Labeled_trees). Each function corresponds to a unique graph with vertices 1... n and an edge i, j if f(i) = j. The problem statement says that you can come back to 1 if you follow the edges, no matter where you start, this means that there are no directed cycles except the ones containing 1.

There is a problem though. Caley's formula counts undirected trees, and we have something that is not even a DAG (because there can be cycles containing 1). We can do a trick to make the thing a DAG — just remove the edge — this breaks the cycle with 1 inside and makes the graph a DAG. Also, it turns out that there are no undirected cycles as well: if there would be an undirected circle, it cannot be a directed one, and this means that some vertex is the cicle has two edges going out from it which is a contradiction because f is a function.

This was a sketch of the proof that the graph is a (unique) labeled tree with an extra edge

f(1) can have k values, so the answer is: there are k·k^(k - 2) ways to choose where the first k values go and (n - k)^(n - k) (independent) ways to choose the last n - k. Thus the complete answer is k^(k - 1)·(n - k)^(n - k).

There are some gaps in the proof: we didn't show that every tree together with the extra edge corresponds to a function, and that the correspondence is unique.