臺灣博碩士論文加值系統

本文主要介紹解決計數問題的兩種基本方法：「排容原理」與「鴿籠原理」。排容原理是以集合的方式，計算滿足某些條件的元素個數，利用非互斥集合彼此交集的情況，來考慮計數時重複計數的問題。我們亦對於數論中的尤拉與映成函數，或是排列組合中錯位排列與非負整數解的問題做介紹，引入排容原理的概念，論證並給出其計算時的一般型式。對於禁位問題的計數，我們提供了棋盤式的表示方法，以簡化計算的繁瑣。我們亦將計數問題中排容原理的形式轉換為機率形式，以提供我們利用排容原理求滿足某些條件之事件的機率。最後給出在數學競賽中應用排容原理的競賽題，說明排容原理以各種巧妙的形式被應用。
鴿籠原理為透過各種形式集合的建立，討論在某些條件下狀況種類的最多或最少個數；或是在給定的條件下，是否能夠滿足其他性質的討論。在鴿籠原理中，鴿子與籠子做適當的選取，其中籠子的形式多為數列或是幾何圖形分割所形成，再利用鴿子較籠子多的想法，來完成某些性質的論述。我們亦對於鴿籠原理在數論中的一個重要應用「Ramsey定理」做介紹，引入完全圖的概念，以多邊形各邊及對角線著色的方式來討論。最後給出在數學競賽中應用鴿籠原理的競賽題，說明鴿籠原理如何被靈活的應用。

In this paper, we will review two fundamental counting methods: inclusionexclusion and pigeonhole principles. The inclusion-exclusion principle considers
the elements of the sets satisfied some conditions, and avoids repeat counting by disjoint sets. We also use the inclusion-exclusion principle to solve the problems of Euler phi function and the number of onto functions in number theory, and derangement and the number of nonnegative integer solutions of equations in combinatorics. We derive the closed-form formula to those problems. For the forbidden positions problems, we use the rook polynomials to simplify the counting process. We also show the form of the inclusion-exclusion principle in probability, and use it to solve some probability problems.
The pigeonhole principle is an easy concept. We can establish some sets and use the pigeonhole principle to discuss the extreme value about the number of
elements. Choose the pigeons and pigeonholes, properly, and solve problems by the concept of the pigeonhole principle. We also introduce the Ramsey theorem which is an important application of the pigeonhole principle. This theorem provides a method to solve problems by complete graph. Finally, we give some contest problems about the inclusion-exclusion and pigeonhole principles to show how those principles are used.

中文摘要 iv
Abstract v
第一章排容原理 1
1.1 前言. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .... 1
1.2 排容原理. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 尤拉函數、映成函數. . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.4 重複集合、整數解. . . . . . . . . . . . . . . . . . . . . . . . ... . . 17
1.5 錯位排列. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.6 棋盤多項式. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.7 相鄰排列. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
1.8 k個限制條件. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
1.9 機率. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ... . . . 37
1.10 競賽題. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
1.11 名辭解釋. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
習題. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
排容原理. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
尤拉函數、映成函數. . . . . . . . . . . . . . . . . . . . . . . . . . . 50
重複集合、整數解. . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
錯位排列. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
棋盤多項式. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
相鄰排列. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
k個限制條件. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
機率. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
競賽題. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
第二章鴿籠原理 55
2.1 前言. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
2.2 鴿籠原理. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
2.3 趣味問題. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
2.4 幾何圖形的應用. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
2.5 Ramsey 定理. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

2.6 競賽題. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
2.7 名辭解釋. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
習題. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
鴿籠原理. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
趣味問題. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
幾何圖形的應用. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
Ramsey 定理. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
競賽題. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
A 簡稱、符號對照表 101
A.1 簡稱. . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . 101
A.2 符號：複數系的集合. . . . . . . . . . . . . . . .. . . . . . . . 101
A.3 符號：集合運算、數論、組合. . . . . . . . . . . .. . . . 102
參考文獻 103
索引 103

Balakrishnan, V.K. (1994). Combinatorics. New York: McGraw-Hill.
Grimaldi, R.P. (2004). Discrete and Combinatorial Mathematics, 5th edition. New York:
Addison Wesley.
Gelca, R. and Andreescu, T. (2007). Putnam and Beyond. New York: Springer.
Ross, S. (2006). A First Course in Probability, 7th edition. New York: Prentice Hall.
Rosen, K.H. (Editor in Chief) (2000). Handbook of Discrete and Combinatorial Mathematics.
New York: CRC.
Sloane, N.J.A. The On-Line Encyclopedia of Integer Sequences. 2009 May 20.
Available from: http://www.research.att.com/∼njas/sequences/
Wikipedia. ”Ramsey’s theorem.”
http://en.wikipedia.org/wiki/Ramsey%27s theorem
單壿、葛軍(1991)，國際數學奧林匹克大陸隊訓練教材。台北：九章出版社。
中國數學奧林匹克委員會、開南大學數學系(2002)，世界數學-奧林匹克-解題大辭典-組合卷。河北: 河北少年兒童出版社。