1 of 12

8.5�Arrangements with Forbidden Position

財金碩二 312707022 陳瑋嘉

2 of 12

Example 8.15

2

範例 8.15 說的是 Grace 和 Nick 要為了他們的兒子辦婚禮，但是由於親人之間的感情不太好，因此針對某四位親人，他們將會有特殊的座位。

在這個範例中共有四位親人五個桌子，而以下是這些親人的限制：

R1不能坐在 T1 或T2；R2 不能坐在 T2；R3 不能坐在 T3 或 T4；R4 不能坐在 T4 或 T5

若我們用可視化的方式來看，會對於這個題目比較清楚，因此這裡我畫了一張圖幫助大家理解。

如圖，R1T1的這個位置就是指說親屬1不能坐在桌號1；R2T2就是親屬2不能坐在桌號2；而其他棕色的部分就是可以坐的桌號

(這裡額外補充說明一下，無論R1坐在哪個table，那個table就不能再安排座位了。因此這裡說的限制是本身親屬受到的限制，比如說這個Table1 可能有親屬1的前女友，這樣他就不能坐在table 1)

3 of 12

Example 8.15 (cont.)

3

我們可以從表格中發現沒被限制的座位共有13個，而被限制的座位只有7個。因此為了簡化運算，我們可以使用下面的方程式來表達我們要的結果，即：可以坐的位置排列 = 所有排列 – 不能坐的位置排列

接下來我們就用數學表達式來解這個問題，我們的 i 是介於1~4之間，而si就是有幾個人受到限制，S1就是若有一個人受到限制的所有排列。所有的可能性我們用分隔號S表示也可以用S0表示，根據我們所學，所有的可能性就會是5!

(因為R1可以有五個位置選，選完之後R2只剩四個位置，以此類推)

接下來我們考慮S1，S1可以表示成N(c1)也就是第一個人受到限制的排列數+第二個人受到限制的排列數+第三個人受到限制的排列數+第四個人受到限制的排列數。

而第一個人只能坐在T1或T2，剩下的人就有4!的可能，因此N(c1) = 4! + 4!

而第二個人只能坐在T2，剩下的人就有4!的可能，因此N(c2) = 4!

同理，第三、第四個人的可能性就會和第一個人一樣，因此皆為4!+4!

最後將這四個結果加總起來就是s1，也就是7(4!)

4 of 12

Example 8.15 (cont.)

4

我們可以以同樣的方式來看S2(若有兩個人受到限制的話，位置可以怎麼坐)，因此經過觀察與計算，我們可以得出兩個人受到限制的話將會有這六種可能(C4取2)。

接下來我們來看N(c1c2)，這個的意思就是第一個親屬和第二個親屬都受到限制後的位置排列數，那由於第二個人一定要坐在桌號2，因此第一個人只能坐在桌號1，而剩下的兩個人的可能性就只剩下3!

然後我們來看N(c1c3)，這個就比較複雜了，他們的受限制方式可以是(T1,T3), (T1,T4), (T2, T3), (T2, T4)，而剩下的兩個人可能性就只剩下3!，所以答案會是3!+3!+3!+3!

接著我們在看一個範例也就是N(c1,c4)，根據前兩個範例我們可以知道若兩個人的座位是互相影響的，我們就要額外考慮，但若為互不影響的，他們受限的可能可以直接用rule of product來做計算，也就是2*2，而由於剩下來的可能性會是3!，因此我們可以很快速的得到N(c1c4)就會是2*2*(3!)，也就是4*(3!)

剩下的可能性我們也可以用同樣的方式來計算，因此我們就可以得到以下的結論，最後再將所有可能性相加，S2的結果就會是16(3!)

我們可以用同樣的方式來處理S3和S4分別會得到13(2!)和3(1!)

藉由前面的計算，我們可以發現對所有的i來說(以這題來說是0~4)，Si其實都可以用ri*(5-i)!來表示，其中ri就是所有放在陰影位置下也就是受限位置的可能性，以S2來說就是這裡的16

根據前面所說，可以坐的位置排列 = 所有排列 – 不能坐的位置排列

而不能坐的位置又可以用容斥原理得到以下結論，因此我們就能推得我們要計算受限的所有可能排列可以以以下表達式來表示，而已這題的範例來看算出來的答案就會是25。

5 of 12

Example 8.15 (cont.)

5

( )

诶，那我們是不是在8.4節的地方有學到 rook polynomial，那不知道你們有沒有觀察到其實這種題目畫成方格之後是不是也可以視為是 rook polynomial 的一種形式。

以T1R1舉例，是不是親屬1坐在table1，橫列的table他就不能做了，直行其他人也不能坐這個table，是不是就像車子互相不攻擊的問題。

因此我們可以用 rook polynomial 的方式來解這題。那首先就是要先把整個4X5的方格拆成是兩個受限方格，由於這兩個方格互不影響，因此一樣可以用 rule of product 將兩個受限方格的可能性相乘起來。

第一個這種L型的方塊，在 8.4 節的時候有學到，我們可以看成是車子互相不攻擊的問題，若放0個車子(也就是x0次方的係數)我們將定義為1種可能(因為不放車子在棋盤上就只有一種可能)；而若放1個車子，我們則將有三種可能可以放(也就是x1次方的係數)；若放兩個車子，我們則只有一種可能性可以放(也就是x2次方的係數)，因此我們可以將此題目以多項式的方式表現就會變成以下這樣。

而你們有沒有發現這個係數有點熟悉，居然跟我們用數的方式算的結果是一樣的耶！只要將x看成是階乘就好了，比如x0次方就看成是沒有人受限時的排列數也就是5!，x1次方就是一個人受限時的排列數也就是(5-1) = 4!。由此我們更能確定這種題目除了用平常的容斥原理來計算之外，我們也可以用rook polynomial來計算。

6 of 12

Example 8.16

We have a pair of dice; one is red, the other green. We roll these dice six times. What is the probability that we obtain all six values on both the red die and the green die if we know that the ordered pairs (1, 2), (2, 1), (2, 5), (3, 4), (4, 1), (4, 5), and (6, 6) did not occur?

6

	1	2	3	4	5	6
1
2
3
4
5
6

	1	2	3	4	5	6
1
2
4
3
5
6

	1	5	3	4	2	6
1
2
3
4
5
6

7 of 12

Example 8.16 (cont.)

7

	1	5	3	4	2	6
1
2
3
4
5
6

	1	5	3	4	2	6
4
2
3
1
5
6

=

( )

8 of 12

Example 8.16 (cont.)

8

9 of 12

Example 8.16 (cont.)

Then the number of (ordered) sequences of the six rolls of the dice for the event we are interested in is:

9

10 of 12

Example 8.17


1
2
3
4

最後我們在進入到範例8.17，現在有兩個function A和B 分別裡面有 1234和 uvwxyz，現在題目想要找有多少個one to one function 不滿足下面的條件，其中f(1) 不能是mapping 到 u 或v，f(2)不能 mapping 到 w，f(3)不能mapping到w或x，而f(4)不能mapping到x 或y或z。

那什麼是one-to-one function呢？教授在上課的時候有提到，簡單來說就是在A裡面的每個元素都要對應到一個B，而且都是一一對應的。

而這個題目一樣也可以使用chessboard來解題唷！而圖型化起來會像右邊這樣，因此我們可以得出他的方程式r(c, x)會是(1+2𝑥)(1+6𝑥+〖9𝑥〗^2+〖2𝑥〗^3 )=1+ 8𝑥+〖21𝑥〗^2+〖20𝑥〗^3+〖40𝑥〗^4接著在使用前面得到的結論計算題目問的所有可能性，得到的答案會是∑_(𝑖=0)^4▒〖(−1)^𝑖 𝑟_𝑖 (6−𝑖)!/𝟐!〗

=(6!/2!)−8(5!/2!)+21(4!/2!)−20(3!/2!)+4(2!/2!)=76

為什麼這裡要多除2!的原因是因為以這題來看(1, u) 和(u,1) 是一樣的意思，所以要除2!回去唷！

11 of 12

Example 8.17 (cont.)

	7	8
1
2
3
4
5
6
7
8

12 of 12

Thanks!

Do you have any questions?

12