### dingshu's blog

By dingshu, 7 years ago, , Let's divide this queue into to 2 parts: 1... k and k + 1... n.

It's obvious that pi ≤ k while i ≤ k, pi > k while i > k.

So the answer to the part of pk + 1... n is (n - k)n - k.

Image a tree with k vertexes. The number of those trees is kk - 2. (Cayley trees)

Choose a vertex to be root, there are k ways.

Set pi = fatheri in the tree. And for the root, set proot = 1.

It's easy to find p1... k satisfied the problem.

So answer is kk - 1(n - k)n - k.  Comments (9)
 » 7 years ago, # | ← Rev. 3 →   Maybe kk - 1(n - k)n - k?ADD: It's OK now.
•  » » Thx, I made a mistake just now. :)
•  » » i cann't understand the k^(k-1) ?? if input is 3 3 so all of the number are e.g:(p1,p2,p3),(2,1,1),(2,3,1),(3,2,1),(3,3,1),(3,1,1). can you tell me some else?
 » Because k <= 8, it could be solved by backtrack too.
 » i cann't understand the k^(k-1) ?? if input is 3 3 so all of the number are e.g:(p1,p2,p3),(2,1,1),(2,3,1),(3,2,1),(3,3,1),(3,1,1). can you tell me some else?
•  » » Actually, first number in a triple can be equal to one. Therefore, we have got (1,1,1), (1,3,1), (1,1,2), (2,1,1), (2,3,1), (2,1,2), (3,1,1), (3,3,1), (3,1,2). That is, answer=9.
•  » » » thank you very much~ ^-^
•  » » » I'm confused about whether (1,1,1),(1,3,1),(1,1,2) satisfy the restriction 3: "When the penguin starts walking from house number 1, he can get back to house number 1 after some non-zero number of walks from a house to a house."?
•  » » » » ohh...from house 1 to house 1, though we have no move, that's also 1 step.