Board logo

標題: 同字不相鄰 [打印本頁]
作者: rudin    時間: 2011-5-4 14:22     標題: 同字不相鄰

AABBBCCCC排列，同字不相鄰的方法數

將「南港愛我，我愛南港」8 個字全取排成一列，其中「南」與「港」兩字不相鄰之排法有＿＿＿種。
(100南港高工，https://math.pro/db/viewthread.php?tid=1143&page=3#pid3874)

114.6.20補充
\(AAAABBBCCC\)排成一列，相同字母不相鄰的排法有多少種？
(113桃園陽明高中，https://math.pro/db/viewthread.php?tid=3853&page=1#pid26025)
作者: weiye    時間: 2011-5-4 14:57

ｎ（任兩C都不相鄰）－ｎ（任兩C都不相鄰且AA相鄰）
　　　　　　　　　－ｎ（任兩C都不相鄰且至少兩B相鄰）
　　　　　　　　　＋ｎ（任兩C都不相鄰且AA相鄰且至少兩B相鄰）

\(\displaystyle=\frac{5!}{2!3!}C^6_4-\frac{4!}{3!}C^5_4-\left(\frac{4!}{2!}C^5_4-\frac{3!}{2!}C^4_4\right)+3!C^4_4\)

\(=79\)


註：1. 以上算式如有疏漏，還請不吝告知。

　　2. 數字這麼小，感覺似乎可以直接列出 AABBB 的所有排列可能性（１０種），再一一討論C要如何插空隙，應該也很快。

　　　另解，先排 AABBB，再將 CCCC 插空隙，

　　　　　　AABBB　→　插入 4個C 的方法有 C(3,1) 種
　　　　　　ABABB　→　插入 4個C 的方法有 C(5,3) 種
　　　　　　ABBAB　→　插入 4個C 的方法有 C(5,3) 種
　　　　　　ABBBA　→　插入 4個C 的方法有 C(4,2) 種
　　　　　　BAABB　→　插入 4個C 的方法有 C(4,2) 種
　　　　　　BABAB　→　插入 4個C 的方法有 C(6,4) 種
　　　　　　BABBA　→　插入 4個C 的方法有 C(5,3) 種
　　　　　　BBAAB　→　插入 4個C 的方法有 C(4,2) 種
　　　　　　BBABA　→　插入 4個C 的方法有 C(5,3) 種
　　　　　　BBBAA　→　插入 4個C 的方法有 C(3,1) 種

　　　　　　共計有 79 種。

　　3.  有網友問 ｎ（任兩C都不相鄰且至少兩B相鄰）為何是 (4!/2!)*C(5,4) - (3!/2!)*C(4,4) 呢？

　　　　A,A,"BB",B ---> 四者排列 (4!/2!)

　　　　再將四個 C 分別插入五個空隙中 ---> (4!/2!)*C(5,4)

　　　　算完之後～會發現 A,A,"BBB" 的情況會多算

　　　　因為 "BB"+B 與 B+"BB" 都是 "BBB"

　　　　所以要扣掉

　　　　A,A,"BBB" ---> 三者排列 (3!/2!)

　　　　再將四個 C 分別插入四個空隙中 ---> (3!/2!)*C(4,4)

類題1：文章已合併h ttps://math.pro/db/thread-1610-1-1.html
類題2： 1. aaaabbbccd十個字母，全取排列，a與b不相鄰的排法有幾種？
　　　　2. aaaabbbccd十個字母，全取排列，同字不相鄰的排法有幾種？
　　　　文章已合併h ttps://math.pro/db/thread-3134-1-1.html
作者: rudin    時間: 2011-5-4 16:23     標題: 回復 2# weiye 的帖子

謝謝weiye的回答
作者: sambulon    時間: 2013-5-17 14:14     標題: 排列組合_同字不相鄰

1. AAABBBCDEF等十個字母，全取排列，同字不相鄰的排法有幾種？
2. AAABBBCCCD等十個字母，全取排列，同字不相鄰的排法有幾種？

謝謝指教!!
作者: weiye    時間: 2013-5-17 17:20     標題: 回復 1# sambulon 的帖子

1. 任排 － 至少兩A相鄰 － 至少兩B相鄰 ＋ 至少兩A相鄰且至少兩B相鄰

　\(\displaystyle =\frac{10!}{3!3!}-C^2_1\left(\frac{9!}{3!}-\frac{8!}{3!}\right)+C^2_2\left(8!-2\cdot 7!+6!\right)\)


2. 任排 － 至少兩A相鄰 － 至少兩B相鄰  － 至少兩C相鄰 ＋ 至少兩A相鄰且至少兩B相鄰  ＋ 至少兩B相鄰且至少兩C相鄰 ＋ 至少兩A相鄰且至少兩C相鄰 － 至少兩A相鄰且至少兩B相鄰且至少兩C相鄰

　\(\displaystyle =\frac{10!}{3!3!3!}-C^3_1 \left(\frac{9!}{3!3!}-\frac{8!}{3!3!}\right)+C^3_2\left(\frac{8!}{3!}-2\cdot\frac{7!}{3!}+\frac{6!}{3!}\right)-C^3_3\left(7!-3\cdot 6!+3\cdot 5!-4!\right)\)

註：1. 以上算式如有疏漏，還請不吝告知。

　　2. 相似題：ｉ. 文章已合併h ttps://math.pro/db/thread-1097-1-9.html

　　　　　　　ｉｉ. http://math.pro/db/viewthread.php?tid=1377&page=6#pid16473

　　　　　　　ｉｉｉ. 1. aaaabbbccd十個字母，全取排列，a與b不相鄰的排法有幾種？
　　　　　　　　　　　2. aaaabbbccd十個字母，全取排列，同字不相鄰的排法有幾種？
　　　　　　　　　　　文章已合併h ttps://math.pro/db/thread-3134-1-1.html
作者: peter0210    時間: 2014-5-25 21:35

老師
我想請問第一題為何在扣掉至少兩B相鄰的部份
還要再扣掉3個B相鄰的方法數(也就是老師所寫的8!/3!)
作者: Pacers31    時間: 2014-5-27 17:30     標題: 回復 3# peter0210 的帖子

\(\displaystyle \Big(\frac{9!}{3!}-\frac{8!}{3!}\Big)\)才是至少二B鄰〈也就是有B鄰〉的排法數

也就是先將兩個B綁一起跟其他字母排列，而其中BB,B與B,BB是重複算的排法，也就是多算了一次三個B綁一起的排法，故須扣除

這題也可用以下另解做，縮減不少計算量  〈直接少掉一層排容！〉

首先，將"無A鄰"視為全部排法〈意即，以下所有狀況都是在無A鄰的前提下〉，則：

1. 全 \(-\) 有B鄰

   \(\displaystyle =\frac{7!}{3!}\cdot {C_3^8}-\Big(6!\cdot {C_3^7}-5!\cdot {C_3^6}\Big)=24240\)  

2. 全 \(-\) 有B鄰 \(-\) 有C鄰 \(+\) 有B且有C鄰

   \(\displaystyle =\frac{7!}{3!3!}\cdot {C_3^8}-2\Big(\frac{6!}{3!}\cdot {C_3^7}-\frac{5!}{3!}\cdot {C_3^6}\Big)+\Big(5!\cdot {C_3^6}-2\cdot 4!\cdot {C_3^5}+3!\cdot {C_3^4}\Big)=2184\)

以上皆以計算機確認與Weiye老師答案相同！ 〈發現...原來Weiye老師給的相似題就用此法解了@@〉
作者: Exponential    時間: 2019-5-12 23:17     標題: 排列組合

將\(aaaabbbccd\)這十個字母全取排成一列，求下列各排列數
(1)\(a\)與\(b\)不相鄰，共有　　　種排法。
(2)同字不相鄰，共有　　　種排法。
作者: weiye    時間: 2019-5-13 00:08     標題: 回復 1# Exponential 的帖子

請見
類題1： AABBBCCCC排列，同字不相鄰的方法數
　　　　文章已合併h ttps://math.pro/db/thread-1097-1-9.html

類題2：1. AAABBBCDEF等十個字母，全取排列，同字不相鄰的排法有幾種？
　　　　2. AAABBBCCCD等十個字母，全取排列，同字不相鄰的排法有幾種？
　　　　文章已合併h ttps://math.pro/db/thread-1610-1-1.html
作者: Exponential    時間: 2019-5-13 10:30

請教第一小題作法
作者: weiye    時間: 2019-5-13 12:49     標題: 回復 3# Exponential 的帖子



圖片附件: IMG_20190513_143750.jpg (2019-5-13 14:39, 789.91 KB) / 該附件被下載次數 6336
https://math.pro/db/attachment.php?aid=5053&k=da687afbeb0735956bcf5f15c387760c&t=1769618406

作者: Exponential    時間: 2019-5-13 13:48

小弟我在模仿瑋岳老師的作法作第二小題時，算到至少有2個a和2個b相鄰時不知道如何計算，煩請老師指點
作者: weiye    時間: 2019-5-13 14:19     標題: 回復 5# Exponential 的帖子



圖片附件: IMG_20190513_141812.jpg (2019-5-13 14:33, 865.41 KB) / 該附件被下載次數 6283
https://math.pro/db/attachment.php?aid=5056&k=89b247077d1a07e2707f1b25895428e3&t=1769618406

作者: satsuki931000    時間: 2019-5-13 14:24     標題: 回復 5# Exponential 的帖子

把A都分離開來下去做

有錯還請指教
\(\displaystyle \frac{6!}{3!2!}\times\textrm{C} _{4}^{7}\)-\((\frac{5!}{2!}\times\textrm{C} _{4}^{6}-\frac{4!}{2!}\times\textrm{C} _{4}^{5})\)-\((\frac{5!}{3!}\times\textrm{C} _{4}^{6})\)+\((4!\times\textrm{C} _{4}^{5}-3!\times\textrm{C} _{4}^{4})\)

瑋岳老師已經先早一步回覆了XD
作者: satsuki931000    時間: 2019-5-13 14:32     標題: 回復 4# weiye 的帖子

想問瑋岳老師
在A兩區 B一區的部分 C(4，2)是A先選兩區 這樣B應該剩下2可以選才對 為何是C(3，1)
作者: weiye    時間: 2019-5-13 14:35     標題: 回復 8# satsuki931000 的帖子

筆誤，等等來修正。感謝您。 ^___^



歡迎光臨 Math Pro 數學補給站 (https://math.pro/db/) 論壇程式使用 Discuz! 6.1.0