Número de subconjuntos no vacíos $A \subset \{1,...,n\}$ tal que el elemento más pequeño de $A$ es igual al número de elementos en $A$

Question

Dejemos que $g_n$ denotan el número de subconjuntos no vacíos $A \subset \{1,...,n\}$ tal que el elemento más pequeño de $A$ es igual al número de elementos en $A$ . Por ejemplo, si $n = 5$ , entonces los posibles subconjuntos A son: $\{1\}, \{2, 3\}, \{2, 4\}, \{2, 5\}, \{3, 4, 5\}$ . Encuentra y demuestra una recurrencia para $g_n$ .

Simplemente escribiendo todos los casos, está claro que la recurrencia es $$g_n=g_{n-1}+g_{n-2}$$ pero no puedo terminar una prueba de ello. Está bastante claro que todo $g_{n-1}$ subconjuntos en el $n-1$ caso se incluyen en el número total de subconjuntos del $n$ caso, pero no puedo encontrar una biyección entre el número de subconjuntos adicionales y $g_{n-2}$ . ¡Cualquier ayuda para hacerlo y/o dirección para un enfoque diferente de esta prueba sería increíble!

Answer 1

Si un subconjunto de $\{1,\ldots,n\}$ tiene $k$ y su elemento más pequeño es $k$ entonces es de la forma $\{k\}\cup S$ , donde $S$ es un subconjunto de $\{k+1,\ldots,n\}$ de $k-1$ elementos. A la inversa, para cada $k$ y cada $S\subset\{k+1,\ldots,n\}$ de $k-1$ elementos el conjunto $\{k\}\cup S$ tiene $k$ y su elemento más pequeño es $k$ . Así que $$g_n=\sum_{k=1}^n\binom{n-k}{k-1}.$$ Se podría interpretar como un $0$ -de orden, que es un poco artificioso, o elegir sabiamente alguna recurrencia para los coeficientes binomiales, y luego fabricar eso en un $1$ -recurrencia de primer orden para $g_n$ .

Answer 2

Tenemos $g_n = g_{n-1}+g_{n-2}$ .

Prueba:

De los subconjuntos de $\{1,2,\dots,n\}$ claramente hay $g_{n-1}$ subconjuntos que no contienen $n$ .

Ahora mostramos que hay $g_{n-2}$ subconjuntos que lo hacen. Para ello, consideremos la siguiente transformación: Dado un subconjunto que contiene $n$ eliminamos $n$ y reducir cada elemento en $1$ . Esto nos da un conjunto válido siempre que el conjunto no contenga $1$ (pero no puede contener $1$ y $n$ al mismo tiempo). A la inversa, también podemos tomar un subconjunto de $\{1,2,\dots,n-2\}$ que funcione y aumente todo por $1$ y añadir el elemento $n$ . Hemos dado una biyección entre ambas familias.

Por lo tanto, hay $g_{n-1}$ que no contienen $n$ y $g_{n-2}$ que sí.

Answer 3

Hay $g_{n-2}$ subconjuntos con la propiedad especificada en $[n-2]$ . Ahora bien, dado dicho conjunto, añade uno a cada uno de los elementos del conjunto y luego une el elemento $n$ . Esto dará la biyección.