2009年8月23日日曜日

投票数

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

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

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

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

一般に2nCn - 2nCn-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回ずつ現れている.



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

0 件のコメント: