Define a selfish set to be a set which has its own cardinality (number of elements) as an element. Find, with proof, the number of subsets of $\{1, 2, \ldots, n\}$ which are minimal selfish sets, that is, selfish sets none of whose proper subsets is selfish.
My Attempt:
Assume $\textbf{A}$ to be a selfish set. If the cardinality of $\textbf{A}$ is $c$, then can $\textbf{A}$ contain $1,2,3….c-1$. Definitely answer is no. because if it contains $k<c$ then deleting $c-k$ elements except $k$ from $\textbf{A}$ gives a subset of k elements contradicting the fact that $\textbf{A}$ is minimal selfish.
Thus $\textbf{A}$ must contain elements greater than or equal to $c$. But how do I find the minimal selfish sets with order $c$?
Best Answer
Your argument is correct.
Lets see if recursion helps.
Let $[n]$ denote the set $\{1,2,\ldots,n\}$, and let $f_n$ denote the number of minimal selfish subsets of $[n]$. Then the number of minimal selfish subsets of $[n]$ not containing $n$ is equal to $f_{n-1}$. On the other hand, for any minimal selfish subset of $[n]$ containing $n$, by subtracting 1 from each element, and then taking away the element $n-1$ from the set, we obtain a minimal selfish subset of $[n-2]$ (since $1$ and $n$ cannot both occur in a selfish set). Conversely, any minimal selfish subset of $[n-2]$ gives rise to a minimal selfish subset of $[n]$ containing $n$ by the inverse procedure. Hence the number of minimal selfish subsets of $[n]$ containing $n$ is $f_{n-2}$. Thus we obtain $f_n=f_{n-1}+f_{n-2}$. Since $f_1=f_2=1$, we have $f_n=F_n$, where $F_n$ denotes the $n$th term of the Fibonacci sequence.