Permutaciones de {1.. n} que {1.. k} no son adyacentes

Question

El Problema:

Así que tengo que pensar de algunos simple combinatoria problemas, y esta sacado de mí.

Vamos N el conjunto de los números $\{1 .. n\}$, o cualquier conjunto de cardinalidad $n$

Sea K el conjunto de los números $\{1 .. k\}$ donde $k < n$, o cualquier subconjunto de N de cardinalidad $k$

¿Cuántas permutaciones de N existe tal manera que no hay dos miembros del conjunto k son adyacentes?

---

Aquí fue mi enfoque básico:

Soluciones = Permutaciones de N - Permutaciones de N que contienen un par de K

Permutaciones de N = nPn = n!

Cada elemento de K va a ocurrir en cada permutación de los N así que el bucle a través de:

 You place down one item of K
 Possibilities where the next is in K = K - 1
 You place down an item of K 
 possibilities where next is in k = k-2
 ...
 You place the last item in K

El total de permutaciones con un par por lo tanto, sería:

$ (k-1) + (k-2) + ... + 0 $

Sin embargo, muchas de esas entradas son duplicados, por lo que debemos descartar situaciones en que dos de estos pares se produjo en una serie, y luego de nuevo la regla de las instancias que ocurrió tres veces, hasta parejas se produjo k veces

Creo que la cantidad con dos pares sería la mejor forma de encontrarse mediante la obtención de la cantidad con un par menos la cantidad que, con no más.

Para ello me gustaría bucle como:

You place two items in K
There are k-2 chances the next item is in k
You place an item in K
There are k-3 chances the next item is in k
...
You place your last item in K

Total de permutaciones con dos pares de $= (k - 2) + (k - 3) + ... + 0$

Total de permutaciones de tres pares de $= (k - 3) + (k - 4) + ... + 0$

Y así sucesivamente..

Y en este punto sé que soy incorrecto, porque me gustaría obtener un total de:

$( (k-1) + (k-2) + ... + 0 ) - ( (k-2) + (k-3) + ... + 0 ) - ( (k-3) + (k-4) + ... + 0 ) + ... + 0$ permutaciones que contienen pares.

Este número es muchísimo negativo...

Como he señalado al final de eso, mi solución se encuentra un importe negativo de permutaciones que han pares en ellos, y lo que es claramente erróneo. Si alguien pudiera explicar mi error, o bien mostrar una mejor manera de abordar el problema, me sería de gran aprecio.

Cosas que creo que podría ser la causa de que mi respuesta sea incorrecta:

• No estoy seguro de si mi generalización para la eliminación de las permutaciones con varios pares de la cantidad total de posibles pares funciona correctamente si la pareja no se produce como la primera aparición de un miembro del conjunto K

Answer 1

Vamos a llamar a los elementos de a $k$ blancos y otros negros, y considerar los elementos del mismo color para ser indistinguible por ahora. Para los arreglos de inicio con el blanco elemento, pegamento negro elemento a la izquierda de todos los demás elementos blancos y elija $k-1$ ranuras de entre los resultantes $n-k$ objetos (excepto la inicial del blanco elemento) para el pegado de los pares. Para los arreglos de inicio con un negro elemento, pegamento negro elemento a la izquierda de todos los elementos blancos y elija $k$ ranuras de entre los resultantes $n-k$ objetos para el pegado de los pares. En total, la que hace de $\binom{n-k}{k-1}+\binom{n-k}k=\binom{n-k+1}k$ arreglos. Cada uno corresponde a $k!$ permutaciones de los elementos blancos y $(n-k)!$ permutaciones de los elementos negros, por lo que el número total de permutaciones es

$$ \binom{n-k+1}kk!(n-k)!=\frac{(n-k+1)!k!(n-k)!}{(n-2k+1)!k!}=\frac{(n-k+1)!(n-k)!}{(n-2k+1)!}\;. $$

Si $n-2k+1\lt0$, es decir,$k\gt\frac{n+1}2$, el coeficiente binomial es cero y no hay ningún tipo de permutaciones.

Answer 2

Una explicación alternativa a @joriki la respuesta.

Vamos a la $k$ elementos $\{1,2,3,\dots,k\}$ ser llamado "blanco" y el restante $n-k$ elementos a ser llamado "el negro".

Primero arreglar las $n-k$ negro de los elementos en una fila, dejando un poco de espacio extra a cada lado, incluyendo a la izquierda de la izquierda y a la derecha de la derecha es el negro elemento.

En estos $n-k+1$ de los espacios disponibles, elija $k$ de las ocupadas por elementos blancos.

Organizar los elementos blancos en una fila y colocarlos en los lugares elegidos.

Hay, a continuación, $\binom{n-k+1}{k}(n-k)!k!$ arreglos.

Tenga en cuenta que cuando se $k>n-k+1$, es decir, $k>\frac{n+1}{2}$ usted se verá obligado a tener dos blancos elementos adyacentes y tendrá cero posibles arreglos.