7 bailarines en un círculo

Question

7 bailarines van a participar en un concurso. Inicialmente se colocan en sus posiciones de base a la letra inicial de su apellido. En la segunda parte del concurso, que se dan posiciones aleatorias alrededor del círculo, que está determinado por un sorteo. ¿Cuál es la probabilidad de que ninguno de los bailarines están en su posición inicial o de sus vecinos?

Parece muy simple para mí, pero obviamente no lo es. Para cada bailarín, la probabilidad es $\frac47$ así que para todos 7 es $\frac{4^7}{7^7}$ – muy simplista, no?

Answer 1

El problema está pidiendo el número de permutaciones de $\{0,\dots,6\}$ tal que la diferencia entre cada elemento y su imagen es de más de 1 (módulo 7), como una proporción del número total de permutaciones. Las permutaciones no debe tener puntos fijos, lo que significa que sólo puede tener cuatro tipos de ciclo de estructuras – $\{7\}, \{5,2\},\{4,3\},\{2,2,3\}$ – y estas dan lugar a los once patrones para permuting los bailarines alrededor de:

Excepto para los dos estrellado de 7 ciclos, cada patrón puede ser en alguna de las 7 orientaciones. También pueden tener $2^n$ ciclo de direcciones, donde $n$ es el número de ciclos que no son transposiciones, escrito en la esquina superior izquierda de cada permutación en la imagen. Así tenemos a $7(8\cdot2+4)+2+2=144$ admisible permutaciones, y esto está fuera de $7!=5040$, por lo que la probabilidad deseada es $\frac{144}{5040}=\frac1{35}$.

---

Permutaciones de este tipo, donde los elementos se mueven más de un lugar alrededor de un círculo, se denominan discordantes y enumerada (con enlaces a un general de sistema de enumeración) bajo OEIS A000183.

Answer 2

Llego $144.$ me hizo esto mediante el cálculo de la permanente de una matriz apropiada. (Véase mi respuesta a esta pregunta(la Combinatoria problema Específico) para una explicación de este método.

La matriz en cuestión es una $7\times7$ matriz con un $1$ en la posición $(i,j)$ es bailarina $i$ se les permite ocupar la posición de $j$ y ceros en otros lugares.

Añado el guión, aunque yo no recomendaría el uso de una secuencia de comandos de python para el cálculo de la permanente de una gran matriz.

#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))