¿Cuántos subconjuntos no contienen elementos consecutivos?

Question

¿Cuántos subconjuntos de $\{1,2,...,n\}$ no tienen dos números consecutivos?

Aquí está la solución:

Los subconjuntos se interpretan como $n$ -palabras del alfabeto $\{0,1\}$ . Deje que $a_n$ sea el número de palabras sin consecutivos. Entonces, una palabra puede empezar desde $0$ y proceder en $a_{n-1}$ o empezar con $10$ y proceder en $a_{n-2}$ maneras. Por lo tanto, $a_{n} = a_{n-1} + a_{n-2}$ . $a_1 = 2, a_2 = 3$ . Así que.., $a_n = F_{n+2}$ .

No tengo problemas para entender la parte del argumento que vincula $a_n$ con los números de Fibonacci. Pero, tengo problemas para entender el argumento bijectivo.

¿Qué es un $n$ ¿la palabra? Y, ¿cómo se construye el bijectivo aquí? ¿Cómo se construye $a_n$ vinculado a la pregunta?

Answer 1

Un $n$ -palabra es una palabra de longitud $n$ . Llamar a un conjunto sin consecutivos bueno .

Hay dos tipos de conjuntos buenos (i) los que no contienen $1$ y (ii) los que contienen $1$ .

Hay $a_{n-1}$ buenos subconjuntos de $\{1,2,\dots,n\}$ de Tipo $1$ . Hay $a_{n-2}$ buenos subconjuntos de $\{1,2,\dots,n\}$ del tipo (ii), ya que si nuestro conjunto contiene $1$ entonces $2$ está prohibido.

Observación: El autor ha optado por expresarse en términos de funciones características en lugar de subconjuntos. Eso no supone ninguna diferencia, las funciones características y los subconjuntos son esencialmente lo mismo.

Answer 2

Un $n$ -palabra es sólo una cadena binaria de longitud $n$ . Dado un $n$ -puede construir un subconjunto de $\{1,2,\ldots,n\}$ incluyendo $i$ si y sólo si el $i$ dígito del $n$ -la palabra es un $1$ y viceversa. Esta es la biyección. En el problema que nos ocupa, un subconjunto no tiene números consecutivos si y sólo si su correspondiente $n$ -la palabra no tiene adyacentes $1$ 's.

Answer 3

Elija el primer valor del conjunto:

$$\sum_{q=1}^n z^q = z \sum_{q=0}^{n-1} z^q = z\frac{1-z^n}{1-z}.$$

Elige un número de huecos que sea al menos dos:

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

Suma las contribuciones que terminan como máximo en $n$ y extraer el coeficiente:

$$[z^n] \frac{1}{1-z} z\frac{1-z^n}{1-z} \frac{1-z^{2n}/(1-z)^n}{1-z^2/(1-z)} \\ = [z^{n-1}] \frac{1-z^n}{1-z} \frac{1-z^{2n}/(1-z)^n}{1-z-z^2}.$$

Eliminar los términos que no contribuyen a $[z^{n-1}],$ primero

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

y segundo

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

Extrayendo los coeficientes obtenemos

$$F_{n-1} + 2 F_n - 1 = F_n + F_{n+1} - 1 = F_{n+2} - 1.$$

Observación. Aquí no hemos contado el conjunto vacío como se señala en los comentarios. La respuesta es $$F_{n+2}$$ si se incluye el conjunto vacío, lo que debería ser.

Answer 4

A $n$ -palabra es una palabra con $n$ las letras, 00, 01, 10, 11 son las $2$ -palabras del alfabeto $\{0,1\}$ .

Propuesta. Dejemos que $E$ sea un conjunto, entonces los subconjuntos de $E$ están en biyección con $\{0,1\}^E$ .

Prueba. Definamos el siguiente mapa: $$\varphi:\left\{\begin{array}{ccc}\mathcal{P}(E)&\to&\{0,1\}^E\\A&\mapsto&x\in E\mapsto\left\{\begin{array}{ll}0&\textrm{, if }x\notin A\\1&\textrm{, if }x\in A\end{array}\right.\end{array}\right..$$ $\varphi$ es una biyección cuya inversa viene dada por: $$\left\{\begin{array}{ccc}\{0,1\}^E&\to&\mathcal{P}(E)\\f&\mapsto&\{x\in E\textrm{ s.t. }f(x)=1\}\end{array}\right..$$ De ahí el resultado. $\Box$

En su caso, su proposición nos dice que los subconjuntos de $\{1,\cdots,n\}$ están en biyección con $\{0,1\}^{\{1,\cdots,n\}}$ , es decir, el $n$ -palabras del alfabeto $\{0,1\}$ .

¿Puedes ver desde ahí por qué el número de $n$ -palabras sin consecutivo $1$ s es el número de subconjuntos de $\{1,\cdots,n\}$ sin números consecutivos?

Answer 5

Un $n$ -palabra es sólo una cadena binaria de longitud $n$ .

Por ejemplo, si $n=4$ Hay $2^4=16$ subconjuntos de $\{1,2,3,4\}$ . Un subconjunto $A \subseteq \{1,2,3,4\}$ corresponde a la cadena binaria $a_1 a_2 a_3 a_4$ , donde $a_i = 1$ si $i \in A$ y $a_i=0$ si $i \notin A$ . En otras palabras, se pone un $1$ en el $i$ de la cadena si el elemento $i$ está en el subconjunto. Por lo tanto, a $1$ en la cadena significa "el elemento está presente en el subconjunto" y un $0$ significa "el elemento está ausente en el subconjunto". Por ejemplo, el subconjunto $\{2,3\}$ corresponde a la cadena binaria $\{0110\}$ donde el $1$ le indican qué elementos están presentes en el subconjunto.

Está claro que el número de cadenas binarias de longitud $n$ es $2^n$ porque cada uno de los $n$ Los bits se pueden elegir de dos maneras. Obsérvese que un subconjunto $A$ contiene dos enteros consecutivos si y sólo si los correspondientes $n$ -La cadena de bits contiene dos $1$ 's.