Combinação com Exclusão
- Kate está planejando para ela $8$ dias Período de estudo.
- Cada dia ela pode escolher um dos $3$ Disciplinas: Matemática, Inglês ou Física.
- Ela nunca estuda matemática e inglês em dias consecutivos. (ou seja, sem ME ou EM)
- Ela também quer estudar pelo menos todos $3$ assuntos em pelo menos um dia de seu período de estudo.
Quantos horários diferentes são possíveis ?.
eu tentei $3^4-3 \cdot 2^4+3 \cdot 1= 36$ para $4$programação do dia. Eu desenho a imagem e haverá apenas$10$horários possíveis. Não tenho certeza de como fazer exclusão em nenhuma matemática e inglês em dias consecutivos. Por favor ajude. Obrigado.
Respostas
A resposta a seguir é uma abordagem de duas etapas baseada no Método de Cluster Goulden-Jackson e PIE, o princípio de inclusão-exclusão.
Primeiro passo: $A(z)$ evitando palavrões
Nós consideramos o conjunto de palavras de comprimento $n\geq 0$ construído a partir de um alfabeto $$\mathcal{V}=\{E,M,P\}$$ e o conjunto $B=\{EM, ME\}$de palavrões , que não podem fazer parte das palavras que procuramos. Nós derivamos uma função geradora$A(z)$ com o coeficiente de $z^n$ sendo o número de palavras desejadas de comprimento $n$.
De acordo com o artigo (p.7) a função geradora $A(z)$ é \begin{align*} A(z)=\frac{1}{1-dz-\text{weight}(\mathcal{C})}\tag{1} \end{align*} com $d=|\mathcal{V}|=3$, o tamanho do alfabeto e $\mathcal{C}$sendo o numerador de peso de palavrões com\begin{align*} \text{weight}(\mathcal{C})=\text{weight}(\mathcal{C}[EM])+\text{weight}(\mathcal{C}[ME]) \end{align*}
Também monitoramos as letras usadas que são necessárias ao considerar o PIE e calculamos de acordo com o papel \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*} o que resulta em \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) e (2) em (1), obtemos a função geradora
\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*}
Observe 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*} onde os coeficientes de $z^n$ dê o número de palavras de comprimento $n$ que não contém $EM$ ou $ME$. Esses coeficientes (calculados com Wolfram Alpha) estão de acordo com os números declarados na resposta @GregBrowns.
Segunda etapa: Com o PIE para $B(z;E,M,P)$
Estamos procurando palavras que contenham cada uma das letras $\{E,M,P\}$ e denotam a função geradora correspondente $B(z;E,M,P)$. Fazemos isso excluindo palavras que não contêm uma dessas letras usando PIE. Para obter palavras que não contêm, por exemplo$E$, nós 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 o PIE, calculamos $B(z;E,M,P)$ com a ajuda 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 conseguimos a função de geração desejada $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*} onde a última linha foi calculada com a ajuda de Wolfram Alpha.
Resultado: existem$\color{blue}{882}$ palavras válidas de comprimento $8$ que não contém $EM$ e $ME$ e assim, cada palavra contém as três letras $E,M,P$.
Duas verificações de plausibilidade: $n=4$ e $n=8$.
Vemos em (5) que existem $10$ palavras válidas de comprimento $4$. Esses são\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 o coeficiente de $z^8$de (5). Usamos o coeficiente do operador$[z^n]$para denotar o coeficiente de uma série. Nós obtemos\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 esperado.
No Dia1, se P escolheu, então todos os 3 (P, M, E) no Dia 2. Se ela escolheu M, então ela só tem 2 (P, M) no dia 2 e se ela escolheu E ela também tem apenas 2 ( P, E) para o dia 2. Some todas as possibilidades que ela tem no total de 7 casos para o dia 2.
No dia 3 e em todos os cenários do dia 2, ela pode fazer P, então ela tem 3 + 2 + 2 = 7 opções. Se ela escolheu E, ela tem 3 + 2 = 5 e o mesmo para M. Adiciona todas as possibilidades para o Dia 3 é 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 99 239 577 1393
Retirar nem todas as 3 disciplinas da programação = 2 * 2 ^ 8 (número de dias) = 512
Adicione 1 para contagem inferior
882
Aqui está uma abordagem recursiva simples. Para$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}\}$, deixei $f(d,m,e,p,s)$ seja o número de horários, dado $d$ Dias restantes, $m$ dias necessários de matemática restantes, $e$ dias necessários de inglês restantes, $p$ dias necessários de Física restantes e matéria anterior $s$. Então$$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} $$ E se $d<m+e+p$, não faltam dias suficientes para satisfazer o requisito de todas as disciplinas. Caso contrário, se$d=0$, existe apenas a programação vazia. Caso contrário, as escolhas permitidas do assunto atual dependem do assunto anterior$s$, e qualquer assunto escolhido reduz os dias restantes em $1$ e o requisito para esse assunto por $1$a menos que o requisito já tenha sido atendido. Os colchetes$[]$ são notação Iverson que produz $1$ se a expressão for verdadeira e $0$se a expressão for falsa. Queremos calcular$f(8,1,1,1,.)$, que acaba sendo $882$.
A propósito, $f(4,1,1,1,.)=10 \not= 8$.
Porque o número necessário de dias para cada assunto é $1$, você poderia deixar $g(d,S,s)$ seja o número de horários, dado $d$ Dias restantes, $S\subseteq\{\text{M},\text{E},\text{P}\}$ subconjunto de assuntos restantes e assunto anterior $s$. Então$$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} $$ Então $g(8,\{\text{M},\text{E},\text{P}\},.)=882$.
Aqui está uma formalização da primeira parte da abordagem de @GregBrown, ignorando a necessidade de estudar cada assunto pelo menos uma vez. Deixei$m_n$ (e $e_n$ e $p_n$) ser o número de horários de comprimento $n$ que termina em $M$ (e $E$ e $P$, respectivamente) e não contêm $ME$ ou $EM$. Então$m_1=e_1=p_1=1$, $m_2=e_2=2$, $p_2=3$, e para $n\ge 3$ temos \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} Agora deixe $t_n=m_n+e_n+p_n$ seja o número de horários de comprimento $n$ que não contém $ME$ ou $EM$, e observe que a soma $(1)$, $(2)$, e $(3)$ implica que $$t_n=2t_{n-1}+p_{n-1}=2t_{n-1}+t_{n-2}.$$ Usando esta recorrência e as condições iniciais $t_1=3$ e $t_2=7$, nós achamos que \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}