# Number of permutations in $[2n]$ such that every cycle has exactly one even number

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 2n \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 2n-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.

• I hope this post is understandable (I had trouble writing this in my native language let alone english ) Mar 19, 2022 at 15:45
• 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). Mar 19, 2022 at 16:21
• 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. Mar 19, 2022 at 16:27
• @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. Mar 19, 2022 at 16:55

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)$$.
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.
• 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. Mar 19, 2022 at 17:26