Combinaison avec exclusion
- Kate prépare pour elle $8$ jours de période d'étude.
- Chaque jour, elle peut choisir l'un des $3$ Matières: mathématiques, anglais ou physique.
- Elle n'étudie jamais les mathématiques et l'anglais des jours consécutifs. (c'est-à-dire pas de ME ou EM)
- Elle veut aussi étudier au moins tous $3$ sujets pendant au moins un jour de sa période d’étude.
Combien d'horaires différents sont possibles ?.
j'ai essayé $3^4-3 \cdot 2^4+3 \cdot 1= 36$ pour $4$horaire de jour. Je dessine l'image et il n'y aura que$10$horaires possibles. Je ne sais pas comment faire l'exclusion sur les mathématiques et l'anglais pendant des jours consécutifs. Veuillez aider. Je vous remercie.
Réponses
La réponse suivante est une approche en deux étapes basée sur la méthode du cluster Goulden-Jackson et PIE, le principe d'inclusion-exclusion.
Pas de poing: $A(z)$ éviter les mauvais mots
Nous considérons l'ensemble des mots de longueur $n\geq 0$ construit à partir d'un alphabet $$\mathcal{V}=\{E,M,P\}$$ et l'ensemble $B=\{EM, ME\}$de mauvais mots , qui ne sont pas autorisés à faire partie des mots que nous recherchons. Nous dérivons une fonction génératrice$A(z)$ avec le coefficient de $z^n$ étant le nombre de mots de longueur voulus $n$.
Selon l'article (p.7) la fonction de génération $A(z)$ est \begin{align*} A(z)=\frac{1}{1-dz-\text{weight}(\mathcal{C})}\tag{1} \end{align*} avec $d=|\mathcal{V}|=3$, la taille de l'alphabet et $\mathcal{C}$être le poids-numérateur des mauvais mots avec\begin{align*} \text{weight}(\mathcal{C})=\text{weight}(\mathcal{C}[EM])+\text{weight}(\mathcal{C}[ME]) \end{align*}
Nous gardons également une trace des lettres utilisées qui sont nécessaires lors de l'examen de PIE et calculons en fonction du 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*} ce qui se traduit par \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) et (2) dans (1) nous obtenons la fonction génératrice
\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*}
Notez 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*} où les coefficients de $z^n$ donner le nombre de mots de longueur $n$ qui ne contiennent pas $EM$ ou $ME$. Ces coefficients (calculés avec Wolfram Alpha) sont conformes aux nombres indiqués dans la réponse @GregBrowns.
Deuxième étape: avec PIE pour $B(z;E,M,P)$
Nous recherchons des mots contenant chacune des lettres $\{E,M,P\}$ et désignent la fonction génératrice correspondante $B(z;E,M,P)$. Nous faisons cela en excluant les mots qui ne contiennent pas une de ces lettres en utilisant PIE. Pour obtenir des mots qui ne contiennent pas par exemple$E$, nous calculons \begin{align*} [E^0]A(z;E,M,P)=A(z;E,M,P)|_{E=0} \end{align*} que nous désignons par $A(z;0,M,P)$.
En utilisant PIE, nous calculons $B(z;E,M,P)$ avec l'aide de (3) comme \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*}
On obtient enfin la fonction génératrice souhaitée $B(z)$ de (4) comme \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*} où la dernière ligne a été calculée avec l'aide de Wolfram Alpha.
Résultat: il y a$\color{blue}{882}$ mots valides de longueur $8$ qui ne contiennent pas $EM$ et $ME$ et ainsi, que chaque mot contient les trois lettres $E,M,P$.
Deux contrôles de plausibilité: $n=4$ et $n=8$.
On voit dans (5) il y a $10$ mots valides de longueur $4$. Ceux-ci sont\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*}
Nous calculons manuellement le coefficient de $z^8$à partir de (5). Nous utilisons le coefficient d' opérateur$[z^n]$pour désigner le coefficient d'une série. On obtient\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*} comme prévu.
Au Jour 1, si P a choisi, alors les 3 (P, M, E) le Jour 2. Si elle a choisi M, alors elle n'a que 2 (P, M) le Jour 2 et si elle a choisi E, elle n'a également que 2 ( P, E) pour le jour 2. Additionnez toutes les possibilités qu'elle a au total 7 cas pour le jour 2.
Au jour 3 et dans tous les scénarios du jour 2, elle peut faire P, donc elle a 3 + 2 + 2 = 7 options. Si elle a choisi E, elle a 3 + 2 = 5 et la même chose pour M. Ajoute toute possibilité pour le jour 3 est 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 99239577
Total 3 7 17 41 99239577 1393
À emporter pas tous les 3 sujets du calendrier = 2 * 2 ^ 8 (nombre de jours) = 512
Ajouter 1 pour sous-dénombrement
882
Voici une approche récursive simple. Pour$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}\}$, laisser $f(d,m,e,p,s)$ être le nombre d'horaires, donné $d$ Jours restant, $m$ jours requis de mathématiques restants, $e$ jours requis d'anglais restants, $p$ jours requis de physique restants et sujet précédent $s$. ensuite$$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$, il ne reste plus assez de jours pour satisfaire les exigences de tous les sujets. Sinon, si$d=0$, il n'y a que le calendrier vide. Sinon, les choix possibles du sujet actuel dépendent du sujet précédent$s$, et quel que soit le sujet choisi, réduit les jours restants de $1$ et l'exigence de ce sujet par $1$sauf si l'exigence a déjà été remplie. Les supports$[]$ sont la notation Iverson qui donne $1$ si l'expression est vraie et $0$si l'expression est fausse. Nous voulons calculer$f(8,1,1,1,.)$, qui s'avère être $882$.
Au fait, $f(4,1,1,1,.)=10 \not= 8$.
Parce que le nombre de jours requis pour chaque sujet est $1$, tu pourrais plutôt laisser $g(d,S,s)$ être le nombre d'horaires, donné $d$ Jours restant, $S\subseteq\{\text{M},\text{E},\text{P}\}$ sous-ensemble de sujets restants et sujet précédent $s$. ensuite$$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} $$ ensuite $g(8,\{\text{M},\text{E},\text{P}\},.)=882$.
Voici une formalisation de la première partie de l'approche de @ GregBrown, en ignorant l'exigence d'étudier chaque sujet au moins une fois. Laisser$m_n$ (et $e_n$ et $p_n$) soit le nombre d'horaires de longueur $n$ qui se terminent par $M$ (et $E$ et $P$, respectivement) et ne contiennent pas $ME$ ou $EM$. ensuite$m_1=e_1=p_1=1$, $m_2=e_2=2$, $p_2=3$, et pour $n\ge 3$ nous avons \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} Maintenant, laisse $t_n=m_n+e_n+p_n$ être le nombre d'horaires de longueur $n$ qui ne contiennent pas $ME$ ou $EM$, et notez que la somme $(1)$, $(2)$, et $(3)$ implique que $$t_n=2t_{n-1}+p_{n-1}=2t_{n-1}+t_{n-2}.$$ En utilisant cette récurrence et les conditions initiales $t_1=3$ et $t_2=7$, on trouve 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}