Las particiones de$\{1,\dots,n\}$ sin enteros consecutivos en cada bloque se cuentan como$B(n-1)$?

Question

Estoy tratando de entender por qué $B(n-1)$ también cuenta el número de particiones de $[n]$ donde no dos enteros consecutivos aparecen en el mismo bloque.

Ahora la campana número $B(n-1)$ cuenta el número de particiones de la $n-1$-establecer $[n-1]$. Supongamos que tomar cualquier partición $\pi$$[n-1]$. Ahora tomando la $i,i+1,\dots,j$ a un máximo de secuencia de dos o más números enteros consecutivos en un bloque, me puede quitar la alternancia de los números enteros $j-1$, $j-3$, $j-5$,... y ponerlos en un bloque con $n$. Hacerlo para todas las secuencias de enteros consecutivos en bloques de $\pi$ le dará una partición de $[n]$ no hay dos números consecutivos.

Creo que esto da una necesaria bijection de las dos cosas, pero si me dan una partición de $[n]$ no hay dos números enteros consecutivos en un bloque, ¿cómo puedo reconstruir la partición de $[n-1]$ a ver que es, de hecho, un bijection?

Gracias!

Answer 1

La relación es de hecho un bijection! Para reconstruir la partición original de $[n-1]$, tomar cada elemento $j \neq n$ en el mismo bloque como $n$ y ponerlo en el bloque que contiene a $j+1$.

Ejemplo: digamos que usted realice su función y llegar a la no-consecutivos partición

{1,3,6}, {5}, {2,4,7}.

A partir de su especificación de cómo elegir qué números para quitar de la original de los bloques, usted sabe que el 2 fue retirado de un bloque que contiene 3, así que poner 2 de vuelta en el bloque {1,3,6}. Del mismo modo, sabemos que 4 fue tomada desde el bloque que contiene 5, así que la puse a 4 de nuevo en el bloque {5}. Por último, acaba de sacar un 7 en su totalidad, y te dejan con la partición original: {1,2,3,6}, {4,5}.