Numero di permutazioni di $D,D,D,O,O,O,G,G,G$ tale che non ce ne siano due $D$ sono adiacenti e non due $G$ sono adiacenti

Aug 19 2020

Ho il seguente problema. L'ho già risolto ma non sono soddisfatto della mia soluzione. Spero in una soluzione più intelligente e forse qualcuno può aiutarla. C'è un modo per risolvere questo problema solo con il metodo stelle / barre?

Calcola il numero di modi per permutare tutte le lettere da $D,D,D,O,O,O,G,G,G$ tale che non ce ne siano due $D$ sono adiacenti e non due $G$ sono adiacenti.

Il mio tentativo.

Per $k=2,3$, permettere $\Delta_k$ denotano solo l'insieme di permutazioni st $k$ di $D$ sono adiacenti e lasciate $\Gamma_k$ denotano solo l'insieme di permutazioni st $k$ di $G$sono adiacenti. Permettere$U$ essere l'insieme di tutte le permutazioni senza alcuna condizione.

Poi $$|U|=\frac{(3+3+3)!}{3!3!3!}=1680.$$ abbiamo $$|\Delta_3|=\frac{(1+3+3)!}{1!3!3!}=140$$ (come $\Delta_3$ è l'insieme delle permutazioni di $DDD,O,O,O,G,G,G$), e $$|\Delta_2|+2|\Delta_3|=\frac{(1+1+3+3)!}{1!1!3!3!}=1120$$ poiché questo numero conta le permutazioni di $DD,D,O,O,O,G,G,G$. Perciò$$|\Delta_2|=1120-2(140)=840.$$ Allo stesso modo $|\Gamma_3|=140$ e $|\Gamma_2|=840$.

Vogliamo trovare $|\Delta_i\cap\Gamma_j|$. Da$\Delta_3\cap\Gamma_3$ è l'insieme delle permutazioni di $DDD,O,O,O,GGG$, $$|\Delta_3\cap\Gamma_3|=\frac{(1+3+1)!}{1!3!1!}=20.$$ Da $|\Delta_2\cap\Gamma_3|+2|\Delta_3\cap\Gamma_3|$ conta le permutazioni di $DD,D,O,O,O,GGG$, noi abbiamo $$|\Delta_2\cap\Gamma_3|+2|\Delta_3\cap\Gamma_3|=\frac{(1+1+3+1)!}{1!1!3!1!}=120$$ così $$|\Delta_2\cap\Gamma_3|=120-2(20)=80.$$ Allo stesso modo $|\Delta_3\cap\Gamma_2|=80$.

Ora vogliamo trovare $|\Delta_2\cap\Gamma_2|$. Da$|\Delta_2\cap\Gamma_2|+2|\Delta_3\cap\Gamma_2|+2|\Delta_2\cap\Gamma_3|+4|\Delta_2\cap\Gamma_3|$ conta il numero di permutazioni di $DD,D,O,O,O,GG,G$, noi abbiamo $$|\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.$$ Quindi $$|\Delta_2\cap\Gamma_2|=840-2(80)-2(80)-4(20)=440.$$

Per principio di inclusione-esclusione abbiamo $$|\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|.$$ Perciò $$|\Delta_2\cup\Delta_3\cup\Gamma_2\cup\Gamma_3|=2(840)+2(140)-(440+80+80+20)=1340.$$ La domanda chiede la dimensione di $U\setminus(\Delta_2\cup\Delta_3\cup\Gamma_2\cup\Gamma_3)$, che è $$|U|-|\Delta_2\cup\Delta_3\cup\Gamma_2\cup\Gamma_3|=1680-1340=340.$$

Risposte

4 MathLover Aug 19 2020 at 12:56

Non so se esiste un modo più semplice per farlo, ma può essere più semplice, anche usando il tuo approccio.

Le permutazioni di "DD DGGGOO O" coprono tutti i casi di D adiacenti e G adiacenti tranne dove le G sono adiacenti ma le D non lo sono.

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

[ La sottrazione consiste nel prendersi cura di DD D e D DD adiacenti considerati diversi. Quindi le permutazioni DDD vengono contate due volte e devono essere eliminate una volta. ]

$ $

$ii)$ Permutazioni di "GG GOO O" e posizionamento $3$ D's in $3$ del non adiacente $6$ posti

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

[ La sottrazione consiste nel prendersi cura di GG G adiacenti e G GG considerati diversi. Quindi le permutazioni GGG e l'inserimento di D in$3$ fuori da $5$i posti sono stati contati due volte e devono essere contati una volta. ]

$ $

Questo ti dà le disposizioni desiderate $= 1680 - 980 - 360 = 340$

1 DanielN Aug 20 2020 at 22:27

Inizio riaffermando e modificando leggermente il problema, quindi lo risolvo con questa nuova forma; il passaggio al problema iniziale è canonico.

Problema. Considera il set$S=S(d+4)=\{x_1, x_2, x_3, y_1, y_2, y_3, z_1, \ldots, z_{d-2}\}$. Una permutazione di$S$ è chiamato $x,y$- adiacente libero (e successivo di tipo$(1,1)$) se non due $x$e non due $y$sono adiacenti. Determina il numero di file$x,y$- permutazioni libere adiacenti.

Nota che gli elementi $x_1$, $x_2$, e $x_3$ sono visti come elementi distinti (e lo stesso per $y$'S).
Il passaggio dal Problema alla domanda iniziale è dato dalla formula ovvia$$ \frac{\text{number of $x, y$-adjacent free permutations of $S$}} {3!\, 3!\, (d-2)!} $$ in cui prendiamo $d=3$.

La soluzione tende a calcoli algebrici ricorsivi (il modello è il triangolo di Pascal). Sul lato positivo, potremmo essere soddisfatti delle formule ricorsive (generalizzazioni, calcoli di altri numeri simili ...). Sul lato negativo, ci saranno ingombranti indici volanti in tutte le direzioni.

Notazione e descrizione della soluzione. Permettere$S^{a,b}\subset S$ essere il sottoinsieme $$ S^{a,b} = \{ x_1,\ldots,x_a, y_1, \ldots, y_b, z_1, \ldots, z_{d-2}\} \subset S $$ con $1\leq a,b\leq3$. Esso ha$d+a+b-2$elementi. Denota da$P_{(i,j)}^{a,b}$, con $i\leq a$ e $j\leq b$, l'insieme di permutazioni di $S^{a,b}$ con esattamente $i$ adiacente $x$è e $j$ adiacente $y$'s, chiamate permutazioni di tipo $(i,j)$. Chiaramente l'insieme di tutte le permutazioni di$S^{a,b}$ è $$ \bigcup_{\substack{1\leq i\leq a\\1\leq j\leq b}} P_{(i,j)}^{a,b}. $$ Vogliamo calcolare $N_{(1,1)}^{3,3}$, il cardinale di $P_{(1,1)}^{3,3}$. L'idea è di eseguire il calcolo in modo ricorsivo utilizzando il seguente filtraggio di$S^{3,3}$: $$ S^{1,1} \subset S^{2,1} \subset S^{3,1} \subset S^{3,2} \subset S^{3,3}. $$ Ogni $N_{(i,j)}^{a,b}$ corrispondente al sottoinsieme $S^{a,b}$ nella filtrazione è espresso come una combinazione lineare con coefficienti interi di tutti i $N$del sottoinsieme precedente. Una volta determinati i coefficienti (usando il calcolo combinatorio della costruzione) per tutti questi passaggi, il problema è risolto.

Trovare i coefficienti. Partiamo da quello che stiamo cercando:$$ N_{(1,1)}^{3,3} = d\,N_{(1,1)}^{3,2} + N_{(2,1)}^{3,2}. $$Gli altri coefficienti sono tutti zero in questo caso. La spiegazione è che una permutazione di$S^{3,3}$ di tipo $(1,1)$ può essere emesso solo da una permutazione di $S^{3,2}$ che è uno dei due tipi $(1,1)$ o di tipo $(2,1)$. Per una permutazione nel primo caso, ci sono esattamente$d=d+4-4$ posizioni (fuori $d+4$) dove $y_3$ può essere inserito (adiacente a nessuno dei due $y_1$ né $y_2$). Nel secondo caso,$y_3$ deve essere inserito tra i due adiacenti $x$'S.

Perseguiamo con le formule per $N_{(1,1)}^{3,2}$ e $N_{(2,1)}^{3,2}$ usando il passaggio da $S^{3,1}$ per $S^{3,2}$nella nostra filtrazione. La formula per$N_{(1,1)}^{3,2}$ è quasi uguale al precedente: $$ 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 formula per $N_{(2,1)}^{3,2}$è più complicato. Si legge$$ 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}. $$ Il coefficiente $d+3-3$ viene dalla seguente osservazione: If a type $(2,1)$ permutazione di $S^{3,2}$ viene emesso da un tipo $(2,1)$ permutazione di $S^{3,1}$, poi $y_2$ ha esattamente $d+3-3$ possibili luoghi da inserire in: $d+3$ è il numero totale di posti e $y_2$ non può occupare né il posto tra gli adiacenti $x$Né nessuno dei due luoghi adiacenti $y_1$.

Osservando le ultime due formule, notiamo che d'ora in poi abbiamo bisogno di tutti i file $N$Corrisponde ai restanti sottoinsiemi della filtrazione. Ma sono meno e le formule sono più facili da capire. Otteniamo successivamente:

per $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} $$
per $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}. $$

I calcoli Ora, per ottenere$N_{(1,1)}^{3,3}$ è sufficiente tornare indietro iniziando con $N_{(1,1)}^{1,1}=d!$. Eseguiamo i calcoli sottolineando il loro carattere algoritmico. Spero che la notazione di seguito sia autoesplicativa.