Prueba inductiva de que $S_{m,2} = 2^{m-1} - 1$ (conjuntos de división)

Question

$S_{m,l}$ es el número de posibilidades de dividir un conjunto de $m$ elementos en $l$ conjuntos no vacíos ( $m,l 1$ ).

Obviamente, $S_{m,1} = 1$ para todos $m 1$

Cómo prueba inductivamente sobre $m$ que $S_{m,2} = 2^{m-1} - 1$

Permítanme darles un ejemplo de esto:

M = {a,b,c,d}

m = 4 (porque M tiene 4 elementos)

$S_{4,2} = 2^{4-1} - 1 = 7$ (Así que podemos dividir M en 7 conjuntos de 2 diferentes no vacíos). Esos fueron:

1. $\{a\},\{b,c,d\}$
2. $\{b\},\{a,c,d\}$
3. $\{c\},\{b,a,d\}$
4. $\{d\},\{b,c,a\}$
5. $\{a,b\},\{c,d\}$
6. $\{a,c\},\{b,d\}$
7. $\{b,c\},\{a,d\}$

Answer 1

Tenga en cuenta que $$ S_{m+1, 2}= S_{m,1}+2S_{m,2}=1+2S_{m,2}\tag{1} $$ clasificando el conjunto de particiones de $[m+1]$ en dos bloques basados en la colocación de $m+1$ . O bien $m+1$ está en su propio bloque (hay $S_{m,1}$ tales particiones) o $m+1$ no está en su propio bloque (en cuyo caso la partición $1,\dotsc,m$ en $2$ y hay dos opciones para el bloque $m$ pertenece).

La ecuación uno junto con la hipótesis inductiva implica el resultado.

Answer 2

Se puede contar el número de subconjuntos, es decir, el conjunto de potencias de un $m$ -conjunto de elementos, luego restar $2$ de la cardinalidad del conjunto potencia porque no se quiere incluir el conjunto vacío y el conjunto entero, y luego se divide por dos. Esto equivale a dividir el conjunto. Cada elemento, excepto el conjunto vacío y el conjunto entero, en el conjunto potencia corresponde a una división, ya que se divide el conjunto en el elemento $A\in\mathcal{P}(\{1,\ldots,m\})$ del conjunto de la potencia y su complemento $A^C$ en $\{1,\ldots,m\}$ . Como no se quiere contar el doble, hay que dividir la cardinalidad de este conjunto de potencias por dos, ya que si no se cuenta con un subconjunto $A$ dos veces: también se cuenta su complemento, pero dividiendo el conjunto en $A$ y $A^C$ es, por supuesto, la misma división que la división en $A^C$ y $A$ .

Así que en realidad estás buscando un argumento de inducción para la cardinalidad del conjunto de potencias de un conjunto finito. Esto es igual a $2^m$ con $m$ la cardinalidad del conjunto finito. El paso base es claro: el conjunto vacío (que tiene cero elementos) sólo tiene como subconjunto el conjunto vacío. Entonces supongamos que cada $m$ El conjunto de elementos tiene $2^m$ subconjuntos, y considerar un $m+1$ conjunto de elementos. Para cada subconjunto del primer $m$ puede incluir o excluir los elementos $m+1$ elemento, dando $2$ posibilidades, por lo que por la hipótesis de inducción hay $2\cdot2^m=2^{m+1}$ tales subconjuntos. Ahora el resultado se sigue por inducción en $\mathbb{N}$ .

Answer 3

Caso base. $m=2$ da $S_{2,2}=2^{2-1}-1=1$ que se mantiene.

Hipótesis inductiva. Supongamos que es cierto para $m$ es decir $S_{m,2}=2^{m-1}-1.$

Paso inductivo. Ahora, veamos a dónde llegamos con $m+1$ . En este caso, utilizamos el Repetición de Stirling $$S_{n,k}=kS_{n-1,k}+S_{n,k-1},$$ y obtener \begin{align*} S_{m+1,2}&=2S_{m,2}+S_{m,1}\\ &=2(2^{m-1}-1)+1\\ &=2^{m}-2+1\\ &=2^m-1, \end{align*} que es precisamente lo que queríamos demostrar.

Sé que esto es un poco off-topic; pero también daré una prueba combinatoria de esta identidad.

---

Considere $S_{m,2}=2^{m-1}-1$ . El lado izquierdo, por supuesto, cuenta el número de maneras de dividir un conjunto de $m$ elementos en dos subconjuntos no vacíos. Ahora, consideremos dos conjuntos $A$ y $B$ . Si primero permitimos que cualquiera de los dos recipientes esté vacío, hay precisamente $2^m$ formas de dividir el conjunto de $m$ elementos en los dos contenedores. Ahora, vamos a eliminar algunas de estas restricciones. En primer lugar, eliminando la condición de que $A$ y $B$ puede estar vacío descarta dos de estos arreglos, por lo que nos quedamos con $2^m-2$ . Por último, eliminando la noción de ordenación de los recipientes; también debemos dividir este número por $2$ . Esto da $$\frac{2^m-2}{2}=2^{m-1}-1,$$ que es la expresión del lado derecho.

Probablemente hay una declaración más correcta de esta prueba en otro lugar, pero pensé que sería bueno ofrecerle esto también.