3
$\begingroup$

If one types e.g. "Derangements[4]" in MMA, all it does is echo the command itself. If one goes to the help page for "Derangements" and expand the "details" section, all it says is: "To use Derangements, you first need to load the Combinatorica Package using Needs["Combinatorica`"]." So, I add that to my notebook. Now, the first thing MMA does is respond: " Combinatorica Graph and Permutations functionality has been superseded by preloaded functionality. The package now being loaded may conflict with this. Please see the Compatibility Guide for details." The Derangements function now works, but it also tells you that it is shadowed by another version. Moreover, lots of my other combinatorial functions stop working (presumably since the commands were different in Combinatorica than in the now-preloaded versions, making loading it crash my code). The Compatibility guide for Combinatorica is no help and seems out of date. In Wolfram Mathworld, it gives an explicit function for Derangements[] but the code doesn't work in MMA 12 which I am using. So, I am stuck.

Please, what is the up-to-date way to ask for Derangements[] and why is the documentation out-of-date? Thanks.

$\endgroup$
4
$\begingroup$

Please see Computational Discrete Mathematics by Pemmaraju and Skiena, pages 106 and 107.

DerangementQ[p_?PermutationListQ]:= !(Apply[Or,Map[(#===p[[#]])&,Range[Length[p]]]])

NumberOfDerangements[0] = 1;

NumberOfDerangements[n_Integer?Positive] := 
   Block[{$RecursionLimit = Infinity}, n*NumberOfDerangements[n - 1] + (-1)^n]

Derangements[0] = {{}};

Derangements[n_Integer] := Derangements[Range[n]]

Derangements[p_?PermutationListQ] := Select[Permutations[p], DerangementQ]

For example,

Table[NumberOfDerangements[i], {i, 1, 10}]

{0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961}

Derangements[4]

{{2, 1, 4, 3}, {2, 3, 4, 1}, {2, 4, 1, 3}, {3, 1, 4, 2}, {3, 4, 1, 2}, {3, 4, 2, 1}, {4, 1, 2, 3}, {4, 3, 1, 2}, {4, 3, 2, 1}}

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks - that works for me. $\endgroup$ – Paul Harrison Feb 6 at 21:14
  • 1
    $\begingroup$ For more on derangements, and fast methods to generate them without necessarily generating all permutations, please see this question. $\endgroup$ – KennyColnago Feb 6 at 22:25
  • $\begingroup$ But why is there not a simple Derangements[p] command preloaded in MMA? $\endgroup$ – Paul Harrison Feb 7 at 7:32

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.