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?

  • $\begingroup$ It seems like you can still apply inclusion-exclusion in a reasonable way, so long as you know where the arrangements agree and disagree. $\endgroup$ – TokenToucan Mar 4 '16 at 8:31
  • $\begingroup$ @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. $\endgroup$ – Fimpellizieri Mar 4 '16 at 22:47
  • $\begingroup$ 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) $\endgroup$ – TokenToucan Mar 4 '16 at 22:52
  • $\begingroup$ @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. $\endgroup$ – Fimpellizieri Mar 4 '16 at 22:59
  • $\begingroup$ As in $n$ different permutations. $\endgroup$ – TokenToucan Mar 4 '16 at 23:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.