Número de lindas permutaciones

Así es como formamos una linda permutación: seleccione$m$números;$x_{1}<x_{2}<...<x_{m}$. Poner$x_{m}$en$x_{1}$la ubicación original de entonces para todos$i\in[1,2,...,m-1]$poner$x_{i}$en$x_{i+1}$ubicación original de . El número de lindas permutaciones viene dado por la siguiente expresión:

La idea es que fuera de$n$números, algunos cambiarán de posición ($m$de ellos) mientras que el resto permanecerá en su posición original. De todos los números que cambian de posición, solo uno se mueve hacia la izquierda mientras que los demás se mueven hacia la derecha.

por cierto para$n=4$hay$11$lindas permutaciones en lugar de$10$

Una linda permutación en$S_n$siempre se puede identificar con uno no trivial (longitud mayor o igual a$2$) permutación cíclica actuando sobre$\{1,2,\dots,n\}$de una forma especial, por lo que la tarea en cuestión es contar el número de lindas permutaciones cíclicas.

Si se le presentan los elementos 'activos' de una linda permutación cíclica de longitud dos o más, descubrirá fácilmente que hay una y solo una forma de reconstruir esa permutación (vea el ejemplo en la siguiente sección) .

Desde

$\quad \text{The number of subsets of } \{1,2,\dots,n\} = 2^n$
$\;\;\;$y el número de subconjuntos con$0$elementos es$1$,
$\quad\;$y el número de subconjuntos con$1$el elemento es$n$,
concluimos que el conteo de permutaciones lindas está dado por

$\tag{1} 2^n-1-n$

Ejemplo: Si$n = 4$entonces el subconjunto$\{1,3,4\}$corresponde a la permutación linda (cíclica)

$\quad (4\, 3\, 1)$