Nombre de permutations de $D,D,D,O,O,O,G,G,G$ tel que pas deux $D$ sont adjacents et pas deux $G$ sont adjacents

Aug 19 2020

J'ai le problème suivant. Je l'ai déjà résolu mais je ne suis pas satisfait de ma solution. J'espère une solution plus astucieuse et peut-être que quelqu'un pourra vous aider. Existe-t-il un moyen de résoudre ce problème uniquement avec la méthode étoiles / barres?

Calculez le nombre de façons de permuter toutes les lettres de $D,D,D,O,O,O,G,G,G$ tel que pas deux $D$ sont adjacents et pas deux $G$ sont adjacents.

Ma tentative.

Pour $k=2,3$, laisser $\Delta_k$ désigne l'ensemble des permutations st uniquement $k$ de $D$ sont adjacents et laissez $\Gamma_k$ désigne l'ensemble des permutations st uniquement $k$ de $G$sont adjacents. Laisser$U$ être l'ensemble de toutes les permutations sans aucune condition.

ensuite $$|U|=\frac{(3+3+3)!}{3!3!3!}=1680.$$ Nous avons $$|\Delta_3|=\frac{(1+3+3)!}{1!3!3!}=140$$ (comme $\Delta_3$ est l'ensemble des permutations de $DDD,O,O,O,G,G,G$), et $$|\Delta_2|+2|\Delta_3|=\frac{(1+1+3+3)!}{1!1!3!3!}=1120$$ puisque ce nombre compte les permutations de $DD,D,O,O,O,G,G,G$. Par conséquent$$|\Delta_2|=1120-2(140)=840.$$ De même $|\Gamma_3|=140$ et $|\Gamma_2|=840$.

Nous voulons trouver $|\Delta_i\cap\Gamma_j|$. Depuis$\Delta_3\cap\Gamma_3$ est l'ensemble des permutations de $DDD,O,O,O,GGG$, $$|\Delta_3\cap\Gamma_3|=\frac{(1+3+1)!}{1!3!1!}=20.$$ Depuis $|\Delta_2\cap\Gamma_3|+2|\Delta_3\cap\Gamma_3|$ compte les permutations de $DD,D,O,O,O,GGG$, nous avons $$|\Delta_2\cap\Gamma_3|+2|\Delta_3\cap\Gamma_3|=\frac{(1+1+3+1)!}{1!1!3!1!}=120$$ alors $$|\Delta_2\cap\Gamma_3|=120-2(20)=80.$$ De même $|\Delta_3\cap\Gamma_2|=80$.

Nous voulons maintenant trouver $|\Delta_2\cap\Gamma_2|$. Depuis$|\Delta_2\cap\Gamma_2|+2|\Delta_3\cap\Gamma_2|+2|\Delta_2\cap\Gamma_3|+4|\Delta_2\cap\Gamma_3|$ compte le nombre de permutations de $DD,D,O,O,O,GG,G$, on a $$|\Delta_2\cap\Gamma_2|+2|\Delta_3\cap\Gamma_2|+2|\Delta_2\cap\Gamma_3|+4|\Delta_2\cap\Gamma_3|=\frac{(1+1+3+1+1)!}{1!1!3!1!1!}=840.$$ Par conséquent $$|\Delta_2\cap\Gamma_2|=840-2(80)-2(80)-4(20)=440.$$

Par principe d'inclusion-exclusion, nous avons $$|\Delta_2\cup\Delta_3\cup\Gamma_2\cup\Gamma_3|=\sum_{k=2}^3|\Delta_k|+\sum_{k=2}^3|\Gamma_k|-\sum_{i=2}^3\sum_{j=2}^3|\Delta_i\cap \Gamma_j|.$$ Par conséquent $$|\Delta_2\cup\Delta_3\cup\Gamma_2\cup\Gamma_3|=2(840)+2(140)-(440+80+80+20)=1340.$$ La question demande la taille de $U\setminus(\Delta_2\cup\Delta_3\cup\Gamma_2\cup\Gamma_3)$, lequel est $$|U|-|\Delta_2\cup\Delta_3\cup\Gamma_2\cup\Gamma_3|=1680-1340=340.$$

Réponses

4 MathLover Aug 19 2020 at 12:56

Je ne sais pas s'il existe une manière plus astucieuse de faire cela, mais cela peut être plus simple, même en utilisant votre approche.

Les permutations de «DD DGGGOO O» couvrent tous les cas de D adjacents et de G adjacents sauf lorsque les G sont adjacents mais pas les D.

$i)$ Permutations de "DD DGGGOO O" $= \dfrac{8!}{3!3!} - \dfrac{7!}{3!3!} = 980$

[ La soustraction consiste à prendre en compte les DD D et D DD adjacents considérés comme différents. Les permutations DDD sont donc comptées deux fois et doivent être retirées une fois. ]

$ $

$ii)$ Permutations de "GG GOO O" et placement $3$ D est dans $3$ du non-adjacent $6$ des endroits

$$= \dfrac{5!}{3!}.{^6}C_3 - \dfrac{4!}{3!}.{^5}C_3 = 360$$

[ La soustraction consiste à prendre en compte les GG G et G GG adjacents considérés comme différents. Donc permutations GGG et placer D dans$3$ hors de $5$les places ont été comptées deux fois et doivent l'être une fois. ]

$ $

Cela vous donne les arrangements souhaités $= 1680 - 980 - 360 = 340$

1 DanielN Aug 20 2020 at 22:27

Je commence par reformuler et modifier légèrement le problème, puis le résoudre sous cette nouvelle forme; le passage au problème initial est canonique.

Problème. Considérez l'ensemble$S=S(d+4)=\{x_1, x_2, x_3, y_1, y_2, y_3, z_1, \ldots, z_{d-2}\}$. Une permutation de$S$ est appelé $x,y$- adjacent libre (et plus tard de type$(1,1)$) si pas deux $x$et pas deux $y$sont adjacents. Déterminez le nombre de$x,y$-permutations libres adjacentes.

Notez que les éléments $x_1$, $x_2$, et $x_3$ sont vus comme des éléments distincts (et il en va de même pour le $y$'s).
Le passage du problème à la question initiale est donné par la formule évidente$$ \frac{\text{number of $x, y$-adjacent free permutations of $S$}} {3!\, 3!\, (d-2)!} $$ dans lequel nous prenons $d=3$.

La solution penche vers les calculs algébriques récursifs (le modèle étant le triangle de Pascal). Du côté positif, nous pourrions être satisfaits des formules récursives (généralisations, calculs d'autres nombres similaires ...). Du côté négatif, il y aura des indices de vol encombrants dans toutes les directions.

Notation et description de la solution. Laisser$S^{a,b}\subset S$ être le sous-ensemble $$ S^{a,b} = \{ x_1,\ldots,x_a, y_1, \ldots, y_b, z_1, \ldots, z_{d-2}\} \subset S $$ avec $1\leq a,b\leq3$. Il a$d+a+b-2$éléments. Dénoter par$P_{(i,j)}^{a,b}$, avec $i\leq a$ et $j\leq b$, l'ensemble des permutations de $S^{a,b}$ avec exactement $i$ adjacent $x$'le sable $j$ adjacent $y$'s, appelées permutations de type $(i,j)$. Clairement l'ensemble de toutes les permutations de$S^{a,b}$ est $$ \bigcup_{\substack{1\leq i\leq a\\1\leq j\leq b}} P_{(i,j)}^{a,b}. $$ Nous voulons calculer $N_{(1,1)}^{3,3}$, le cardinal de $P_{(1,1)}^{3,3}$. L'idée est de faire le calcul récursivement en utilisant la filtration suivante de$S^{3,3}$: $$ S^{1,1} \subset S^{2,1} \subset S^{3,1} \subset S^{3,2} \subset S^{3,3}. $$ Chaque $N_{(i,j)}^{a,b}$ correspondant au sous-ensemble $S^{a,b}$ dans la filtration est exprimé comme une combinaison linéaire avec des coefficients entiers de tous les $N$'s du sous-ensemble précédent. Une fois les coefficients déterminés (en utilisant la combinatoire de la construction) pour tous ces passages, le problème est résolu.

Trouver les coefficients. Commençons par ce que nous recherchons:$$ N_{(1,1)}^{3,3} = d\,N_{(1,1)}^{3,2} + N_{(2,1)}^{3,2}. $$Les autres coefficients sont tous nuls dans ce cas. L'explication est qu'une permutation de$S^{3,3}$ de type $(1,1)$ ne peut être émis qu'à partir d'une permutation de $S^{3,2}$ qui est soit de type $(1,1)$ ou de type $(2,1)$. Pour une permutation dans le premier cas, il y a exactement$d=d+4-4$ positions (hors $d+4$) où $y_3$ peut être inséré (à côté de ni $y_1$ ni $y_2$). Dans le dernier cas,$y_3$ doit être inséré entre les deux $x$'s.

Nous poursuivons avec les formules pour $N_{(1,1)}^{3,2}$ et $N_{(2,1)}^{3,2}$ en utilisant le passage de $S^{3,1}$ à $S^{3,2}$dans notre filtration. La formule pour$N_{(1,1)}^{3,2}$ est presque le même que le précédent: $$ N_{(1,1)}^{3,2} = (d+3-2)\,N_{(1,1)}^{3,1} + N_{(2,1)}^{3,1} = (d+1)\,N_{(1,1)}^{3,1} + N_{(2,1)}^{3,1}. $$ La formule pour $N_{(2,1)}^{3,2}$est plus délicat. Ça lit$$ N_{(2,1)}^{3,2} = 0\,N_{(1,1)}^{3,1} + (d+3-3)\,N_{(2,1)}^{3,1} + 2N_{(3,1)}^{3,1} \\ = d\,N_{(2,1)}^{3,1} + 2N_{(3,1)}^{3,1}. $$ Le coefficient $d+3-3$ vient du constat suivant: Si un type $(2,1)$ permutation de $S^{3,2}$ est émis d'un type $(2,1)$ permutation de $S^{3,1}$, puis $y_2$ a exactement $d+3-3$ endroits possibles à insérer dans: $d+3$ est le nombre total de places et $y_2$ ne peut prendre ni la place entre les $x$ni aucun des deux endroits adjacents à $y_1$.

En regardant les deux dernières formules, nous notons qu'à partir de maintenant nous avons besoin de tous les $N$correspond aux sous-ensembles restants de la filtration. Mais ils sont moins nombreux et les formules plus faciles à comprendre. On obtient successivement:

pour $S^{2,1}\subset S^{3,1}$ $$ N_{(1,1)}^{3,1} = (d+2-4)\,N_{(1,1)}^{2,1} + 0\,N_{(2,1)}^{2,1} $$ $$ N_{(2,1)}^{3,1} = 4\,N_{(1,1)}^{2,1} + (d+2-3)\,N_{(2,1)}^{2,1} $$ $$ N_{(3,1)}^{3,1} = 0\,N_{(1,1)}^{2,1} + 3\,N_{(2,1)}^{2,1} $$
pour $S^{1,1}\subset S^{2,1}$ $$ N_{(1,1)}^{2,1} = (d+1-2)\,N_{(1,1)}^{1,1} \quad\text{and}\quad N_{(2,1)}^{2,1} = 2\,N_{(1,1)}^{1,1}. $$

Les calculs maintenant, pour obtenir$N_{(1,1)}^{3,3}$ il suffit de revenir en arrière en commençant par $N_{(1,1)}^{1,1}=d!$. Faisons les calculs en soulignant leur caractère algorithmique. J'espère que la notation ci-dessous est explicite.