1
$\begingroup$

Since there are n even numbers in $[2n]$ we know we will have $n$ cycles.

If length of all cycles is 2 we have $n!$ ways to make a permutation which satisfies given condition.

We can also have some cycles of length 3(they contain one even and two odd numbers) and for each of those we have a fixed point and it must be even.

Its easy to notice that the highest number of pairs of cycles of lengths 1 and 3 is whole part of the number $\frac{n}{2}$ (I don't know how to write whole part and this sentence is generally terrible but bear with me)

So now I want to see what happens when we have $k$ pairs of cycles of length 1 and 3.

We choose two even and two odd numbers in $n \choose 2$$n \choose 2$ ways.Now we can make 4 permutations out of those numbers(we choose cycle of length 1 in two ways because it must be even and then we choose a cycle of length 3 out of numbers that are left)

We repeat this $k$ times (for last pair of cycles we choose two even and two odd numbers in $n-2(k-1) \choose 2$$n-2(k-1) \choose 2$ ways and make a permutation in 4 ways)

Now we have $2(n-2k)$ elements left ($(n-2k)$ even and $(n-2k)$ add).

Now we pair them even with odd in $((n-2k)!)^2$ ways.

Ok, so now I want to divide all of this with something(since order is not important) but I cant figure out with what. Notice I didn't divide with anything when I was counting pairs of cycles of length 1 and 3 and when I was counting transpositions.I thought maybe I could divide it all by $n!$ at the end(now that is) and then multiply it by 2 since I was considering order when I was counting number of permutations for those pairs of cycles, but that just doesn't seem right.

I would appreciate some help with finishing this.Also alternative solution would also be greatly appreciated since I have a feeling I'm doing this the worst possible way.

$\endgroup$
4
  • $\begingroup$ I hope this post is understandable (I had trouble writing this in my native language let alone english ) $\endgroup$ Mar 19, 2022 at 15:45
  • $\begingroup$ What about cycles that contain more than $2$ odd numbers? For instance $(1,2,3,5)$ or $(4,7,9,11,13)$ (assuming $n$ is sufficiently large). $\endgroup$
    – paw88789
    Mar 19, 2022 at 16:21
  • $\begingroup$ I ruled that out in the beginning and I'm sure I thought I had a good reasoning behind why it can't happen but now that you mention it that is another possibility. For example in S6 we can have (1345)(2)(6). I guess my approach isn't good then. $\endgroup$ Mar 19, 2022 at 16:27
  • $\begingroup$ @paw88798 I'm now thinking I should make n cycles of length 1 with even numbers in them and then consider all permutations of subset of [2n] consisting of odd numbers and for each such permutation, depending on number of its cycles, I should merge some number of cycles of length 1 with those cycles.Finally for every such pick I'll have k options to position that even number(where k is length of a cycle in permutation consisting of odd numbers) But this seems impossible to compute this way. $\endgroup$ Mar 19, 2022 at 16:55

1 Answer 1

3
$\begingroup$

Consider any listing of the numbers $1, 2,...,2n$ that obey the following two conditions: (1) The even numbers appear in order (not necessarily consecutively), and the last number in the list is $2n$. For example if $n=4$, the following would be a permissible list: $5,1,2,4,3,7,6,8$.

Each such listing corresponds to a permissible permutation of $1, 2,...,2n$, where a cycle ends with an even number. For instance in the example above, the permutation would be $(5,1,2)(4)(3,7,6)(8)$.

And this correspondence is reversible. Given a permissible permutation, we can get such a listing, by just putting the even number in each cycle at the end of the cycle, and then removing the cycle parentheses to get the listing.

Now start with the even numbers in their proper order $2,4,6,...,2n$. Next place $1$. There are $n$ choices for this--$1$ can go before any of the even numbers. Next place $3$. There are $n+1$ choices here ($3$ could go before any number currently in the list, which now includes $1$ and all the evens). Next place $5$ ($n+2$ ways to do this). Etc.

Altogether there are $n\cdot (n+1)\cdot (n+2)\cdot \ldots \cdot (2n-1)$ ways to construct these sequences; and consequently that is the number of admissible permutations as well.

$\endgroup$
2
  • $\begingroup$ That's a great observation.,thanks a lot $\endgroup$ Mar 19, 2022 at 17:12
  • $\begingroup$ Or: there are $2n-1\choose n-1$ ways to place positions for the even numbers and then $n!$ ways to place the odd numbers in the gaps. $\endgroup$ Mar 19, 2022 at 17:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .