จำนวนการเรียงสับเปลี่ยนของ $D,D,D,O,O,O,G,G,G$ เช่นนั้นไม่มีสอง $D$ อยู่ติดกันและไม่มีสอง $G$ อยู่ติดกัน
ฉันมีปัญหาดังต่อไปนี้ ฉันแก้ไขแล้ว แต่ฉันไม่พอใจกับวิธีแก้ปัญหาของฉัน ฉันหวังว่าจะได้วิธีแก้ปัญหาที่เนียนกว่านี้และอาจมีใครช่วยได้บ้าง มีวิธีแก้ปัญหานี้ด้วยวิธีดาว / แท่งหรือไม่?
คำนวณจำนวนวิธีในการอนุญาตตัวอักษรทั้งหมดจาก $D,D,D,O,O,O,G,G,G$ เช่นนั้นไม่มีสอง $D$ อยู่ติดกันและไม่มีสอง $G$ อยู่ติดกัน
ความพยายามของฉัน
สำหรับ $k=2,3$, ปล่อย $\Delta_k$ แสดงถึงชุดของการเรียงสับเปลี่ยน st เท่านั้น $k$ ของ $D$ อยู่ติดกันและปล่อยให้ $\Gamma_k$ แสดงถึงชุดของการเรียงสับเปลี่ยน st เท่านั้น $k$ ของ $G$อยู่ติดกัน ปล่อย$U$ เป็นชุดของการเรียงสับเปลี่ยนทั้งหมดโดยไม่มีเงื่อนไขใด ๆ
แล้ว $$|U|=\frac{(3+3+3)!}{3!3!3!}=1680.$$ เรามี $$|\Delta_3|=\frac{(1+3+3)!}{1!3!3!}=140$$ (เช่น $\Delta_3$ คือชุดของการเรียงสับเปลี่ยนของ $DDD,O,O,O,G,G,G$) และ $$|\Delta_2|+2|\Delta_3|=\frac{(1+1+3+3)!}{1!1!3!3!}=1120$$ เนื่องจากตัวเลขนี้นับการเรียงสับเปลี่ยนของ $DD,D,O,O,O,G,G,G$. ดังนั้น$$|\Delta_2|=1120-2(140)=840.$$ ในทำนองเดียวกัน $|\Gamma_3|=140$ และ $|\Gamma_2|=840$.
เราต้องการค้นหา $|\Delta_i\cap\Gamma_j|$. ตั้งแต่$\Delta_3\cap\Gamma_3$ คือชุดของการเรียงสับเปลี่ยนของ $DDD,O,O,O,GGG$, $$|\Delta_3\cap\Gamma_3|=\frac{(1+3+1)!}{1!3!1!}=20.$$ ตั้งแต่ $|\Delta_2\cap\Gamma_3|+2|\Delta_3\cap\Gamma_3|$ นับการเรียงสับเปลี่ยนของ $DD,D,O,O,O,GGG$, เรามี $$|\Delta_2\cap\Gamma_3|+2|\Delta_3\cap\Gamma_3|=\frac{(1+1+3+1)!}{1!1!3!1!}=120$$ ดังนั้น $$|\Delta_2\cap\Gamma_3|=120-2(20)=80.$$ ในทำนองเดียวกัน $|\Delta_3\cap\Gamma_2|=80$.
ตอนนี้เราต้องการค้นหา $|\Delta_2\cap\Gamma_2|$. ตั้งแต่$|\Delta_2\cap\Gamma_2|+2|\Delta_3\cap\Gamma_2|+2|\Delta_2\cap\Gamma_3|+4|\Delta_2\cap\Gamma_3|$ นับจำนวนการเรียงสับเปลี่ยนของ $DD,D,O,O,O,GG,G$, เราได้รับ $$|\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.$$ ดังนั้น $$|\Delta_2\cap\Gamma_2|=840-2(80)-2(80)-4(20)=440.$$
โดยหลักการรวม - ยกเว้นเรามี $$|\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|.$$ ดังนั้น $$|\Delta_2\cup\Delta_3\cup\Gamma_2\cup\Gamma_3|=2(840)+2(140)-(440+80+80+20)=1340.$$ คำถามถามขนาดของ $U\setminus(\Delta_2\cup\Delta_3\cup\Gamma_2\cup\Gamma_3)$, ซึ่งเป็น $$|U|-|\Delta_2\cup\Delta_3\cup\Gamma_2\cup\Gamma_3|=1680-1340=340.$$
คำตอบ
ฉันไม่รู้ว่ามีวิธีที่ไม่ซับซ้อนในการทำเช่นนี้หรือไม่ แต่มันอาจจะง่ายกว่านี้แม้จะใช้วิธีของคุณก็ตาม
การเรียงลำดับของ "DD DGGGOO O" ครอบคลุมทุกกรณีของ D ที่อยู่ติดกันและ G ที่อยู่ติดกันยกเว้นที่ของ G อยู่ติดกัน แต่ D ไม่ใช่
$i)$ ลำดับของ "DD DGGGOO O" $= \dfrac{8!}{3!3!} - \dfrac{7!}{3!3!} = 980$
[ การลบคือการดูแล DD D และ D DD ที่อยู่ติดกันถือว่าแตกต่างกัน ดังนั้นการเรียงสับเปลี่ยน DDD จึงถูกนับสองครั้งและต้องนำออกหนึ่งครั้ง ]
$ $
$ii)$ ลำดับของ "GG GOO O" และการวาง $3$ D อยู่ใน $3$ ของไม่ติดกัน $6$ สถานที่
$$= \dfrac{5!}{3!}.{^6}C_3 - \dfrac{4!}{3!}.{^5}C_3 = 360$$
[ การลบคือการดูแล GG G และ G GG ที่อยู่ติดกันซึ่งถือว่าแตกต่างกัน ดังนั้นการเรียงสับเปลี่ยน GGG และการวาง D ใน$3$ ออกจาก $5$สถานที่ถูกนับสองครั้งและจำเป็นต้องนับหนึ่งครั้ง ]
$ $
ที่ช่วยให้คุณจัดเตรียมที่ต้องการ $= 1680 - 980 - 360 = 340$
ฉันเริ่มต้นด้วยการทำซ้ำและแก้ไขปัญหาเล็กน้อยจากนั้นแก้ปัญหาในรูปแบบใหม่นี้ ข้อความที่ไปสู่ปัญหาเริ่มต้นเป็นเรื่องที่ยอมรับได้
ปัญหา. พิจารณาชุด$S=S(d+4)=\{x_1, x_2, x_3, y_1, y_2, y_3, z_1, \ldots, z_{d-2}\}$. การเปลี่ยนแปลงของ$S$ ถูกเรียก $x,y$- ฟรีที่อยู่ติดกัน (และรุ่นที่ใหม่กว่า$(1,1)$) ถ้าไม่มีสอง $x$และไม่มีสอง $y$อยู่ติดกัน กำหนดจำนวน$x,y$เรียงสับเปลี่ยนฟรีที่อยู่ติดกัน
สังเกตว่าองค์ประกอบต่างๆ $x_1$, $x_2$และ $x_3$ จะถูกมองว่าเป็นองค์ประกอบที่แตกต่างกัน (และเหมือนกันสำหรับไฟล์ $y$ของ).
ข้อความจากปัญหาไปสู่คำถามเริ่มต้นจะได้รับจากสูตรที่ชัดเจน$$ \frac{\text{number of $x, y$-adjacent free permutations of $ส$}} {3!\, 3!\, (d-2)!} $$ ที่เราใช้ $d=3$.
วิธีแก้ปัญหานี้เอนไปสู่การคำนวณพีชคณิตแบบวนซ้ำ (แบบจำลองที่เป็นสามเหลี่ยมของปาสคาล) ในด้านบวกเราอาจพอใจกับสูตรแบบวนซ้ำ (การสรุปทั่วไปการคำนวณตัวเลขอื่น ๆ ที่คล้ายกัน ... ) ในด้านลบจะมีดัชนีบินที่ยุ่งยากในทุกทิศทาง
สัญกรณ์และคำอธิบายของโซลูชัน ปล่อย$S^{a,b}\subset S$ เป็นส่วนย่อย $$ S^{a,b} = \{ x_1,\ldots,x_a, y_1, \ldots, y_b, z_1, \ldots, z_{d-2}\} \subset S $$ ด้วย $1\leq a,b\leq3$. มันมี$d+a+b-2$องค์ประกอบ แสดงโดย$P_{(i,j)}^{a,b}$กับ $i\leq a$ และ $j\leq b$ชุดการเรียงสับเปลี่ยนของ $S^{a,b}$ ตรงกับ $i$ ที่อยู่ติดกัน $x$และ $j$ ที่อยู่ติดกัน $y$เรียกว่าการเรียงสับเปลี่ยนประเภท $(i,j)$. ชัดเจนชุดของการเรียงสับเปลี่ยนทั้งหมดของ$S^{a,b}$ คือ $$ \bigcup_{\substack{1\leq i\leq a\\1\leq j\leq b}} P_{(i,j)}^{a,b}. $$ เราต้องการคำนวณ $N_{(1,1)}^{3,3}$พระคาร์ดินัลของ $P_{(1,1)}^{3,3}$. แนวคิดคือทำการคำนวณซ้ำโดยใช้การกรองต่อไปนี้ของ$S^{3,3}$: $$ S^{1,1} \subset S^{2,1} \subset S^{3,1} \subset S^{3,2} \subset S^{3,3}. $$ แต่ละ $N_{(i,j)}^{a,b}$ สอดคล้องกับชุดย่อย $S^{a,b}$ ในการกรองจะแสดงเป็นการรวมเชิงเส้นกับสัมประสิทธิ์จำนวนเต็มของทั้งหมด $N$ของชุดย่อยก่อนหน้านี้ เมื่อกำหนดค่าสัมประสิทธิ์แล้ว (โดยใช้ค่าผสมของโครงสร้าง) สำหรับทางเดินเหล่านี้ปัญหาจะได้รับการแก้ไข
การหาค่าสัมประสิทธิ์ เริ่มจากสิ่งที่เรากำลังมองหา:$$ N_{(1,1)}^{3,3} = d\,N_{(1,1)}^{3,2} + N_{(2,1)}^{3,2}. $$ค่าสัมประสิทธิ์อื่น ๆ เป็นศูนย์ทั้งหมดในกรณีนี้ คำอธิบายก็คือการเปลี่ยนแปลงของ$S^{3,3}$ ประเภท $(1,1)$ สามารถออกได้จากการเรียงสับเปลี่ยนของ $S^{3,2}$ ซึ่งเป็นประเภทใดประเภทหนึ่ง $(1,1)$ หรือประเภท $(2,1)$. สำหรับการเปลี่ยนแปลงในกรณีเดิมมีอยู่อย่างแน่นอน$d=d+4-4$ ตำแหน่ง (จาก $d+4$) ที่ไหน $y_3$ สามารถแทรกได้ (ไม่ติดกับทั้งคู่ $y_1$ หรือ $y_2$). ในกรณีหลังนี้$y_3$ จะต้องแทรกระหว่างทั้งสองที่อยู่ติดกัน $x$ของ
เราติดตามด้วยสูตรสำหรับ $N_{(1,1)}^{3,2}$ และ $N_{(2,1)}^{3,2}$ โดยใช้ข้อความจาก $S^{3,1}$ ถึง $S^{3,2}$ในการกรองของเรา สูตรสำหรับ$N_{(1,1)}^{3,2}$ เกือบจะเหมือนกับก่อนหน้านี้: $$ 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}. $$ สูตรสำหรับ $N_{(2,1)}^{3,2}$ยากกว่า มันอ่าน$$ 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}. $$ ค่าสัมประสิทธิ์ $d+3-3$ มาจากการสังเกตดังต่อไปนี้: ถ้าเป็นประเภท $(2,1)$ การเปลี่ยนแปลงของ $S^{3,2}$ ออกเป็นประเภท $(2,1)$ การเปลี่ยนแปลงของ $S^{3,1}$แล้ว $y_2$ ได้อย่างแน่นอน $d+3-3$ สถานที่ที่เป็นไปได้ที่จะแทรกใน: $d+3$ คือจำนวนสถานที่ทั้งหมดและ $y_2$ ไม่สามารถใช้สถานที่ระหว่างจุดที่อยู่ติดกันได้ $x$หรือสถานที่สองแห่งที่อยู่ติดกัน $y_1$.
เมื่อดูสองสูตรสุดท้ายเราสังเกตว่าจากนี้ไปเราต้องการ $N$สอดคล้องกับส่วนย่อยที่เหลือของการกรอง แต่มีจำนวนน้อยกว่าและหาสูตรได้ง่ายกว่า เราได้รับอย่างต่อเนื่อง:
สำหรับ $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} $$
สำหรับ $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}. $$
การคำนวณตอนนี้เพื่อให้ได้มา$N_{(1,1)}^{3,3}$ ก็เพียงพอแล้วที่จะย้อนกลับไปโดยเริ่มจาก $N_{(1,1)}^{1,1}=d!$. มาทำการคำนวณโดยเน้นอักขระอัลกอริทึม ฉันหวังว่าสัญกรณ์ด้านล่างจะอธิบายตนเองได้
สำหรับ $S^{2,1}$: $$ \begin{array}{c||c|cr} & (1,1) && result/d! \\ \hline (1,1) & d-1 && (d-1) \\ (2,1) & 2 && 2 \end{array} $$
สำหรับ $S^{3,1}$: $$ \begin{array}{c||c|c|cr} & (1,1) & (2,1) && result/d! \\ \hline (1,1) & d-2 & 0 && (d-2)(d-1) \\ (2,1) & 4 & d-1 && 6(d-1) \\ (3,1) & 0 & 3 && 6 \end{array} $$
สำหรับ $S^{3,2}$ (ตารางบางส่วน): $$ \begin{array}{c||c|c|c|cr} & (1,1) & (2,1) & (3,1) && result/d! \\ \hline (1,1) & d+1 & 1 & 0 && (d-1)(d^2-d+4) \\ (2,1) & 0 & d & 2 && 6(d^2-d+2) \end{array} $$
ดังนั้น $$ \begin{split} N_{(1,1)}^{3,3} &= d\,N_{(1,1)}^{3,2} + N_{(2,1)}^{3,2} \\ &= \big( (d^2-d)(d^2-d+4) + 6(d^2-d+2) \big)\,d! \\ &= \big( (d^2-d)^2 + 10(d^2-d) + 12 \big)\,d! \\ &= \big( (d^2-d+4)(d^2-d+6) - 12 \big)\,d!. \end{split} $$
โดยเฉพาะอย่างยิ่งคำตอบสำหรับคำถามเริ่มต้นคือ $$ \frac{(5^2-5+4)(5^2-5+6)-12}{3!\,3!}\,\frac{5!}{3!} = 20\,\frac{2\cdot26-1}{3} = 340. $$