number of permutations that does not "go back" more than $k$

Question

I got a conjecture that enumerate some permutations and I want to ask if it has already known or not.

Let $n$ and $k$ be natural numbers that satisfies $n\geq k\geq 1$. Define a set $\mathcal{F}(n,k)$ as follows.

$\mathcal{F}(n,k):=\{\sigma\in\mathfrak{S}_n\mid \forall i\in\{1,\ldots,n\} \ \sigma(i)>i-k\}$.

For example, ${{1\ 2\ 3\ 4}\choose{3\ 1\ 2\ 4}}\in\mathcal{F}(4,2)$ and ${{1\ 2\ 3\ 4}\choose{2\ 3\ 1\ 4}}\notin\mathcal{F}(4,2)$.

I calculated the numbers $\#\mathcal{F}(n,k)$ using Python and conjectured that

$\#\mathcal{F}(n,k)=k!k^{n-k}$.

Is this conjecture known or not? If it is known, I want to know how to prove it.

Answer 1

If it is known or not I don't know, but for the latter part:

Start by noticing that for any valid permutation $\sigma \in F(n,k)$ you have for the largest number $n$ the condition

$\sigma(n) > n - k$

and thus exactly $k$ possibilities for $\sigma(n)$.

For the next biggest number $n-1$ we have the condition

$\sigma(n-1) > n-k-1$

so the number $n-k$ is now possible as well (if n is big enough). As we already made a choice for $\sigma(n)$, we end up with yet again $k$ possibilities.

If go forth like that until there are exactly $k$ numbers left, you get the factor $k^{n-k}$.

Now for the last $k$ numbers the condition

$\sigma(j) > j - k$ , $j \in \{1,...,k\}$

is always true as $j-k <= 0$ holds. Thus we only have to decide on an order of the $k$ last numbers, which gives us the factor $k!$.

Combining both leads to

$|F(n,k)| = k! k^{n-k}$