Up-to-date way to access Derangements (and other Combinatorica)

Question

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.

Answer 1

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}}