推 mover:這提要討論對稱狀況..超麻煩.. XD 02/23 11:46
> -------------------------------------------------------------------------- <
作者: doa2 (邁向高手之路) 看板: tutor
標題: Re: [問題] 重覆珠狀排列
時間: Thu Feb 23 12:36:12 2006
※ 引述《agga (小孩)》之銘言：
: 2個紅珠子, 3個黃珠子, 4個白珠子
: 排成項鍊有幾種可能
: 好像是 9!/ (2!*3!*4!*9*2)=70
: 但不是
: 除了這樣的題目外,
: 還有哪些題目也會產生同樣可能的盲點?
這一題算起來是這樣沒錯..
不過如果題目改成2紅,4黃,6白的話
因為(2,4,6)=2
所以必須再把項鍊拆成兩段討論 每段是1紅2黃3白
12! 6!
(---------- - ---------) / 12 這些是不會對稱的圖形
2!4!6! 1!2!3!
6!
加上 ------- 這些是對稱圖形
1!2!3!6
當然如果最大公因數是4就更麻煩 要討論拆兩段跟拆四段
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 219.84.128.123
推 chitarra:這不是離散數學嗎?....家教會用到? 02/23 14:04
推 doa2:也算排列組合的題目啦 但是高中應該不會教 02/23 15:34
※ 編輯: doa2 來自: 219.84.128.123 (02/23 19:36)
※ 編輯: doa2 來自: 219.84.128.123 (02/23 23:15)
> -------------------------------------------------------------------------- <
作者: agga (小孩) 看板: tutor
標題: Re: [問題] 重覆珠狀排列
時間: Fri Feb 24 11:26:37 2006
※ 引述《doa2 (邁向高手之路)》之銘言：
: ※ 引述《agga (小孩)》之銘言：
: : 2個紅珠子, 3個黃珠子, 4個白珠子
: : 排成項鍊有幾種可能
: : 好像是 9!/ (2!*3!*4!*9*2)=70
: : 但不是
: : 除了這樣的題目外,
: : 還有哪些題目也會產生同樣可能的盲點?
: 這一題算起來是這樣沒錯..
答案是76
因為也有一些是對稱的
共12種, 0.5*(140-12)+12=76
除了用排的, 還能怎算出來呢?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 192.192.12.71
> -------------------------------------------------------------------------- <
作者: moun9 (hi.) 看板: tutor
標題: Re: [問題] 重覆珠狀排列
時間: Fri Feb 24 23:03:20 2006
※ 引述《agga (小孩)》之銘言：
: 2個紅珠子, 3個黃珠子, 4個白珠子
: 排成項鍊有幾種可能
: 好像是 9!/ (2!*3!*4!*9*2)=70
: 但不是
: 除了這樣的題目外,
: 還有哪些題目也會產生同樣可能的盲點?
計算項狀排列必須注意
一. 考慮重複環狀 二. 考慮對稱性(對稱的項狀排列無須除以2,非對稱要除以2)
首先重複環狀必須要利用(直線排列 轉成 環狀排列的方法)
首先重複環狀的算法必須小心,
n個相異物的環狀排列=(n-1)!, 是因為n個相異物直線排列= n! , 經過平移n次後會相同
所以要除以n, 也就是n!/n=(n-1)!
但是當n個不盡相異東西的時候, 就不是這樣了...因為會發現並不是每種直線排列
都必須平移n次才會相同...
舉一個例子..形狀大小都相同之2顆紅珠,2顆白珠做環狀共有幾種情形?
很多人應該都會算 : 4!/4[(2!)(2!)] = 3/2 , 一看就知道有問題
因為2與2的正公因數有 1,2(所以可以分成兩個partition來計算)
1.公因數是2的時候...表示可以把2顆紅珠,2顆白珠分做相同的兩段(每段的排列狀況一樣)
也就是 1紅1白,1紅1白 or 1白1紅,1白1紅
如果是 1紅1白,1紅1白
向右平移一次變成 1白1紅1白1紅(就環狀而言這和1紅1白,1紅1白
一樣)
再右平移一次他就恢復1紅1白,1紅1白
所以其實可以討論第一段1紅1白的直線排列(2!)即可
因為後面那一段的排列跟第一段一樣
但是記得除以2(因為直線排列平移兩次會恢復成原來的狀況)
所以此時方法數是2!/2=1(也就是此時直線排列數除以2等於
環狀排列)
2.公因數是1的時候...表示可以把2顆紅珠,2顆白珠分做一段
也就是2紅2白做任意直線排列,必須扣除第一種狀況的情形
夠除完之後的狀況,會發現必須平移4次才會恢復原來的狀況)
所以[4!/(2!2!) － 2!]/4= 1
所以將兩個case下算出的答案加起來等於1+1=2 -->>>即為所求(環狀排列)ꐊ
這一題因為 2,3,4 公因數只有 1
所以只需要分成一段....
其直線排列= 9!/[(4!)(3!)(2!)] = 1260
因為每種直線排列平移9次之後,會和原先的直線排列一樣
所以其環狀排列= 1260/9 = 140
接下來必須考慮對稱
因為總個是9個, 是奇數, 所以對軸上只有一個
而且對稱軸上一定是黃球(因為黃球是奇數個)
對稱軸兩邊的排列方法必須要一樣, 因為要對稱
所以只需考慮對稱軸一邊即可.
對稱軸兩邊必是1紅2白1黃...其排列數等於4!/2! = 12
所以對稱性的環狀排列數 = 12 = 其項狀排列數
非對稱性環狀的排列數 = 140 - 12 = 128 , 其項狀排列數 = 128/2 = 64
所以答案 64 + 12 = 76 ..
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.113.166.93
推 kissmy116:你會喜歡研究這種題目喔~ 02/26 01:15