Let $a(n)$ be the number of permutations $\{ x_{i}| 1 \leq i \leq 2n \}$ of $\{ i | 1 \leq i \leq 2n \}$ such that $\left| x_{i}-x_{i+1}\right| = n$ for some $1\leq i<2n$ Consider the $(2n+2)$-element permutations If the elements $\{n+1,2n+2\}$ are adjacent, There are exactly $2(2n+1)!$ possible permutations If the elements $\{n+1,2n+2\}$ are not adjacent, There exist adjacent elements $(p,q)$ such that $p-q=n+1$ for $n+2 \leq p \leq 2n+1$, $1 \leq q \leq n$ Consider the ordered $(2n)$-element subset $\{ y_{i}| 1 \leq i \leq 2n \}$ without the elements $\{n+1,2n+2\}$ Construct the permutation $\{ z_{i}| 1 \leq i \leq 2n \}$ of $\{ i | 1 \leq i \leq 2n \}$ where $z_{i}=\left\{{\begin{tabular}{lll}y_{i}& if & y_{i}n+1 \\ \end{tabular}}$ This permutation also satisfies the property because the elements $\{p,q\}$ will become $\{p-1,q\}$ and will remain adjacent in the new permutation Note that the number of permutations $\{x_{i}\}$ that map to the same permutation $\{z_{i}\}$ is exactly $(2n)(2n-1)$ because there are exactly $(2n)(2n-1)$ ways to insert the elements $\{n+1,2n+2\}$ between adjacent elements in the permutation $\{z_{i}\}$ except between elements $\{p-1,q\}$ Therefore $a(n+1) = a(n) \times (2n)(2n-1)+2(2n+1)!$ $a(1) = 2$ $\frac{ a(n+1) }{ (2n)! }= \frac{ a(n) }{ (2n-2)! }+2(2n+1)$ Let $b(n) = \frac{ a(n+1) }{ (2n)! }$ $b(0) = 2$ $b(n) = b(n-1)+(4n+2)$ $b(n) = b(0)+\sum_{i=1}^{n}{4i+2}= 2+2n(n+2)$ $b(n-1) = 2 n^{2}$ $a(n) = b(n-1) (2n-2)! = 2 n^{2}(2n-2)!$ It is now obvious that $a(n) > \frac{1}{2}(2n)(2n-1) (2n-2)! = \frac{1}{2}(2n)!$

The number of ways $P$ such that the pairs $\{ 1, n+1\},\ldots ,\{n,2n\}$ do not appear as adjacent entries, i.e. the number of ways without property $T$, is by the inclusion-exclusion principle equal to \[P=\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(2n-k)!2^{k}\leq \sum_{k=0}^{2}(-1)^{k}\binom{n}{k}(2n-k)!2^{k}<\frac{(2n)!}{2}\] And the conclusion follows. $\blacksquare$

boxedexe wrote: $\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(2n-k)!2^{k}\leq \sum_{k=0}^{2}(-1)^{k}\binom{n}{k}(2n-k)!2^{k}$ This inequality is far from obvious.

I read about Benferroni's Inequality of the Exclusion and Inclusion principle. If in an inclusion-exclusion, the sum ends after you add, the sum is less than or equal to the finite sum, and if it ends after you subtract, the infinite sum is greater than or equal to the finite sum.

Is this solution correct? Seems rather simple (found in about 20 minutes just now): Let S be the set of permutations without property T, and T the set with. I define the function $ f: S \rightarrow T$ by $ f((x_1,x_2,...,x_{2n})) = (x_2,x_3,....,x_k,x_1,x_{k + 1},...,x_{2n})$ where k is the unique positive integer such that $ |x_1 - x_k| = n$. We first note that the image of f is a set of permutations with only one k such that $ |x_k - x_{k + 1}| = n$, because its domain was S and we have only created one such pair in applying the function. It is therefore a proper subset of T (not containing, for example (1,n+1,2,n+2,....,2n). We next note that it is injective, because we can define an inverse function $ g((y_1,y_2,...,y_{2n})) = (y_{k + 1},y_1,y_2,....,y_{2n})$ where k is the unique integer such that $ |x_k - x_{k + 1}| = n$ defined on the image of f. Thus there exists an injection from S into a proper subset of T, so $ |S| < |T|$ as required.

I found another solution but also am not sure if it's correct: We count those permutations without property $ T$ and show that it is less than $ n(2n-1)!$. At first we take out the numbers from $ n+1$ to $ 2n$. There are then $ n!$ ways to permute the numbers $ 1$ through $ n$. Let a permutation of these numbers be $ \{a_1, a_2, ..., a_n\}$. Now we begin inserting the rest of the numbers. There are currently $ n+1$ "slots" existing before $ a_1$, between $ a_1$ and $ a_2$, between $ a_2$ and $ a_3$, ..., and after $ a_n$. The number $ a_1+n$ must be inserted in one of the $ n-1$ slots not bordering $ a_1$. Its insertion then makes a total of $ n+2$ slots. Similarly, $ a_2+n$ must be inserted in one of the $ n$ slots not bordering $ a_2$, and so on, so the number of ways to insert the numbers $ n+1$ to $ 2n$ is $ (n-1)(n)(n+1)\cdots (2n-2)$, so the total number of permutations without property $ T$ is $ n(n-1)(2n-2)!<n(2n-1)(2n-2)!$.

ZzZzZzZzZzZz wrote: There are currently $ n + 1$ "slots" existing before $ a_1$, between $ a_1$ and $ a_2$, between $ a_2$ and $ a_3$, ..., and after $ a_n$. The number $ a_1 + n$ must be inserted in one of the $ n - 1$ slots not bordering $ a_1$. Its insertion then makes a total of $ n + 2$ slots. Similarly, $ a_2 + n$ must be inserted in one of the $ n$ slots not bordering $ a_2$, and so on, so the number of ways to insert the numbers $ n + 1$ to $ 2n$ is $ (n - 1)(n)(n + 1)\cdots (2n - 2)$ Sorry for the silly revive, but I just feel like posting right now. Unfortunately, this is incorrect, because if we consider $ n=2$ and the permutation $ (a_1,a_2)=(1,2)$, then your algorithm cannot yield $ (1,4,3,2)$ since in doing so it would require the first insertion to make it $ (1,3,2)$.

For $n=1$ this is obvious. For $n \ge 2$ let a "nice pair" in a permutation be a pair of consecutive integers with difference $n$. We construct an bijection from the set of permutations that don't have the property to the set of permutations that have exactly one nice pair that is not at the end. Since there are permutations with the property with more than one nice pair ($112233...nn$, here is where we need $n \ge 2$), we will be done. We will call the permutations without the property ugly permutations, and permutations with exactly one nice pair that is not at the end, nice permutations. The bijection is: for each ugly permutation, take the last number $k$, and move it so that it is exactly after the number $k \pm n$. For example, for $n=4$, $17542386$ goes to $17542638$, where we moved the $6$. This produces a nice permutation, since we created exactly one nice pair (in the example this is $26$). Notice how removing the final number cannot create nice pairs since there are no numbers after the final number. Also, the nice pair in the resulting permutation is obviously not at the end, since if it were, there would be a nice pair at the end of the original ugly permutation. This is a bijection, since, for each nice permutation, we can do the opposite: take the latter number of the nice pair and move it to the end, creating an ugly permutation. This is because the removal of that number $k$ cannot create more nice pairs because it was already paired up, and putting it at the end also does not create nice pairs, since $k \pm n$ isn't the next to last number (since the nice pair in the nice permutation isn't at the end). So we're done. P.S. 100th post

@JuanOrtiz Can you explain to me how your bijection solves the problem? Wait, correct me if I am wrong, but because we have this bijection which proves that the number of ways to permute the set such that there is property T and the number of ways to permute without any T is equal. So adding back in the number of ways to permute with property T at the end shows that the number of ways in total with property T is greater then the number of ways without T.

We first observe that the expected number of pairs $\{i, i+1\}$ for which $ | x_i - x_{i+1} | = n$ is $E = 1$. To see this note if $j$, $ 1 \leq j \leq n$, appears in position $1$ or $2n$ it's adjacent to one number, otherwise two. Thus the probability it's adjacent to its partner $j+n$ in a random permutation is \begin{align*} e_j &= \frac{2}{2n}\cdot \frac{1}{2n-1} + \frac{2n-2}{2n}\cdot \frac{2}{2n-1} \\ &= \frac{2(2n-1)}{2n(2n-1)} \\ &= \frac{1}{n}. \end{align*}By linearity of expectation we overall have the expected number of $j$ adjacent to its partner $j+n$ is $\sum_{j=1}^{n} e_j = n\cdot\frac{1}{n} = 1$. More is true. By the same argument, if we remove any partner pair $\{j,j+n\}$, the expected number of partner pairs in a random permutation of the remaining integers is still 1. This is the critical observation. Conditional on the partner pair $\{j,j+n\}$ appearing in a random permutation, what is the expected number of partner pairs $e$? Observe that if $n>1$ it must be less than 2, since as before the expected number of partner pairs ignoring $\{j,j+n\}$ is 1, and the probability the $\{j,j+n\}$ pair where they appear has separated another partner pair is greater than 0. Putting this together, if $n=1$ the property $P$ obviously holds. For $n>1$, note the expected number of partner pairs $E = p\cdot e$, where $p$ is the probability that a random permutation has property $P$ and $e$ is as before. But we already know $E=1$, and by the previous argument if $n>1$ we have $e<2$, hence $ 1 = p\cdot e < 2p $ and we conclude $ p > \frac{1}{2}$.

Here's a different solution (Hopefully correct): For $n=1$, the statement is trivially true. So from now on assume that $n \geq 2$. Call a permutation $\mathbb{P}$ of $\{1,2, \dots ,2n\}$ $k$-good if exactly $k$ values of $i$ satisfy the relation $|x_i-x_{i+1}|=n$, and bad if it doesn't have property $T$. Let $f(T_k)$ be the number of $k$-good sequences. Note that, as $n \geq 2$ by our assumption, so $f(T_2)>0$. Consider a $1$-good sequence with $i \in \{1,2, \dots ,2n-1\}$ satisfying $|x_i-x_{i+1}|=n$. Interchange $x_{i+1}$ with $x_{i+2}$ to get a new sequence which is bad (Here we take $x_{2n+1}=x_1$). For example, for $n=3$, the $1$-good sequence $\{1,6,2,5,4,3\}$ becomes $\{1,6,2,4,5,3\}$, which is evidently bad. It is easy to see that for two different $1$-good sequences, it is possible to get the same bad sequence after this process, but the converse is not true, i.e. we cannot get the same $1$-good sequence from two distinct bad sequences on applying this same process in the reverse order. This means that $f(T_1)$ cannot be less than the number of bad sequences. But the total number of permutations which show property $T$ is $f(T_1)+f(T_2)+ \dots +f(T_n)$, which is definitely greater than $f(T_1)$. Thus, the total number of permutations with property $T$ is more than the number of permutations without property $T$. Hence, done. $\blacksquare$

Here's a solution which involves constructing a bipartite graph. For $n \le 2$, it's easy to check the problem by simple computations. Let's assume now that $n \ge 3.$ First of all, we only care about the pairs of positions that $\{1, n+1\}, \{2, n+2\},$ etc. occupy. For instance, for the permutation $126435$, our pairs are $\{1, 4\}, \{2, 6\}, \{3, 5\}$. There are $n !!$ different ways to select pair up the positions. Call a pair tasty if it is of the form $\{k, k+1\}$ for some $1 \le k < 2n.$ We just need to show that at least half of that $n!!$ pairing methods have at least one tasty pair in them. Let $S_x$ be the set of pairing methods with exactly $x$ tasty pairs, for each $x \in \mathbb{Z}_{\ge 0}.$ Let's construct a bipartite graph with $S_0$ on the left side and $S_1, S_2$ on the right side as follows. Consider some pairing $\{a_1, a_2\}, \{a_3, a_4\}, \cdots, \{a_{2n-1}, a_{2n}\} \in S_0$. We will connect it to $2n-1$ things in $S_1 \cup S_2$. For each $1 \le k \le 2n-1$, we know that $k, k+1$ are not in the same pair. Suppose that $\{a_{2j-1}, a_{2j}\} = \{k, x\}$ and $\{a_{2i-1}, a_{2i}\} = \{k+1, y\}.$ Then, connect our pairing with the one where we use $\{k, k+1\}$ and $\{x, y\}$ instead of $\{k, x\}, \{k+1, y\}.$ It's easy to see that this new pairing must be in $S_1 \cup S_2,$ and that each pairing in the left side has degree exactly $2n-1$ (note that if $y = x+1$ or something, then we allow a double edge). Now, observe that each pairing $p \in S_1$ has degree at most $2(n-1)$, since if $\{a, a+1\}$ is the one tasty pair of $p$ then the only pairs which could map to $p$ are those where we replace $\{a, a+1\}, \{b, c\}$ with $\{a, b\}$ and $\{a+1, c\}$ or with $\{a, c\}$ and $\{a+1, b\}$, where $\{b, c\}$ is some other pair of $p$. This gives us at most $2(n-1)$ pairs since there's $n-1$ other pairs of $p$. Finally, each pairing $p \in S_2$ has degree at most $4$. Suppose that $\{x, x+1\}, \{y, y+1\}$ are the two tasty pairs in $p$. Then, the only pairings which can map to $p$ are those which replace $\{x, x+1\}, \{y, y+1\}$ with $\{x, y\}$ and $\{x+1, y+1\}$ or with $\{x, y+1\}$ and $\{y, x+1\}$. This would imply that $p$ has degree at most $2$, however remember that in these cases a double edge would have been constructed. Therefore, we actually have that $p$ has degree at most $4$. With the previous results, we have constructed a bipartite graph with $S_0$ on the left side, and $S_1 \cup S_2$ on the right side. This graph satisfies the property that every vertex on the left side has degree strictly larger than any vertex on the right side (since $2n-1 > 2n-2, 4$). Therefore, we have that $|S_0| < |S_1| + |S_2|.$ This implies that $|S_0| < |S_1| + |S_2| + \cdots + |S_n|$, which implies the result. $\square$

The problem can be generalized for all $0\le r\le n$ Let $A$ be the set of permutations that do not satisfy $P(r)$, and let $B$ be the set of permutation that do satisfy $P(r)$. Define a function $f:A\longrightarrow B$ as $$f(x_1x_2\ldots x_{2n})=x_2x_3\ldots x_1x_s\ldots x_{2n}$$where $s=\min{\{x_s\,|\, |x_s-x_1|=r\}}$ which is possible because $r\le n$. We claim that $f$ is injective. Suppose that $f(a)=f(b)$ meaning $$a_2a_3\ldots a_1a_s\ldots x_{2n}=b_2b_3\ldots b_1b_r\ldots x_{2n}$$Upon noticing that $(a_1,a_s),(b_1,b_r)$ are the only pairs that satisfy $|x_s-x_1|=r$ we have $s=r$ and thus $a_i=b_i$ for all $i$, implying that $a=b$ and that $f$ is injective. However there are now permutations that have more than one pair of numbers that satisfy $P(r)$ which are obviously not attainable by $f$. Hence, $f$ is injective but not surjective, implying $|A|<|B|$.

Cute problem.

I won't bother proofreading this, so as a heads-up, expect a lot of typos.

Nice problem

Use the transformation$$(x_1, x_2, \cdots, x_{2n}) = (x_2, \cdots, x_{ki1}, x_1, x_i, \cdots, x_{2n}),$$where $x_i$ is the element such that $|x_i - x_1| = n$, which is injective but not surjective.

Suspicious... Consider the $n$ pairs: $$(1, n+1)$$$$(2, n+2)$$$$\ddots$$$$(n, 2n)$$Notice that the set of permutations with this property $P$ are exactly the sets with one of these pair's elements adjacent. We count the number of permutations satisfying this using the Principle of Inclusion Exclusion to get: $$\sum_{k=1}^{n} \binom{n}{k} \cdot (2n-k)! \cdot (-1)^k \cdot (2)^k$$so we wish to prove that $$\sum_{k=1}^{n} \binom{n}{k} \cdot (2n-k)! \cdot (-1)^k \cdot (2)^k > \frac{(2n)!}{2}$$or in other words $$\sum_{k=0}^{n} \binom{n}{k} \cdot (2n-k)! \cdot (-1)^k \cdot (2)^k < \frac{(2n)!}{2}$$Now by the Bonferroni bounds, we notice that $$\sum_{k=0}^{n} \binom{n}{k} \cdot (2n-k)! \cdot (-1)^k \cdot (2)^k < \frac{(2n)!}{2}$$$$ \Rightarrow \sum_{k=0}^{2} \binom{n}{k} \cdot (2n-k)! \cdot (-1)^k \cdot (2)^k < \frac{(2n)!}{2}$$$$ \Rightarrow n \cdot (2n-1)! \cdot (-2) + 4 \cdot \binom{n}{2} \cdot (2n-2)! < \frac{(2n)!}{2}$$$$n > \frac14$$which is obviously true so we are done.