Find the number of permutations of $(1,2,…,n)$ so that they can be sorted in $k$ runs


Find the number of permutations $ (p_1,p_2,…,p_n)$ of $ (1,2,…,n)$ such that they are sorted (in ascending order) in at most $ k$ runs.

A run is defined as :

for ($ i=1$ to $ n-1$ ) do

if ($ p_i > p_{i+1}$ ) then

swap ($ p_i, p_{i+1}$ )

end if

end for

This is probably doable by recursion though I’m not sure of that. Define the number of permutations of $ n$ numbers in $ k$ runs by $ f(n,k)$ . For the case of $ k=1$ , we get the recursion $ f(n,1)=f(n-1,1)f(0,0)+f(n-2,1)f(1,0)+ \cdots +\cdots = 2^{n-1}$ . And it’s not hard to deduce the answer. I’m not sure how to generalize this. I have noted that $ f(p,p)=p!$ for any natural number $ p$ . That’s obvious because $ \{p,p-1, \cdots , 1\}$ gets sorted ($ j^\text{th}$ run takes the respective element to its respective location) and since that’s the worst possible case, any other case will also get sorted. Note that the answer to this problem is $ k! (k+1)^{n-k}$ . Now, an element $ j$ can go to any location b/w $ 1$ and $ j+k$ such that after it moves to some location $ l$ , any number between these two elements can be sorted in $ k-1$ runs. Considering all these in mind, I am not sure how to get a recursive or a non recursive solution.

The answer, if represented in the form $ f(n,k)$ can be written as $ f(n,k)=(k+1)f(n-1,k)$ for $ n-1 > k$ and then going recursively, we will get to the step when $ f(k,k)=k!$ and we will be done. But I’m not sure if this particular recursive relation will help solve this problem. It’s just that I observed it, I’m not sure if that would help.