開票一路領先的對射證明

Abstract

本文所討論的是開票一路領先問題。假設有A、B兩位候選人，開票結果A得m票、B得n票，開票過程中A的票數一路領先B的票數，我們將開票過程建立在平面的方格上，由(0,0)開始，A得1票記錄成向量(1,0)，B得1票記錄成向量(0,1)，分解成路徑後，A一路領先的開票方法數，就是對角線下的全部路徑數。但是算式及轉換步驟有點複雜，所以我們希望能建構一種簡單的模型對應來解決這個問題。\n本文找出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). \nHow 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.\nIn 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.