Venia's blog

By Venia, 7 years ago, In English,

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.

 
 
 
 
  • Vote: I like it
  • +12
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For 1 <= x <= k, I came up with this solution: out of k^k ways we must remove (k-1)*k^(k-1) ways because for each p[i] = i (1 < i <= k) we cannot go back to home 1 from position i. And k^k — (k-1)*k^(k-1) is k^(k-1).