Combinazione con esclusione
- Kate sta progettando per lei $8$ giorni Periodo di studio.
- Ogni giorno può scegliere uno dei $3$ Materie: matematica, inglese o fisica.
- Non studia mai matematica e inglese per giorni consecutivi. (cioè No ME o EM)
- Vuole anche studiare almeno tutti $3$ soggetti in almeno un giorno del suo periodo di studio.
Quanti orari diversi sono possibili ?.
Provai $3^4-3 \cdot 2^4+3 \cdot 1= 36$ per $4$programma giornaliero. Disegno l'immagine e ci sarà solo$10$possibili orari. Non so come fare l'esclusione in matematica e inglese per giorni consecutivi. Per favore aiuto. Grazie.
Risposte
La seguente risposta è un approccio in due fasi basato sul metodo cluster Goulden-Jackson e PIE, il principio di inclusione-esclusione.
Primo passo: $A(z)$ evitando parolacce
Consideriamo l'insieme di parole di lunghezza $n\geq 0$ costruito da un alfabeto $$\mathcal{V}=\{E,M,P\}$$ e il set $B=\{EM, ME\}$di parolacce , che non possono far parte delle parole che stiamo cercando. Deriviamo una funzione generatrice$A(z)$ con il coefficiente di $z^n$ essendo il numero di parole di lunghezza desiderate $n$.
Secondo il documento (p.7) la funzione generatrice $A(z)$ è \begin{align*} A(z)=\frac{1}{1-dz-\text{weight}(\mathcal{C})}\tag{1} \end{align*} con $d=|\mathcal{V}|=3$, la dimensione dell'alfabeto e $\mathcal{C}$essendo il numeratore del peso delle parolacce con\begin{align*} \text{weight}(\mathcal{C})=\text{weight}(\mathcal{C}[EM])+\text{weight}(\mathcal{C}[ME]) \end{align*}
Teniamo anche traccia delle lettere usate che sono necessarie quando si considera la torta e calcoliamo in base alla carta \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*} che si traduce in \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*}
Da (1) e (2) in (1) otteniamo la funzione generatrice
\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*}
Nota che \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*} dove i coefficienti di $z^n$ dare il numero di parole di lunghezza $n$ che non contengono $EM$ o $ME$. Questi coefficienti (calcolati con Wolfram Alpha) sono conformi ai numeri indicati nella risposta di @GregBrowns.
Secondo passo: con PIE a $B(z;E,M,P)$
Stiamo cercando parole che contengano ciascuna delle lettere $\{E,M,P\}$ e denotano la corrispondente funzione generatrice $B(z;E,M,P)$. Lo facciamo escludendo parole che non contengono una di queste lettere usando PIE. Per ottenere parole che non contengono, ad esempio$E$, calcoliamo \begin{align*} [E^0]A(z;E,M,P)=A(z;E,M,P)|_{E=0} \end{align*} che indichiamo come $A(z;0,M,P)$.
Utilizzando PIE calcoliamo $B(z;E,M,P)$ con l'aiuto di (3) come \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 otteniamo la funzione di generazione desiderata $B(z)$ da (4) come \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*} dove l'ultima riga è stata calcolata con l'aiuto di Wolfram Alpha.
Risultato: ci sono$\color{blue}{882}$ valide parole di lunghezza $8$ che non contengono $EM$ e $ME$ e così, che ogni parola contiene le tre lettere $E,M,P$.
Due controlli di plausibilità: $n=4$ e $n=8$.
Vediamo in (5) ci sono $10$ valide parole di lunghezza $4$. Questi sono\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*}
Calcoliamo manualmente il coefficiente di $z^8$da (5). Usiamo il coefficiente di operatore$[z^n]$per denotare il coefficiente di una serie. Otteniamo\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*} come previsto.
Nel Day1, se P ha scelto, allora tutti e 3 (P, M, E) il Day 2. Se ha scelto M, allora ha solo 2 (P, M) il giorno 2 e se ha scelto E ha anche solo 2 ( P, E) per il giorno 2. Sommare tutte le possibilità che ha in totale 7 casi per il giorno 2.
Nel giorno 3 e in tutti gli scenari del giorno 2, può fare P, quindi ha 3 + 2 + 2 = 7 opzioni. Se ha scelto E ha 3 + 2 = 5 e lo stesso per M. Aggiunge tutte le possibilità per il giorno 3 è 17.
Day 1 Day 2 Day 3 Day 4 Day 5 Day 6 Day 7 Day 8
M 1 2 5 12 29 70169408
E 1 2 5 12 29 70169408
P 1 3 7 17 41 99239 577
Totale 3 7 17 41 99239577 1393
Take Away non tutti e 3 i soggetti nel programma = 2 * 2 ^ 8 (numero di giorni) = 512
Aggiungi 1 per il conteggio inferiore
882
Ecco un semplice approccio ricorsivo. Per$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}\}$, permettere $f(d,m,e,p,s)$ essere il numero di programmi, dato $d$ giorni rimanenti, $m$ giorni rimanenti di matematica richiesti, $e$ giorni necessari di inglese rimanenti, $p$ giorni richiesti di fisica rimanenti e soggetto precedente $s$. Poi$$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} $$ Se $d<m+e+p$, non sono rimasti abbastanza giorni per soddisfare il requisito di tutte le materie. Altrimenti, se$d=0$, c'è solo il programma vuoto. In caso contrario, le scelte consentite del soggetto corrente dipendono dal soggetto precedente$s$e qualunque argomento venga scelto riduce i giorni rimanenti di $1$ e il requisito per tale soggetto da $1$a meno che il requisito non sia già stato soddisfatto. Le parentesi$[]$ sono notazioni di Iverson che producono $1$ se l'espressione è vera e $0$se l'espressione è falsa. Vogliamo calcolare$f(8,1,1,1,.)$, che risulta essere $882$.
A proposito, $f(4,1,1,1,.)=10 \not= 8$.
Perché il numero di giorni richiesto per ogni soggetto è $1$, potresti invece lasciare $g(d,S,s)$ essere il numero di programmi, dato $d$ giorni rimanenti, $S\subseteq\{\text{M},\text{E},\text{P}\}$ sottoinsieme di soggetti rimanenti e soggetto precedente $s$. Poi$$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} $$ Poi $g(8,\{\text{M},\text{E},\text{P}\},.)=882$.
Ecco una formalizzazione della prima parte dell'approccio di @ GregBrown, ignorando l'obbligo di studiare ogni argomento almeno una volta. Permettere$m_n$ (e $e_n$ e $p_n$) essere il numero di programmi di lunghezza $n$ che finiscono in $M$ (e $E$ e $P$, rispettivamente) e non contengono $ME$ o $EM$. Poi$m_1=e_1=p_1=1$, $m_2=e_2=2$, $p_2=3$, e per $n\ge 3$ noi abbiamo \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} Adesso molla $t_n=m_n+e_n+p_n$ essere il numero di programmi di lunghezza $n$ che non contengono $ME$ o $EM$e nota che sommando $(1)$, $(2)$, e $(3)$ implica che $$t_n=2t_{n-1}+p_{n-1}=2t_{n-1}+t_{n-2}.$$ Utilizzando questa ricorrenza e le condizioni iniziali $t_1=3$ e $t_2=7$, lo troviamo \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}