Consider an alphabet with $2n$ symbols and the substitution cipher that maps $p_i$ to $c_i$ for all $i$. If the numerical representation of $p_i = i$ for every $i$, how many substitution ciphers exist such that $$c_i + c_{i+1} \neq 2n-1$$ for all $i \in \{0,1,2, \dots, 2n-2 \}$
My first attempt to solve this (using the principle of inclusion-exclusion) was to define $S$ as the set of ciphers where there exists an $i$ such that $c_i + c_{i+1} = 2n-1$. But I can't seem to make any progress using this set. Does anyone have any tips about what else to try? I'd appreciate hints without necessarily giving away the full answer. I feel like once I can figure out what sets to use for inclusion-exclusion I'll be fine, but my trouble always arises in picking good sets.
The correct sets to use are those of ciphers where $k$ chosen pairs $c_i,c_{i+1}$ satisfy the given relation; such pairs must be disjoint, since for any $a$ here is only one symbol $b$ for which $a+b=2n-1$, so $0\le k\le n$.
For a fixed choice of $k$ pairs – $\binom nk$ ways to make that choice – there are $(2n-k)!$ ways to permute the singles (unpaired $c_i$) and pairs and $2^k$ ways to order the pairs, so inclusion/exclusion gives the number of admissible ciphertexts as $$\sum_{k=0}^n(-1)^k\binom nk(2n-k)!2^k$$ which is OEIS A007060.