But yes, their calculations to support that claim do seem to be erroneous.

They don't argue that no square ends in $4\ldots 41$ but that no square (other than 441) is of the form $4\ldots 41$.

It's certainly not going to be amortised $O(1)$ per subset.

The question doesn't ask for bijections $\varphi\colon \mathrm{Par}\to \mathrm{Par}$: it asks for bijections from partitions of $n$ to partitions of $n$. That rules out, for example, the general $a\times b$ complement, although restrictions of the complement to partitions of $\frac{a+b}2$ would be acceptable.

@BrendanMcKay, if this kind of approach does meet OP's goals then I think having the variables be quadratic in the number of vertices might actually be better than linear, because there are $2^{O(n^2)}$ possible edge sets.

I haven't worked through the details, but I think that TSP on $n$ vertices can be reduced to 3SAT with $O(n^2)$ variables and $O(n^2)$ clauses. What I'm not sure is whether that addresses your question. Would "the set of problems produced by X reduction from a different NP-complete problem" be an acceptable answer in principle, if the details work out?

Am I understanding correctly that within each $E_i$ one element may divide another? If so, there may be interesting ideas where each $E_i$ is something like $\{m_i x : x \in X\}$ where $X$ is something like squarefree $k$-smooth numbers.

Simple case of misunderstanding the notation: $B_n^{(\frac m2)} \neq \sqrt{B_n}^m$.

Nor is it in the version of the Inverse Symbolic Calculator available at wayback.cecm.sfu.ca/projects/ISC/ISCmain.html

@Voile, now that you mention it I have been a bit cavalier in the switch from $\mathbb{Z}/(p^2-p-1)$ treating $p$ as a variable to specific values of $p$. We might require $F(n+1)p + F(n) < p^2 - p - 1$, so which gives a bound of approximately $\frac12 F(n+2) + F(\frac n2)$.

@virtuolie, yes. Multiply by $\binom{n}{k} \cdot !(n-k)$ to get the total number of inversions in all permutations with $k$ fixed points.

@virtuolie, part (b) done: I think the simplified form should be sufficiently useful for you subject to part (a).

@virtuolie, the full list of values for n=30 is (to 3dp) [222.583, 217.583, 212.417, 207.083, 201.583, 195.917, 190.083, 184.083, 177.917, 171.583, 165.083, 158.417, 151.583, 144.583, 137.417, 130.083, 122.583, 114.917, 107.083, 99.083, 90.917, 82.583, 74.083, 65.416, 56.585, 47.576, 38.444, 29.000, 19.667, NaN, 0.000]. Empirically it seems that there's more to be said about the trend: if you fit a quadratic to E(inv) as a function of k for fixed n, it seems to be an extremely good fit, so it may be worth trying to (a) prove the conjectured formula; (b) prove a quadratic asymptotic form.

In that case I still need clarification as to what the conjecture is. Take $n=4, j=4$. Then $k=1$ is possible (take $2431$). Looking at permutations with $j-1$ inversions we get $S_\beta = \{1432, 2341, 2413, 3142, 3214, 4123\}$ and $S_\delta = \{ 2341, 2413, 3142, 4123 \}$. Either I've misunderstood the conjecture or this is a counterexample.

I think there must be some typo in the problem statement: you define $S_\alpha$ but don't use it. My guesses for the corrected conjecture don't hold for even $n=4$, so I'm clearly not guessing correctly.