What is $A-B$_?

$B-A$ is set of the elements that are in $B$ but not in $A$

Let $X_i = \sum _{ j = 0} ^{\left\lfloor\frac{n-i}{3}\right\rfloor} \dbinom{n}{i+3j}, i = 0, 1, 2$ and $M = X_k$ such that $X_k \ge X_{k+1}, X_k \ge X_{k+2}$ where indices are modulo $3$. Let $S_n = \{1, 2, \ldots, n \}$. Consider a set $T$ such that each element of $T$ is of the form $\{\phi, \{a_1\}, \{a_1, a_2\}, \ldots, \{a_1, a_2, \ldots, a_n \} \}$ where $\{a_1, a_2, \ldots, a_n \} = S_n$ and if we have any $K\subset S_n$ with $|K| = k$, then $K$ should occur in $\frac{ \prod_{i = 0} ^{n} \dbinom{n}{i}} {\dbinom{n}{k} }$ elements of $T$. The existence of such a set $T$ can be proven using Hall's Marriage Theorem by considering a set to have $\dbinom{n}{k}$ copies of each subset of $S_n$ of size $k$ and then noticing that there is a matching from subsets of size $k$ and those of size $k+1$ because they can be shown to satisfy Hall's condition and gluing the matchings would give rise to $T$. Let $K$ be any set satisfying the given conditions. Then \[|K| = \frac{\sum_{A\in K}\dbinom{n}{|A|}\cdot \sum_{P}^{A\in P \in T} 1}{|T|} = \frac{\sum_{P\in T} \sum _{A\in P\cap K } \dbinom{n}{|A|}}{|T|}\le \frac{\sum_{P\in T} M}{|T|} = M\] Equality holds when \[K = \bigcup_{j=0}^{\left\lfloor\frac{n-k}{3}\right\rfloor} \{ S| S\subset\{1, 2, \ldots, n\}, |S|=k+3j\}\]

Proposed by Ali Khezeli

is this correct? if we call $X_{n}$ the solution of the problem for $n$ then it is enough to find $X_{1},..,X{6}$ and then continue on knowing what sum of binomial coefficents to take(module $3$ either $1,2,3$)

Let $A_1,A_2,\dots ,A_r$ be sets which satisfies the conditions of the problem. Let $f(A_i)=\{ A_i,A_i\cup \{1\},A_i\cup \{2\},\dots ,A_i\cup \{n\},A_i-\{1\},A_i-\{2\},\dots , A_i-\{n\}\}$. It is easy to see that $|f(A_i)|=n+1$ and 1) $f(A_i)\cap f(A_j)=\varnothing$ or 2) $|A_i-A_j|=1$, $|A_i|=|A_j|$ and so $|f(A_i)\cap f(A_j)|=2$. Can anyone help me to complete this idea?

I think this must be right First, note that the group of all subsets with number of elements $3i+1$ ($n$ is even) or $3i+2$ ($n$ is odd) satisfy the requirements of the problem, the number of the subsets in this group is $\Sigma(\frac{n}{3i+1})$ or $\Sigma(\frac{n}{3i+2})$ one of which equals $\frac{2^{n}-(-1)^{n}}{3}$. We will prove by induction on $n$ that the maximum number of subsets is $\frac{2^{n}-(-1)^{n}}{3}$. The case $n=4$ is obvious. We suppose that we have the answer for $n-1$, and we will prove for $n$. Let's split the group of subsets satisfying the requirements of the problem into $2$ subgroups, on of which contains all subsets which do not contain the element ${1}$ and the other subgroup contains the rest of the subsets. The first subgroup has at most $\frac{2^{n-1}-(-1)^{n-1}}{3}$ by induction, the second subgroup has at most $\frac{2^{n-1}-(-1)^{n-1}}{3}+1$ elements (we can consider subsets $A-\{1\}$ instead of $A$ if $A \neq \{1\}$, then add to the number of that subsets $1$ for the subset $\{1\}$) by induction. This gives the result in case $n$ is odd, still for even $n$ more tricks must be done.

A faster way to see it is as follows: Let $S_n$ be the maximum. We note that $S_1=1,S_2=1$. Now we show that $S_{n+2}=2^n+S_n$, from which we can easily finish by induction. Consider a family of sets satisfying the condition for $n+2$. Note for every $A\subseteq \{1,2,...,n\}$, at most one of $A,A\cup\{n+1\},A\cup\{n+1,n+2\}$ is in the family. For the remaining sets (which contain $n+2$ and exclude $n+1$), we can pick at most $S_n$ more sets. Hence our conclusion follows. Of course, it still remains to show that the maximum can always be attained, but this has been demonstrated in previous posts.

${S_2} = 2$，so we have ${S_n} = \frac{{{2^{n + 1}} + 3 + {{( - 1)}^n}}}{6}$.

Err, another way is to show by straight induction you can split the $2^n$ subsets into the floor of $\frac {2^n} {3}$ chains of $3$ elements and then the last is either a singleton or a chain of $2$, depending on the parity of $n$. The induction step is more or less "clone and combine."

Can someone help me explain the idea of GOUTHAM ? ( I don't understand much his solution)

Can anyone give a more detailed solution for me please? Thank you so much!

Are you sure that for $n$ the answer is $\frac{2^{n}-(-1)^{n}}{3}$ ? For $n=4$ we can get $6$ subsets whereas you predicted to have at most $5$. Here are the $6$ subsets, $\{1,2\},\{2,3\},\{1,3\},\{1,4\},\{2,4\},\{3,4\}$. It seems to have at most $\left \lceil \dfrac{2^n}{3} \right \rceil $ subsets instead. Sorry, in advance if I am wrong somewhere.