Loading...
|
Please use this identifier to cite or link to this item:
https://nccur.lib.nccu.edu.tw/handle/140.119/60087
|
| Title: | 開票一路領先的對射證明
A bijective proof of leading all the way |
| Authors: | 韓淑惠
Han, Shu-Hui |
| Contributors: | 李陽明
李陽明
Li, Young-Ming
韓淑惠
Han, Shu-Hui |
| Keywords: | 一路領先
對射證明
leading all the way
bijective proof |
| Date: | 2011 |
| Issue Date: | 2013-09-04 15:16:53 (UTC+8) |
| Abstract: | 本文所討論的是開票一路領先問題。假設有A、B兩位候選人，開票結果A得m票、B得n票，開票過程中A的票數一路領先B的票數，我們將開票過程建立在平面的方格上，由(0,0)開始，A得1票記錄成向量(1,0)，B得1票記錄成向量(0,1)，分解成路徑後，A一路領先的開票方法數，就是對角線下的全部路徑數。但是算式及轉換步驟有點複雜，所以我們希望能建構一種簡單的模型對應來解決這個問題。
本文找出A至少一路領先m票的方法數，會對應到m×n的全部路徑走法，最後證明這樣的對應是一對一且映成，並猜想若有多位候選人，其中一人一路領先其他候選人的開票過程，也會有相似的對應方法。
Suppose A and B are candidates for all election. A receives m votes and B receives n votes. If A stays ahead of B as the ballots are counted, we can think of a ballot permutation as a lattice path starting at (0,0), where votes for A are expressed as east (1,0) and votes for B are expressed as north (0,1).
How to calculate the number of paths that A is always in the lead? We just count these paths from (0,0) to (m,n) that are under or touch the diagonal. However, the formula of combinatorial mathematics is not easy to obtain. So we hope to construct a model to resolve this problem.
In this paper, we establish a one-to-one correspondence. The ways of A to receive at least m votes are always ahead the same as counting paths from (0,0) to (m,n). Finally, we find a bijective proof in the ballot problem. If there are many candidates, it will be a similar correspondence of one candidate leading the others. |
| Reference: | [1] Hilton, P. and Pedersen, J., The Ballot Problem and Catalan Numbers, Nieuw Archief voor Wiskunde 8 (1990), pp. 209-216.
[2] Joseph Louis François Bertrand, Solution d`un problème, Comptes Rendus de l`Académie des Sciences (1887), pp. 369.
[3] Marc Renault, Four Proofs of the Ballot Theorem, Mathematics Magazine, Vol.80, No.5 (2007), pp. 345-352.
[4] Weisstein, Eric W., Motzkin Number, From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/MotzkinNumber.html
[5] 楊蘭芬， 一個有關開票的問題， 政治大學應用數學系數學教學碩士在職專班碩士論文(2009)，台北市。
[6] 羅富僑， 一個二項等式的對射證明， 政治大學應用數學系數學教學碩士在職專班碩士論文(2009)，台北市。
[7] 侯宗誠、許德瑋， 由蟲子問題衍生一路領先與Motzkin路徑之對應及推廣， 2010台灣國際科學展覽會優勝作品專輯(2010)， 台北市：國立台灣科學教育館。
[8] 戴久永， 機率名題二則漫談， 數學傳播，第四卷第四期(1980)，頁17-25。 |
| Description: | 碩士
國立政治大學
應用數學系數學教學碩士在職專班
98972001
100 |
| Source URI: | http://thesis.lib.nccu.edu.tw/record/#G0098972001 |
| Data Type: | thesis |
| Appears in Collections: | [應用數學系] 學位論文
|
Files in This Item:
| File |
Size | Format | |
|---|
| 200101.pdf | 6345Kb | Adobe PDF2 | 2150 | View/Open |
|
All items in 政大典藏 are protected by copyright, with all rights reserved.
|
