投票数

投票数の続きである. 前回はかっこの配置の話だったので, 左かっこと右かっこの数が同じ場合であった. つまり左は右に追い越されないが, 最後は左と右は同票を得た.

得票数が違う場合はどうか. 候補者Qがq票, 候補者Pがp票とって, Qがずーっと優勢を保って敗けなかったとすると, 下の図のようになろう.



(0,0)から出発し, 斜線を越えることなく点(q,p)までくるコースの数C_pqが知りたい. 図に矢じるしで示すように, (q,p)には(q-1,p)から来る場合と, (q,p-1)から来る場合とがあるから,

C_pq = C_{p q-1} + C_{p-1 q}

である. 境界条件を考えると C_{0 0} = 1, C_{0 q} = 1, C_{p q}(p > q) = 0 だから, 図の格子点に合わせてCの値を書くと

 q   0   1   2   3   4   5
p3               5  14  28
 2           2   5   9  14
 1       1   2   3   4   5
 0   1   1   1   1   1   1

空白の場所は0と思い, 上の図の矢じるしの元に相当する左と下の値を足せばこの表は次々と作れる. 前回のn=3の時の値5は, q=3,p=3のところにある. 1711年にこの三角形に気づいたのは, de Moivreだそうだ. de Moivreの定理というのを, 高校のころ習ったので, 懐かしい名前である.

この表の出来方は, なんとなくPascal 三角形を連想させるが, 果たして関係はあるか. 前回と同じ推論をするなら, (0,0)から(q,p)まで格子点を経由していく全コースは_p+qC_pである. このうち, 例の斜線を越えるものを修正コースに変更するとすれば, 前回は_2nC_n-1 であったのと同様,_p+qC_p-1が, 途中でPの票がQの票を上回る場合である. 従って

C_pq = _p+qC_p - _p+qC_p-1        (1)

となる. Cが2種類あって申し訳ないが, 添字をみればどちらか分かるはず.

ところで2項定理を思い出してみると,

_mC_n = _m-1C_n + _mC_n-1        (2)

とう式があった. これを(1)に適用すれば

C_pq = _p+qC_p - _p+qC_p-1

={unfolding}

(_p+q-1C_p + _p+qC_p-1) - (_p+q-1C_p-1 + _p+qC_p-1-1)

={項の並べ替え (A+B)-(C+D) -> (A-C)+(B-D)}

(_p+q-1C_p - _p+q-1C_p-1) + (_p+qC_p-1 - _p+qC_p-1-1)

={folding}

C_{p q-1} + C_{p-1 q}.


至極当然であった. (こういう式の変形は, 手書きでやっていると思うと大変そうだが, 実はエディタを使っているので, まったく大したことではない)

投票数

延び延びの衆議院選挙のただ中になった. 新聞などによると, 自公が退潮で, 民主が攻勢らしい. 私は治承4年の世の中を連想している. 傲れる平家が都落ちし, 木曾義仲や源義経が京都に向っている.

ところでTAOCPにballot numberの話がでていた. AとBの候補の得票を順に書いていき, 一方が他方を一度も越えない系列の数である. もともとはn対のかっこのならべ方のことで, n=3とすると, 3対の正しいかっこの配置は,

()()(), ()(()), (())(), (()()), ((()))

の5通りしかない. 左から見ていき, 左かっこより右かっこが多くなることはない. つまり, 右かっこの得票が左かっこの得票を越えることがないというので,　ballot numberと関係する. つまりn=3のballot numberは5だ.

一般に_2nC_n - _2nC_n-1である. この式の導き方が面白い.

0, 1, ..., 5から3個のものをとる組合せは, 辞書式順で

((2 1 0) (3 1 0) (3 2 0) (3 2 1) (4 1 0) (4 2 0) (4 2 1)
 (4 3 0) (4 3 1) (4 3 2) (5 1 0) (5 2 0) (5 2 1) (5 3 0)
 (5 3 1) (5 3 2) (5 4 0) (5 4 1) (5 4 2) (5 4 3))

だけある. ちなみにこのリストはTAOCPのアルゴリズム7216-Lをschemeにして

(define c '(0 1 2 6 0)) (define cs '())
(define (loop j c)
  (if (cddr c)
   (if (= (+ (car c) 1) (cadr c))
       (cons j (loop (+ j 1) (cdr c)))
       (cons (+ (car c) 1) (cdr c)))
  '()))
(define (comb)
  (set! cs (cons (cddr (reverse c)) cs))
  (set! c (loop 0 c))
  (if (list-tail c 3) (comb) 'ok))

と定義し, (comb) と起動して (reverse cs)で得た.

この(2 1 0)は左から0,1,2番目に左かっこを, 残りに右かっこをおくということである. 従って ((()))に相当する. (3 1 0)は(()())だ. x,yとも0,1,2,3の格子を書き, (0,0)をStartとし, 左かっこがあれば右へ, 右かっこなら上へ進む. かっこは左右3個ずつだから, 最後は(3,3)のGoalに至る.

この格子で, (0,0)から(3,3)への対角線を上へ越えなければ, 正しいかっこの対応が得られる.

下の図の左でその要領をしめす. 0,1,2,3の4つのコースが描いてある. 0と1は対角線を越えないのでOKだが, 2と3はだめだ. 2は())((), 3は)))(((である.




上へ越えたコースがあれば, 上へ越えた最初の点((0,1)から(2,3)への斜線に遭遇した点)で, それまでのコースの縦横を交換する. 例えば2は横, 縦, 縦と進んだが, これを縦, 横, 横に進んだことにする. 残りの横, 横, 縦はそのまま進む. つまり点(1,2)で, 点(2,1)にいたことにし, 残りを進むので, Goalは(3,3)ではなく(4,2)になる.

次の図は, 20通りのかっこの図のコースを, 上の規則で描いたものである. コースは太線で示す. それぞれの図の下の, 2 1 0のようなのは, 左かっこの位置, その次に 5 4のように書いてあるのは, 修正コースでの縦に移動した位置である. これを見ると0,1,...,5から2個取る組合せはすべて1回ずつ現れている.



最初の式に戻ると, _2nC_nはStartからGoalに至るすべてのコースの数. _2nC_n-1はGoal'に至る修正コースの数であり, その差が正しいかっこの配置の数であったのだ.