Descomposición de $2^{[n]}$ en $\binom{n}{n/2}$ cadenas

Question

Estoy luchando con este problema:

Sea n un número par, y denotemos $[n]=\{1,2,...,n\}$ . Una secuencia de conjuntos $S_1 , S_2 , \cdots , S_m \subseteq [n]$ se considera elegante si:

1. $m$ es impar.
2. $S_1 \subset S_2 \subset \cdots \subset S_m \subseteq [n]$
3. $\forall m \in \{1,...,m-1\}: \; |S_{i+1}|=|S_i|+1$
4. $|S_m|+|S_1|=n$

Demuestre que es posible descomponer el $2^n$ subconjuntos de $[n]$ utilizando $\binom{n}{n/2}$ cadenas graciosas. Las diferentes cadenas pueden tener diferentes longitudes. Cada subconjunto de $[n]$ debe aparecer en una, y sólo una, cadena.

Me he dado cuenta de que $$|S_1|=\frac{n-m+1}{2}, \; |S_i|=\frac{n-m+2i-1}{2}$$ para cualquier elección válida de $m$ . Además, sugiere $m\in\{1,3,...,n+1\}$ . También está claro que una de las cadenas debe ser $$\emptyset\subset\{1\}\subset\{1,2\}\subset\cdots\subset\{1,...,n\}$$ donde todos los conjuntos interiores de esta cadena pueden ser elegidos arbitrariamente.

Agradecería cualquier ayuda.

Answer 1

Lo que está construyendo se conoce en la literatura como descomposición simétrica en cadena del conjunto parcialmente ordenado de los subconjuntos de $[n]$ . Por lo tanto, utilizaré "simétrico" en lugar de "elegante" en todo el texto.

---

Hay una solución explícita utilizando la factorización catalana, que aprendí de este trabajo de Ömer Eğecioğlu y Alastair King . Identificar subconjuntos de $[n]$ con secuencias de longitud $n$ con entradas en $\{0,1\}$ . La factorización catalana se obtiene como sigue:

1. En primer lugar, subraya dos entradas cualesquiera que sean un $1$ seguido de un $0$ con sólo las entradas subrayadas entre ellas. Repita este paso hasta que no queden entradas de este tipo.

2. Ahora, las entradas que no están subrayadas estarán formadas por algún número de $0$ seguido de un cierto número de $1$ 's. Si no, no habríamos terminado con el paso $1$ .

3. Por último, cualquier entrada que no esté subrayada se sustituye por un nuevo símbolo, $z$ . Además, el número de $1$ que se convirtió en $z$ se registra como un número $k$ . Este resultado final, que consiste en la $(0,1,z)-$ secuencia y el número $k$ es la factorización catalana.

Tenga en cuenta que puede recuperar la palabra binaria original a partir de la factorización catalana sustituyendo la última $k$ casos de $z$ con un $1$ y todos los demás $z$ con un $0$ .

Daré un ejemplo en breve, pero permítanme primero decir cómo la factorización catalana da una descomposición en cadena elegante. Podemos pensar en la factorización catalana como un par ordenado $(w,k)$ , donde $w$ es el $(0,1,z)-$ secuencia, y $k$ es el número de $z$ que representan $1$ 's. Dos subconjuntos están en la misma composición cuando tienen la misma palabra $w$ para su factorización catalana. Es decir, para cada secuencia $w$ donde el número de $z$ es $m$ entonces $$ (w,0)\subset (w,1)\subset\dots\subset (w,m) $$ representa una cadena simétrica de subconjuntos.

---

Ejemplo: Con $n=15$ , considere el subconjunto $$\{2,3,5,9,10,13,14,15\}$$

Esto corresponde a la secuencia binaria $$ 011010001100111 $$ donde el $i^{th}$ entrada siendo $1$ significa $i$ está en el subconjunto. Primero subrayamos todas las instancias de un $1$ seguido inmediatamente por un $0$ : $$ 01\underline{1010}001\underline{10}0111 $$ Esto crea más pares de $1$ s seguido de $0$ s con sólo las entradas subrayadas entre ellas, así que continuamos: $$ 0\underline{110100}0\underline{1100}111 $$ Ahora, todos los ceros no subrayados ocurren antes de todos los unos no subrayados, así que hemos terminado. Terminamos sustituyendo todas las entradas no subrayadas por un $z$ y anotando el número de $1$ s: $$ z110100z1100zzz,\qquad k=3 $$ Por lo tanto, este subconjunto estará en una cadena simétrica de longitud $6$ correspondientes a los subconjuntos formados manteniendo la misma palabra y sustituyendo $k$ con los números entre $0$ y $5$ inclusive. Esto se ilustra a continuación: $$ \begin{array}{c|c|c} k& \text{binary word} & \text{subset}\\ \hline 0 & 0\underline{110100}0\underline{1100}000 & \{2,3,5,9,10\}\\ 1 & 0\underline{110100}0\underline{1100}001 & \{2,3,5,9,10,15\}\\ 2 & 0\underline{110100}0\underline{1100}011 & \{2,3,5,9,10,14,15\}\\ 3 & 0\underline{110100}0\underline{1100}111 & \{2,3,5,9,10,13,14,15\}\\ 4 & 0\underline{110100}1\underline{1100}111 & \{2,3,5,8,9,10,13,14,15\}\\ 5 & 1\underline{110100}1\underline{1100}111 & \{1,2,3,5,8,9,10,13,14,15\}\\ \end{array} $$

Answer 2

Viendo que Mike Earnest ya ha proporcionado algunas buenas referencias y también una forma de construir una descomposición elegante, me limitaré a publicar algunos de mis comentarios.

1. Se puede ver que el elemento central de cada cadena tiene que ser un subconjunto de $[n]$ con tamaño $n / 2$ . Es decir, para una cadena de tamaño $m$ , $|S_{(m + 1)/2}| = n / 2$ . Dado que cualquier cadena incluye algunos $S_m$ con $|S_m| = n / 2$ y además cada uno de los ${n \choose n / 2}$ subconjuntos de tamaño $n/2$ está incluido en exactamente una cadena, cualquier descomposición graciosa realmente debe tienen ${n \choose n / 2}$ cadenas.

2. Creo que hay una forma sencilla de construir las cadenas. Construyamos el dígrafo $G$ cuyos vértices $S_i$ son subconjuntos de $[n]$ y hay un borde de $S_i$ a $S_j$ si y sólo si $S_i \subset S_j$ y $|S_j| = |S_i| + 1$ . Inicializar $\Sigma = V(G)$ Entonces, haz lo siguiente:

• Encontrar un elemento $\sigma \in \Sigma$ del tamaño más pequeño; si $\Sigma$ está vacío, entonces el algoritmo termina. Supongamos que $|\sigma| = k$ . Construiremos una cadena en la que $\sigma$ es el primer elemento de la cadena. Inicializar $i = k + 1$ .
• Mientras que $i \leq n - k$ , elija cualquier $\sigma_{i+1}$ que es un vecino externo de $\sigma_i$ para ser el siguiente elemento de la cadena. Incremento $i$ y eliminar $\sigma_i$ de $\Sigma$ .

La exactitud de este algoritmo se basa en un par de hechos. Las cuatro propiedades de las cadenas graciosas pueden verificarse fácilmente para este algoritmo. Además, cada elemento se incluye una vez y exactamente una vez en alguna cadena, ya que cada elemento está inicialmente en $\Sigma$ y se elimina cuando se añade a una cadena (el algoritmo no se detiene hasta que $\Sigma$ está vacío).

La parte un poco complicada es explicar por qué el algoritmo nunca se atasca. En concreto, tenemos que demostrar que en el segundo punto, siempre podemos encontrar un vecino externo $\sigma_{i+1}$ de $\sigma_{i}$ si $i < n - k$ . Supongamos lo contrario, es decir, que en algún momento del algoritmo nos encontramos con un $\sigma_i$ sin un vecino externo $\sigma_{i+1}$ que no haya sido ya utilizado. Tenga en cuenta que $|\sigma_i| = i$ y $\sigma_{i}$ tiene $n - i$ a los vecinos. Para que este mal escenario ocurra, debemos haber creado al menos $n - i$ cadenas, cada una con algún elemento $\sigma$ donde $|\sigma| = i$ . Por supuesto, cualquier cadena con un elemento de tamaño $i$ debe tener también un elemento de tamaño $n - i$ ya que se estableció previamente que todo elemento medio de la cadena es de tamaño $n/2$ .

Aquí está el hecho crucial: el número de subconjuntos de $2^{[n]}$ de tamaño $i$ es exactamente igual al número de subconjuntos de tamaño $n - i$ por lo que, de hecho, debe haberse dado el caso de que antes de esta iteración del algoritmo, todos los subconjuntos de longitud $i$ se había incluido en una cadena que ya habíamos construido. (Nótese que aquí es importante señalar que todas las cadenas creadas por el algoritmo son graciosas). Pero esto contradice el hecho de que $\sigma_i$ que tiene un tamaño $i$ no se ha incluido en una cadena. $\square$