Let's divide this queue into to 2 parts: 1... *k* and *k* + 1... *n*.

It's obvious that *p*_{i} ≤ *k* while *i* ≤ *k*, *p*_{i} > *k* while *i* > *k*.

So the answer to the part of *p*_{k + 1... n} is (*n* - *k*)^{n - k}.

Image a tree with *k* vertexes. The number of those trees is *k*^{k - 2}. (Cayley trees)

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

Set *p*_{i} = *father*_{i} in the tree. And for the root, set *p*_{root} = 1.

It's easy to find *p*_{1... k} satisfied the problem.

So answer is *k*^{k - 1}(*n* - *k*)^{n - k}.

Maybe

k^{k - 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.