【正文】 nkS n ???23322133221 )1()1()1(nnknknknknknk?????????33 應用舉例 23323221 332nknknkknkk??????130320332132??????kkkkkk,31,21,6131 2 ??? kkk)312161( 32 nnnhS n ????32312161 nnnSn ???34 應用舉例 例 10個數(shù)字 (0到 9)和 4個四則運算符（ +、 、 、 247。 ）組成的 14個元素。求由其中的 n個元素的排列構(gòu)成一算術(shù)表達式的個數(shù)。 與 an1的關(guān)系 解：設 n個元素的算術(shù)表達式個數(shù)為 an。 10an1 。 與 an2的關(guān)系 40an2 。 21 4010 ?? ?? nnn aaa35 應用舉例 例 n條直線將平面分成多少個域？假定無三線共點，且兩兩相交。 設 n條直線將平面分成 Dn個域，則第 n條直線被其余的 n1條直線分割成 n段。這 n段正好是新增加的 n個域的邊界。 所以： Dn=Dn1+n,D1=2, D0=1 36 應用舉例 例 設有 n條橢圓曲線，兩兩相交于兩點，任意 3條橢圓曲線不相交于一點，試問這樣的 n個橢圓將平面分隔成多少部分？ 一個橢圓將平面分隔成內(nèi)、外兩部分。 an= an1+2(n1), a1=2 37 應用舉例 例 一個圓域，依圓心等分成 n個部分如圖所示，用 k種顏色對這 n個域進行涂色，要求相鄰的域不同色，試問有多少種涂色方案。 設 an表示 n個域的涂色方案數(shù)，分兩種情況來討論。 (1)與 an1的關(guān)系， (k2)an1。 (2)與 an2的關(guān)系， (k1)an2。 21 )1()2( ?? ???? nnn akaka)1(, 21 ??? kkaka38 兩名教師分別對 6名學生進行面試（每位教師各負責一門課）每名學生面試時間固定，試問共有多少種面試的順序？ 解：第一位教師的面試順序有 6!種 第一位教師： a1a2a3a4a5a6 第二位教師： a2a1a4a3a6a5 容斥原理舉例 265)!61...!21!111(!66 ??????D 共有 6! 265 對第一位教師的任何一種面試順序， 第二門課的順序有： *** 39 第 3章 容斥原理與鴿巢原理 De Man定理 1 容斥原理 1 容斥原理舉例 1 棋盤多項式與有限制的排列 2 有禁區(qū)的排列 2 廣義的容斥原理 3 廣義容斥原理的應用 3 第二類 Stirling數(shù)的展開式 1 歐拉函數(shù) ?(n) 1 n對夫妻問題 3 * Mobius反演定理 鴿巢原理 4 鴿巢原理舉例 4 鴿巢原理的推廣 4 * Ramsey數(shù)