¿Cuántas permutaciones de {1,2,3,...,n}{1,2,3,...,n}\{1,2,3,...,n\} hay sin 2 ¿numeros consecutivos?

Considere la siguiente recurrencia: el conteo deseado$Q_n$es$1$para$n=1$y$1$para$n=2.$Para$n\gt 2$obtenemos una permutación admisible ya sea colocando el valor$n$en cualquier lugar en$n-1$posiciones posibles de una permutación admisible de$Q_{n-1}$(esto no es$n$porque no podemos colocar$n$al lado y a la derecha de$n-1$) o construimos una permutación que tenga exactamente un par de números consecutivos y colocamos el valor$n$entre estos dos. Esto se puede hacer tomando una permutación de$Q_{n-2}$y reemplazando uno de los$n-2$valores por un par fusionado que contiene el valor y su sucesor e incrementando los valores que son mayores que el primer elemento del par fusionado.

Obtenemos la recurrencia

y$Q_1= Q_2= 1.$Esto produce la secuencia

que es OEIS A000255 , donde se puede encontrar una entrada detallada.

El código de Maple para esto fue el siguiente.

con (combinar);

C :=
proceso(n)
opción recordar;
permanente local, pos, res;

    resolución := 0;
    perm := primerperm(n);

    while type(perm, `list`) hacer
        para pos a n-1 hacer
            si perm[pos] + 1 = perm[pos+1] entonces
                romper;
            fi;
        sobredosis;

        si pos = n entonces
            resolución := resolución + 1;
        fi;

        perm := nextperm(perm);
    sobredosis;


    res;
fin;


P :=
proceso(n)
opción recordar;

    si n = 1 o n = 2, devuelve 1 y termina si;

    (n-1)*Q(n-1) + (n-2)*Q(n-2)
fin;

Apéndice. Esta es mi perspectiva sobre el enfoque de inclusión-exclusión. Tomamos como el conjunto parcialmente ordenado subyacente el conjunto$P$de subconjuntos (estos son los nodos del poset) de$\{1,2,\ldots,n-1\}$donde un subconjunto$S\in P$representa permutaciones donde los elementos de$S$están al lado de sus sucesores, más posiblemente algunos otros elementos también al lado de sus sucesores. El conjunto parcialmente ordenado se ordena por inclusión de conjunto. Para calcular la cardinalidad de las permutaciones correspondientes a$S$Supongamos que los elementos de$S$enumerado en el formulario de pedido$m$bloques Primero los eliminamos de$[n].$También debemos eliminar los elementos que son consecutivos con el elemento más a la derecha de cada bloque, por lo que ahora hemos eliminado$|S|+m$elementos. Luego volvemos a colocar los bloques aumentados y fusionados en la permutación y los permutamos. Hemos agregado en$m$bloques, por lo tanto el cambio neto es$-|S|-m +m = -|S|.$Por tanto, por inclusión-exclusión calculamos la cantidad

Ahora bien, esto depende sólo del número$q$de elementos en$S$entonces obtenemos

Ahora debemos preguntarnos sobre el peso asignado a una permutación con$p$elementos (llamemos a este conjunto$T$) junto a su sucesor. Esta permutación está incluida o más bien representada por todos los conjuntos$S$que son subconjuntos del conjunto$T$, que es el poset abarcado por los singletons y$T$siendo el nodo superior. Obtenemos

El conteo asigna el peso menos uno a la permutación. Se sigue que cuando sumamos$n!$quedan exactamente aquellas permutaciones que no contienen valores adyacentes consecutivos, por un resultado de

Podemos simplificar esto a

Si, como parece ser el caso, planea usar un argumento de inclusión-exclusión , necesitará$\left|\bigcap_{k\in I}A_k\right|$por cada no vacío$I\subseteq[n-1]$. El truco es darse cuenta de que no importa cómo los números enteros en$I$están espaciados, la cardinalidad va a ser la misma. Cuando$|I|=2$, el caso que está discutiendo en la pregunta, hay dos posibilidades: los dos miembros de$I$son consecutivos, o no lo son. Pero en ambos casos resulta que la cardinalidad de la intersección es$(n-2)!$: hay cálculos diferentes para los dos casos, pero conducen al mismo resultado. Tenga en cuenta que no hay ninguna razón para agregar estos cálculos: no$I$pertenece a ambos casos.

El conjunto$I$se puede dividir en bloques de enteros consecutivos. Por ejemplo,$I=\{2,3,5,6,7,9\}$tiene$3$bloques:$\{2,3\},\{5,6,7\}$, y$\{9\}$. Suponer que$I$tiene un bloque$\{k,k+1,\ldots,k+r\}$. Entonces cada permutación en$\bigcap_{k\in I}A_k$debe contener la subsecuencia$\langle k,k+1,\ldots,k+r,k+r+1\rangle$; llame a esto un bloque extendido . Si$I$tiene$b$bloques por completo, cada permutación de$[n]$que pertenece a$\bigcap_{k\in I}A_k$debe contener todo$b$bloques extendidos como subsecuencias, pero puede contenerlos en cualquier orden. Esos bloques extendidos contienen en total$|I|+b$enteros: los propios bloques contienen$|I|$enteros, y cada bloque extendido tiene un entero adicional en el extremo derecho. Eso deja$n-|I|-b$miembros de$[n]$que se pueden permutar arbitrariamente, porque no están en ningún bloque extendido de$I$. Así, las permutaciones en$\bigcap_{k\in I}A_k$son realmente permutaciones de

cosas:$b$bloques extendidos, y el$n-|I|-b$elementos únicos que no forman parte de ningún bloque extendido. Resulta que

cuando sea$\varnothing\ne I\subseteq[n-1]$.

Ahora el principio de inclusión-exclusión te dice que

y te dejo el resto para que lo termines.

En ambos casos, hay$(n-2)!$permutaciones
En el primer caso, existe el triple$(i,i+1,i+2)$y$n-3$otros numeros
En el segundo caso, hay dos pares, y$n-4$otros numeros