Hallar el número de maneras, de modo que cada niño es adyacente a más de una niña.

Question

Hay $7$ niños y $3$ de las niñas que necesitan ser alineados en una fila. Hallar el número de maneras, de modo que cada niño es adyacente a más de una niña.

En términos simples, la situación exige que cualquier distribución del tipo $$...GBG...$$ no deben entrar en juego.

Primero de todo, el número total de arreglos $10!$ y realmente podemos encontrar un complemento de aquellas situaciones que no queremos.

Con el fin de calcular el número de maneras en las que la posición incorrecta puede ser cierto, que yo consideraba $GBG$ a ser una especie de un solo paquete. El número de maneras para hacer de este paquete son:$${7 \choose 1} \cdot {3 \choose 2} \cdot 2!$$, now considering this package and $6$ boys plus the $1$ la chica de la izquierda, podemos permutar todos ellos en 8! las formas [$6$ varones, $1$ chica y nuestro "paquete"], con lo que el total a ser $$ {7 \choose 1} \cdot {3 \choose 2} \cdot 2! \cdot 8! \tag{1}$$

Las cosas parecen ser manejable hithero, pero como yo estaba escribiendo esta pregunta vi un problema en mi argumento: Los casos que contiene las configuraciones $GBGBG$ sido posible contado varias veces por lo tanto, $(1)$ no está dando el número correcto de formas de ser sustraído.

Podemos de todos modos hacer algunos cambios en este enfoque y encontrar la solución?

Answer 1

Considerando que los niños y las niñas indistinguibles, cada arreglo tiene la forma

$$ (S_1\, G \,S_2 \,G \,S_3 \,G\, S_4)$$

donde $S_i$ es el número consecutivo de los niños, con $S_i\ge 0$$\sum S_i=7$. La restricción ("cada niño es adyacente a una chica") corresponde al $S_2\ne 1$$S_3\ne 1$.

Deje $W_{n,k}=\binom{n+k-1}{k-1}$ recuento de los débiles composiciones de $n$ $k$ partes (formas de sintetizar $k$ no los números negativos para obtener el $n$, el orden importa).

A continuación, el régimen jurídico está dado por

$$ W_{7,4} - 2 W_{6,3} + W_{5,2}=\binom{10}{3}-2\binom{8}{2}+\binom{6}{1}=70$$

El $W_{6,3}$ plazo, sustrae el prohibido configuraciones ($S_2=1$ o $S_3=1$), y el $W_{5,2}$ plazo compensa (inclusión-exclusión) para el cómputo doble de las $S_2=1$ $S_3=1$ de los casos.

Pero los niños y las niñas son distinguibles, por lo tanto se multiplica por las permutaciones. Y la respuesta final es

$$ 70 \7 veces! \times 3! =2116800 $$

Answer 2

Sugiero otra solución, con base en los métodos de análisis combinatoria (creo que la biblia de la asignatura es que este libro de P. Flajolet y R. Sedgewick).

Una buena configuración (tomando sólo en cuenta el género) se ve algo como esto

\begin{align*} {\mathop{SEQ}}(B) \,\,G \,\,{\mathop{SEQ}}^{\neq 1}(B) \,\,G \,\,{\mathop{SEQ}}^{\neq 1}(B) \,\,G \,\,{\mathop{SEQ}}(B), \end{align*}

significado:

• Un (posiblemente vacía) de la secuencia de $B$oys; seguido por
• $G$irl; seguido por
• Un (posiblemente vacía) de la secuencia de $B$oys, excepto para la secuencia con una sola $B$oy; seguido por
• $G$irl; seguido por
• Un (posiblemente vacía) de la secuencia de $B$oys, excepto para la secuencia con una sola $B$oy; seguido por
• $G$irl; seguido por
• Un (posiblemente vacía) de la secuencia de $B$oys.

Esto corresponde a una generación de función:

$$f(z) = \frac{1}{1-z} \cdot z \cdot \left(\frac{1}{1-z} - z\right) \cdot z \cdot \left(\frac{1}{1-z} - z\right) \cdot z \cdot \frac{1}{1-z} = \frac{z^3\,{(1-z+z^2)}^2}{(1-z)^4}.$$

Usted está interesado en el caso de que no se $10$ de las personas, por lo que el coeficiente de $z^{10}$ en la expansión de $f(z)$:

$$[z^{10}]\,f(z) = [z^7]\,\frac{{(1-z+z^2)}^2}{(1-z)^4}.$$

Esto es fácil de calcular, se $70$.

Ahora, para cada configuración, podemos permutar los niños alrededor de $7!$ formas y las niñas de todo en $3!$ formas, mientras que la preservación de la configuración. Esto debe nos da un total de

$$70\cdot 7! \cdot 3! = 2116800$$

buena compra.

---

Creo que esta exposición muestra que el problema se reduce a: ¿Cómo podemos distribuir $7$ de varones de más de $4$ depósitos, donde $2$ de los contenedores que no se puede asignar exactamente la de un chico? (Cada contenedor puede estar vacío.)
Esto también se generaliza fácilmente a $b$ niños y $g$ niñas. Tendríamos

$$f(z) = \frac{z^g\,{\left(1-z+z^2\right)}^{g-1}}{(1-z)^{g+1}},$$

el coeficiente sería

$$[z^{b+g}]\,f(z) = [z^b]\,\frac{{\left(1-z+z^2\right)}^{g-1}}{(1-z)^{g+1}}$$

y la respuesta sería así

$$[z^b]\,\frac{{\left(1-z+z^2\right)}^{g-1}}{(1-z)^{g+1}} \cdot b! \cdot g!$$

Answer 3

Antes de la colocación de los individuos que tiene que contar el total admisible de los arreglos de los niños y las niñas.

Entre dos chicas no puede ser $0$ o $\geq2$ varones. De ello se desprende que el total admisible de los arreglos son de los siguientes cuatro tipos: $$\eqalign{b^xg^3b^y,&\qquad x+y=7,\cr b^x gb^{2+y}g^2 b^z\quad{\rm o}\quad b^x g^2 b^{y+2}gb^z,&\quad x+y+z=5,\cr b^x g b^{2+y}gb^{2+z}gb^w,&\quad x+y+z+w=3\cr}$$ con $x$, $y$, $z$, $w$ enteros $\geq0$. El número de estos acuerdos es $${8\choose1}+2\cdot{7\choose2}+{6\choose3}=70\ .$$ Tomando los nombres de los niños y niñas en cuenta llegamos a $$7!\,3!\,70=2\,116\,800$$ admisible configuraciones.

Answer 4

Utilizando la misma lógica que @Fimpellizieri, el problema también puede resolverse por técnicas elementales. Cualquier problemática disposición parece $$S \, GBG \, S \, G \, S $$ or $$S \, G \, S \, GBG \, S $$ where the $S$ parts are (possibly non-empty) sequences of boys. Now, for both the cases, the problem is reduced to a problem of putting $6$ boys into $3$ places, which using stars-and-bars algorithm, can be easily solved. The number turns out to be ${6+3-1 \elegir 6}={8 \elegir 6}=28$. Desde que los niños y las niñas pueden ser mezcladas entre sí, en todos los casos, el número total es de $28 \times 7! \times 3!=846720$.

La combinación de los dos casos, el número total de casos no válidos es $2 \times 846720=1693440$. Tenga en cuenta que estamos contando los casos de la forma $$S \, GBGBG \, S $$ twice. Using a similar algorithm as before, the total number of such cases is ${5+2-1 \elegir 5}\times 7! \times 3!=6 \7 veces! \times 3! = 181440$.

Por lo tanto, el número total permitido de arreglos es $10!-1693440+181440=2116800$.

(Me puse a calcular antes de @Fimpellizieri 's respuesta fue publicada. Desde mi enfoque es mucho más elemental y simple de entender, he decidido publicar de todos modos.)

Los cálculos corregido gracias a fallo descubierto por @leonbloy.

Answer 5

Vamos $G = \{g_1,g_2,g_3\}$, $B = \{b_1,\ldots,b_7\}$, y deje $X$ ser el conjunto de todas las permutaciones de $G\cup B$. Ahora para $1\le i\le 8$ deje $A_i$ el conjunto de las permutaciones $\pi\in X$ s.t. $\pi(i), \pi(i+2)\in G$ $\pi(i+1)\in B$.

Necesitamos encontrar a $|X\setminus\bigcup_i A_i|$, lo que, por la Inclusión-Exclusión Principio, es igual a $$\sum_{j\ge 0}(-1)^j S_j,$$ donde $S_j = \sum_{i_1,\ldots,i_j} |A_{i_1}\cap\cdots\cap A_{i_j}|$.

$S_0$ es simplemente $|X| = 10!$, $|A_i| = 3\cdot 2\cdot 7\cdot 7! = 42\cdot 7!$ (recoger a una niña en la posición $i$, luego otra chica en la posición $i+2$, a continuación, un niño en la posición $i+1$, a continuación, coloque el resto de los niños en forma arbitraria), por lo $S_1 = 8\cdot 42\cdot 7!$.

Al igual, $|A_i\cap A_{i+1}| = 0$, $|A_i\cap A_{i+2}| = 3\cdot 2\cdot 1\cdot 7\cdot 6\cdot 5! = 6\cdot 7!$, $|A_i\cap A_{i+r}| = 0$ para $r>2$, lo $S_2 = 6\cdot 6\cdot 7!$$S_j = 0$$j\ge 3$.

Por último, la respuesta es $10!-S_1+S_2 = 2116800$.