投票数

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

得票数が違う場合はどうか. 候補者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}.


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