臺灣博碩士論文加值系統

在本篇論文中，將討論在輸贏皆有限制下的開票問題。兩位候選人X 、Y 的總票數分別為a 和b ，在開票的時候， X 的票數比Y 的票數不能多於p ， Y 的票數比X 的票數不能多於q ，在此限制下可能會有的開票情形會有多少種？換言之，以平面坐標系而言，討論在不經過x + y - (p + 1) = 0 ，也不經過x + y + (q + 1) = 0 的限制下，從原點(0,0) 出發到達目標點(a,b) 的路徑數共有幾種，其中a 、b 、p 、q 皆為正整數，且-q ≦ a - b ≦ p ，我們將利用遞迴關係式與矩陣的對角化找出開票問題在雙限制下開票方法數的一般化公式。

In this paper, we will discuss the ballot problem under double restrictions between two candidates.In a ballot, candidate X scores a votes and candidate Y scores b votes. We want to nd the number of ways for counting the votes throughout which X's votes is never more than Y's by p + 1 and Y's votes is never more than X's by q + 1. In other words, we will count the number of lattice paths from (0,0) to (a,b) without touching x + y - (p + 1) = 0 and x + y + (q + 1) = 0, where a , b , p , q are positive integers, and -q ≦ a - b ≦ p.

摘要 I
Abstract II
誌謝 III
目錄 IV
圖目錄 V
第一章問題與文獻回顧 1
第二章在雙限制下開票問題的關係矩陣對角化 5
第一節特徵多項式 5
第二節特徵值 7
第三節特徵向量 10
第四節特徵向量的反矩陣 12
第三章結論 14
第一節初始狀態 14
第二節研究結果 14
參考文獻 19

G. Blom, L. Holst, and D. Sandell (1994). Problems and Snapshots from the World of Probability. Springer, New York.
T. Watanabe, and S. G. Mohanty(1987). On An Inclusion-Exclusion Formula Based On The Reection Principle. Discrete Mathematics, 64, 281-288.
D. Zeilberger(1983). Andre's Reection Proof Generalized to the Many-Candidate Ballot Problem. Discrete Mathematics, 44, 325-326.
D. Andre(1887). Solution directe du probleme resolu par M. Bertrand. C.R. Acad. Sci. Paris, 105, 436-437.