【正文】 0 。 定理 2 設(shè) ? ?0,ba 與 ? ?nbna ,? 為平面上可連折線的兩點(diǎn)，則 ? ? ?0,ba 到 ? ?nbna ,? 的折線條數(shù)等于 ????????kn，式中 ? ?nbbkn ??? 021； ? 0,0 ?nbb 時(shí)， ? ?0,ba 到 ? ?nbna ,? 的與 x軸相交的折線條數(shù)等于 ????????39。kn，也等于 ? ?0, ba? 到? ?nbna ,? 的折線條數(shù)，其中 ? ?nbbk n ??? 039。 21 ； ? 0bbn? 時(shí)， ? ?0,ba 到 ? ?0,bna? 的與 nby? 僅在終點(diǎn)相交的折線條數(shù) ???????? ?????????? ?? knkn 111，也等于 ? ?0,ba 到 ? ?nbna ,? 的與 0by? 僅在始點(diǎn)相交的折線數(shù)，其中 ? ?nbbkn ??? 021。 證明 ? 由定理 1的證明易得，每條這樣的折線是由 k個(gè) 1與 nk個(gè) 1的線形排列所決定的，所以折線共有 ????????kn條。 ? 如圖所示，實(shí)線所示為一條 ? ?0,ba 到 ? ?nbna ,? 的與 x軸相交的折線。設(shè)其與 x軸的最左方交點(diǎn)為 ? ?0,c 。將 ? ?0,ba 到 ? ?0,c 的折線關(guān)于 x 軸的對(duì)稱(chēng)折線以虛線畫(huà)出，這樣就有了折線 ? ? ? ? ? ?nbnacba ,0, 0 ??? 與折線 ? ? ? ? ?nbnaca ,0, 0 ???? 的全部折線間的一一對(duì)應(yīng)。進(jìn)而，由 ?即可得知折線條數(shù)。 ? 如圖所示，實(shí)線所示為一條 ? ?0,baM 到 ? ?nbnaN ,? 的與 nby? 僅交于 N點(diǎn)的折線。以MN 中心 P點(diǎn)為對(duì)稱(chēng)中心可得到虛線所示的一條 MN 折線，它與 0by? 僅交于點(diǎn) M。這顯然是一種一一對(duì)應(yīng)。所以可以得知，定理所述兩類(lèi)折線條數(shù)相等。下面計(jì)算與 0by? 僅交于 M點(diǎn)的虛線折線 MN 條數(shù)。為此，將 x軸平移到 M點(diǎn)，所述折線既是新坐標(biāo)系中與橫軸僅交于 M點(diǎn)一處（注意，此時(shí) NM, 點(diǎn)坐標(biāo)已經(jīng)變?yōu)?? ?0,a 及 ? ?0, bbna n ?? ），即由? ?1,1?a 到 ? ?0, bbna n ?? 且與橫軸不相交的。根據(jù) ?和 ?的結(jié)論可知所求的折線條數(shù)為全 本 科 畢 業(yè) 論 文 第 19 頁(yè) 共 23 頁(yè) 部條數(shù)減去與橫軸相交的條數(shù) ? ? ? ????????????????????????????112111121100 nbbnnbbnnn。 采用 ? ?nbbkn ??? 021的記號(hào)，即是 ???????? ?????????? ?? knkn 111。 例 有 2n個(gè)人排隊(duì)購(gòu)入場(chǎng)券，每人限購(gòu)一張，票價(jià) 1元。若有 n個(gè)人僅各有 1元人民幣一張，另 n個(gè)人僅各有 2元人民幣一張。售票處開(kāi)始售票時(shí)只有 3張 1 元人民幣。問(wèn)有多少種隊(duì)形排列可使所有的人均順利購(gòu)票（不發(fā)生找不開(kāi)錢(qián)的情況）？ 解 以 ka 記售票處賣(mài)第 k 個(gè)人 的票時(shí) 1 元人民幣的收支情況。若第 k 個(gè)人持 1 元款，則1?ka （即售票處收入一張 1 元幣）；若持 2元幣則 1??ka （即售票處支出一張 1元幣）。令 30?a （即未賣(mài)票時(shí)售票處有 3 張 1 元幣），則 ???ki ik ab 0將表示售票處賣(mài)出 k 張 票后尚留有的 1元人民幣的張數(shù)。按照題目的要求，需要對(duì)任意的 nk 2,2,1 ?? 始終有 0?kb 。顯然， 30?b 且 32 ?nb （因?yàn)槿?1或者 1的 ka 值各 1個(gè)）。因?yàn)?kk bb ??1 恒為 1或者 1，所以可考察折線 本 科 畢 業(yè) 論 文 第 20 頁(yè) 共 23 頁(yè) ? ? ? ? ? ? ? ?nbnbbb 2210 ,2,2,1,0 ???? ?。 如果不考慮人與人之間的區(qū)別，僅考慮他們所持有的幣是 1元的還是 2 元的，則問(wèn)題的答案應(yīng)當(dāng)是格點(diǎn) ? ?1,0 到 ? ?3,2n 的不超越 x軸的折線條數(shù)，如圖所 示。 若將 x軸向下平移一個(gè)單位，則它等價(jià)于 ? ?4,0 到 ? ?4,2n 的不與 x軸相交的折現(xiàn)條數(shù)按照定理 2中的 ??，它等于 ? ? ? ? ???????? ???????????????????????????????? 422244212244212nnnnnnnn 。 然而持票人都是有區(qū)別的，對(duì)持 1元幣與持 2元幣的各 n個(gè)人分別進(jìn)行全排列，即知問(wèn)題的最終答案為 ? ? ?????? ???????? ?????????? 422! 2 n nnnn 。 本 科 畢 業(yè) 論 文 第 21 頁(yè) 共 23 頁(yè) 結(jié) 論 組合數(shù)學(xué)已經(jīng)成為了現(xiàn)代數(shù)學(xué)學(xué)科中發(fā)展較快的一個(gè)分支，也是一個(gè)極為重要的分支。本文對(duì)路徑問(wèn)題，母函數(shù)與遞推關(guān)系，容斥原理與排列問(wèn)題以及幾何圖形計(jì)數(shù)問(wèn)題進(jìn)行了簡(jiǎn)單的闡述研究。不利用簡(jiǎn)單實(shí)際的例子來(lái)加深理解。這四種組合方法在解決數(shù)學(xué)問(wèn)題是也比較實(shí)際。本文的重點(diǎn)是在這四種組合方法的應(yīng)用上。 本文在寫(xiě)作方法上采用的是邏輯順序的觀念。先對(duì)需要的組合方法進(jìn)行簡(jiǎn)單的闡述，有了初步的理解之后，再結(jié)合各種實(shí)際例子來(lái)理解組合方法在數(shù)學(xué)中的應(yīng)用。 我對(duì)相關(guān)資料進(jìn)行了大量 的收集，閱讀了不少的文獻(xiàn)，借鑒前人的成果，讓理論與實(shí)際相結(jié)合。但是畢竟學(xué)習(xí)組合方法的時(shí)間還是很短，對(duì)一些重點(diǎn)，精華的部分還是把握不好，請(qǐng)各位老師批評(píng)指正。 本 科 畢 業(yè) 論 文 第 22 頁(yè) 共 23 頁(yè) 致 謝 大學(xué)時(shí)間過(guò)得好快，轉(zhuǎn)眼間就要離開(kāi)這所學(xué)校了，大學(xué)四年，有許多的收獲，也有些缺乏進(jìn)取心的感慨。 談到感謝，首先要感謝河北科技大學(xué)，是科大給了我四年的學(xué)習(xí)機(jī)會(huì)，讓我在這充滿(mǎn)學(xué)習(xí)與浪漫色彩的校園學(xué)會(huì)了許多專(zhuān)業(yè)知識(shí)，學(xué)到了更多的為人處世的方式，使我在各個(gè)方面都有很大的進(jìn)步。感謝未來(lái)的母校 —— 科大。 大學(xué)四年，理學(xué)院老師讓我領(lǐng)略 到更多的數(shù)學(xué)風(fēng)格，數(shù)學(xué)魅力，以及相關(guān)專(zhuān)業(yè)的老師，是你們的教學(xué)使我學(xué)到了很多專(zhuān)業(yè)知識(shí)，為以后的人生道路指明了道路。謝謝各位老師。 本論文是作者在呂侖老師悉心指導(dǎo)下完成的，在相處的幾個(gè)月中，是呂侖老師讓我了解到了組合數(shù)學(xué)的魅力所在，讓我能夠再次感受到數(shù)學(xué)的博大精深。是呂老師在忙碌的教學(xué)工作中抽出時(shí)間為我作指導(dǎo)，給我指出缺點(diǎn)，幫助我改正錯(cuò)誤。呂老師有很深的數(shù)學(xué)造詣，他有著嚴(yán)謹(jǐn)?shù)倪壿嬎季S，深厚的數(shù)學(xué)功底。另外呂老師待人非常隨和，和氣。無(wú)論是學(xué)習(xí)專(zhuān)業(yè)知識(shí)還是做人方面，呂老師都是我學(xué)習(xí)的榜樣。在此，感謝呂老師對(duì)我的學(xué)習(xí) 上的批評(píng)與指導(dǎo)，感謝呂老師在做人方面對(duì)我的良好影響。祝愿呂老師工作順利，在數(shù)學(xué)上有更多的成就。 本 科 畢 業(yè) 論 文 第 23 頁(yè) 共 23 頁(yè) 參考文獻(xiàn) 1 田秋成 ． 組合數(shù)學(xué) ． 北京：電子工業(yè)出版社， 2022 2 王元元，王慶瑞，黃紀(jì)麟．組合數(shù)學(xué)理論與解題．上海：上?？茖W(xué)技術(shù)文獻(xiàn)出版社， 1989 3 馬光思．組合數(shù)學(xué)．西安：西安電子科技大學(xué)出版社， 2022 4 盧開(kāi)澄．組合數(shù)學(xué)．北京：清華大學(xué)出版社， 1991 5 孫世新，張先迪 . 組合原理及其應(yīng)用 .北京：國(guó)防工業(yè)出版社， 2022 6 ． Combinatorial Mathematics． Mathematical Association of America, Providence, 1963 7 吳正聲，孫志人．組合數(shù)學(xué)初步．南京師范大學(xué)出版社 , 2022 8 Richard A. Brualdi． Introductory Combinatorics． America, 機(jī)械工業(yè)出版社，2022 9 屈婉玲．組合數(shù)學(xué)．北京大學(xué)出版社， 1989 10 金成梁．小學(xué) 數(shù)學(xué)競(jìng)賽教程．中國(guó)礦業(yè)大學(xué)出版社， 1993 11 孫世新．組合數(shù)學(xué)．成都：電子科技大學(xué)出版社， 2022 12 盧開(kāi)澄，盧明華．組合數(shù)學(xué)．北京：清華大學(xué)出版社， 2022