4 votos

disposición de $n$ naranjas y $n$ manzanas alrededor de un círculo

Cuál es el número total de disposiciones distintas de $n$ naranjas y $n$ ¿manzanas alrededor de una mesa redonda? No tengo ni idea de cómo hacerlo.

7voto

JMoravitz Puntos 14532

Acercamiento a través de Lemma de Burnside ( o más exactamente, "el lema que no es de Burnside" ).

$$|X/G| = \frac{1}{|G|}\sum_{g\in G}|X^g|$$

Aquí, $G$ se referirá al grupo de rotaciones de una mesa circular con $2n$ espacios. $|X^g|$ cuenta el número de arreglos que se fijan bajo una determinada rotación $g$ . En problemas similares en los que todas las personas/objetos son distintos, ocurre que el sólo El término que sobrevive en la suma es la rotación de identidad, sin embargo ese no es el caso aquí.

Dejemos que $\rho_i$ denota la rotación por $i$ espacios en el sentido de las agujas del reloj.

$|X^{\rho_0}| = \frac{(2n)!}{n!n!}$ por el ejemplo anterior.

$|X^{\rho_1}| = 0$ como hay al menos una manzana adyacente a una naranja, después de la rotación hay al menos un espacio que contiene una naranja que ya no contendrá una naranja.

$|X^{\rho_2}| = 2$ ya que dado un lugar específico, si contiene una manzana, entonces el espacio a dos de distancia debe contener también una manzana para que la rotación no la afecte. Del mismo modo, el espacio que está a dos de él también debe tener una manzana. Siguiendo, vemos que todos los demás espacios deben tener una manzana. Como también debemos colocar $n$ naranjas, debe ser que todos los espacios restantes tienen naranjas. Consideremos la posición más al norte como especial. Tenemos entonces dos opciones, o la posición norte tiene una manzana, o la posición norte tiene una naranja.

$|X^{\rho_3}|=0$ ya que dada una ubicación específica, uno de cada tres espacios debe tener el mismo tipo de fruta. Se puede ver que no se utilizará la misma cantidad de manzanas y naranjas en ninguna configuración que permanezca invariante bajo esta rotación.

$\vdots$

$|X^{\rho_{2k}}| = \frac{(2x)!}{x!x!}$ donde $2x=\gcd(2k,2n)$ ya que mirando a la posición norte, el espacio $2k$ de distancia tendrá que ser el mismo, y el espacio $2k$ lejos de eso debe ser el mismo etcétera. Esto se hará en una sola pasada, o en varias pasadas que cubran aún más espacios. Por ejemplo, si $2n=10$ y estamos tratando de rotar $4$ unidades a la vez, esto implica que los espacios $0,4,8,2,6$ debe ser el mismo mientras que si $2n=16$ y estamos tratando de rotar $4$ unidades a la vez, esto implica espacios $0,4,8,12$ todos deben ser iguales. Esto implica que la posición del norte y la $2x-1$ espacios adicionales en el sentido de las agujas del reloj a la posición norte determinarán completamente la disposición completa, la mitad de la cual debe ser manzanas y la otra mitad naranjas, tenemos $\frac{(2x)!}{x!x!}$ maneras de colocar manzanas y naranjas en esos espacios. Las elecciones de manzanas y naranjas en esas posiciones forzarán las posiciones de todas las manzanas y naranjas adicionales alrededor del círculo para asegurar que el arreglo no se cambie bajo la rotación $\rho_{2k}$

$|X^{\rho_s}|=0$ siempre que $s\neq 2k$ para algunos $k$ ya que, de lo contrario, no habrá la misma cantidad de manzanas y plátanos al final.

Tenemos entonces que el número total de arreglos es:

$$\frac{1}{2n}\left(\sum_{k=1}^{n}\frac{\gcd(2k,2n)!}{\gcd(k,n)!\gcd(k,n)!}\right)$$

( nota: $\rho_{2n} = \rho_0$ )

Por ejemplo, con $6$ manzanas y $6$ naranjas, tenemos $\frac{1}{12}\left(\frac{2!}{1!1!}+\frac{4!}{2!2!}+\frac{6!}{3!3!}+\frac{4!}{2!2!}+\frac{2!}{1!1!}+\frac{12!}{6!6!}\right)=\frac{1}{12}\left(2+6+20+6+2+924\right) = 80$

Con $5$ manzanas y $5$ naranjas, tenemos $\frac{1}{10}\left(\frac{2!}{1!1!}+\frac{2!}{1!1!}+\frac{2!}{1!1!}+\frac{2!}{1!1!}+\frac{10!}{5!5!}\right) = \frac{1}{10}\left(8+252\right)=26$

Con $4$ manzanas y $4$ naranjas, tenemos $\frac{1}{8}\left(\frac{2!}{1!1!}+\frac{4!}{2!2!}+\frac{2!}{1!1!}+\frac{8!}{4!4!}\right) = \frac{1}{8}\left(2+6+2+70\right) = 10$


Una vez resuelta la pregunta, calculando los primeros valores, pude encontrar la secuencia en OEIS como A003239 que ofrece formas adicionales de expresar el resultado final.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X