A path to combinatorics 第６章前半(最初-Ex6.5) 京都大学情報学研究科 通信情報システム専攻 岩間・伊藤研究室 M１　西田　尚平

Ex 6.1 番号のついた３つの箱と５つのボールがある。どの箱にも少なくとも１つのボールが入っているように、ボールを箱に振り分ける振り分け方は何通り存在するか？ １ ２ ３ ２ ５ １ ３ ４ 振り分ける数を固定して、それにどの番号を割り振るかを考えるという数え方もあるが・・・・

S V1 V３ V２ S=振り分け方全体の集合 → 個 Vi=少なくとも箱 i が空の振り分け方の集合 → 個 ViかつVｊである集合 → 振り分け方を集合として考えると・・・・ S V1 S=振り分け方全体の集合 → 個 Vi=少なくとも箱 i が空の振り分け方の集合 V３ V２ → 個 ViかつVｊである集合 → 個

定理 6.1 A1 A３ A２ 任意の 集合族 で以下の式が成立する。これを包除原理という。 任意の 集合族　　　　　　　　　　 で以下の式が成立する。これを包除原理という。 n個の要素の空集合以外の全てのサブセットを取ってきて、その要素数+1回-1を掛けてやればよい A1 A３ A２

定理 6.2 任意の 集合族　　　　　　　　　　 で以下の式が成立する。 A1 証明はSからAのcapを引けばいい A３ A２

定理 6.3 集合に対するある関数 f を以下が成り立つものとする。 するとある集合Aと、和集合がAになる集合族 において以下が成立する。 　　　　　　　　　　 において以下が成立する。 証明は定理６．１の物の絶対値をｆに変更すればいい

Ex 6.2 １１１以下の素数を全部求めて下さい 全ての数が素数かどうか判定するのもいいが・・・ そもそもどんな数が素数では無いのか →　　　 　以下の素数で割り切れる数か１ そんな数を数え上げて１１１から引けばよい 具体的には、２、３、５、７の倍数となっているものを数え上げる

S S=１１１までの自然数集合 １ A２ A３ ２ ３ Ai= i の倍数の自然数集合 ５ ７ A５ A７ が求めたい答え

を１１１以下の i の倍数の集合と定義する 今求めたいのは 包除原理より

→ i の倍数かつ j の倍数で i と j が互いに素 答えは２９個

Ex 6.3 ３＊３のマス目があり、その各マスを赤か青で塗る。各マスが等しい確率でどちらかに塗られたとき、２＊２の赤のみで塗られたブロックができる確率はいくらか

を赤の四角形ができた時 i がその右上端になっているような盤面の集合とする

を赤の四角形ができた時 　　が起きている確率とする

求めたいものは 包除原理より式をcapの式に分解して計算する 計算式はそのままな上資料に書いてある通りなので省略 答えは

Ex 6.4 (3,2,2) (0,0,0) 赤いライン上の点は数式で(150t,324t,175t) と書ける １５０＊３２４＊３７５のブロックをもつジャングルジムがある。その対角線に線を引いた時、その線はいくつの ブロックをまたぐか？ (3,2,2) (0,0,0) 赤いライン上の点は数式で(150t,324t,175t)　と書ける

そもそもラインが通過しているブロックってどんなの 線が通過し終わる時の点は 少なくとも一つの座標が自然数 少なくとも一つの座標が自然数になっている点は赤いラインが通過してるブロック１つに対応する このような点を カウントしていく

　　 を k 座標が整数になっているライン上の点の集合とする　 我々の知りたいのはどれかの点が 整数になっている点集合の数 ←包除原理

ある点でxとyが同時に整数になったとし、そのようなｘ座標最小の点を（a,b）とする、するとその点は150と324をそれらのGCDで割ることで求められる。かつ同時に座標が整数になる点は（ka,kb）と表せる。

先ほどの式に代入すると・・・ 解の768個を得られる

Ex 6.5 どの４点も同一平面上に無い２ｎ個の点　　　　 がある。その点間の区間のうち　　　　　個の区間を選ぶ。するとどんな選び方をしたとしてもそれらの区間によってｎ個以上の三角形が構成されることを示せ。 n=3の時

補題 6.5 証明： n=2の時はすぐにわかる nに関する帰納法、nまでで補題が成立すると仮定すると・・・・ (n+1)の時、 個の区間が どの４点も同一平面上に無い２ｎ個の点 がある。その点間の区間のうち　　　　　個の区間を選ぶ。するとどんな選び方をしたとしてもそれらの区間によって少なくとも１個以上の三角形が構成される。 証明： n=2の時はすぐにわかる nに関する帰納法、nまでで補題が成立すると仮定すると・・・・ (n+1)の時、　　　　　　　　個の区間が 選ばれる。グラフから次数の最も少ない2点とその 点に結ばれている区間を全て取り除く。 取り除かれる辺の数は高々　　　　（　　　　　　　 を(n+1)で割ったもの、つまり平均を超えない） 残った辺は少なくとも　　　　 と2n個の点

Ex 6.5の証明： n=2の時はすぐに検証可能 nに関する帰納法、nまでで補題が成立すると仮定する。今n+1を考えるが、補題6．5より 少なくとも一つの三角形が生成されている その三角形の３点をノード番号１，２，３とする。 →選ばれた枝で i と繋がっているノード集合 かつ　　 →三角形ができる

少なくとも　　　　　　　　　　　　　　　　　　　　　 個 の三角形が存在する。 ここで包除原理より という関係式から・・・

となるときは、点１、２、３できる三角形の数がｎを超える→三角形１，２，３を含めてn+1個の三角形ができて再帰が成立 では問題は　　　　　　　　　　　　　　　　　　　の時

のどれか1つは2n-1を下回る ↑ 平均値以下のものが少なくとも1つ存在 一般性を失わずそうなる組を　　　　 とおく この状態で点１，２とそれにつながっている枝を取り除くとどうなるのか

残っている枝と点の数を考える 点： 2n 個 枝： 仮定より点３以降の点群で既に n 個の三角形ができる →三角形１，２，３を含めて n+1 個の三角形が できる →再帰が成り立って任意のnで問は成立