'selfish' configurado para ser un conjunto que tiene su propia cardinalidad (número de elementos) como un elemento

Question

Define un conjunto egoísta como un conjunto que tiene su propia cardinalidad (número de elementos) como un elemento. Encuentra, con prueba, el número de subconjuntos de $\{1, 2, \ldots, n\}$ que son conjuntos egoístas minimal, es decir, conjuntos egoístas ninguno de cuyos subconjuntos propios son egoístas.

Mi intento: Supongamos que $\textbf{A}$ es un conjunto egoísta. Si la cardinalidad de $\textbf{A}$ es $c$, entonces ¿puede $\textbf{A}$ contener $1, 2, 3....c-1$? Definitivamente la respuesta es no, porque si contiene $k, entonces al eliminar $c-k$ elementos excepto $k$ de $\textbf{A}$ obtendríamos un subconjunto de k elementos contradiciendo el hecho de que $\textbf{A}$ es egoísta minimal. Por lo tanto, $\textbf{A}$ debe contener elementos mayores o iguales a $c$. ¿Pero cómo encuentro los conjuntos egoístas mínimos con orden $c$?

Answer 1

Tu argumento es correcto.

Vamos a ver si la recursión ayuda.

Sea $[n]$ el conjunto $\{1,2,\ldots,n\}$, y sea $f_n$ el número de subconjuntos egoístas mínimos de $[n]$. Entonces, el número de subconjuntos egoístas mínimos de $[n]$ que no contienen a $n$ es igual a $f_{n-1}$. Por otro lado, para cualquier subconjunto egoísta mínimo de $[n]$ que contenga a $n$, al restar 1 a cada elemento y luego quitar el elemento $n-1$ del conjunto, obtenemos un subconjunto egoísta mínimo de $[n-2]$ (ya que $1$ y $n$ no pueden ocurrir juntos en un conjunto egoísta). A la inversa, cualquier subconjunto egoísta mínimo de $[n-2]$ da lugar a un subconjunto egoísta mínimo de $[n]$ que contiene a $n$ mediante el procedimiento inverso. Por lo tanto, el número de subconjuntos egoístas mínimos de $[n]$ que contienen a $n$ es $f_{n-2}$. Así obtenemos $f_n=f_{n-1}+f_{n-2}$. Dado que $f_1=f_2=1$, tenemos $f_n=F_n$, donde $F_n$ denota el término $n$-ésimo de la secuencia de Fibonacci.

Answer 2

Tu lógica hasta ahora está bien. Entonces, lo que sabes es que, dado que $c$ está en el conjunto, entonces los otros $c-1$ elementos deben ser al menos $c+1$. Hay $\binom{n-c}{c-1}$ formas de elegirlos.

Sumando sobre estos te da el conteo total. Resulta que esto te da el $n^{th}$ número de Fibonacci, lo cual puedes demostrar por inducción (pista: usa la identidad de Pascal).