ところで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 件のコメント:
コメントを投稿