número de permutaciones que no "regresan" más que$k$

Question

Tengo una conjetura que enumerar algunas permutaciones y quiero preguntar si ya ha conocido o no.

Deje $n$ e $k$ ser números naturales que satisface $n\geq k\geq 1$. Definir un conjunto $\mathcal{F}(n,k)$ como sigue.

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

Por ejemplo, ${{1\ 2\ 3\ 4}\choose{3\ 1\ 2\ 4}}\in\mathcal{F}(4,2)$ y ${{1\ 2\ 3\ 4}\choose{2\ 3\ 1\ 4}}\notin\mathcal{F}(4,2)$.

He calculado los números de $\#\mathcal{F}(n,k)$ usando Python y conjeturó que

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

Es esta conjetura se conoce o no? Si es conocido, quiero saber cómo demostrarlo.

Answer 1

Si es conocido o no, no sé, pero para la última parte:

Empezar por darse cuenta de que por cualquier razón permutación $\sigma \in F(n,k)$ tiene el mayor número de $n$ la condición

$\sigma(n) > n - k$

y así exactamente $k$ posibilidades de $\sigma(n)$.

Para el siguiente mayor número de $n-1$ tenemos la condición

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

por lo que el número de $n-k$ ahora es posible (si n es suficientemente grande). Como ya hemos hecho una selección de $\sigma(n)$, que se termina con un nuevo $k$ posibilidades.

Si ir de un lado a otro como que hasta que no se exactamente $k$ números de la izquierda, se obtiene el factor de $k^{n-k}$.

Ahora, durante los últimos $k$ números de la condición

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

es cierto siempre como $j-k <= 0$ sostiene. Por lo tanto sólo tenemos que decidir sobre el orden de la $k$ últimos números, lo que nos da el factor de $k!$.

La combinación de ambos conduce a

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