La organización de bolas iguales

Question

• Suponga que tiene cuatro pares de pelotas, cada par es idéntico en color ( digamos $\color{#00f}{blue}$, $\color{#f00}{red}$, $\color{#06b121}{green}$ y $\color{#d4ac0d}{yellow}$ ).
• De cuántas maneras pueden colocarse de manera que no hay dos bolas iguales están uno al lado del otro ?.

Tengo una idea vaga de que el principio de inclusión/exclusión es necesaria, pero no estoy completamente segura. También, hay una técnica para resolver este uno sin el uso de principio de inclusión/exclusión ?.

Answer 1

Esta respuesta se basa en la generación de la función de generalizada polinomios de Laguerre \begin{align*} L_k^{(\alpha)}(t)=\sum_{i=0}^k(-1)^k\binom{k+\alpha}{k-i}\frac{t^i}{i!}\tag{1} \end{align*}

Los polinomios de Laguerre tienen notables propiedades combinatorias y uno de ellos es precisamente el adecuado para responder a los problemas de este tipo. Esto está muy bien presentado en el Conteo de palabras con Laguerre serie por Jair Taylor.

Nos codificar los colores (b)lue (r)ed, (g)creen y (y)ellow de las bolas con las letras \begin{align*} \{b,r,g,y\} \end{align*} y están en busca de palabras de longitud $8$ construido a partir de \begin{align*} b,b,r,r,g,g,y,y \end{align*} que tienen la propiedad de que no contienen consecutivos iguales letras. Estas palabras se llaman Carlitz palabras o Smirnov palabras.

Nos encontramos en la sección 2 de la referida papel polinomios de Laguerre $l_k(t)$ definido por su función de la generación de \begin{align*} \sum_{k=0}^\infty l_k(t)x^k=\exp\left({\frac{tx}{1+x}}\right) \end{align*} El primer par de dichos polinomios son \begin{align*} l_0(t)&=1\\ l_1(t)&=t\\ l_2(t)&=\frac{1}{2}t^2-t\\ l_3(t)&=\frac{1}{6}t^3-t^2+t\tag{2} \end{align*} Ellos son una forma específica de polinomios de Laguerre (1), es decir, $$l_k(t)=(-1)^kL_k^{(-1)}(t)$$

Teorema 2.1 en el referido documento señala: Dados los números enteros no negativos $n_1,\ldots,n_k$, el número de $k$-ary Carlitz palabras con la letra $i$ utiliza exactamente $n_i$ veces es \begin{align*} \int_{0}^\infty e^{-t}\left(\prod_{i=1}^kl_{n_i}(t)\right)\,dt\tag{3} \end{align*}

Ya tenemos cuatro caracteres $b,r,g,y$ cada ocurren dos veces, hemos establecido \begin{align*} &n_1=n_2=n_3=n_4=2 \end{align*}

Aplicamos el teorema 2.1. y obtener el uso de (2) y (3) y con la ayuda de Wolfram Alpha \begin{align*} \int_{0}^\infty&e^{-t}\left(\prod_{i=1}^4l_{n_i}(t)\right)\,dt\\ &=\int_{0}^\infty e^{-t}\left(l_2(t)\right)^4\,dt\\ &=\int_{0}^\infty e^{-t}\left(\frac{1}{2}t^2-t\right)^4\,dt\\ &=\int_{0}^\infty e^{-t}\left(\frac{1}{16}t^{8}-\frac{1}{2}t^{7}+\frac{3}{2}t^{6} -2t^5+t^4\right)\,dt\\ &=\color{blue}{864} \end{align*}

Variación 2:

Otra variación es directamente sobre la base de un generación de la función de Smirnov palabras. (Véase el ejemplo III.24 Smirnov palabras de la Analítica de la Combinatoria de Philippe Flajolet y Robert Sedgewick para obtener más información.)

Una generación de función para el número de Smirnov palabras sobre una de cuatro letras del alfabeto $V=\{b,r,g,y\}$ está dado por \begin{align*} \left(1-\frac{4z}{1+z}\right)^{-1} \end{align*}

El número de todos Smirnov palabras de longitud $8$ a través de una de cuatro letras del alfabeto es, por tanto, \begin{align*} [z^8]\left(1-\frac{4z}{1+z}\right)^{-1} \end{align*}

Ya que queremos contar el número de palabras de longitud $8$ con cada personaje en $V$ se producen dos veces, hacemos un seguimiento de cada personaje. De nuevo con la ayuda de Wolfram Alpha, obtenemos \begin{align*} [b^2r^2g^2y^2]\left(1-\frac{b}{1+b}-\frac{r}{1+r}-\frac{g}{1+g}-\frac{y}{1+y}\right)^{-1}=\color{blue}{864} \end{align*}

Answer 2

Aquí es un peatón solución.

Cada admisible para colorear induce un emparejamiento de $8$ puntos en una fila de la cual no hay dos sucesivos puntos están emparejados. Por el contrario, cada emparejamiento da lugar a $4!$ admisible colorantes.

Con el fin de contar el total admisible de emparejamientos nos marca el primer elemento de cada par con una bala y la segunda con un círculo. Los dos primeros puntos, entonces son balas, y los últimos dos círculos. Hay seis maneras de poner dos balas y dos círculos en el medio. La figura siguiente muestra las posibles filas de las balas y de los círculos: $$\matriz{ \bullet&\bullet&\bullet&\bullet&\circ&\circ&\circ&\circ\cr \bullet&\bullet&\bullet&\circ&\bullet&\circ&\circ&\circ\cr \bullet&\bullet&\bullet&\circ&\circ&\bullet&\circ&\circ\cr \bullet&\bullet&\circ&\bullet&\bullet&\circ&\circ&\circ\cr \bullet&\bullet&\circ&\bullet&\circ&\bullet&\circ&\circ\cr \bullet&\bullet&\circ&\circ&\bullet&\bullet&\circ&\circ\cr }$$ Ahora tenemos a la par con los círculos permitido balas a la izquierda de ellos. La siguiente figura muestra cómo muchas opciones que tenemos, que va de izquierda a derecha. Tenga en cuenta que en cada paso el número de opciones disponibles no depende de las decisiones tomadas en la etapa anterior. $$\matriz{ \bullet&\bullet&\bullet&\bullet&3&3&2&1\cr \bullet&\bullet&\bullet&2&\bullet&2&2&1\cr \bullet&\bullet&\bullet&2&2&\bullet&1&1\cr \bullet&\bullet&1&\bullet&\bullet&2&2&1\cr \bullet&\bullet&1&\bullet&1&\bullet&1&1\cr \bullet&\bullet&1&1&\bullet&\bullet&1&1\cr }$$ Multiplicar las cifras de cada fila y sumar. El resultado es $36$, por lo que tenemos $36\cdot24=864$ admisible colorantes en todos.

Uno puede establecer un recursividad para el número admisible de emparejamientos, dado $2n$ puntos, y obtiene la siguiente tabla: $$0, 1, 5, {\bf 36}, 329, 3655, 47844, 721315, 12310199, 234615096\ .$$ Este es A278990 en OEIS, donde uno puede encontrar más información en esta secuencia.

Answer 3

Deje $S_j$ ser la disposición de que las bolas de color $j$ están juntos. A continuación, vamos a $$ N_k=\sum_{|A|=k}\left|\,\bigcap_{j\in A} S_j\,\right| $$ donde $A\subset\{1,2,3,4\}$

$\binom{4}{k}$ formas de elegir los $|A|=k$
$(8-k)!$ formas de organizar la $k$ elegido pares y $8-2k$ "singletons"
$2^{4-k}$ número de arreglos de los "únicos" que se cuentan como una

Por lo tanto, $$ N_k=\frac{\binom{4}{k}(8-k)!}{2^{4-k}} $$ La Generalizada del Principio de Inclusión-Exclusión , dice que el número de acuerdos en $0$ de la $S_j$ es $$ \sum_{k=0}^4(-1)^k\binom{k}{0}\frac{\binom{4}{k}(8-k)!}{2^{4-k}}=864 $$

Answer 4

La respuesta es $864$

supongamos que tenemos dos bolas de color azul (AA), dos bolas rojas (BB), dos bolas verdes (CC) y dos bolas amarillas (DD). Entonces tenemos la siguiente manera para obtener la respuesta. Este método utiliza inclusión-exclusión.

Nota: se crean utilizando las Permutaciones de la Calculadora

Answer 5

Deje $A_i$ ser el conjunto de disposiciones donde las bolas en los lugares $i$ $i+1$ tienen el mismo color, para $1\le i\le 7$.

Mediante La Inclusión-Exclusión,

$\displaystyle\lvert\overline{A_1}\cap\cdots\cap\overline{A_7}\rvert=|S|-\sum_i |A_i|+\sum_{i<j}|A_i\cap A_j|-\sum_{i<j<k}|A_i\cap A_j\cap A_k|+\cdots$

$\displaystyle\hspace{1.0 in}=\frac{8!}{2^4}-\binom{7}{1}\cdot4\cdot\frac{6!}{2^3}+\binom{6}{2}\cdot4\cdot3\cdot\frac{4!}{2^2}-\binom{5}{3}\cdot4\cdot3\cdot2+4!=864$

(donde, por ejemplo, en el 3er trimestre hay $\binom{6}{2}$ maneras de elegir los dos pares consecutivos en los lugares, $\;\;\;\;4\cdot3$ formas de los colores, y $\frac{4!}{2^2}$ formas de color que el resto de los lugares).