§B4.20二通りに数える

最終更新

同じ有限集合の要素を異なる方法で数えると、得られた二つの式は等しくなります。各方法について、重複と数え落ちがないことを確認します。

1 指定要素つき部分集合

定理 1.1. 正の整数nnについて、

∑k=0nknCk=n2n−1\sum_{k=0}^{n}k{}_nC_k=n2^{n-1}

が成り立ちます。

証明.nn元集合の部分集合SSと、SSに属する指定要素xxの組(S,x)(S,x)を数えます。∣S∣=k|S|=kごとに数えると左辺です。一方、xxをnn通りから選び、残りのn−1n-1個をSSに入れるかどうか選ぶとn2n−1n2^{n-1}通りです。どちらも同じ組を重複なく数えるので等式が成り立ちます。▨

2 格子経路

定理 2.1 (Pascal の恒等式).r,sr,sを正の整数とすると、

r+sCr=r+s−1Cr−1+r+s−1Cr{}_{r+s}C_r={}_{r+s-1}C_{r-1}+{}_{r+s-1}C_r

が成り立ちます。

証明. 原点から右へrr回、上へss回進む最短格子経路を数えます。全r+sr+s回の移動から右へ進む位置を選ぶと左辺です。最後の一歩が右ならば、その前までに右へr−1r-1回進むのでr+s−1Cr−1{}_{r+s-1}C_{r-1}本です。最後の一歩が上ならば、その前までに右へrr回進むのでr+s−1Cr{}_{r+s-1}C_r本です。二つの場合は排反で全経路を尽くします。▨

3 グラフの次数

定義 3.1 (有限単純無向グラフと次数). 有限集合VVの二要素部分集合を辺とし、その有限集合をEEとした組G=(V,E)G=(V,E)を有限単純無向グラフといいます。VVの要素を頂点といいます。頂点v∈Vv\in Vを含む辺の個数をvvの次数といい、d(v)d(v)と書きます。この定義では、一つの頂点だけを端点とするループと、同じ二頂点を結ぶ複数の辺はありません。

定理 3.2 (握手補題).G=(V,E)G=(V,E)を有限単純無向グラフとします。このとき、

∑v∈Vd(v)=2∣E∣\sum_{v\in V}d(v)=2|E|

が成り立ちます。

証明. 頂点と、その頂点に接続する辺の組(v,e)(v,e)を数えます。頂点vvごとに数えると左辺です。各辺には端点が二つあるので、辺ごとに数えると2∣E∣2|E|です。ループをもたない無向グラフを扱っているため、各辺の端点は二つです。▨

例 3.3. 握手補題の右辺は偶数です。したがって奇数次数の頂点の個数は偶数です。奇数の和が偶数になるには、項数が偶数でなければならないためです。

4 演習

問題 4.1.nnを正の整数とする。nn元集合の部分集合SSと、SSに含まれない指定要素xxの組を二通りに数え、

∑k=0n−1(n−k)nCk=n2n−1\sum_{k=0}^{n-1}(n-k){}_nC_k=n2^{n-1}

を証明せよ。

解答.

nn元集合をUUとし、S⊆US\subseteq Uとx∈U∖Sx\in U\setminus Sの組(S,x)(S,x)の全体を数える。

∣S∣=k|S|=kごとに数える。要素数kkの部分集合SSはnCk{}_nC_k個あり、各SSについてxxはU∖SU\setminus Sのn−kn-k個の要素から選ぶ。k=nk=nのときはxxの選び方がないので、組の個数は∑k=0n−1(n−k)nCk\sum_{k=0}^{n-1}(n-k){}_nC_kである。

次に、xxを先に選ぶ。xxの選び方はnn通りである。SSはU∖{x}U\setminus\{x\}の部分集合であり、残りのn−1n-1個の要素のそれぞれをSSに入れるかどうかを選ぶので、SSの選び方は2n−12^{n-1}通りである。したがって、組の個数はn2n−1n2^{n-1}である。

二つの数え方はどちらも同じ組を重複なく数えているので、二つの式は等しい。▨

問題 4.2. 原点から(4,3)(4,3)へ、右または上へ1ずつ進む最短格子経路を、最後の一歩で分類して数え、定理 2.1を数値で確かめよ。

解答.

最短格子経路は右へ4回、上へ3回進むので、全7回の移動から右へ進む4回の位置を選ぶと7C4=35{}_7C_4=35本ある。最後の一歩が右である経路は、その前に(3,3)(3,3)まで進むので6C3=20{}_6C_3=20本ある。最後の一歩が上である経路は、その前に(4,2)(4,2)まで進むので6C4=15{}_6C_4=15本ある。二つの場合は排反で全経路を尽くすので、

7C4=6C3+6C4=20+15=35{}_7C_4={}_6C_3+{}_6C_4=20+15=35

が成り立つ。この等式は、定理 2.1のr=4r=4、s=3s=3の場合である。▨

問題 4.3. 頂点が7個で、次数が1,2,2,2,4,4,41,2,2,2,4,4,4である有限単純無向グラフが存在しないことを説明せよ。

解答.

次数の総和は1+2+2+2+4+4+4=191+2+2+2+4+4+4=19であり、奇数である。一方、定理 3.2により、有限単純無向グラフの次数の総和は辺の個数の2倍なので偶数である。19は偶数でないので、次数が1,2,2,2,4,4,41,2,2,2,4,4,4である7頂点の有限単純無向グラフは存在しない。▨

前提記事