¿Cuántos subconjuntos de $A=\{0,1,2,...,n\}$ son tales que no se juntan números consecutivos

Question

Es probable que sea un duplicado, pero no he podido encontrar una pregunta original, así que he creado una nueva.

Dado un conjunto $A=\{1,2,...,n\}$ encontrar la cantidad de sus subconjuntos tal que cada subconjunto no contenga ningún número consecutivo.

Por ejemplo, $\{1,3\}, \varnothing, \{1,3,5\}$ están bien, pero $\{1,2\}, A, \{1,3,n-1,n\}$ no están bien.

He intentado resolver esta tarea utilizando la fórmula de inclusión-exclusión, pero me he quedado atascado al calcular el tercer término. Según la fórmula el resultado deseado es igual a: $$ |\{\text{total # of subsets}\}| - |\{\text{# of subsets with 1 pair of consecutive numbers}\}| + |\{\text{# of subsets with 2 pairs of consecutive numbers}\}| - ... $$ El primer término es fácil, es igual a $2^n$ .

Para calcular el segundo término elijo un par consecutivo de $n-1$ posible y luego calcular subconjuntos con este par incluido. Así que es igual a $(n-1) \cdot 2^{n-2}$ .

Para el 3er término traté de elegir un par de $n-1$ posible, entonces el segundo par de $n-2$ restante y luego calcular la cantidad de subconjuntos con ambos pares incluidos, es decir, sería algo así como $(n-1)(n-2)\cdot 2^{n-4}$ . Pero el problema es que el primer par podría ser $\{1,2\}$ y el segundo es $\{2,3\}$ y habrá $(n-3)$ dígitos que quedan para elegir. Para tener en cuenta esto tendremos que dividir las variantes en estos dos casos. Para el tercer término puede estar bien, pero para los términos posteriores será demasiado complicado, ¿no? ¿Hay alguna solución más agradable?

Answer 1

Dejemos que $A_n = \{1,2,3,\dots,n\}$ . Sea $G_n$ sea el número de subconjuntos "buenos" de $A_n$ . Aquí consideraré que el conjunto vacío es un subconjunto "bueno" de cada $A_n$ .

Para cada subconjunto, $S$ de $A_n$ existe una función $f_{n,S}:A_n \to \{0,1\}$ definir por $f_{n,S}(x)= \begin{cases} 0 & \text{If $x \not \in S$} \\ 1 & \text{If $x \in S$} \\ \end{cases}$

---

\begin{array}{c} & f \\ \text{subset} & 1 & \text{good?} \\ \hline & 0 &\checkmark \\ 1 & 1 &\checkmark \\ \hline \end{array}

Así que $A_1=2$ .

---

\begin{array}{c} & f \\ \text{subset} & 12 & \text{good?} \\ \hline & 00 &\checkmark \\ 1 & 10 &\checkmark \\ 2 & 01 &\checkmark \\ 12 & 11 \\ \hline \end{array}

Así que $A_2=3$ .

---

\begin{array}{c} & f \\ \text{subset} & 123 & \text{good?} \\ \hline & 000 &\checkmark &\text{Compare to $A_2$}\\ 1 & 100 &\checkmark \\ 2 & 010 &\checkmark \\ 12 & 110 \\ \hline 3 & 001 &\checkmark &\text{Compare to $A_1$}\\ 13 & 101 &\checkmark \\ 23 & 011 & \\ 123 & 111 \\ \hline \end{array}

Así que $A_3=A_1+A_2=5$ .

---

\begin{array}{c} & f \\ \text{subset} & 1234 & \text{good?} \\ \hline & 0000 &\checkmark &\text{Compare to $A_3$}\\ 1 & 1000 &\checkmark \\ 2 & 0100 &\checkmark \\ 12 & 1100 \\ 3 & 0010 &\checkmark \\ 13 & 1010 &\checkmark \\ 23 & 0110 & \\ 123 & 1110 \\ \hline 4 & 0001 &\checkmark &\text{Compare to $A_2$}\\ 14 & 1001 &\checkmark \\ 24 & 0101 &\checkmark \\ 124 & 1101 \\ 34 & 0011 & \\ 134 & 1011 & \\ 234 & 0111 & \\ 1234 & 1111 \\ \hline \end{array}

Así que $A_4=A_2+A_3=8$ .

---

Así que parece que $A_1=2, \quad A_2=3, \quad$ y $A_{n+2}=A_n + A_{n+1}$ Así, $A_n = F_{n+2}$ El $(n+2)^{th}$ número de fibonacci.

Answer 2

Suponiendo que el subconjunto no sea el conjunto vacío, elegimos primero el valor más pequeño valor:

$$\frac{z}{1-z}.$$

A continuación, sumamos al menos dos veces para obtener los valores restantes:

$$\frac{z}{1-z} \sum_{m\ge 0} \left(\frac{z^2}{1-z}\right)^m = \frac{z}{1-z} \frac{1}{1-z^2/(1-z)} = \frac{z}{1-z-z^2}.$$

Por último, recogemos las contribuciones que suman como máximo $n$ y añadir una para tener en cuenta el conjunto vacío:

$$1+ [z^n] \frac{1}{1-z} \frac{z}{1-z-z^2} \\ = [z^n] \frac{1}{1-z} + [z^n] \frac{1}{1-z} \frac{z}{1-z-z^2} \\ = [z^n] \frac{1}{1-z} \frac{1-z^2}{1-z-z^2} \\ = [z^n] \frac{1+z}{1-z-z^2}.$$

Llamar a la OGF $G(z)$ tenemos

$$G(z) (1-z-z^2) = 1 + z$$

de modo que para $[z^0]$ obtenemos

$$[z^0] G(z) (1-z-z^2) = 1$$

o $g_0 = 1.$ También obtenemos

$$[z^1] G(z) (1-z-z^2) = 1$$

o $g_1-g_0 = 1$ o $g_1=2.$ Tenemos al final para $n\ge 2$

$$g_n-g_{n-1}-g_{n-2} = 0,$$

que es la recurrencia del número de Fibonacci. Con estos dos valores iniciales obtenemos

$$\bbox[5px,border:2px solid #00A000]{ F_{n+2}.}$$