Quod Erat Demonstrandum

2017/03/17

不排在一起

Filed under: NSS — johnmayhk @ 1:58 下午
Tags:

講兩題。

1. m 男 n 女排 1 行

(a) 若女不排在一起,排列數是?

先放置 m 男,共 m! 種排列。

男旁留一空位放置女,共 (m+1) 空位。

情況 1:n > (m+1),則必有兩女排在一起,故排列數是為零。

情況 2:若 n \le (m+1),則放置女之排列數為 P^{m+1}_n,故總排列數為 m!P^{m+1}_n

(b) 若男不排在一起,排列數是?

先放置 n 女,共 n! 種排列。

女旁留一空位放置男,共 (n+1) 空位。

情況 1:若 m > (n+1),則必有兩男排在一起,故排列數是為零。

情況 2:若 m \le (n+1),則放置男之排列數為 P^{n+1}_m,故總排列數為 n!P^{n+1}_m

2.設有 A,B,C 三個家庭,分別有成員 p,q,r 人。現 (p+q+r) 人排成一行。

(a) 給定:p=2,q=3,r=6

若 A 家庭成員不排在一起,B 家庭成員不排在一起,且 A 和 B 的家庭成員也不排在一起,共有多少排列?

解:

先安排 6 個 C 人排好,共 6! 種排列。

C 人旁留一個空位,共 6+1=7 個空位。

只要 2 個 A 人和 3 個 B 人填於空位,即符合要求。

即把 2+3=5 人排在 7 個空位內,共 P^7_5 種排列。

於是要求的排列數為 6!P^7_5

(一般地,如果 p+q<=r+1,答案為 r!P^{r+1}_{p+q}。)

(b) 給定:p=3,q=4,r=5

若同一家庭成員不排在一起,共有多少排列?

(注:這題較 (a) 難,我有不同方法解;而所謂不同方法解,不過是不同的分情況方式,並非快捷方法,高手見諒。)

先排列字母 A,A,A,B,B,B,B,C,C,C,C,C 以放置各家庭成員在該字母上。

先放置 5 個 C:

_C_C_C_C_C_

再在空位放置 3 個 A。

而 3 可分拆為

3=1+2 即 A+AA 模式
3=1+1+1 即 A+A+A 模式

兩個模式。根據這兩個模式,我們有以下 5 個情況:

A+AA 模式:
(情況 1)AAC_CAC_C_C_ 即 AA 或 A 置於頭尾。
(情況 2)_C_CAC_CAAC_ 即 AA 或 A 也不置於頭尾。

A+A+A 模式:
(情況 3)AC_CAC_C_CA 即 1A 置於頭及 1A 置於尾。
(情況 4)AC_CAC_CAC_ 即只有 1A 置於頭或尾。
(情況 5)_CACAC_CAC_ 即沒有 A 置於頭或尾。

現在數算各情況數目。

(情況 1)AAC_CAC_C_C_ 即只有 AA 置於頭或尾。

留意,不可能出現 AAC_C_C_C_CA,因為只有 4 個 B,而 C 旁有 4 個空位,填 B 後,不足以分隔 AA。於是只可能有諸如以下情況:

AAC_C_CAC_C
AC_C_CAAC_C

於是,AA(或 A)有 2 個放法(頭或尾),餘下的 A(或 AA)有 4 個放法(C 旁 4 空位),而 1B 必放在 AA 間,即

ABAC_C_CAC_C
AC_C_CABAC_C

故還有 3B 必放在餘下 3 個空格。

於是,(情況 1)共 2\times 2\times 4=16 種排法。

(情況 2)_C_CAC_CAAC_ 即 AA 或 A 也不置於頭尾。

在 C 旁 4 空格放 AA, A,共 P^4_2 種排列方式。

1B 必放在 AA 間,1B 必放在 CC 間,例如

_CBCACBCABAC_

餘下的 1B 必放哪?2 空位?不止的,如上圖,其實可放 B 的空格有:

_CBC_A_CBC_ABA_C_

共 6 個。

於是,(情況 2)共 P^4_2\times 6=72 種排法。

(情況 3)AC_CAC_C_CA 即 1A 置於頭及 1A 置於尾。

放置 2 個 A 於頭尾後,餘下的 1A 有 4 空位可放,即 4 個選擇。

1B 必放在 CC 間,例如

ACBCACBCBCA

還有 1B 可放以下空位,

_A_CBC_A_CBCBC_A_

共 6 選擇。

於是,(情況 3)共 4\times 6=24 種排法。

(情況 4)AC_CAC_CAC_ 即只有 1A 置於頭或尾。

1A 置於頭或尾,即 2 個選擇。

餘下 2 個 A 置於 4 空位:

AC_C_C_C_C

C^4_2 種選擇,例如

AC_CACAC_C

用 2 個 B 分隔 C,即

ACBCACACBC

餘下 2 個 B 置於 7 空位:

_A_CBC_A_C_A_CBC_

C^7_2 種選擇。

於是,(情況 4)共 2\times C^4_2\times C^7_2=252 種排法。

(情況 5)_CACAC_CAC_ 即沒有 A 置於頭或尾。

3 個 A 置於 4 個空位,

C_C_C_C_C

C^4_3 種選擇,例如

_CACAC_CAC_

1B 必放在 CC 間,即

_CACACBCAC_

餘下 3 個 B 置於 8 空位:

_C_A_C_A_CBC_A_C_

C^8_3 種選擇。

於是,(情況 5)共 C^4_3\times C^8_3=224 種排法。

即是說,若同一家庭成員不排在一起,共有

(16+72+24+252+224)3!4!5!=588\times3!4!5!=10160640 種排法。

歡迎提供更好解題方法,謝謝!

(習題)

以下是之前測驗不慎擬的一題,有興趣做做:

把以下 10 張牌排 1 行:

\spadesuitA,\spadesuitK,\spadesuitQ,\spadesuitJ,\spadesuit10,

\heartsuitA,\heartsuitK,\heartsuitQ,

\diamondsuitA,\diamondsuitK

要求 \heartsuit 牌和 \diamondsuit 牌不排在一起,(但 \heartsuit 牌和 \heartsuit 牌,\diamondsuit 牌和 \diamondsuit 牌可以排在一起)共多少排法?

(仍未做解答 XD)

廣告

發表迴響 »

仍無迴響。

RSS feed for comments on this post. TrackBack URI

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s

在 WordPress.com 建立免費網站或網誌.

%d 位部落客按了讚: