Combinación con Exclusión
- Kate está planeando para ella $8$ días Periodo de estudio.
- Cada día puede elegir uno de los $3$ Asignaturas: Matemáticas, Inglés o Física.
- Ella nunca estudia matemáticas e inglés en días consecutivos. (es decir, no ME o EM)
- Ella también quiere estudiar al menos todos $3$ sujetos en al menos un día de su período de estudio.
¿Cuántos horarios diferentes son posibles ?.
Lo intenté $3^4-3 \cdot 2^4+3 \cdot 1= 36$ para $4$horario del día. Hago el dibujo y solo quedará$10$posibles horarios. No estoy seguro de cómo hacer la exclusión sin matemáticas e inglés en días consecutivos. Por favor ayuda. Gracias.
Respuestas
La siguiente respuesta es un enfoque de dos pasos basado en el método de agrupación Goulden-Jackson y PIE, el principio de inclusión-exclusión.
Paso de puño: $A(z)$ evitando malas palabras
Consideramos el conjunto de palabras de longitud $n\geq 0$ construido a partir de un alfabeto $$\mathcal{V}=\{E,M,P\}$$ y el set $B=\{EM, ME\}$de malas palabras , que no pueden formar parte de las palabras que buscamos. Derivamos una función generadora$A(z)$ con el coeficiente de $z^n$ siendo el número de palabras deseadas de longitud $n$.
Según el artículo (p.7) la función generadora $A(z)$ es \begin{align*} A(z)=\frac{1}{1-dz-\text{weight}(\mathcal{C})}\tag{1} \end{align*} con $d=|\mathcal{V}|=3$, el tamaño del alfabeto y $\mathcal{C}$siendo el numerador de peso de malas palabras con\begin{align*} \text{weight}(\mathcal{C})=\text{weight}(\mathcal{C}[EM])+\text{weight}(\mathcal{C}[ME]) \end{align*}
También hacemos un seguimiento de las letras utilizadas que se necesitan al considerar PIE y calculamos de acuerdo con el documento. \begin{align*} \text{weight}(\mathcal{C}[EM])&=-(EM)z^2-Ez\cdot\text{weight}(\mathcal{C}[EM])\\\ \text{weight}(\mathcal{C}[ME])&=-(ME)z^2-Mz\cdot\text{weight}(\mathcal{C}[ME])\\ \end{align*} lo que resulta en \begin{align*} \text{weight}(\mathcal{C}[EM])=-EMz^2\frac{1-Ez}{1-EMz^2}\tag{2}\\ \text{weight}(\mathcal{C}[ME])=-EMz^2\frac{1-Mz}{1-EMz^2}\\ \end{align*}
De (1) y (2) en (1) obtenemos la función generadora
\begin{align*} \color{blue}{A}&\color{blue}{(z;E,M,P)}\\ &=\frac{1}{1-(E+M+P)+EMz^2\frac{1-Ez}{1-EMz^2}+EMz^2\frac{1-MZ}{1-EMz^2}}\\ &\,\,\color{blue}{=\frac{1-EMz^2}{1-(E+M+P)z+EMz^2+EMPz^3}}\tag{3} \end{align*}
Tenga en cuenta que \begin{align*} A(z)&=A(z;1,1,1)\\ &=\frac{1-z^2}{1-3z+z^2+z^3}\\ &=1+3z+7z^2+17z^3+41z^4+99z^5\\ &\qquad+239z^6+577z^7+\color{blue}{1\,393}z^8+3\,363z^9+8\,119z^{10}+\cdots \end{align*} donde los coeficientes de $z^n$ dar el número de palabras de longitud $n$ que no contienen $EM$ o $ME$. Estos coeficientes (calculados con Wolfram Alpha) están de acuerdo con los números indicados en la respuesta de @GregBrowns.
Segundo paso: Con PIE para $B(z;E,M,P)$
Buscamos palabras que contengan cada una de las letras $\{E,M,P\}$ y denotar la función generadora correspondiente $B(z;E,M,P)$. Lo hacemos excluyendo las palabras que no contienen una de estas letras usando PIE. Para obtener palabras que no contienen, por ejemplo$E$, calculamos \begin{align*} [E^0]A(z;E,M,P)=A(z;E,M,P)|_{E=0} \end{align*} que denotamos como $A(z;0,M,P)$.
Usando PIE calculamos $B(z;E,M,P)$ con la ayuda de (3) como \begin{align*} B&(z;E,M,P)\\ &=A(z;E,M,P)\\ &\qquad-A(z;0,M,P)-A(z;E,0,P)-A(z;E,M,0)\\ &\qquad+A(z;0,0,P)+A(z;0,M,0)+A(z;E,0,0)\\ &\qquad-A(z;0,0,0)\\ &=\frac{1-EMz^2}{1-(E+M+P)z+EMz^2+EMPz^3}\\ &\qquad-\frac{1}{1-(M+P)z}-\frac{1}{1-(E+P)z}-\frac{1-EMz^2}{1-(E+M)z+EMz^2}\\ &\qquad+\frac{1}{1-Pz} +\frac{1}{1-Mz}+\frac{1}{1-Ez}\\ &\qquad-1\tag{4}\\ \end{align*}
Finalmente obtenemos la función generadora deseada $B(z)$ de (4) como \begin{align*} \color{blue}{B(z)}&=B(z;1,1,1,1)\\ &=\frac{1-z^2}{1-3z+z^2+z^3}-\frac{2}{1-2z}-\frac{1-z^2}{1-2z+z^2}+\frac{3}{1-z}-1\\ &\,\,\color{blue}{=\frac{1+z}{1-2z-z^2}-\frac{2}{1-2z}+\frac{1}{1-z}}\\ &=2z^3+10z^4+36z^5+112z^6+322z^7+\color{blue}{882}z^8+2\,340z^9+\cdots\tag{5} \end{align*} donde se calculó la última línea con ayuda de Wolfram Alpha.
Resultado: hay$\color{blue}{882}$ palabras válidas de longitud $8$ que no contienen $EM$ y $ME$ y así, que cada palabra contenga las tres letras $E,M,P$.
Dos comprobaciones de plausibilidad: $n=4$ y $n=8$.
Vemos en (5) hay $10$ palabras válidas de longitud $4$. Estos son\begin{align*} &\text{EEPM}\quad\text{EPMM}\quad\text{EPMP}\quad\text{EPPM}\quad\text{MMPE}\\ &\text{MPEE}\quad\text{MPEP}\quad\text{MPPE}\quad\text{PEPM}\quad\text{PMPE} \end{align*}
Calculamos manualmente el coeficiente de $z^8$de (5). Usamos el coeficiente de operador$[z^n]$para denotar el coeficiente de una serie. Obtenemos\begin{align*} \color{blue}{[z^8]}&\color{blue}{B(z)}=[z^8]\left(\frac{1+z}{1-2z-z^2 }-\frac{2}{1-2z}+\frac{1}{1-z}\right)\\ &=\left([z^8]+[z^7]\right)\sum_{j=0}^\infty z^j(2+z)^j-2[z^8]\sum_{j=0}^\infty(2z)^j+[z^8]\sum_{j=0}^\infty z^j\\ &=\sum_{j=0}^8[z^{8-j}](2+z)^j+\sum_{j=0}^7[z^{7-j}](2+z)^j-2(2^8)+1\\ &=\sum_{j=0}^8\binom{j}{8-j}2^{2j-8}+\sum_{j=0}^7\binom{j}{7-j}2^{2j-7}-2^9+1\\ &=\binom{4}{4}2^0+\binom{5}{3}2^2+\binom{6}{2}2^4+\binom{7}{1}2^6+\binom{8}{0}2^8\\ &\qquad+\binom{4}{3}2^1+\binom{5}{2}2^3+\binom{6}{1}2^5+\binom{7}{0}2^7-511\\ &=1+40+240+448+256\\ &\qquad+8+80+192+128-511\\ &\,\,\color{blue}{=882} \end{align*} como se esperaba.
En el día 1, si eligió P, entonces los 3 (P, M, E) el día 2. Si eligió M, entonces solo tiene 2 (P, M) el día 2 y si eligió E, también solo tiene 2 ( P, E) para el día 2. Sume todas las posibilidades que tiene en total 7 casos para el día 2.
En el día 3 y en todos los escenarios del día 2, puede hacer P, por lo que tiene 3 + 2 + 2 = 7 opciones. Si eligió E, tiene 3 + 2 = 5 y lo mismo para M. Agrega que todas las posibilidades para el día 3 son 17.
Day 1 Day 2 Day 3 Day 4 Day 5 Day 6 Day 7 Day 8
M 1 2 5 12 29 70 169 408
E 1 2 5 12 29 70 169 408
P 1 3 7 17 41 99 239 577
Total 3 7 17 41 99239577 1393
Para llevar, no los 3 temas del programa = 2 * 2 ^ 8 (número de días) = 512
Agregue 1 para contar menos
882
Aquí hay un enfoque recursivo simple. por$d \in \{0, \dots, 8\}$, $m \in \{0,1\}$, $e \in \{0,1\}$, $p \in \{0,1\}$, $s \in \{.,\text{M},\text{E},\text{P}\}$, dejar $f(d,m,e,p,s)$ ser el número de horarios, dado $d$ Días restantes, $m$ días requeridos de matemáticas restantes, $e$ días requeridos de inglés restantes, $p$ días requeridos de Física restantes y asignatura anterior $s$. Luego$$f(d,m,e,p,s) = \begin{cases} 0 & \text{if $d <m + e + p$} \\ 1 & \text{if $d = 0$} \\ [s \not= \text{E}] f(d-1,\max(m-1,0),e,p,\text{M})\\ + [s \not= \text{M}] f(d-1,m,\max(e-1,0),p,\text{E})\\ + f(d-1,m,e,\max(p-1,0),\text{P}) &\text{otherwise} \end{cases} $$ Si $d<m+e+p$, no quedan días suficientes para satisfacer el requisito de todas las asignaturas. De lo contrario, si$d=0$, solo existe el horario vacío. De lo contrario, las opciones permitidas del tema actual dependen del tema anterior.$s$, y el tema que se elija reduce los días restantes en $1$ y el requisito para ese tema por $1$a menos que el requisito ya se haya cumplido. Los corchetes$[]$ son la notación Iverson que produce $1$ si la expresión es verdadera y $0$si la expresión es falsa. Queremos calcular$f(8,1,1,1,.)$, que resulta ser $882$.
Por cierto, $f(4,1,1,1,.)=10 \not= 8$.
Porque el número de días requerido para cada asignatura es $1$, en su lugar podrías dejar $g(d,S,s)$ ser el número de horarios, dado $d$ Días restantes, $S\subseteq\{\text{M},\text{E},\text{P}\}$ subconjunto de sujetos restantes y tema anterior $s$. Luego$$g(d,S,s) = \begin{cases} 0 & \text{if $d <| S |$} \\ 1 & \text{if $d = 0$} \\ [s \not= \text{E}] g(d-1,S\setminus \{\text{M}\},\text{M})\\ + [s \not= \text{M}] g(d-1,S\setminus \{\text{E}\},\text{E})\\ + g(d-1,S\setminus \{\text{P}\},\text{P}) &\text{otherwise} \end{cases} $$ Luego $g(8,\{\text{M},\text{E},\text{P}\},.)=882$.
Aquí hay una formalización de la primera parte del enfoque de @ GregBrown, ignorando el requisito de estudiar cada tema al menos una vez. Dejar$m_n$ (y $e_n$ y $p_n$) sea el número de horarios de duración $n$ que terminan en $M$ (y $E$ y $P$, respectivamente) y no contienen $ME$ o $EM$. Luego$m_1=e_1=p_1=1$, $m_2=e_2=2$, $p_2=3$, y para $n\ge 3$ tenemos \begin{align} m_n &= m_{n-1} + p_{n-1} \tag1\\ e_n &= e_{n-1} + p_{n-1} \tag2\\ p_n &= m_{n-1} + e_{n-1} + p_{n-1} \tag3 \end{align} Ahora deja $t_n=m_n+e_n+p_n$ ser el número de horarios de duración $n$ que no contienen $ME$ o $EM$y tenga en cuenta que sumando $(1)$, $(2)$y $(3)$ implica que $$t_n=2t_{n-1}+p_{n-1}=2t_{n-1}+t_{n-2}.$$ Usando esta recurrencia y las condiciones iniciales $t_1=3$ y $t_2=7$, encontramos eso \begin{align} t_3 &= 2t_2 + t_1 = 2(7)+3=17 \\ t_4 &= 2t_3 + t_2 = 2(17)+7=41 \\ t_5 &= 2t_4 + t_3 = 2(41)+17=99 \\ t_6 &= 2t_5 + t_4 = 2(99)+41=239 \\ t_7 &= 2t_6 + t_5 = 2(239)+99=577 \\ t_8 &= 2t_7 + t_6 = 2(577)+239=1393 \end{align}