I am seeing that the answer to the following problem should be just $(n-1)! \over ({(n \over 2})!$ and am wondering what conceptual errors I am making:
How many permutations of 1 through $n$ are there such that for each $i, \sigma(\sigma(i))=i$ and $\sigma(i) \neq i$ ? (For example, the permutation 3,4,1,2 is such a permutation, since for example $\sigma(\sigma(1))=\sigma(3)=1$. You may assume $n$ is even.) Answer: $\frac{n !}{2^{n / 2}(n / 2) !}$. This is the number of ways to swap, so we can pick them out in pairs
I seeing that it is $(n-1)! \over ({n \over 2})!$ because there are $n-1$ ways to pick the first item in our permutation (we exclude this being $1$), which then determines what another item in our permutation should be- but we could pick an item for an element not determined by this choice, for which we have $n-2$ choices: this again pre-determines another item of the permutation, but there still exists another item not predetermined, which we then pick having $n-3$ choices, etc. Eventually, when we have picked for half of the elements in our permutation of length $n$, so picked $n \over 2$ times, we would get an entire permutation. The possibilities explored here was $(n-1)! \over ({n \over 2})!$. Why is this wrong?
