Kombination mit Ausschluss
- Kate plant für sie $8$ Tage Studienzeit.
- Jeden Tag kann sie eine der wählen $3$ Fächer: Mathematik, Englisch oder Physik.
- An aufeinanderfolgenden Tagen lernt sie nie Mathematik und Englisch. (dh KEIN ME oder EM)
- Sie will auch mindestens alle studieren $3$ Probanden an mindestens einem Tag ihrer Studienzeit.
Wie viele verschiedene Zeitpläne sind möglich?
Ich habe es versucht $3^4-3 \cdot 2^4+3 \cdot 1= 36$ zum $4$Tagesplan. Ich zeichne das Bild und es wird nur geben$10$mögliche Zeitpläne. Ich bin mir nicht sicher, wie ich an aufeinanderfolgenden Tagen ohne Mathematik und Englisch ausschließen soll. Bitte helfen Sie. Vielen Dank.
Antworten
Die folgende Antwort ist ein zweistufiger Ansatz, der auf der Goulden-Jackson-Cluster-Methode und PIE, dem Prinzip des Einschluss-Ausschlusses, basiert .
Erster Schritt: $A(z)$ schlechte Worte vermeiden
Wir betrachten die Menge der Wörter der Länge $n\geq 0$ aus einem Alphabet gebaut $$\mathcal{V}=\{E,M,P\}$$ und das Set $B=\{EM, ME\}$von schlechten Wörtern , die nicht Teil der Wörter sein dürfen, nach denen wir suchen. Wir leiten eine generierende Funktion ab$A(z)$ mit dem Koeffizienten von $z^n$ ist die Anzahl der gewünschten Wörter der Länge $n$.
Nach dem Papier (S.7) die Erzeugungsfunktion $A(z)$ ist \begin{align*} A(z)=\frac{1}{1-dz-\text{weight}(\mathcal{C})}\tag{1} \end{align*} mit $d=|\mathcal{V}|=3$, die Größe des Alphabets und $\mathcal{C}$der Gewichtszähler von schlechten Wörtern mit\begin{align*} \text{weight}(\mathcal{C})=\text{weight}(\mathcal{C}[EM])+\text{weight}(\mathcal{C}[ME]) \end{align*}
Wir verfolgen auch die verwendeten Buchstaben, die bei der Betrachtung von PIE benötigt werden, und berechnen gemäß dem Papier \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*} was in ... endet \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*}
Aus (1) und (2) in (1) erhalten wir die Erzeugungsfunktion
\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*}
Beachten Sie, dass \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*} wo die Koeffizienten von $z^n$ Geben Sie die Anzahl der Wörter mit der Länge an $n$ die nicht enthalten $EM$ oder $ME$. Diese Koeffizienten (berechnet mit Wolfram Alpha) stimmen mit den in der Antwort von @GregBrowns angegebenen Zahlen überein.
Zweiter Schritt: Mit PIE zu $B(z;E,M,P)$
Wir suchen nach Wörtern, die jeden der Buchstaben enthalten $\{E,M,P\}$ und bezeichnen die entsprechende Erzeugungsfunktion $B(z;E,M,P)$. Wir tun dies mit Worten ohne die sie nicht eines dieser Buchstaben mit PIE enthalten. Um Wörter zu erhalten, die zum Beispiel nicht enthalten$E$, wir rechnen \begin{align*} [E^0]A(z;E,M,P)=A(z;E,M,P)|_{E=0} \end{align*} was wir als bezeichnen $A(z;0,M,P)$.
Mit PIE berechnen wir $B(z;E,M,P)$ mit Hilfe von (3) als \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*}
Wir bekommen endlich die gewünschte Erzeugungsfunktion $B(z)$ aus (4) als \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*} wo die letzte Zeile mit Hilfe von Wolfram Alpha berechnet wurde.
Ergebnis: Es gibt$\color{blue}{882}$ gültige Wörter der Länge $8$ die nicht enthalten $EM$ und $ME$ und so, dass jedes Wort die drei Buchstaben enthält $E,M,P$.
Zwei Plausibilitätsprüfungen: $n=4$ und $n=8$.
Wir sehen in (5), dass es gibt $10$ gültige Wörter der Länge $4$. Diese sind\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*}
Wir berechnen den Koeffizienten von manuell $z^8$aus (5). Wir verwenden den Koeffizienten des Operators$[z^n]$um den Koeffizienten einer Reihe zu bezeichnen. Wir erhalten\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*} wie erwartet.
Wenn an Tag 1 P gewählt wurde, dann alle 3 (P, M, E) an Tag 2. Wenn sie M gewählt hat, hat sie nur 2 (P, M) an Tag 2 und wenn sie E gewählt hat, hat sie auch nur 2 (P, M) P, E) für Tag 2. Addieren Sie alle Möglichkeiten, die sie für Tag 2 insgesamt 7 Fälle hat.
An Tag 3 und in allen Szenarien an Tag 2 kann sie P ausführen, sodass sie 3 + 2 + 2 = 7 Optionen hat. Wenn sie E gewählt hat, hat sie 3 + 2 = 5 und das gleiche für M. Fügt hinzu, dass alle Möglichkeiten für Tag 3 17 sind.
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
Gesamt 3 7 17 41 99 239 577 1393
Nehmen Sie nicht alle 3 Probanden im Zeitplan mit = 2 * 2 ^ 8 (Anzahl der Tage) = 512
Addiere 1 für die Unterzählung
882
Hier ist ein einfacher rekursiver Ansatz. Zum$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}\}$, Lassen $f(d,m,e,p,s)$ Geben Sie die Anzahl der angegebenen Zeitpläne an $d$ verbleibende Tage, $m$ erforderliche Tage Mathe verbleiben, $e$ erforderliche Tage Englisch übrig, $p$ erforderliche Tage der verbleibenden Physik und vorheriges Fach $s$. Dann$$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} $$ Wenn $d<m+e+p$Es bleiben nicht genügend Tage, um die Anforderungen aller Probanden zu erfüllen. Ansonsten wenn$d=0$gibt es nur den leeren Zeitplan. Andernfalls hängen die zulässigen Auswahlmöglichkeiten für das aktuelle Fach vom vorherigen Fach ab$s$und welches Thema auch immer gewählt wird, reduziert die verbleibenden Tage um $1$ und die Anforderung für dieses Thema von $1$es sei denn, die Anforderung wurde bereits erfüllt. Die Klammern$[]$ sind Iverson-Notation, die ergibt $1$ wenn der Ausdruck wahr ist und $0$wenn der Ausdruck falsch ist. Wir wollen rechnen$f(8,1,1,1,.)$, was sich herausstellt $882$.
Apropos, $f(4,1,1,1,.)=10 \not= 8$.
Weil die erforderliche Anzahl von Tagen für jedes Fach ist $1$könnte man stattdessen lassen $g(d,S,s)$ Geben Sie die Anzahl der angegebenen Zeitpläne an $d$ verbleibende Tage, $S\subseteq\{\text{M},\text{E},\text{P}\}$ Teilmenge der verbleibenden Themen und vorheriges Thema $s$. Dann$$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} $$ Dann $g(8,\{\text{M},\text{E},\text{P}\},.)=882$.
Hier ist eine Formalisierung des ersten Teils des Ansatzes von @ GregBrown, wobei die Anforderung, jedes Fach mindestens einmal zu studieren, ignoriert wird. Lassen$m_n$ (und $e_n$ und $p_n$) ist die Anzahl der Längenpläne $n$ das endet in $M$ (und $E$ und $P$jeweils) und enthalten nicht $ME$ oder $EM$. Dann$m_1=e_1=p_1=1$, $m_2=e_2=2$, $p_2=3$, und für $n\ge 3$ wir haben \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} Nun lass $t_n=m_n+e_n+p_n$ sei die Anzahl der Zeitpläne der Länge $n$ das enthalten nicht $ME$ oder $EM$und beachten Sie die Summierung $(1)$, $(2)$, und $(3)$ impliziert, dass $$t_n=2t_{n-1}+p_{n-1}=2t_{n-1}+t_{n-2}.$$ Durch Verwendung dieser Wiederholung und der Anfangsbedingungen $t_1=3$ und $t_2=7$, wir glauben, dass \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}