Category Archives: permutations

Yet Another Nice Proof of the Derangements Formula

A couple of posts from a few years back give proofs of the formula for , the number of derangements on n elements.  (A derangement is a permutation with no fixed points.)  Both proofs avoid the use of the principle of inclusion-exclusion, which … Continue reading

Posted in combinatorics, derangements, permutations | Leave a comment

The Maximum Value of Spearman’s Footrule Distance

Given a permutation on n elements, Spearman’s Footrule Distance is the sum of the absolute differences between i and over all values of i: Spearman’s Footrule Distance can be thought of as a measure of the disarray of a permutation.  Another such … Continue reading

Posted in combinatorics, permutations | 1 Comment

Another Nice Proof of the Derangements Formula

Strangely enough, a couple of days after I made my last post on a way to prove the derangements formula that I had never seen before, I came across another new (to me) way to prove the derangements formula in … Continue reading

Posted in combinatorics, derangements, permutations, recurrence relations | Leave a comment

A Nice Proof of the Derangements Formula

A derangement is a permutation in which none of the elements is mapped to itself.  The formula for the number of derangements on elements is This formula is normally proved using inclusion-exclusion (and, in fact, it is one of the … Continue reading

Posted in combinatorics, derangements, permutations, recurrence relations | 6 Comments

Permutations with Fixed Points and Successions

Suppose we have a permutation on the set .  A fixed point of is a value such that .  If , then we say has a succession at .  Take, for example, the permutation 213596784.  It has four fixed points: … Continue reading

Posted in combinatorics, permutations | 3 Comments