Given an even number $n$ of pairs such that we always create $2n$ elements, we can group them total times of $P=\frac{(2n)!}{2^n n!}=(2n-1)!!$. I would like to add a restriction to this: odd numbers can only be paired with even numbers.
Example: n=1 gives {1,2} so 1 pairing. n=2 gives {1,2,3,4} which I group into {(1,2),{3,4}} and {(1,4),{2,3}} so 2 pairings, for n=3 {1,2,3,4,5,6} gives {(1,2),(3,4),(5,6)},{(1,4),(3,2),(5,6)},{(1,6),(3,2),(5,4)}, etc. and gives me 6 pairings
Somehow, by deduction, it seems that it should be $P=n!$ However, I do not have proper proof of it.
Any help would be appreciated.
Edit: The parity and the order of pairs do not matter. For example, when n=2 {(1,2),(3,4)}, this is the same as {(2,1),(4,3)} and the same as {(4,3),(2,1)}.
Best Answer
Arrange the odd numbers and even numbers in two different rows, eg for $3$ pairs,
$1\;3\;5$
$2\;4\;6$
Pairing them from left to right, the $1$ has three choices, two choices are left for the $3$, and $5$ has only one possible choice now, thus $3\cdot2\cdot1 = 3!$,
and generalizing for $n$ pairs, $n!$