Contando partición del conjunto de $i$ $i+1$ no están en ninguna parte

Question

Tengo que contar el número de particiones del conjunto $\{1,\ldots,n\}$ bajo la restricción de que para cada una de las $i$, los elementos $i$ $i+1$ se encuentran en diferentes lugares.

Mi idea es:

Tenemos dos situaciones cuando se trata de $1,2,3 \a \{1\}\{2\}\{3\}$ or $\{1,3\}\{2\}\{\texto{ un }\{4,5,\ldots n\}\}$. Para cada elemento elijo parte (hay dos posibilidades) Por lo tanto, $$2^{n-3} + (n-3)2^{n-4} $$

Answer 1

Yo llame a una partición de $\{1,2,\dots,n\}$ exactamente $k$ conjuntos con las restricciones sobre los vecinos se menciona en la pregunta "$(n,k)$ partición". Deje $f(n,k)$ el número de $(n,k)$ particiones. Podemos obtener una fórmula recursiva de la siguiente manera:

Considere la posibilidad de una $(n,k)$ partición. Retire $n$ a partir de la partición. Ahora estamos a la izquierda, ya sea con un $(n-1,k)$ partición (si $n$ no estaba en un singleton set) o con un $(n-1,k-1)$ partición (si $n$ estaba en un singleton conjunto). Por lo tanto, cada una de las $(n,k)$ partición puede ser construido a partir de una $(n-1,k)$ partición o de un $(n,k-1)$ partición. Por otra parte, la construcción es siempre única.

Hay $k-1$ formas de extender un $(n-1,k)$ partición a una $(n,k)$ partición: $n$ se puede añadir a cualquiera de los conjuntos que no tienen $n-1$. No sólo es $1$ forma de extender una $(n-1,k-1)$ partición a una $(n,k)$ partición: agregar un nuevo conjunto de $\{n\}$.

Ahora llegamos a la fórmula de recursión $$ f(n,k) = (k-1) f(n-1,k) + f(n-1,k-1). $$ Las condiciones iniciales son, por ejemplo, $f(1,1)=1$, $f(n,1)=0$ para todos los $n\geq2$, e $f(n,k)=0$ si $n<k$.

La respuesta a su pregunta ahora es $\sum_{k=1}^{n} f(n,k)$.

Por desgracia no he averiguado cómo resolver esta fórmula recursiva.

---

Edit 1: Gracias a xawey comentario, miraba más de cerca a los números dados por esta fórmula recursiva. El recurrente fórmula es similar a la fórmula recursiva de los números de Stirling de segundo tipo. Esto le da a $f(n,k)=S(n-1,k-1)$ donde $S(a,b)$ es el número de maneras para crear una partición de un conjunto de tamaño $a$ exactamente $b$ conjuntos. Esto implica que $\sum_{k=1}^{n} f(n,k) = B_{n-1}$, el número de formas de partición de un conjunto de tamaño $n-1$. No debe ser un simple combinatoria de interpretación.

Answer 2

Un buen enfoque combinatorio es para 'leer' una partición del conjunto como un acuerdo de no atacar a torres en la parte diagonal de un tablero de ajedrez:
partición del conjunto de {1,5,6},{2,4,7},{3}
se transforma a pares (1,5),(5,6),(2,4),(4,7) mediante la partición de la no-singleton establece en sucesivas (superpuestas) pares. La observación de que esto permite una reconstrucción total de la serie original de la partición.
El uso de este 'rooky' la interpretación, es fácil mostrar que cualquier par (i,i+1) se sentará en la diagonal, justo por encima de la diagonal principal.

Ahora, es evidente que la pérdida de esta diagonal reduce el de arriba de la diagonal de un tablero de ajedrez de n por n (n-1) (n-1).

Por lo tanto, el número de vecino, evitando las particiones del conjunto de tamaño n es igual al número de particiones de tamaño (n-1).

Answer 3

Desde el problema sin restricciones tiene como solución el conjunto de la partición función de recuento $B_n$ (la Campana de los números), para la que no hay realmente simple expresión existe, no veo cómo uno podría esperar obtener una respuesta en términos de $2^n$.

Aquí inclusión-exclusión se aplica con bastante facilidad. Primer recuento de todos los $B_n$ particiones de $n$; a continuación, para cada una de las $1\leq i<n$ restar el número de $B_{n-1}$ de particiones en el que se $\{i,i+i\}$ está contenida en una parte (los dos esencialmente funcionan como un único elemento nuevo); a continuación, para cada una de las $1\leq i<j<n$, las particiones en el que se $\{i,i+i\}$ $\{j,j+i\}$ son cada contenida en una parte (posiblemente la misma parte, como siempre sucede cuando $j=i+1$) han restado dos veces, por lo que deben agregarse para atrás, y allí se $B_{n-2}$ particiones (independientemente de la opción de $i,j$); y así sucesivamente, alternando los signos. Teniendo en cuenta el número de opciones para $i$, $\{i,j\}$, ..., uno encuentra $$ \sum_{k=0}^{n-1}(-1)^k\binom{n-1}kB_{n-k}. $$ La primera Campana de números (omitiendo $B_0$, lo que nunca ocurre en esta fórmula)$1,2,15,52,203,877$, y el cálculo de la fórmula anterior (que se puede hacer fácilmente mediante la toma repetida de las diferencias) es difícil que no se note que evalúa a $B_{n-1}$, al menos para las pequeñas $n$. De hecho estos cálculos son la reproducción de la Campana triángulo de una manera inusual (en el arreglo, como se muestra en el enlace, se comienza con la Campana de los números en el borde de la derecha, a continuación, calcula las sucesivas filas de derecha a izquierda, cada valor es la diferencia de las rectas a su derecha y a su superior derecho; el orden habitual de la construcción es mediante la adición de izquierda a derecha); esto muestra una corazonada debe ser cierto en general. Para entender por qué $B_{n-1}$ es la respuesta, voy a dejar la opción de deducir $$ B_{n-1}=\sum_{k=0}^{n-1}(-1)^k\binom{n-1}kB_{n-k} \quad\text{de}\quad B_{n+1}=\sum_{k=0}^{n} \binom{n}{k} B_k $$ (el último es mencionado aquí; la deducción es fácil) o se busca la explicación de la Campana triángulo, o de la interpretación de la combinatoria argumento en la respuesta por parte de JiK.