mjhjmtu

7 dancers are going to participate in a contest. They are initially placed in their positions basis the initial letter of their surname.
At the second part of the contest, they are given random positions around the circle, which are determined by a draw. What is the probability that none of the dancers are in their initial positions or their neighboring?

It seems very simple to me but obviously isn't. For each dancer, the probability is $frac47$ so for all 7 it is $frac4^77^7$ – very simplistic, no?

I get $144.$ I did this by computing the permanent of an appropriate matrix. (See my answer here(Combinatorial Analysis - Specific problem) for an explanation of this method.

The matrix in question is a $7times7$ matrix with a $1$ in position $(i,j)$ is dancer $i$ is allowed to occupy position $j$ and zeros elsewhere.

I append the script, though I would not recommend using a python script to compute the permanent of a large matrix.

#perm01.py
'''
Compute the permanent of a 0-1 matrix
'''

import numpy as np
from math import factorial

def minor(M, i, j):
 return np.delete(np.delete(M,i,axis=0), j, axis=1)

def perm(M):
 size = M.shape[0]
 colsums = sum(M)
 rowsums = sum(M.transpose())
 c = np.argmin(colsums)
 r = np.argmin(rowsums)
 answer = 0
 if colsums[c] <= rowsums[r]:
 if colsums[c] == size:
 return factorial(size)
 for k in range(size):
 if M[k, c] == 1:
 answer += perm(minor(M,k,c))
 else:
 for k in range(size):
 if M[r, k] == 1:
 answer += perm(minor(M,r,k)) 
 return answer

if __name__=='__main__':
 M = np.zeros((7,7), dtype=np.int)
 for k in range(7):
 M[k,k]=M[k,(k+1)%7]=M[k,(k-1)%7]=1
 M = np.ones((7,7), dtype=int)-M
 print(perm(M))

The problem is asking for the number of permutations of $0,dots,6$ such that the difference between each element and its image is more than 1 (modulo 7), as a proportion of the total number of permutations. The permutations must have no fixed points, which means they can only have four types of cycle structures – $7, 5,2,4,3,2,2,3$ – and these give rise to eleven patterns for permuting the dancers around:

Except for the two starry 7-cycles, each pattern can be in any of 7 orientations. They can also have $2^n$ cycle directions, where $n$ is the number of cycles that are not transpositions, written in the top-left corner of each permutation in the picture. Thus we have $7(8cdot2+4)+2+2=144$ admissible permutations, and this is out of $7!=5040$, so the desired probability is $frac1445040=frac135$.

Permutations of this sort, where elements move more than one place around a circle, are termed discordant and enumerated (with links to a general enumeration system) under OEIS A000183.