出版時(shí)間:2006-11 出版社:電子工業(yè)出版社 作者:田秋成 頁數(shù):247 字?jǐn)?shù):362000
內(nèi)容概要
本書介紹組合計(jì)數(shù)及解決計(jì)數(shù)問題的數(shù)學(xué)工具,如母函數(shù)、容斥原理、鴿籠原理、P’olya定理等,還介紹了組合設(shè)計(jì)、計(jì)算機(jī)編碼理論、組合算法及其復(fù)雜性。該書基礎(chǔ)理論部分講述比較詳細(xì),且突出了算法。書中有大量的示例、習(xí)題,書后附有習(xí)題解答與提示,便于講授、自學(xué)。 本書既可作為計(jì)算機(jī)、數(shù)學(xué)及相關(guān)專業(yè)本、研教材,又可作為計(jì)算機(jī)、數(shù)學(xué)愛好者的自學(xué)用書。
書籍目錄
第1章 基本解題方法與計(jì)數(shù)法則 1.1 組合數(shù)學(xué)簡介與基本解題方法 1.1.1 組合數(shù)學(xué)簡介 1.1.2 基本解題方法 1.2 常用符號(hào)與基本計(jì)數(shù)法則 1.2.1 常用符號(hào) 1.2.2 基本計(jì)數(shù)法則 習(xí)題1第2章 二項(xiàng)式與多項(xiàng)式定理 2.1 二項(xiàng)式定理與楊輝三角形 2.1.1 二項(xiàng)式定理 2.1.2 楊輝三角形 2.2 多項(xiàng)式定理 2.2.1 多項(xiàng)式定理簡介 2.2.2 多項(xiàng)式系數(shù)的性質(zhì) 2.2.3 多項(xiàng)式系數(shù)的計(jì)數(shù)意義 習(xí)題2第3章 排列與組合 3.1 初等排列與組合 3.1.1 排列 3.1.2 組合 3.2 排列與組合恒等式 3.2.1 基本恒等式 3.2.2 組合恒等式 3.2.3 排列恒等式 3.2.4 可重組合恒等式 3.3 網(wǎng)絡(luò)路徑問題 3.4 進(jìn)位制與正整數(shù)的階乘表示法 3.4.1 進(jìn)位制 3.4.2 最優(yōu)進(jìn)制 3.4.3 正整數(shù)的階乘表示法 3.5 排列與組合的生成 3.5.1 排列的生成算法 3.5.2 組合的生成算法 3.6 Wallis公式 3.7 Stirling公式 習(xí)題3第4章 母函數(shù)與遞推關(guān)系 4.1 母函數(shù) 4.1.1 母函數(shù)的定義 4.1.2 母函數(shù)的性質(zhì) 4.2 遞推關(guān)系 4.2.1 Hanoi塔問題 4.2.2 Fibonacci級(jí)數(shù) 4.2.3 遞推關(guān)系的定義 4.2.4 有理分式的分項(xiàng)表示 4.2.5 遞推關(guān)系的解 4.3 普母函數(shù)與遞推關(guān)系 4.3.1 示例 4.3.2 線性常系數(shù)齊次遞推關(guān)系的母函數(shù)解法 4.3.3 線性常系數(shù)非齊次遞推關(guān)系的母函數(shù)解法 4.4 母函數(shù)與排列組合 4.4.1 普母函數(shù)與組合 4.4.2 指母函數(shù)與排列 4.5 指母函數(shù)與錯(cuò)排 4.6 普母函數(shù)與分拆 4.6.1 分拆的定義 4.6.2 有序分拆 4.6.3 Ferrers圖 4.6.4 無序分拆 4.6.5 關(guān)于?p(n)? 4.7 普母函數(shù)與Catalan數(shù) 4.7.1 三角剖分問題 4.7.2 乘法結(jié)合方式問題 4.7.3 Catalan數(shù)的通項(xiàng)公式 4.7.4 Catalan數(shù)的組合意義 4.7.5 Catalan數(shù)的性質(zhì) 4.8 母函數(shù)與Stirling數(shù) 4.8.1 Stirling數(shù)的定義 4.8.2 Stirling數(shù)的遞推關(guān)系 4.8.3 Stirling數(shù)的母函數(shù) 4.8.4 Stirling數(shù)的通項(xiàng)公式 4.8.5 Stirling數(shù)的組合意義 4.8.6 Stirling數(shù)的性質(zhì) 4.9 球盒分配問題 4.10 有限和式 4.10.1 遞推關(guān)系求有限和式 4.10.2 母函數(shù)求有限和式 4.10.3 差分表求有限和式 習(xí)題4第5章 容斥原理 5.1 容斥原理 5.1.1 容斥原理的簡單形式 5.1.2 容斥原理的一般形式 5.1.3 對(duì)稱篩公式 5.2 容斥原理與限位排列 5.3 棋盤多項(xiàng)式與限位排列 5.3.1 棋盤多項(xiàng)式 5.3.2 限位排列 5.4 M?bius函數(shù)與Euler函數(shù) 5.5 M?bius反演 5.6 多重集的圓排列 習(xí)題5第6章 鴿籠原理 6.1 鴿籠原理 6.1.1 鴿籠原理的簡單形式 6.1.2 鴿籠原理的基本形式 6.1.3 鴿籠原理的推廣 6.2 Ramsey理論 6.2.1 Ramsey定理 6.2.2 Ramsey數(shù) 習(xí)題6第7章 幾何圖形計(jì)數(shù) 7.1 簡單圖形計(jì)數(shù) 7.2 子圖形計(jì)數(shù) 7.3 圖形的切割 7.4 折線法 7.5 整點(diǎn)與整邊三角形 習(xí)題7第8章 P′olya定理 8.1 群的基本概念 8.2 置換與置換群 8.2.1 置換 8.2.2 置換群 8.3 輪換與置換的奇偶性 8.3.1 輪換 8.3.2 置換的奇偶性 8.4 Burnside引理 8.4.1 共軛類 8.4.2 置換群的軌道 8.4.3 不變置換類 8.4.4 Burnside引理 8.5 P′olya定理 8.6 母函數(shù)型的P′olya定理 習(xí)題8第9章 組合設(shè)計(jì) 9.1 拉丁方 9.1.1 拉丁方的概念 9.1.2 正交拉丁方 9.2 域 9.2.1 域的概念 9.2.2 Galois域 9.2.3 正交拉丁方的構(gòu)造 9.3 區(qū)組設(shè)計(jì) 9.3.1 區(qū)組設(shè)計(jì) 9.3.2 完全區(qū)組設(shè)計(jì) 9.3.3 均衡不完全區(qū)組設(shè)計(jì) 9.3.4 區(qū)組設(shè)計(jì)的構(gòu)造 9.4 Hadamard矩陣 9.4.1 Hadamard矩陣 9.4.2 Hadamard矩陣的構(gòu)成 9.5 編碼理論簡介 9.5.1 編碼及其分類 9.5.2 線性碼 習(xí)題9第10章 組合算法及其復(fù)雜性 10.1 排序 10.1?1 選擇排序 10.1.2 氣泡浮起排序 10.1.3 分段交換排序 10.1.4 樹型排序 10.1.5 合并排序 10.1.6 FORD_JOHNSON排序 10.2 查找 10.2.1 順序查找 10.2.2 折半查找 10.2.3 分塊查找 10.3 尋求第?k?個(gè)元素 10.4 快速Fourier變換 10.5 組合算法的復(fù)雜性 10.5.1 示例 10.5.2 貪心算法的時(shí)間上界 10.5.3 “倒樹”算法 10.5.4 組合算法的復(fù)雜性問題 習(xí)題10附錄A 習(xí)題答案與提示 習(xí)題1答案 習(xí)題2答案 習(xí)題3答案 習(xí)題4答案 習(xí)題5答案 習(xí)題6答案 習(xí)題7答案 習(xí)題8答案 習(xí)題9答案參考文獻(xiàn)
圖書封面
評(píng)論、評(píng)分、閱讀與下載