Finding permutations using the general theorem on inclusion & exclusion

Question

Count the number of permutations $x_1, x_2, ..., x_{2n}$ of the integers $1$ to $2n$ such that $$x_i + x_{(i+1)} ≠ 2n + 1 \quad \text{for all $i = 1, 2, ..., 2n-1$.}$$

I know I need to use the PIE, but I'm not really sure where to start.

Answer 1

Let $A_i$ be the set of permutations such that $x_i+x_{i+1}=2n+1$

Note the convenient property that $A_i\cap A_{i+1}=\emptyset$ since for $x_i+x_{i+1}=2n+1=x_{i+1}+x_{i+2}$ this would imply that $x_i=x_{i+2}$ which is impossible as it is a permutation.

We know there to be $(2n)!$ permutations were we not to care about violating the conditions.

The number of permutations where we do violate a specific single condition can be counted as $2n(2n-2)!$

Similarly, the number of permutations where we violate a specific two conditions simultaneously is either $(2n)(2n-2)(2n-4)!$ or $0$, keeping in mind that it is impossible to violate adjacent conditions. This pattern continues where the number of permutations where the number of permutations where we violate a specific $k$ conditions as $(2n)(2n-2)\cdots (2n-2k+2)(2n-2k)! = \frac{(2n)!!}{2n-2k)!!}(2n-2k)!$.

All that remains now is to count how many pairings of conditions exist that don't contradict one another for each value of $k$.

Note that $A_{2n}$ doesn't exist since there is no $x_{2n+1}$ to be concerned about, so there are $2n-1$ total conditions. If we want have $k$ conditions that are nonadjacent, think of it as arranging a sequence of $k$ 2's and the appropriate number of 1's.

$(2n)!-(2n-1)(2n)(2n-2)!+\binom{2n-2}{2}(2n)(2n-2)(2n-4)!-\dots\pm\binom{2n-k}{k}\frac{(2n)!!}{(2n-2k)!!}(2n-2k)!\pm\dots$

Answer 2

There are $n$ pairs of numbers that add up to $2n+1$ namely $(1,2n), (2, 2n-1), \ldots, (n, n+1)$. In order for a permutation to be invalid, it needs to have at least one of these pairs in adjacent positions.

So how many permutations contain the pair $(k,2n+1-k)$ in adjacent positions? Well we can think of the pair as a single block and can consider the number of permutations of this block along with the remaining $2n-2$ numbers. This gives us $(2n-1)!$. However, we can also flip which element in the pair comes first giving us a total of $2\cdot (2n-1)!$.

Now there are a $\binom{n}{1}$ ways to choose one of the $n$ pairs. Thus there are $\binom{n}{1}$ pairs each contained in $2\cdot (2n-1)!$ permutations giving us $\binom{n}{1}\cdot 2 \cdot (2n-1)!$.

However this overcounts the number of invalid permutations with at least $2$ pairs in it. So for $2$ given pairs, how many invalid permutations contain both of these pairs? Well once again considering each pair as a block, this is just the permutation of $2n-2$ objects (the two pairs plus the remaining $2n-4$ numbers) which is $(2n-2)!$. However, for each of the pairs we have a choice of what number in the pair comes first. This gives us $2^2\cdot (2n-2)!$.

There are $\binom{n}{2}$ ways to choose $2$ pairs giving us $\binom{n}{2} \cdot 2^2\cdot (2n-2)!$ However this overcounts the number of invalid permutations with at least $3$ permutations in it. Continuing this process we see there are $$\binom{n}{1}\cdot 2 \cdot (2n-1)! - \binom{n}{2} \cdot 2^2\cdot (2n-2)! + \ldots = \sum_{k=1}^{n}(-1)^{k-1} 2^{k} \binom{n}{k} (2n-k)!$$ number of invalid permutations.

Therefore the number of valid permutations is $$2n!-\bigg(\sum_{k=1}^{n}(-1)^{k-1} 2^{k} \binom{n}{k} (2n-k)!\bigg)= \sum_{k=0}^{n} (-2)^k \binom{n}{k} (2n-k)!$$

Other formulas can be found here: https://oeis.org/A007060