Maximum number of subsets of $\{1,2,\dots,n\}$ of cardinalities $1, \ldots, \ell$ that are not included in each other Given a natural number $n \ge 4 $, what is the maximum number $\ell$ of subsets $A_1,A_2,\ldots, A_\ell$ of $\{1,2,\ldots,n\}$ satisfying:


*

*$A_i$ contains exactly $i$ elements for $1 \le i \le \ell$.

*None of the subsets $A_i$ is included in any other.


I tried small examples but I don't see the pattern.
Any ideas are welcome.
 A: For $n \geq 4$, the maximum is $n-2$.
Clearly, $\ell \geq n-1$ is impossible: wlog $A_1 = \{1\}$ and $A_2 = \{2, 3\}$. Because $\ell \geq n-1 \geq 3$, we have $\ell \neq 1, 2$ and hence $1 \notin A_\ell$ and wlog $2 \notin A_\ell$. So $\ell = |A_\ell| \leq n-2$.
We can obtain $\ell = n-2$ as follows: For $1 \leq k \leq n/2$, define
$$A_k = \{2, 4, \ldots, 2(k-1) \} \cup \{2k-1\}$$
and
$$A_{n-1-k} = \{2, 4, \ldots, 2(k-1) \} \cup \{2k+1, 2k+2, \ldots, n \}$$
(If $n$ is odd and $k = \frac{n-1}2$, both of the above choices work.)
It is easy to check none of these sets includes another.

One can come up with these sets as follows: wlog $A_1 = \{1\}$.
All other $A_k$ must not contain $1$. Thus wlog $A_{n-2} = [3, n]$.
All other $A_k$ must not contain $1$, and must contain $2$ (otherwise they are a subsetof $A_{n-2}$). Thus wlog $A_2 = \{2, 3\}$.
All other $A_k$ must not contain $1$ and must contain $2$ but not $3$. Thus wlog $A_{n-3} = \{2 \} \cup [5, n]$.
All other $A_k$ must not contain $1$ nor $3$, and must contain $2$ and $4$ (otherwise they are a subset of $A_{n-3}$). Thus wlog $A_3 = \{2, 4, 5\}$.
All other $A_k$ must contain $2$ and $4$, but not $1$ nor $3$ nor $5$. Thus wlog $A_{n-4} = \{2, 4 \} \cup [7, n]$. And so on.
That is, up to permutation the choice of $A_k$ above is the only one: there are $n!$ possibilities.
A: Let the maximum $l$ for some $n$ be given by $l_n$.
The first thing to note is that $l_n \leq n-2$ for all $n\geq 4$ as the element in $A_1$ cannot be in $A_{l_n}$ and atmost one of the two elements in $A_2$ can be in $A_{l_n}$.
Now, we shall prove that $l_n = n-2$ for all $n\geq 4$.
We have that $l_4=2$ as we have $A_1=\{1\},A_2=\{2,3\}$ as a solution.
Also, $l_5=3$ as we have $A_1=\{1\}, A_2=\{2,3\}$ and $A_3=\{2,4,5\}$ as a solution. 
For $n\geq 6$, let $l_k=k-2$ for all $k\leq n$.
Let $A_1=\{1\}$. Let $A_{n-2}=\{3,4,\cdots,n\}$. Now, let $3=1'$, $4=2'$ and so on. (Rename $i+2$ as $i'$ for $1\leq i\leq n-2$).
We can find $n-4$ subsets $A'_i, 1\leq i\leq n-4$ satisfying the given conditions for $\{1',2',3',\cdots,(n-2)'\}.$
Finally, let $A_k=\{2\}\cup A'_{k-1}$.
We have this as a solution as:


*

*$\{1\}\not\subseteq A_i$ for $i\geq 1$

*$A_k\not\subseteq A_{n-2}$ for $2\leq k\leq n-3$ as $2\in A_k$ but $2\not\in A_{n-2}$.

*$A_i\not\subseteq A_j$ for $2\leq i<j\leq n-3$ as we have defined the $A_i$'s in terms of a previous solution in such a way that no subset is contained in another. (We have used the fact that $l_{n-2}=n-4$)


As we have $l_5=3$ and $l_6=4$, $l_n = n-2$ for all $n\geq 4$.


For example, take $n=6$.
We have $A_1 = \{1\}$, $A_2=\{2\}\cup \{1'\}=\{2,3\}$, $A_3=\{2\}\cup\{2',3'\}=\{2,4,5\}$ and $A_4=\{3,4,5,6\}.$
