# Finding permutations using the general theorem on inclusion & exclusion

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.

• This looks like one of those where you count the permutations that violate the condition, and then subtract from $(2n)!$. – saulspatz Aug 2 at 18:55

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$$

• Are you saying that $\lvert A_i \rvert = (2n-1)!$? If so, shouldn't it be $2n \cdot (2n-2)!$? For instance if we look at the case when $n=2$ and $i=1$, there are $8$ elements in $A_i$ namely 1423, 1432, 4123, 4132, 2314, 2341, 3214, and 3241. – parafoo Aug 2 at 19:56
• @parafoo, ah, yes. Good catch. – JMoravitz Aug 2 at 20:11

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