排列組合+鴿籠原理

[gauss_legend77 10]

1.4個a、2個b、2個c、2個d進行排列，相同字母不得相鄰的排法有幾種？

2.10個人任意排成一列，證明：必有四個人按照高矮順序。

3.假設一個議題有甲，乙，丙三個方案，10個人採無記名表決，或許會有廢票，問開票解果中，甲的得票數超過總票數的一半情況有幾種?

4.設A，B，C，D，E屬於{1,2,3,4,5}，則使(A-B(B-C)(C-D)(D-E)(E-A)=0的方法有幾種

小弟不材，請各位大大高抬貴手替在下解答:'(:'(:'(:'(:'(:'(

[Auron 10]

1.4個a、2個b、2個c、2個d進行排列，相同字母不得相鄰的排法有幾種？

這好像要討論很多種情形

Re #3 曾阿牛 我是想說要先討論a相鄰的情形，因為(aa,aa)和(aaa,a)是不一樣的情況，

然後再用任意排-相鄰的情形，這樣就能求同字母不相鄰的排法。

這樣應該沒錯吧

2.10個人任意排成一列，證明：必有四個人按照高矮順序。

等高手

3.假設一個議題有甲，乙，丙三個方案，10個人採無記名表決，或許會有廢票，問開票結果中，甲的得票數超過總票數的一半情況有幾種?

總票數是10票嗎???廢票的要算嗎???

如果是10張的話就甲得六張、七張、八張、九張、十張，剩餘的就另外兩個分配

廢票的不算進總票數的話就比較麻煩，不過還是差不多

4.設A，B，C，D，E屬於{1,2,3,4,5}，則使(A-B)(B-C)(C-D)(D-E)(E-A)=0的方法有幾種

任意選-五個全都不相等的

有錯請跟我說一聲

此內容已被編輯, May 21, 2010 ,由 Auron

[曾阿牛 10]

Re #2 Auron　　關於第一題　題目說：相同字母不得相鄰　所以我看不懂你的做法

Re #1 gauss_legend77　　雖然看得懂第二題在問什麼　不過我還是要抱怨一下題目敘述的太簡短

[I'm‧泥〃 11]

我是想說要先討論a相鄰的情形，因為(aa,aa)和(aaa,a)是不一樣的情況，

然後再用任意排-相鄰的情形，這樣就能求同字母不相鄰的排法。

這樣應該沒錯吧

相鄰有 ( aa相鄰 且 另外兩個aa不相鄰 )、( aa相鄰 且 另外兩個aa相鄰 )、( aaa相鄰 )、( aaaa相鄰 )、( bb相鄰 )、( cc相鄰 )、( dd相鄰 )

前三項不可能同時成立所以不用考慮同時出現

其他的話還要扣掉 xx相鄰 且 yy相鄰 的可能 ...

整個算起來其實是相當複雜 = ='

此內容已被編輯, May 21, 2010 ,由 I'm‧泥〃

[black40114 10]

學弟你瘋了 - -

第一題 好複雜= =

只會第三題 因該是H 4 4 = 35種 是麻 = =?

[gauss_legend77 10]

第二題就是說10個高矮不同的人，排成一列，必會有4個人（不一定要相鄰）照高矮順序排。

例如9、1、8、2、7、3、6、4、5、10

第一題可以解釋地清楚一點嘛＠＠小弟才疏學淺

[曾阿牛 10]

Re #6 gauss_legend77 謝謝您對第二題的的解釋　

關於第三題　#2 Auron 大大所問的也是我想問的　您還沒提出說明

至於第一題　這麼多大大都還沒提出答案的數據　我猜主要的原因是算不下去

如果用排容原理的話　計算上會遇到重重困難

題目如果只有兩個 a 的話　用排容原理就好辦事　只可惜不是

看樣子　四個 a 把事情搞砸了　　不過那是對排容原理而言

這四個 a　卻讓"各個擊破法"變得還算有效率

10個字母裡既然有4個 a　那我用 a 在排列裡的位置　來將問題分類

第一型：　＿a＿a＿a＿a　( 也包括 a＿a＿a＿a＿ )　

第二型：　＿a＿a＿a＿a＿　　第三型：　a＿a＿a＿a

底線表示至少要放 a 以外的一個字母　並滿足相同字母不相鄰的要求

結果　第一型有 1152　第二型有 360　第三型有 374　　共 1886

樓主若有答案的話　幫我對一下吧　謝謝

此內容已被編輯, May 22, 2010 ,由 曾阿牛

[actino 10]

第一題排容應該還是可以做

AAABBCDE--->960 這是有正確答案 有興趣的可以試一下自己的方法

想法是"訂報紙"

目標A不相鄰∩B不相鄰∩C不相鄰∩D不相鄰

在A不相鄰的情況下

A不相鄰B不相鄰∩A不相鄰C不相鄰∩A不相鄰D不相鄰 (由四個交集變成三個）

=A不相鄰全部可能 - A不相鄰B相鄰 - A不相鄰C相鄰 - A不相鄰D相鄰 + A不相鄰B相鄰C相鄰 + A不相鄰B相鄰D相鄰 + A不相鄰C相鄰D相鄰 - A不相鄰B相鄰C相鄰D相鄰

第一項

先排bcd 6!/2!/2!/2!* (C7取4 安插a不連)

第二、三、四項

先排bcd 5!/2!/2!* (C6取4 安插a不連) (b連 就把b圈起來兩個當成一個)

同理可做c連 d連

第五、六、七項

先排bcd 4!/2!* (C5取4 安插a不連)

一樣三項相同

最後一項

先排bcd 3!* (C4取4 安插a不連)

這樣算出來是3024

感覺跟樓上差有點多，是不是我算錯了~~~

[曾阿牛 10]

大大的確算錯了　　但做法是正確的　而且比我的做法簡單太多了

用大大的做法　我算出來是 1976　比我的答案多 90

於是　重新用我的做法再算一次　發現當時忽略了第一型之中的一種情況　所以算出來比較少

感謝大大的分享　讓我獲益良多

[howt 10]

大大的確算錯了　　但做法是正確的　而且比我的做法簡單太多了

用大大的做法　我算出來是 1976　比我的答案多 90

於是　重新用我的做法再算一次　發現當時忽略了第一型之中的一種情況　所以算出來比較少

感謝大大的分享　讓我獲益良多

我用遞迴算是1974，事實上答案應該要是6的倍數，因為bcd的個數是對稱的，而其排列置換有6種。

第二題可以用點線圖證明，方法是先證明五個點必有3點遞增或遞減，然後令原題目中的56點連線是正的，由題目的要求可知道15、25、35、45全為負或67、68、69、610全負，如此分析下去即可證明，不過我認為這不是一個好方法。

第三題題意不清，但答案跟前幾樓說的一樣，並不難。

第四題用遞迴可解出答案為 4^5 + 4*(-1)^5 = 1020，一般化後的答案是

(m-1)^n + (m-1)*(-1)^n ，n是排列數，m是集合內有幾個相異元素。

[曾阿牛 10]

:|　呃......　我在 #9 打錯了　應該是 1974　與大大的答案相同

敢問大大的遞迴關係是如何建立的？

[howt 10]

定義F(w,x,y,z)表示題目要求的方法數(顯然w、x、y、z本身的排列不影響F的值)

原題要求F(4,2,2,2)，考慮F(5,2,2,2)與F(4,2,2,2)的關係：

在F(4,2,2,2)中插入一 個a使其對應到F(5,2,2,2)，總共有11個空格，但有8個不能選(與a相鄰)

，因此每個F(4,2,2,2)中的排列可以對應到3個F(5,2,2,2)的排列。

再考慮從F(5,2,2,2)中拿掉一個a，有5種拿法，但必須注意的是若排列中有形如xax這種排

列，則拿掉後不會對應到F(4,2,2,2)，而F(5,2,2,2)中具有bab的排列數為F(4,1,2,2)

(可以想成bab變成一個新的b)

於是有5F(5,2,2,2) - 3F(4,1,2,2) = 3F(4,2,2,2) (就像連連看一樣，一邊的總線數等於另一邊)

依此想法可得到：

(為了省去打字麻煩，

令F(n,2,2,2)=J(n)、F(n,2,2,1)=K(n)、F(n,2,1,1)=L(n)、F(n,1,1,1)=M(n) )

nJ(n) = (8-n)J(n-1)+ 3K(n-1)

nK(n) = (7-n)K(n-1)+ 2L(n-1)

nL(n) = (6-n)L(n-1)+ M(n-1)

nM(n) = (5-n)M(n-1)

值得一提的是n越大F越好算，顯然我們有F(x+y+z+1,x,y,z) = (x+y+z)!/(x!y!z!)

此外 nX(n) = (a-n)X(n-1)的通解為X(a-1)*C(a-1,n)，C是組合數

由以上可得

M(n) = 6C(4,n)

n[M(n)+L(n)] = (6-n)[M(n-1)+L(n-1)] => L(n) = 12C(5,n) - 6C(4,n)

n[M(n)+2L(n)+K(n)] = (7-n)[M(n-1)+2L(n-1)+K(n-1)]

=> K(n) = 30C(6,n)-24C(5,n)+6C(4,n)

n[M(n)+3L(n)+3K(n)+J(n)] = (8-n)[M(n-1)+3L(n-1)+3K(n-1)+J(n-1)]

=> J(n) = 90C(7,n)-90C(6,n)+36C(5,n)-6C(4,n) = 90C(6,n-1)+36C(5,n)-6C(4,n)

J(4) = 90*20 + 36*5 - 6 = 1974

上面是一般化的結果，如果直接算其實也不用搞這麼多，不過這個遞迴關係可以用來推廣到

更高階的部分(譬如說就算b不只兩個，那bab的作用還是等價於一個b)。

此內容已被編輯, June 9, 2010 ,由 howt

[曾阿牛 10]

Re #12 howt　　嗯嗯了解大大的想法了　　雖然細節沒有仔細看

感謝　howt 大大的分享

[howt 10]

2.10個人任意排成一列，證明：必有四個人按照高矮順序。

利用反證法。不妨令十人身高為An且不相等，現在將其任意排成一列：A1、A2....A10

定義Bj為從Aj開始算起的最大遞增數(包含自己)

ex： 10 9 8 7 6 5 4 1 2 3，其中A8=1,B8=3

假設不存在Bj>3，那麼所有的Bn必定只能在(1,2,3)中選取，

由鴿籠原理知存在四數w<x<y<z，使得Bw=Bx=By=Bz，且Aw>Ax>Ay>Az

(若Aw<Ax則表示Bw>Bx，矛盾)，但Aw>Ax>Ay>Az 即表示存在由四數構成的遞減序列。

也就是任意十個數排列必有四數遞增或遞減。