¿De cuántas maneras puede $7$ niñas y $3$ los chicos se sientan en un banco de tal manera que cada chico se sienta al lado de al menos una chica
La respuesta es supuestamente $1,693,440 + 423,360 = 2,116,800$
$7$ las niñas pueden sentarse en $7!=5040$ formas. Cada asiento crea seis ranuras interiores en las que se pueden colocar uno o dos chicos, y dos ranuras finales en las que se puede colocar como máximo un chico.
Cuando no haya dos niños sentados juntos podemos colocarlos en $8\cdot 7\cdot6=336$ formas en las ocho ranuras ( $8$ opciones para el primer chico, $7$ restante para el segundo, y $6$ para el tercero).
Cuando dos chicos se sientan juntos podemos elegir cualquiera de los $6$ ranuras interiores para ellos. Entonces podemos elegir el de la izquierda de los dos en $3$ formas, la de la derecha en $2$ formas. Finalmente podemos elegir cualquiera de los $7$ ranuras sobrantes para el tercer chico. En total tenemos $6\cdot3\cdot2\cdot 7=252$ posibilidades de un acuerdo de este tipo.
De ello se deduce que el número total de asientos admisibles viene dado por $$5040\cdot(336+252)=2\,963\,520\ .$$
@Chellapillai: La secuencia puede comenzar con $GBG\ldots$ , $GBBG\ldots$ , $BG\ldots$ pero no con $BBG\ldots$ .
Una pista: Considera el complemento, que es "hay un chico que se sienta entre dos chicos O hay un chico al final de la fila que está al lado de un chico".
Hay 10! formas de organizar sin restricciones.
Hay $ 3! \times 8!$ formas de organizar BBB como un bloque.
Hay $3! \times 8! \times 2$ formas de organizar BB como un bloque en cualquier extremo.
Hay $ 3! \times 7! \times 2$ formas de organizar BBB como un bloque en cualquier extremo.
También podemos resolverlo mediante una recursión de dos variables:
Dejemos que $A(b,g)$ sea el número de formas de ordenar la cadena de B's y G's, tal que no contenga ``BBB'' como subcadena. Se puede escribir como:
\begin {align*} A(b,g) &= A(b,g-1)+A(b-1,g-1)+A(b-2,g-1) \\ A(0,g) &= 1 \\ A(1,g) &= 1+g \\ A(2,g) &= \binom {2+g}{2} \\ A(b,0) &= 0 \end {align*} Como también necesitamos una condición de que no puede empezar por "BBG'' ni terminar por "GBB'', el número de cadenas válidas (por PIE) son $$A(m,n)-2\, A(m-2,n-1)+A(m-4,n-2)$$ donde $m$ y $n$ son el número de niños y niñas, respectivamente.
Como las B y las G son distinguibles, el número total de formas posibles es
$$\mathbb{N}\left(m,n\right) = \Big(A(m,n)-2\, A(m-2,n-1)+A(m-4,n-2)\Big)\cdot m!\cdot n!$$
Y para nuestro problema, $\mathbb{N}(3,7) = 98\cdot 3!\cdot 7! = 2963520$
Actualización
Podemos obtener una función generadora, a partir de su expresión regular (obtenida construyendo un autómata finito determinista y minimizándolo), como se describe en combinatoria analítica
El RE es $((g+bg)g^*b)^*(\epsilon+(g+bg)g^*)$ y el f.g. obtenido será: \begin {align*} G(x,y) &= \mathrm {SEQ} \left ( \left (y+xy \right ) \mathrm {SEQ}(y)x \right ) \left (1+(y+xy) \mathrm {SEQ}(y) \right ) \\ &= \mathrm {SEQ} \left ( \frac {y+xy}{1-y} x \right ) \left (1+ \frac {y+xy}{1-y} \right ) \\ &= \frac {1+xy}{1-y(1+x+x^2)} \end {align*}
Actualización 2
A partir de la f.g., también podemos obtener la siguiente fórmula:
\begin {align*} \mathbb {N}(m,n) &= \left ( \sum_ {k= \lfloor m/2 \rfloor }^m \binom {n-1}{k} \binom {k}{m-k-1} + \binom {n}{k} \binom {k}{m-k} \right ) \cdot ¡m! \cdot ¡n! \end {align*}
Gracias por confirmar que la respuesta era correcta. Estoy seguro de que aprenderé este método más adelante en mi curso
De nada. Sin embargo, no puedo decir nada sobre su curso. Sin embargo, es interesante para mí. ¡Buen problema para una recursión!
Muy bien, eso es bueno :) Me alegro de que lo hayas encontrado interesante. Bueno, estoy estudiando Ciencias Actuariales en Sudáfrica con una doble especialización en estadística matemática, así que estoy a mitad de camino en el primer año de estadísticas y sólo hemos pasado unas pocas semanas en permutaciones y combinaciones, además de un poco de teoría de la probabilidad, por lo que espero profundizar un poco en algunas cosas más interesantes más adelante. El resto del tiempo hemos estado haciendo estadísticas descriptivas, etc.
Creo que tengo una respuesta. Por favor, dime si ves algún fallo en ella.
Un método de sustracción de los casos imposibles parecía ser el mejor, pero ya no lo creo. Sin embargo. La respuesta que dieron parece errónea en cualquier caso.
Así que trabajando con los casos que son posibles es
B B B
G G G G G G G
O
BB B
G G G G G G G
En el primer caso, todos los chicos están separados. Deben ocupar un puesto entre dos chicas o en el extremo de cada una. Todos estos casos son válidos
$7! \times {^8\mathrm{P}_3} = 1 693 440$
En el segundo caso, hay un grupo de 2 chicos y un chico solo que hay que clasificar. El grupo de 2 NO PUEDE estar en ninguno de los extremos por lo que sólo son válidos los espacios entre las chicas donde el último chico puede ocupar cualquier espacio incluyendo los del extremo EXCEPTO aquel en el que el grupo de dos ocupó un espacio
$7! \times {^3\mathrm{P}_2} \times {^6\mathrm{P}_1} \times {^7\mathrm{P}_1} = 1 270 080$
$\begin{align}\operatorname{n}(S) &= 1 693 440 + 1 270 080 \\ & = 2 963 520\end{align}$
--------------->Por favor, dígame si cree que he hecho una suposición falsa o que he calculado algo incorrectamente
El segundo caso debería ser: ${^7\mathrm{P}_7}\times {^3\mathrm{P}_3} \times {^6\mathrm{C}_1} \times {^7\mathrm{C}_1} = 1270080$ ; valor correcto, lógica equivocada. Cuenta las formas de ordenar todas las chicas, ordenar todos los chicos, y seleccionar lugares para poner los chicos entre las chicas.
Oh, vale, veo tu lógica, pero lo que hice fue ordenar el grupo de dos chicos y luego usar permutaciones para colocar a los chicos y ordenarlos
¿No es una lógica correcta en el primer paso decir 7P7 x 8P3 Y 7P7 x 8C3 x 3!. Supuse que el método de las permutaciones sólo lo ordena ya
Este problema equivale a hacer los arreglos con chicos consecutivos sentados entre chicas. El número total de formas en las que se pueden disponer 3 chicos y 7 chicas es de 10! formas. De ellas, el número de formas en que los chicos se sientan con las chicas se puede desglosar en tres casos.
Podemos considerar que el primer reparto tiene dos pares, el segundo caso tiene un par y el tercero no tiene pares. La suma del número de vías en los tres casos debe ser igual a 10!. En la pregunta formulada, no queremos el primero porque, resulta que hay dos parejas consecutivas de chicos sentados violando la regla. Lo que no queremos de la segunda son los que empiezan por BBG y los que terminan por GBB.
BBG _ _ _ _ _ _. Esto se podría arreglar en ${3\choose2}{7\choose1}2!7!$
Del mismo modo _ _ _ _ _ _GBB. Esto se podría arreglar en ${3\choose2}{7\choose1}2!7!$
Sumando estos dos, obtenemos $14*3!*7!$ .
Atlast lo que queremos es el tercer caso cuando no hay parejas y cada chico está sentado con chicas Llamemos $n_1$ = nº de chicas y $n_2$ = número de niños
Cada pareja debe tener un miembro de la izquierda, que podemos elegir entre cualquiera de los chicos excepto el último : $\tbinom{n_2-1}{p}$ . Esto creará $n_2-p$ bloques de chicos, que podemos distribuir en el $n_1+1$ ranuras entre y alrededor de las chicas: $\tbinom{n_1+1}{n_2-p}$ . Por lo tanto, el número de formas con exactamente $p$ pares es $\tbinom{n_2-1}{p}\tbinom{n_1+1}{n_2-p}$ .
Para p = 2: $\tbinom{3-1}{2}\tbinom{7+1}{3-2} = 8$ y esto lo multiplicas por 3! para ordenar a los chicos y 7! maneras de ordenar a las chicas.
No queremos nada de lo anterior.
Para p = 1: $\tbinom{3-1}{1}\tbinom{7+1}{3-1} = 2*28*3!*7! = 56*3!*7!$
Ahora resta lo que no queremos en un par que es $14*3!7!$
Lo que queremos de p = 1 es $(56-14)*3!*7! = 42*3!*7!$
Para p = 0: $\tbinom{3-1}{0}\tbinom{7+1}{3-0} = 56 = 56*3!*7!$
Lo que queremos de p = 0 es todo y por tanto el número de formas $ = 56*3!*7! = 1693440$
El número total de formas tales que todos los chicos se sientan con al menos una chica $=(56+42)*3!*7! = 98*3!*7!$ = 2963520.
"Cada chico debe sentarse al lado de una chica significa" ¿qué? Debería ser así ...GB...GB... GB.... Por lo tanto, no debería comenzar con BG y "BB" no debería aparecer en ninguna parte de la secuencia, ¿no?
Puede ser a la izquierda o a la derecha. Así que BG es una forma correcta. BB es una forma correcta siempre y cuando no sea a los dos extremos, Porque, GBBG es admisible ya que Los chicos están sentados al lado de una chica. Creo que tienes que ir a leer las soluciones de los demás y darle sentido.
Gracias. Por lo tanto, la pregunta debería ser de esta manera. El vecino de cada chico debe contener al menos una chica. En la práctica, la palabra "siguiente" significa que considerará sólo una dirección, ¿no?
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.
1 votos
Estimado usuario157220: Si las respuestas te resultan útiles, puedes votar cada una de ellas. Si encuentras que una respuesta es la más útil, también puedes aceptar la respuesta. Para aceptar una respuesta, basta con pulsar el botón gris $\large \checkmark$ a la izquierda de la respuesta que desea aceptar. Al hacer clic en ella, se vuelve verde y se obtiene $2$ puntos de reputación por cada respuesta que puedas aceptar. (Sólo puedes aceptar una respuesta por pregunta formulada).
0 votos
Chico debe sentarse al lado de una chica significa, el arreglo no debe leer ''BB" y no debe comenzar con Chico. ¿Estoy en lo cierto?