第四冊 第一章 排列組合

(A)計數原理 ：

(1)乘法原理 ：

    如果做某件事要經過k個步驟，

    而第一個步驟有 種方法可做，

    第2個步驟有 種方法可做 ，………

    第k個步驟有 種方法可做：

    則完成這件事的方法共有 ‧ ‧………‧ 種

(2)加法原理：

    設作成一事 E 有 m 種方法，

    作成一事 F 有n種方法，

    若此二事不能同時發生，

    則作E或F二事共有m+n種方法。

(3)排容組合：

    一個整體內含數個群體，

    計數整體之元素個數可由

      (各群體元素個數和)

      —(群體兩兩之共有個數)

      ＋(群體三三共有個數)

      —(四四共有個數)＋………

(B)一般直線排列組合：

(1)不重複排列：

(2)重複排列：

    由 n個不同的事件中，任選出 m 個，

    可以重複選擇，排成一列，

    叫做 n 中取 m 的重複排列。

  它的方法數共有 種

(C)限制位置之排列：

(1)   k人必定相鄰：

先視k為一整體，排定後再排此k人之位置

(2)某些人必不相鄰之排法：

    將這些人叫開，先排其餘，然後把這些人排入間隔

(3)男女相間排法：

    先排男人，再把女人排入間隔（或先排女人，再把男人排入間隔）

(4)某人必須排某位置：

    先把此人排入此位置，其餘n-1人排入其餘n-1位置，共(n-1)!方法。

  例：n人中，甲必須排首之方法共(n-1)

(5)錯列公式：

  1、（n人排成一列，規定甲不排首）之方法為n!-(n-1)!

    （其係數與(a-b)之展開式係數相同）

  2、（n人排成一列，規定甲不排首，乙不排第二）

之方法共n！—2(n-1)！+(n-2)！

（其係數與 之展開式係數相同）

  3、（n人排成一列，規定甲不排首，乙不排第二，丙不排第三位）

之方法共n！—3(m-1)！+3(n-2)！-(n-3)！

(係數與 之展開式係數相同)………依此可繼續類推

(D)環狀排列及翻轉排列：

(1)   環狀排列：

1.      n個元素，取m個環狀排列為

2.      n個元素，全取之環狀排列數為（n-1）！

(2)   項鍊排列：

不同顏色的n顆珠子成一項鍊有

  (環狀數)

(3)   桌行排列：正n邊桌坐法=

(4)   翻轉排列：

立體圖形能自由旋轉並翻轉時用

翻轉排列數=

(E)不儘相異物排列

(1)設有n件物品，含有k種不同種列，其第一類有 件，

    第二類有 件，…，第k類有 件等，則將此 n 件排成一列

  ，共有 種不同之排法

(2)捷徑問題：

    有m條橫街，有n條縱街之走法有

(3)某些元素順序不變，但不一定相鄰之排法：

    中，其中

    之順序前後固定，但不一定相鄰的排法有

(F)組合問題

(1)不可重複之組合：

1.  自n個不同事物，每次取m個為一組，

     每一組稱為一種組合，所有組合的種數稱為組合數，

    以C(n,m) 或 表示。

  2.  之關係：

(2)可重複之組合：

1.  從n種不同的物件中，每種都多於m個，

     每種物件可重複選取，則此種組合，

     稱為 n 中取 m 的重複組合。

     常以 (n,m)或S(n,m) 表示。

2.  H(n,m)之算法：

(G)組合性質：

(1)   設 ，

(2)   巴斯卡定理：

設 則

(3)巴斯卡定理討論：

    例：

     (註)：對應巴斯卡定理，在排列中有如下之性質：

  1. 

  2.

（H）重複排列與重複組合之比較：

  (1)

   (2)1. m種不同東西，取n個排列方法為mn方法

2. m種不同東西，取n個為一組方法為

  H(n,m)=C(n+m-1,m)

   (3) m個相同物給n人之方法數共H(n,m)種。(重複排列)

        m個不同物給n人之方法數共nm種。(重複組合)

   (4)

   (5) 方程式

        1.      非負之整數解有H(n,m)

        2.      正整數解有H(n,m-n) (其中m n)

        (註)：

           則非負整數解為H(n+1,m)種

   (6) 求下列之元素組(x1、x2、……..、xn)之解的個數

      1.     共有H(m,n)組解

      2.     共有C(m,n)組解

      3.    共有 組解

（I）分組、分配、分箱之比較：

(1)    先依某些數量分成 n 堆，然後配給 n 人

(2)    k 堆個數相同，則每k！種應合併為一種，故除以n！

      例：把18種不同物依8，5，5分成三堆共 種方法 

             ，再給三人，共 ×3!種方法。

(3)    分箱問題：

1.      東西相同，箱子相同 算整數分割數

2.      東西相同，箱子不同 重複組合

3.      東西不同，箱子相同 分組問題

4.      東西不同，箱子不同 分配問題

(實例請參閱徐氏數學規劃(四))

（J）有相同元素取部分之排列法：

(1)    先討論各組之異同及組別數

(2)    取各組之排法相加

例：自Mississippi之字母中取三字共有多少排法？

【解】：4個s，4個i，2個p，1個M

1o三同有 種，每種排法 ，共 =2

2o二同一異有 種，每種排法 ，共 =27

3o 三異有 種，每中排法3!，共 ，

   共2+27+24=53種排法。

(1)   二項式定理：

1.

2.

(2)   二項式定理之應用(組合級數公式)

1.     

2.     

3.     

4.     

(3)   多項式定理：

設n、m為任意自然數 為任意數，

則  =

其中