Permütasyon sayısı $D,D,D,O,O,O,G,G,G$ öyle ki ikisi yok $D$ bitişik ve ikisi yok $G$ bitişik

Aug 19 2020

Aşağıdaki problemim var. Ben zaten çözdüm ama çözümümden memnun değilim. Umarım daha kaygan bir çözüm olur ve belki birileri yardımcı olabilir. Bu sorunu sadece yıldızlar / çubuklar yöntemiyle çözmenin bir yolu var mı?

Tüm harflere izin vermenin yollarının sayısını hesaplayın. $D,D,D,O,O,O,G,G,G$ öyle ki ikisi yok $D$ bitişik ve ikisi yok $G$ bitişiktir.

Benim girişimim.

İçin $k=2,3$, İzin Vermek $\Delta_k$ sadece st permütasyon kümesini gösterir $k$ nın-nin $D$ bitişik ve izin ver $\Gamma_k$ sadece st permütasyon kümesini gösterir $k$ nın-nin $G$bitişiktir. İzin Vermek$U$ herhangi bir koşul olmaksızın tüm permütasyonların kümesi olabilir.

Sonra $$|U|=\frac{(3+3+3)!}{3!3!3!}=1680.$$ Sahibiz $$|\Delta_3|=\frac{(1+3+3)!}{1!3!3!}=140$$ (gibi $\Delta_3$ permütasyon kümesidir $DDD,O,O,O,G,G,G$), ve $$|\Delta_2|+2|\Delta_3|=\frac{(1+1+3+3)!}{1!1!3!3!}=1120$$ çünkü bu sayı permütasyonlarını sayar $DD,D,O,O,O,G,G,G$. Bu nedenle$$|\Delta_2|=1120-2(140)=840.$$ benzer şekilde $|\Gamma_3|=140$ ve $|\Gamma_2|=840$.

Bulmak istiyoruz $|\Delta_i\cap\Gamma_j|$. Dan beri$\Delta_3\cap\Gamma_3$ permütasyon kümesidir $DDD,O,O,O,GGG$, $$|\Delta_3\cap\Gamma_3|=\frac{(1+3+1)!}{1!3!1!}=20.$$ Dan beri $|\Delta_2\cap\Gamma_3|+2|\Delta_3\cap\Gamma_3|$ permütasyonlarını sayar $DD,D,O,O,O,GGG$, sahibiz $$|\Delta_2\cap\Gamma_3|+2|\Delta_3\cap\Gamma_3|=\frac{(1+1+3+1)!}{1!1!3!1!}=120$$ yani $$|\Delta_2\cap\Gamma_3|=120-2(20)=80.$$ benzer şekilde $|\Delta_3\cap\Gamma_2|=80$.

Şimdi bulmak istiyoruz $|\Delta_2\cap\Gamma_2|$. Dan beri$|\Delta_2\cap\Gamma_2|+2|\Delta_3\cap\Gamma_2|+2|\Delta_2\cap\Gamma_3|+4|\Delta_2\cap\Gamma_3|$ permütasyon sayısını sayar $DD,D,O,O,O,GG,G$, anlıyoruz $$|\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.$$ Bu nedenle $$|\Delta_2\cap\Gamma_2|=840-2(80)-2(80)-4(20)=440.$$

Dahil etme-hariç tutma ilkesine göre $$|\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|.$$ Bu nedenle $$|\Delta_2\cup\Delta_3\cup\Gamma_2\cup\Gamma_3|=2(840)+2(140)-(440+80+80+20)=1340.$$ Soru şunun boyutunu sorar: $U\setminus(\Delta_2\cup\Delta_3\cup\Gamma_2\cup\Gamma_3)$, hangisi $$|U|-|\Delta_2\cup\Delta_3\cup\Gamma_2\cup\Gamma_3|=1680-1340=340.$$

Yanıtlar

4 MathLover Aug 19 2020 at 12:56

Bunu yapmanın daha akıllıca bir yolu var mı bilmiyorum ama yaklaşımınızı kullanarak bile daha basit olabilir.

"DD DGGGOO O" permütasyonları, G'lerin bitişik olduğu ancak D'lerin olmadığı durumlar dışında, bitişik D'lerin ve bitişik G'lerin tüm durumlarını kapsar.

$i)$ "DD DGGGOO O" permütasyonları $= \dfrac{8!}{3!3!} - \dfrac{7!}{3!3!} = 980$

[ Çıkarma, bitişik DD D ve D DD farklı kabul edilir. Bu yüzden DDD permütasyonları iki kez sayılır ve bir kez çıkarılması gerekir. ]

$ $

$ii)$ "GG GOO O" nun permütasyonları ve yerleştirme $3$ D'ler $3$ bitişik olmayan $6$ yerler

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

[ Çıkarma, farklı kabul edilen bitişik GG G ve G GG'ye dikkat etmektir. Yani GGG permütasyonları ve D'yi$3$ dışında $5$yerler iki kez sayıldı ve bir kez sayılması gerekiyor. ]

$ $

Bu size istediğiniz düzenlemeleri verir $= 1680 - 980 - 360 = 340$

1 DanielN Aug 20 2020 at 22:27

Sorunu biraz yeniden ifade ederek ve değiştirerek başlıyorum, sonra bu yeni form altında çözüyorum; ilk soruna geçiş kanoniktir.

Sorun. Seti düşünün$S=S(d+4)=\{x_1, x_2, x_3, y_1, y_2, y_3, z_1, \ldots, z_{d-2}\}$. Bir permütasyon$S$ denir $x,y$- bitişik serbest (ve daha sonra tip$(1,1)$) iki değilse $x$iki değil $y$bitişiktir. Sayısını belirle$x,y$- bitişik serbest permütasyonlar.

Unutmayın ki elemanlar $x_1$, $x_2$, ve $x_3$ farklı unsurlar olarak görülüyor (ve aynı $y$'s).
Dan geçiş Problem , ilk soruya bariz formülle verilir$$ \frac{\text{number of $x, y$-adjacent free permutations of $S$}} {3!\, 3!\, (d-2)!} $$ aldığımız $d=3$.

Çözüm, yinelemeli cebirsel hesaplamalara (model Pascal üçgeni) dayanır. Olumlu tarafı, yinelemeli formüllerden (genellemeler, diğer benzer sayıların hesaplamaları ...) memnun olabiliriz. Olumsuz tarafta, her yöne hantal uçuş endeksleri olacaktır.

Çözümün notasyonu ve açıklaması. İzin Vermek$S^{a,b}\subset S$ alt küme ol $$ S^{a,b} = \{ x_1,\ldots,x_a, y_1, \ldots, y_b, z_1, \ldots, z_{d-2}\} \subset S $$ ile $1\leq a,b\leq3$. Var$d+a+b-2$elementler. Gösteren$P_{(i,j)}^{a,b}$, ile $i\leq a$ ve $j\leq b$, permütasyon kümesi $S^{a,b}$ tam olarak $i$ komşu $x$'s ve $j$ komşu $y$tür permütasyonları denir $(i,j)$. Açıkça tüm permütasyonların kümesi$S^{a,b}$ dır-dir $$ \bigcup_{\substack{1\leq i\leq a\\1\leq j\leq b}} P_{(i,j)}^{a,b}. $$ Hesaplamak istiyoruz $N_{(1,1)}^{3,3}$kardinali $P_{(1,1)}^{3,3}$. Buradaki fikir, hesaplamayı aşağıdaki filtrelemeyi kullanarak yinelemeli olarak yapmaktır.$S^{3,3}$: $$ S^{1,1} \subset S^{2,1} \subset S^{3,1} \subset S^{3,2} \subset S^{3,3}. $$ Her biri $N_{(i,j)}^{a,b}$ alt kümeye karşılık gelen $S^{a,b}$ filtrasyonda, tüm tam sayı katsayıları ile doğrusal bir kombinasyon olarak ifade edilir. $N$önceki alt kümeye ait olanlar. Tüm bu geçişler için katsayılar belirlendikten sonra (yapının kombinatorikleri kullanılarak) sorun çözülür.

Katsayıları bulmak. Aradığımız şeyle başlayalım:$$ N_{(1,1)}^{3,3} = d\,N_{(1,1)}^{3,2} + N_{(2,1)}^{3,2}. $$Bu durumda diğer katsayıların hepsi sıfırdır. Açıklama şudur ki bir permütasyon$S^{3,3}$ tip $(1,1)$ sadece bir permütasyondan verilebilir $S^{3,2}$ hangisi tür $(1,1)$ veya türü $(2,1)$. Önceki durumda bir permütasyon için, tam olarak var$d=d+4-4$ pozisyonlar (dışında $d+4$) nerede $y_3$ eklenebilir (hiçbirinin yanına $y_1$ ne de $y_2$). İkinci durumda,$y_3$ iki bitişik arasına yerleştirilmelidir $x$'s.

Formülleri takip ediyoruz $N_{(1,1)}^{3,2}$ ve $N_{(2,1)}^{3,2}$ pasajı kullanarak $S^{3,1}$ -e $S^{3,2}$Filtrasyonumuzda. Formülü$N_{(1,1)}^{3,2}$ neredeyse öncekiyle aynı: $$ 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}. $$ Formülü $N_{(2,1)}^{3,2}$daha yanıltıcıdır. Okur$$ 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}. $$ Katsayı $d+3-3$ aşağıdaki gözlemden gelir: $(2,1)$ permütasyonu $S^{3,2}$ bir türden verilir $(2,1)$ permütasyonu $S^{3,1}$, sonra $y_2$ tam olarak var $d+3-3$ eklenebilecek olası yerler: $d+3$ toplam yer sayısı ve $y_2$ bitişik arasındaki yeri alamaz $x$ne de bitişiğindeki iki yerden herhangi biri $y_1$.

Son iki formüle baktığımızda, bundan sonra tüm $N$filtrasyonun kalan alt kümelerine karşılık gelir. Ancak daha az sayıdadırlar ve formüllerin anlaşılması daha kolaydır. Ardışık olarak şunları elde ederiz:

için $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} $$
için $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}. $$

Hesaplamalar Şimdi, elde etmek için$N_{(1,1)}^{3,3}$ ile başlayarak geriye gitmek yeterlidir $N_{(1,1)}^{1,1}=d!$. Hesaplamaları algoritmik karakterlerini vurgulayarak yapalım. Umarım aşağıdaki notasyon kendini açıklar niteliktedir.