I have corrected your use of disjoint and not-disjoint in the above. Up to the last line, I agree; you proved that in a pair of not-disjoint $n$-tuples, one has to be associated to an even permutation, and one to an odd permutation. This makes the set of all even permutations (or all odd permutations) be associated to a set of cardinality $\dfrac {1}{2}(n+1)!$ of pairwise disjoint $n$-tuples What I fail to see is how you argue that such a set of pairwise disjoint $n$-tuples cannot be larger. It is not true that any pair of even/odd permutations is associated to a pair of not-disjoint $n$-tuples, so a simple PHP argument doesn't work.

mavropnevma wrote: I have corrected your use of disjoint and not-disjoint in the above. Up to the last line, I agree; you proved that in a pair of not-disjoint $n$-tuples, one has to be associated to an even permutation, and one to an odd permutation. This makes the set of all even permutations (or all odd permutations) be associated to a set of cardinality $\dfrac {(n+1)!}{2}$ of pairwise disjoint $n$-tuples What I fail to see is how you argue that such a set of pairwise disjoint $n$-tuples cannot be larger. It is not true that any pair of even/odd permutations is associated to a pair of not-disjoint $n$-tuples, so a simple PHP argument doesn't work.

My post was just a simple idea (or how to start this problem), and the statement that the answer would be $\frac{(n+1)!}{2}$ was just a simple assumption(since we can easily find the example of $\frac{(n+1)!}{2}$), and thank you for completing the solution from my idea. p.s. can you tell me what you meant by PHP?

PHP = Pigeon-Hole Principle.

Extend the sequences to permutations of $[n+1]$ in the obvious way. It is not hard to see that $\sigma_1$ and $\sigma_2$ are not disjoint if and only if there is some $i\in[n]$ such that $\sigma_2=(i,n+1)\sigma_1$ (here $(a,b)$ is the transposition that swaps $a$ and $b$). Thus, we see that we can get $\boxed{\frac{(n+1)!}{2}}$ permutations simply by selecting all the even ones. Draw a bipartite graph with one part consisting of the even permutations of size $n+1$ and one part consisting of the odd ones, and draw an edge between two permutations if and only if they are not disjoint. This graph is $n$-regular, so by Hall's theorem, it has a perfect matching. We can select at most one permutation from each edge of the matching, so we select at most $\frac{(n+1)!}{2}$, as desired.

Solved with Professor Alan J. Hoffman, thing 2, TheBigOne, Paul: Let $G$ be a graph where the vertices are $n$-tuples and there is an edge between two non-disjoint $n$-tuples so that we seek the size of the largest independent set of $G.$ Extending each $n$-tuple to a permutation of $S_n,$ we see that $|V| = (n+1)!$ and adjacent vertices correspond to permutations of different signs. Thus, we may pick all of the vertices corresponding to even permutations to obtain the lower bound $(n+1)!/2.$ We now present $4$ unique proofs that $(n+1)!/2$ is optimal. Solution 1: $G$ is $n$-regular and bipartite, so the largest, smallest eigenvalue of $G$ is $\lambda_1 = n, \lambda_{\min} = -n$ respectively. Let $I$ be an independent set. By the Hoffman ratio bound, $|I| \le -|V|\lambda_{\min}/(\lambda_1 - \lambda_{\min}) = (n+1)! n/(2n) = (n+1)!/2.$ Solution 2: Let $m = (n+1)!/2.$ WLOG let $S$ contain $k$ odd and $\ge m+1-k$ even vertices. Picking an odd vertex $v$ at random, the expected number of edges in $S$ containing $v$ is $nPr(v \in S)Pr(neighbor \in S) = nk(m+1-k)/m^2 \ge nm/m^2 = n/m$ where the 2nd to last step follows from $k \ne 0.$ Letting $E$ be the number of edges in $S,$ we get $E \ge \frac{n}{m} \cdot m = n \ge 1,$ so $S$ is not an independent set. Soluton 3: Shoutouts to Paul for asking for help on this problem and thing2 for immediately replying "Hall?" without any explanation. The proof via Hall's Theorem is covered in previous posts #3, #6. Solution 4: Credits to TheBigOne for this bijection: pair each $\sigma \in S_{n+1}$ with $(1, n+1)\sigma,$ which is a neighbor of $\sigma.$ If $|S| > (n+1)!/2,$ then $S$ contains a pair by the pigeonhole principle, which means $S$ has an edge and is not independent.

Cute problem! The answer is $\frac{(n+1)!}{2}$. There are clearly a total of $(n+1)!$ tuples. Place the tuples on a graph $G$, with each node its own tuple. Then, connect the tuples with an edge if they are not disjoint. For each tuple $T$, there are a total of $n$ other tuples that are not disjoint with it (the other tuple must contain the number that $T$ does not, and there are $n$ ways to place that number while the other numbers are fixed), which means each node has degree $n$. Furthermore, observe there can't be any odd cycles in $G$, since two non-disjoint tuples differ by at most one place, so if there was an odd cycle tuple would differ with itself in an odd number of spaces, a contradiction. Thus, $G$ is bipartite. Since each vertex has the same degree, this means the two groups of this bipartite graph has the same number of vertices, namely $\frac{(n+1)!}{2}$. We can clearly just take the $\frac{(n+1)!}{2}$ vertices from one of the groups to have $\frac{(n+1)!}{2}$ as the lower bound. By Hall's theorem, $G$ has a perfect matching, so we can only pick one vertex from each match, giving $\frac{(n+1)!}{2}$ as the upper bound and the answer.