Non-example: Separable derangements

As mentioned in "Simple permutations and algebraic generating functions," counting derangements falls outside of the "finite query-complete properties" framework.

Still, there are a few results. Aaron Robertson, Dan Saracino, and Doron Zeilberger showed in their paper "Refined restricted permutations" that both 321-avoiding and 132-avoiding permutations are counted by Fine's sequence, which has an algebraic generating function.

In light of this, it would be interesting to know how to enumerate the separable derangements. The first few terms of this enumeration are:

0, 1, 2, 7, 30, 124, 560, 2610.

< back to homepage