0
$\begingroup$

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.

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

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$

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – parafoo Aug 2 at 19:56
  • $\begingroup$ @parafoo, ah, yes. Good catch. $\endgroup$ – JMoravitz Aug 2 at 20:11
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.