Autor Tema: Más sobre permutaciones circulares

0 Usuarios y 1 Visitante están viendo este tema.

23 Mayo, 2022, 09:02 pm
Leído 209 veces

zruspa

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 2
  • País: es
  • Karma: +0/-0
Al ver algunos temas de este subforo me he animado a registrarme y exponer mi propio problema.
Se trata de sentar en una mesa a un número determinado "n" de hombres y mujeres, y calcular las posibles distribuciones atendiendo exclusivamente al sexo de los sedentes. Obviamente, si la mesa es corrida se trata de permutaciones con repetición, pero si la mesa es redonda me llama la atención que el resultado varía si "n" es par o impar. Veamos los ejemplos más simples:

n = 4   2H, 2M   Mesa corrida, P = 6.     Mesa circular, P = 2.   Esto es,  6/(n-1).
n = 5   3H, 2M   Mesa corrida, P = 10.   Mesa circular, P = 2.   Esto es,  10/n.
n = 6   3H, 3M   Mesa corrida, P = 20.   Mesa circular, P = 4.   Esto es,  20/(n-1).
n = 6   4H, 2M   Mesa corrida, P = 15.   Mesa circular, P = 3.   Esto es,  15/(n-1).
n = 7   4H, 3M   Mesa corrida, P = 35.   Mesa circular, P = 5.   Esto es,  35/n.
n = 7   5H, 2M   Mesa corrida, P = 21.   Mesa circular, P = 3.   Esto es,  21/n.
n = 8   5H, 3M   Mesa corrida, P = 56.   Mesa circular, P = 8.   Esto es,  56/(n-1).
n = 9   5H, 4M   Mesa corrida, P = 126.   Mesa circular, P = 14.   Esto es, 126/n.

Me gustaría entender este comportamiento para afrontar casos con "n" mucho más elevados, con la fórmula adecuada y sin el engorro de enumerar todas las posibilidades. Pero sobre todo entender la diferencia de comportamiento entre pares e impares que imagino estará relacionado con la simetría del problema.



23 Mayo, 2022, 11:02 pm
Respuesta #1

manooooh

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 3,881
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola

La secuencia \( 6,10,20,15,35,21,56,126 \) no aparece en una página web muy famosa sobre base de datos de secuencias: https://oeis.org/search?q=6%2C10%2C20%2C15%2C35%2C21%2C56%2C126&language=spanish&go=Buscar

¿Estás seguro que calculaste bien los resultados?

Saludos

24 Mayo, 2022, 12:09 am
Respuesta #2

Carlos Ivorra

  • Administrador
  • Mensajes: 10,115
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
La fórmula general es un poco complicada:

\( \displaystyle P_{i,j}= \sum_{d\mid (i, j)}\frac{\phi(d)}{i+j}\frac{((i+j)/d)!}{(i/d)!(j/d)!} \),

donde \( \phi(d) \) es la función de Euler y \( (i,j) \) es el máximo común divisor de \( i,j \).

Coincide con tus resultados salvo que \( P_{5, 3}=7 \). La demostración requiere la fórmula de inversión de Möbius o bien un teorema de Burnside de teoría de grupos.

Si \( (i,j)=1 \), es decir, si \( i, j \) son primos entre sí, la fórmula se reduce a

\( \displaystyle P_{i,j}=\frac{(i+j-1)!}{i!\,j!} \).

24 Mayo, 2022, 09:33 am
Respuesta #3

zruspa

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 2
  • País: es
  • Karma: +0/-0
Vaya, es más complicada la solución que el problema en sí; con razón no era capaz de dar con la tecla. Gracias de todas formas.
Y, efectivamente, he cometido un error, porque para  n = 8, 5H, 3M, en la mesa circular resulta  P = 7. Ahí se rompe la tendencia.

La fórmula general es un poco complicada:

\( \displaystyle P_{i,j}= \sum_{d\mid (i, j)}\frac{\phi(d)}{i+j}\frac{((i+j)/d)!}{(i/d)!(j/d)!} \),

donde \( \phi(d) \) es la función de Euler y \( (i,j) \) es el máximo común divisor de \( i,j \).

Coincide con tus resultados salvo que \( P_{5, 3}=7 \). La demostración requiere la fórmula de inversión de Möbius o bien un teorema de Burnside de teoría de grupos.

Si \( (i,j)=1 \), es decir, si \( i, j \) son primos entre sí, la fórmula se reduce a

\( \displaystyle P_{i,j}=\frac{(i+j-1)!}{i!\,j!} \).