§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 演習

  1. nn元集合の部分集合SSと、SSに含まれない指定要素xxの組を二通りに数え、
∑k=0n−1(n−k)nCk=n2n−1\sum_{k=0}^{n-1}(n-k){}_nC_k=n2^{n-1}

を証明します。 2. 原点から(4,3)(4,3)へ進む最短格子経路を、最後の一歩で分類して Pascal の恒等式を数値で確認します。 3. 7頂点の単純無向グラフで次数が1,2,2,2,4,4,41,2,2,2,4,4,4になることが不可能である理由を説明します。

1ではxxを先に選び、残りのn−1n-1個からSSを選ぶとn2n−1n2^{n-1}通りです。2では7C4=6C3+6C4=20+15=35{}_7C_4={}_6C_3+{}_6C_4=20+15=35です。3では次数の総和が19で奇数ですが、握手補題によれば次数の総和は辺数の2倍なので偶数です。したがって、この次数列をもつ単純無向グラフは存在しません。

前提記事