Contar el número de divisiones de un conjunto recursivamente.

Question

Estoy tratando de entender el razonamiento detrás de la respuesta a la siguiente pregunta de un viejo examen.

Dado un conjunto $S_n = \{ 1, 2, 3,\dots n\}$ encontrar cuántas divisiones, $K_n$, hay de el usando únicamente los subconjuntos de 1 o 2 miembros. Por ejemplo, $\{ \{1,4\}, 6 , 2, \{5,3\} \}$ es una posible división de $S_6$.

Encontrar una definición recursiva de $K_n$.

Así que la primera cosa que hice fue calcular algunos de los términos combinatoria:

$K_1 = \binom{1}{1} = 1$

$K_2 = \binom{2}{2} + \binom{2}{2} = 2$

$K_3 = \binom{3}{3} + \binom{3}{2} = 4$

$K_4 = \binom{4}{4} + \binom{4}{2} + \frac{\binom{4}{2}}{2!} = 10$

$K_5 = \binom{5}{5} + \binom{5}{2} + \frac{\binom{5}{2}\binom{3}{2}}{2!} = 26$

$K_6 = \binom{6}{6} + \binom{6}{2} + \frac{\binom{6}{2}\binom{4}{2}}{2!} + \frac{\binom{6}{2}\binom{4}{2}}{3!} = 76$

Y así sucesivamente. La definición recursiva dada fue de $K_n = K_{n-1} + (n-1)\cdot K_{n-2}$

Entiendo que la primera mitad de la definición. Usted toma el número de $n$ y agregarlo como un conjunto de 1 para cada uno de los conjuntos en $K_{n-1}$ dándole $K_{n-1}$ nuevos sets en $K_n$. Sin embargo, yo estoy completamente en una pérdida para el razonamiento detrás de la segunda mitad de la definición.

Answer 1

Un grupo de $n$ de la gente llega a un hotel. Queremos seleccionar a $0$ o más pares de ellos. Emparejado la gente va a compartir una habitación. No apareados de la gente, si los hubiere, se obtiene de las habitaciones individuales. Deje $K_n$ el número de maneras de hacer esto.

Nos concentramos en lo que sucede a la persona $n$. (I) (s)se obtiene una sola habitación, o (ii) (s)se obtiene emparejado con alguien para compartir una habitación.

En el caso (i), tenemos $n-1$ a la gente de izquierda para hacer frente, y el número de maneras en que puede ser dividido es, por definición,$K_{n-1}$.

En el caso (ii), persona $n$'s compañero de cuarto puede ser elegido en $n-1$ maneras. Para cada una de estas formas, la $n-2$ de las personas que se quedan, por definición, puede ser dividido en $K_{n-2}$ maneras. Por lo que el número de maneras de hacer un caso (ii) la división de $(n-1)K_{n-2}$.

Hemos demostrado que de la $K_n$ maneras de dividir $n$ de la gente, $K_{n-1}$ son de tipo (i), y $(n-1)K_{n-2}$ son de tipo (ii). Que tenga en cuenta todas las formas de la división de un grupo de $n$, y por lo tanto $$K_n=K_{n-1}+(n-1)K_{n-2}.\qquad\qquad(\ast)$$ Está claro que $K_1=1$$K_2=2$. Ahora podemos utilizar la recurrencia $(\ast)$ a calcular, mecánicamente, $K_3$, $K_4$, $K_5$, y así sucesivamente.

Observación: se utilizó una estrategia que es bastante común. Aquí hay otro ejemplo. Queremos subir un $n$-de la escalera de la escalera. En cualquier momento, no se les permite ir a por una única escalera (pequeño paso), o por dos escaleras (gran paso). En cuántas formas diferentes podemos llegar a la cima? Deje que el número de maneras de ser $W_n$.

El $n$-th (y último) de la escalera fue (i) alcanza a partir de la $(n-1)$-ésimo de la escalera, por tomar un pequeño paso, o (ii) se llegó a ella directamente desde la $(n-2)$-ésimo de la escalera, por tomar un gran paso.

En el caso (i), hemos tenido que llegar a la escalera $n-1$, y por definición, esto se puede hacer en $W_{n-1}$ maneras.

En el caso (ii), teníamos que llegar a la escalera $n-2$ antes de tomando nuestro terminal gran paso. Esto se puede hacer en $W_{n-2}$ maneras.

De ello se sigue que $$W_n=W_{n-1}+W_{n-2},$$ y se han obtenido los familiares de Fibonacci de la recurrencia.

Answer 2

Echemos un vistazo a la recurrencia ... definamos la función de generación exponencial$\hat{K}(z) = \sum_{n \ge 0} K_n \frac{z^n}{n!}$ (para compensar el$n - 1$ factor), y escribimos: $$ K_ {n + 1} = K_n + n K_ { n - 1} \ qquad K_0 = K_1 = 1 $$ Usando propiedades de funciones de generación exponencial: $$ \ hat {K} '(z) = \ hat {K} (z) + z \ frac {d} {dz} \ int \ hat {K} (z) dz $$ Así: $$ \ int_1 ^ \ hat {K} \ frac {d \ hat {K} '} {\ hat {K}} = \ int_0 ^ z (1 + z) dz $$ y así: $$ \ hat {K} (z) = e ^ {z + z ^ 2/2} $$ para que$K_n = 1, 1, 2, 4, 5, \ldots$