Jumlah permutasi $D,D,D,O,O,O,G,G,G$ sehingga tidak ada dua $D$ berdekatan dan tidak ada dua $G$ berbatasan

Aug 19 2020

Saya memiliki masalah berikut. Saya sudah menyelesaikannya tetapi saya tidak senang dengan solusi saya. Saya berharap untuk solusi yang lebih apik dan mungkin seseorang dapat membantu. Apakah ada cara untuk mengatasi masalah ini hanya dengan metode bintang / batang?

Hitung jumlah cara untuk mengubah semua huruf $D,D,D,O,O,O,G,G,G$ sehingga tidak ada dua $D$ berdekatan dan tidak ada dua $G$ berbatasan.

Upaya saya.

Untuk $k=2,3$, biarkan $\Delta_k$ menunjukkan himpunan permutasi st saja $k$ dari $D$ berbatasan, dan biarkan $\Gamma_k$ menunjukkan himpunan permutasi st saja $k$ dari $G$berbatasan. Membiarkan$U$ menjadi himpunan semua permutasi tanpa syarat apa pun.

Kemudian $$|U|=\frac{(3+3+3)!}{3!3!3!}=1680.$$ Kita punya $$|\Delta_3|=\frac{(1+3+3)!}{1!3!3!}=140$$ (sebagai $\Delta_3$ adalah himpunan permutasi dari $DDD,O,O,O,G,G,G$), dan $$|\Delta_2|+2|\Delta_3|=\frac{(1+1+3+3)!}{1!1!3!3!}=1120$$ karena jumlah ini menghitung permutasi dari $DD,D,O,O,O,G,G,G$. Karena itu$$|\Delta_2|=1120-2(140)=840.$$ Demikian pula $|\Gamma_3|=140$ dan $|\Gamma_2|=840$.

Kami ingin mencari $|\Delta_i\cap\Gamma_j|$. Sejak$\Delta_3\cap\Gamma_3$ adalah himpunan permutasi dari $DDD,O,O,O,GGG$, $$|\Delta_3\cap\Gamma_3|=\frac{(1+3+1)!}{1!3!1!}=20.$$ Sejak $|\Delta_2\cap\Gamma_3|+2|\Delta_3\cap\Gamma_3|$ menghitung permutasi dari $DD,D,O,O,O,GGG$, kita punya $$|\Delta_2\cap\Gamma_3|+2|\Delta_3\cap\Gamma_3|=\frac{(1+1+3+1)!}{1!1!3!1!}=120$$ begitu $$|\Delta_2\cap\Gamma_3|=120-2(20)=80.$$ Demikian pula $|\Delta_3\cap\Gamma_2|=80$.

Kami sekarang ingin mencari $|\Delta_2\cap\Gamma_2|$. Sejak$|\Delta_2\cap\Gamma_2|+2|\Delta_3\cap\Gamma_2|+2|\Delta_2\cap\Gamma_3|+4|\Delta_2\cap\Gamma_3|$ menghitung jumlah permutasi $DD,D,O,O,O,GG,G$, kita mendapatkan $$|\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.$$ Karenanya $$|\Delta_2\cap\Gamma_2|=840-2(80)-2(80)-4(20)=440.$$

Dengan prinsip inklusi-eksklusi yang kita miliki $$|\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|.$$ Karena itu $$|\Delta_2\cup\Delta_3\cup\Gamma_2\cup\Gamma_3|=2(840)+2(140)-(440+80+80+20)=1340.$$ Pertanyaannya menanyakan tentang ukuran $U\setminus(\Delta_2\cup\Delta_3\cup\Gamma_2\cup\Gamma_3)$, yang mana $$|U|-|\Delta_2\cup\Delta_3\cup\Gamma_2\cup\Gamma_3|=1680-1340=340.$$

Jawaban

4 MathLover Aug 19 2020 at 12:56

Saya tidak tahu apakah ada cara yang lebih licin untuk melakukan ini tetapi ini bisa lebih sederhana, bahkan menggunakan pendekatan Anda.

Permutasi dari "DD DGGGOO O" mencakup semua kasus D yang berdekatan dan G yang berdekatan kecuali jika G berdekatan tetapi D tidak.

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

[ Pengurangannya adalah untuk menjaga DD D dan D DD yang berdekatan dianggap berbeda. Jadi permutasi DDD dihitung dua kali dan perlu dilakukan sekali. ]

$ $

$ii)$ Permutasi dari "GG GOO O" dan penempatan $3$ D masuk $3$ dari non-berdekatan $6$ tempat

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

[ Pengurangannya adalah mengurus GG G yang berdekatan dan G GG dianggap berbeda. Jadi permutasi GGG dan menempatkan D masuk$3$ dari $5$tempat telah dihitung dua kali dan perlu dihitung sekali. ]

$ $

Itu memberi Anda pengaturan yang diinginkan $= 1680 - 980 - 360 = 340$

1 DanielN Aug 20 2020 at 22:27

Saya mulai dengan mengulangi dan memodifikasi masalah sedikit, lalu menyelesaikannya di bawah formulir baru ini; bagian ke masalah awal adalah kanonik.

Masalah. Pertimbangkan set$S=S(d+4)=\{x_1, x_2, x_3, y_1, y_2, y_3, z_1, \ldots, z_{d-2}\}$. Sebuah permutasi dari$S$ disebut $x,y$- bebas berdekatan (dan yang lebih baru$(1,1)$) jika tidak ada dua $x$dan bukan dua $y$berdekatan. Tentukan banyaknya$x,y$- permutasi gratis yang berdekatan.

Perhatikan bahwa elemennya $x_1$, $x_2$, dan $x_3$ dilihat sebagai elemen yang berbeda (dan sama untuk $y$'s).
Bagian dari Masalah ke pertanyaan awal diberikan oleh rumus yang jelas$$ \frac{\text{number of $x, y$-adjacent free permutations of $S$}} {3!\, 3!\, (d-2)!} $$ di mana kami mengambil $d=3$.

Solusinya bergantung pada perhitungan aljabar rekursif (modelnya adalah segitiga Pascal). Sisi positifnya, kita mungkin senang dengan rumus rekursif (generalisasi, perhitungan bilangan serupa lainnya ...). Di sisi negatif, akan ada indeks terbang yang tidak praktis ke segala arah.

Notasi dan deskripsi solusi. Membiarkan$S^{a,b}\subset S$ menjadi bagiannya $$ S^{a,b} = \{ x_1,\ldots,x_a, y_1, \ldots, y_b, z_1, \ldots, z_{d-2}\} \subset S $$ dengan $1\leq a,b\leq3$. Memiliki$d+a+b-2$elemen. Dilambangkan dengan$P_{(i,j)}^{a,b}$, dengan $i\leq a$ dan $j\leq b$, himpunan permutasi $S^{a,b}$ dengan persis $i$ berdekatan $x$dan $j$ berdekatan $y$'s, disebut permutasi tipe $(i,j)$. Jelas himpunan semua permutasi dari$S^{a,b}$ adalah $$ \bigcup_{\substack{1\leq i\leq a\\1\leq j\leq b}} P_{(i,j)}^{a,b}. $$ Kami ingin menghitung $N_{(1,1)}^{3,3}$, Kardinal $P_{(1,1)}^{3,3}$. Idenya adalah melakukan komputasi secara rekursif menggunakan penyaringan berikut ini$S^{3,3}$: $$ S^{1,1} \subset S^{2,1} \subset S^{3,1} \subset S^{3,2} \subset S^{3,3}. $$ Setiap $N_{(i,j)}^{a,b}$ sesuai dengan subset $S^{a,b}$ dalam filtrasi dinyatakan sebagai kombinasi linier dengan koefisien integer dari semua $N$dari subset sebelumnya. Setelah koefisien ditentukan (menggunakan kombinatorik konstruksi) untuk semua bagian ini, masalah terpecahkan.

Menemukan koefisien. Mari kita mulai dengan apa yang kita cari:$$ N_{(1,1)}^{3,3} = d\,N_{(1,1)}^{3,2} + N_{(2,1)}^{3,2}. $$Koefisien lainnya dalam kasus ini semuanya nol. Penjelasannya adalah permutasi dari$S^{3,3}$ tipe $(1,1)$ hanya dapat dikeluarkan dari permutasi $S^{3,2}$ yang salah satu tipe $(1,1)$ atau tipe $(2,1)$. Untuk permutasi dalam kasus sebelumnya, ada persisnya$d=d+4-4$ posisi (dari $d+4$) di mana $y_3$ dapat disisipkan (berdekatan dengan tidak satu pun $y_1$ maupun $y_2$). Dalam kasus terakhir,$y_3$ harus disisipkan di antara dua yang berdekatan $x$'s.

Kami mengejar dengan rumus untuk $N_{(1,1)}^{3,2}$ dan $N_{(2,1)}^{3,2}$ menggunakan bagian dari $S^{3,1}$ untuk $S^{3,2}$dalam filtrasi kami. Rumus untuk$N_{(1,1)}^{3,2}$ hampir sama dengan yang sebelumnya: $$ 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}. $$ Rumus untuk $N_{(2,1)}^{3,2}$lebih rumit. Bunyinya$$ 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}. $$ Koefisien $d+3-3$ datang dari observasi berikut: Jika tipe $(2,1)$ permutasi dari $S^{3,2}$ dikeluarkan bentuk suatu tipe $(2,1)$ permutasi dari $S^{3,1}$, kemudian $y_2$ memiliki persis $d+3-3$ tempat yang memungkinkan untuk dimasukkan: $d+3$ adalah jumlah total tempat dan $y_2$ tidak dapat mengambil tempat di antara yang berdekatan $x$atau salah satu dari dua tempat yang berdekatan $y_1$.

Melihat dua rumus terakhir, kami mencatat bahwa mulai sekarang kami membutuhkan semua $N$sesuai dengan subset penyaringan yang tersisa. Tapi jumlahnya lebih sedikit dan rumusnya lebih mudah dipahami. Kami memperoleh berturut-turut:

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

Perhitungan Sekarang, untuk mendapatkan$N_{(1,1)}^{3,3}$ itu cukup untuk mundur mulai dengan $N_{(1,1)}^{1,1}=d!$. Mari kita lakukan penghitungan dengan menekankan karakter algoritmiknya. Saya harap notasi di bawah ini cukup jelas.