2
$\begingroup$

This is a special case of the question:
Counting permutations whose elements are not exactly their index ± M

The $M=0$ case has already been solved, but no one was sure how to work out the non-zero cases.

So I decided to try to just brute force some values and search the results for a recursion relation. As a test I first tried $M=0$ and searched for recursion relations that looked like: $$ a_n = \sum_{1\le i \le k} (A_i n + B_i) a_{n-i} $$ where $k$ is some cutoff of how far back to search, $A_i \in \{-1,0,1\}$ and $B_i$ some small integers. It was correctly able to find: $$a_n= (n-1)a_{n-1} +(n-1)a_{n-2}$$

So I then tried for $M=1$ and found: $$ a_n= (n) a_{n-1} +(-n+2) a_{n-3} + (-1)a_{n-4} $$

It's possible it's just a coincidence, but I ran a brute force approach to calculating the $M=1$ cases overnight to get a couple more values and it still holds. But even with this potential answer in hand, I cannot figure out a reason this recursion would hold.

Is there a simple combinatoric argument I'm missing here?

$\endgroup$
  • 1
    $\begingroup$ Another commenter suggested searching oeis. Turns out it is listed in there: oeis.org/A078480 and the recursion relation is correct. But I am no closer to understanding how you get that relation. $\endgroup$ – PPenguin Apr 28 '17 at 20:54
  • 1
    $\begingroup$ Good find! The OEIS entry gives a reference; have you checked it out? $\endgroup$ – Raphael Apr 29 '17 at 8:27
  • $\begingroup$ The OEIS entry even gives you an explicit formula. $\endgroup$ – Yuval Filmus Apr 29 '17 at 14:29
-3
$\begingroup$

Checkout Derangements

"Suppose that there are n people who are numbered 1, 2, ..., n. Let there be n hats also numbered 1, 2, ..., n. We have to find the number of ways in which no one gets the hat having same number as their number."

In applying this to your problem, there would be two hats: the element's index +1, the elements​ index -1.

I'm not certain this solves the problem, but it seems like a step in the right direction.

$\endgroup$
  • 3
    $\begingroup$ This is more of a comment than an answer. The OP is already aware of derangements (the case M=0). $\endgroup$ – Yuval Filmus Apr 29 '17 at 7:30
  • $\begingroup$ And it's not at all clear how to go from the known case to the unknown case, so I'm not sure it's any step at all. $\endgroup$ – David Richerby Apr 29 '17 at 12:13

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.