# Derangements relative to multiple arrangements

Literature is rife with results on classical derangements, that is, permutations on a set of elements that leave no element fixed. Generalizations also abound. In 'Matchings, Derangements, Rencontres', we have a pretty good description of the numbers $D(n,k,r)$ of $k$-permutations on $n$ elements that leave all but $r$ elements fixed. $q$- and even $p,q$- analogues of derangement numbers have been studied.

I am interested in another generalization of derangements. A classical derangement leaves no element of one given arrangement fixed. Given $k$ arrangements $\sigma_i$ $(1 \leq i \leq k)$, of the same $n$ elements, a $k$-derangement is a permutation $\rho$ (of the $n$ elements) that at no point coincides with any $\sigma_i$. In particular, a $1$-derangement is a classical derangement.

The only source I could find discussing this topic is this one. While certainly enlightening, I would like to know how to actually, theoretically, calculate the number $D(\sigma_1, \dots, \sigma_k)$ of $k$-derangements. Any ideas, or references?

• It seems like you can still apply inclusion-exclusion in a reasonable way, so long as you know where the arrangements agree and disagree. – TokenToucan Mar 4 '16 at 8:31
• @TokenToucan Even with relatively simple $\sigma$'s, I've had difficulty finding a sensible pattern. I've been working with $\sigma_1 = 1$ $2$ $\dots$ $n$ and $\sigma_i$ obtained from $\sigma_1$ by $(i-1)$ right shifts. – Fimpellizieri Mar 4 '16 at 22:47
• I was thinking about counting over the set of forbidden positions based on the permutations - in the $n=2$ case it did not seem too difficult, but maybe I am missing something. It seems like it would extend to larger $n$ in a fairly direct way (but not in a general form) – TokenToucan Mar 4 '16 at 22:52
• @TokenToucan $n=2$ is way too simple. The only possible arrangements being $1$ $2$ and $2$ $1$ makes it rather trivial. Trying out a value of, say, $n=10$ should make things more complicated. – Fimpellizieri Mar 4 '16 at 22:59
• As in $n$ different permutations. – TokenToucan Mar 4 '16 at 23:50