組合數學第一講ppt課件(編輯修改稿)
2025-05-30 01:34 本頁面
【文章內容簡介】 一個 x表示 x方向上的一步，一個字母 y表示 y方向上的一步。 ?則 (0,0)→(m,n) 的每一條路徑可表示為m 個 x與 n個 y的一個有重排列。將每一個有重排列的 x與 y分別編號，可得 m!n!個 m+n元的無重全排列。 第一章 排列與組合 ? 設所求方案數為 P(m+n； m， n) ? 則 P(m+n； m， n)m!n!=(m+n)! ? 故 P(m+n。m,n)= ——— = ( ) =( )=C(m+n,m) (c,d) (a,b) (m+n)! m!n! m+n n m+n m (ca)+(db) ca ? 設 c≥a,d≥b, 則由 (a,b)到 (c,d)的簡單格路數為 |(a,b)(c,d)|=( ) 第一章 排列與組合 ? 例：在上例的基礎上若設 mn，求 (0,1)點到(m,n)點不接觸對角線 x=y的格路的數目 (“ 接觸”包括“穿過” ) ? 從 (0,1)點到 (m,n)點的格路，有的接觸 x=y，有的不接觸。 ? 對每一條接觸 x=y的格路，做 (0,1)點到第一個接觸點部分關于 x=y的對稱格路，這樣得到一條從 (1,0)到 (m,n)的格路。 第一章 排列與組合 ?容易看出從 (0,1)到 (m,n)接觸 x=y的格路與 (1,0)到 (m,n)的格路 (必穿過 x=y)一一對應 y y=x (m,n) O (1,0) x (0,1) . . ?故所求格路數為 ( )－ ( )。 m+n1 m+n1 m m1 第一章 排列與組合 ? 若條件改為可接觸但不可穿過，則限制線要向下或向右移一格，得 x－ y=1， (0,0)關于 x－ y=1的對稱點為 (1,1). 格路也是一種常用模型 m+n m+n m m1 (m+n)! (m+n)! m!n! (m1)!(n+1)! m+n m n+1m n+1 ? 所求格路數為 ( )－ ( ) = ——— － ———— = ——— ( ) y xy=1 (m,n) x (0,0) (1,1) . . . .. 第一章 排列與組合 ?例 CnH2n+2是碳氫化合物 ,隨著 n的不同有下列不同的枝鏈： H | H — C — H | H H | H — C — H | H — C — H | H H | H — C — H | H — C — H | H — C — H | H n=1甲烷 n=2 乙烷 n=3 丙烷 第一章 排列與組合 H | H — C — H | H — C — H | H — C — H | H — C — H | H H | H H — C H | | H — C — C — H | | H — C H | H H n=4 丁烷 n=4異丁烷 這說明對應 CnH2n+2的 枝鏈是有 3n+2個頂點的一棵樹，其中 n個頂點與之關聯的邊數為 4；其它 2n+2個頂點是葉子。對于這樣結構的每一棵樹，就對應有一種特定的化 合物。從而可以通過研究具有上述性質的樹找到不同的碳氫化合物 CnH2n+2. 第一章 排列與組合 ? ? 就是對于給定的字符集，用有效的方法將所有可能的全排列 無重復無遺漏 地枚舉出來。 ?全排列的生成算法有許多種，我們僅介紹其中一種 序數法 第一章 排列與組合 ? 序數法 任一自然數 n都可以唯一確定一個 p進制數 ,反之也然。 papan kmkkk ??? ??0,0類似地，有 )!1()!1)(1()!1](1)1[()!1(!????????????nnnnnnnn第一章 排列與組合 同理 )!2()!2)(2()!1( ?????? nnnn所以 !2!22)!3)(3()!2)(2()!1)(1(!??????????????nnnnnnn即 1!!11??? ???nkkkn第一章 排列與組合 不難證明，從 0到 n!1的任一個整數 m都可唯一地表示為： !1)!2()!1( 121 ?
教學課件相關推薦
鄂ICP備17016276號-1