How many subsets can be formed so there won't be a pair of subsets sharing 2 or more of the same elements? Let set $X = ${$0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20$}. Let sets $Y_1, Y_2,...$ be subsets of $X$ that are not empty and no pair has $2$ or more terms in common. How many subsets can be created at most?
I am pretty sure that the maximum is when we create $1$ term and $2$ term subsets, but there may be more. And also, I would like to know how to prove that the maximum is the maximum. Thanks!
 A: More generally, let $n\in\mathbb N$ and let $[n]=\{1,2,3,\dots,n\};$ the maximum size of a family of nonempty subsets of $[n],$ no two of which have two or more elements in common, is $\binom n1+\binom n2=\binom{n+1}2=\frac{n(n+1)}2.$
Proof. Let $S_k$ be the collection of all $k$-element subsets of $[n].$ Clearly $S_1\cup S_2$ is a family of nonempty subsets of $[n],$ no two of which have two or more elements in common, and $|S_1\cup S_2|=\binom n1+\binom n2.$
Now let $S$ be any family of nonempty subsets of $[n]$ such that no two elements of $S$ have two or more elements in common. Define a function $f:S\to S_1\cup S_2$ as follows: for $Y\in S,$ if $Y$ has only one element, let $f(Y)=Y;$ but if $Y$ has two or more elements, let $f(Y)$ be the set consisting of the two smallest elements of $Y.$ Since $f$ is injective, $|S|\le|S_1\cup S_2|.$
A: I tried to sketch a proof using induction. 
Let $X_{n-1}$ be a set with n-1 elements. Let $M_k(n-1)$ be any collection of subsets $Y_i\subseteq X_{n-1}$ such that $Y_i$ is non-empty for all $i$ and for which no pair in $M_k(n-1)$ has 2 or more elements in common. Let $M_{max}(n-1)$ be one of these $M_k(n-1)$ such that $|M_{max}(n-1)|=max_{k}\{ M_k(n-1)\}$. Suppose that $M_{max}(n-1)$ consists of exactly all singletons and doubletons of the set $X_{n-1}$.
Suppose, for sake of contradiction,  that $M_{max}(n+1)$ does not consist of exactly all singletons and doubletons of the set $X_{n+1}$. Then there is a $Y_l\in M_{max}(n+1)$ such that $Y_l$ is neither empty, nor a singleton, nor a doubleton. Then $Y_l$ has more than 2 elements. Then $X_{n+1}-Y_l$ has less then n-1 elements. Then, by the induction hypothesis, $X_{n+1}$ has $1+n+n(n-1)=n^2+1$ such $Y_i$ in $M(n+1)_{max}$, namely the set $Y_l$ (yielding 1 subset) and all singletons (yielding n subsets) and all doubletons of $X_{n+1}$ (yielding $n(n-1)$ subsets). But this is clearly in contradiction with this observation: the collection of subsets consisting of all singletons and doubletons of $X_{n+1}$ has $(n+1)+(n+1)((n+1)-1)=n^2+2n+1>n^2+1$ elements. Thus there is no such $Y_l$. 
