A path to combinatorics for undergraduate

Presentation on theme: "A path to combinatorics for undergraduate"— Presentation transcript:

1 A path to combinatorics for undergraduate
照山順一

2 輪講の目的 B4やM1に英語を読むこと、発表スライドの作成に慣れてもらう。組み合わせに関しての感覚を養う。 基本事項
１０：３０～１２：００程度：会議室 一回に２人発表予定。一人一時間弱で。 終わりきらなければ、続きを次週に。 目標としては、７月の第２週に終わる予定。 (計９回：一回に一章で進むと一回分余る)

3 A Path to Combinatorics for Undergraduate
カウンティングの話 基礎的な力がついていくと思います。 高校で習ったような問題もありますが 丁寧に読んでいきましょう。 流れ：具体的な例題を用いて、解法を与えていく 各章に約15程度の例題

4 １章：和と積 ２章：組み合わせ ３章：二項係数 ４章：全単射 ５章：帰納法 ６章：包除原理 ７章：ダブルカウンティング ８章：生成関数

5 ex１：12345678910111213 ……….. 9899100 100文字消した時にできる最大の数は何か？
何けたの数ができるのか？→ =92 できるだけ左に9が来るようにすればよい。 →9以外の数を左からどんどん削る。 Not So Fast, My Friend!!!! ……… …… …394041…495051……… ……… …… …… 消した文字数： 8 + 19 + 19 + 19 + 19 27 84 8 46

6 ときどき間違った解法を記述して、後で訂正をしている。
書いてあることをうのみにせずに確認しながら読む力もつく。 論文にはよく間違いがあったりするもの。 Not So Fast, My Friend!!!!

7 ex２：以下の条件を満たす4人の並び方はいくつあるか？
①父と母は隣同士 ②弟は、父または母の隣 父、母、弟の並び方を考える。 それぞれの並び方に 兄が右か左にくるので、 ２+２+２+２=８通り 父 母 弟 兄 父 母 弟 弟 父 母 母 父 弟 弟 母 父

8 この点から４つを結んで作られる正方形はいくつあるか？
ex３：１０×１０の格子点 この点から４つを結んで作られる正方形はいくつあるか？ 教科書では１０×１０だが、 ６×６の格子で考えてみる。 パターン１： 長さkのもの：(６-k)２ →(n-k)２ パターン２： 各正方形はパターン１の正方形の いずれか一つに内接する 長さkのパターン１の正方形に 内接するパターン２の正方形の数：k－１

9 １章の内容 和を使って数え上げるのか、積を使って数え上げるのか ex２,ex３：和を使用
集合の考え方では：

10 ここから３本選んで三角形はいくつ作れるか？
ex４：長さが１～nの棒が１本ずつ ここから３本選んで三角形はいくつ作れるか？ 合同なものは同一とみなす 三角形の３辺を短いほうから x, y, z とする 基本方針は三角不等式 x+y>z を考える 最長の辺を固定してカウンティング x y z

11 ここから３本選んで三角形はいくつ作れるか？
ex４：長さが１～nの棒が１本ずつ ここから３本選んで三角形はいくつ作れるか？ 合同なものは同一とみなす A(k)：最長辺の長さがkである三角形の個数 x y z kの偶奇で場合分け k=2m x+y>2m と x+y>2xからxとmの大小関係で場合分け ：①xがm以下②xがmより大きい ① y>k-x が満たすべき条件 y： k-x+1 から k-1 までの x-1 通りの数を取りうる ② y>x が満たすべき条件 y： x+1 から k-1 までの k-x-1 通りの数を取りうる

12 ここから３本選んで三角形はいくつ作れるか？
ex４：長さが１～nの棒が１本ずつ ここから３本選んで三角形はいくつ作れるか？ 合同なものは同一とみなす A(k)：最長辺の長さがkである三角形の個数 x y z kの偶奇で場合分け k=2m k=2m+1

13 ex５ Ａ君はロッカーのカギ番号を忘れてしまった。
分かっていることは以下の通り。 ①鍵は３つの数字を順番に正しく入れると開く ②鍵に使われる数字は１から４０まで ③３つのうち、２つは１７と２４であるが順番は分からない 正しい鍵番号として何通り考えられるか？ 1 2 3 １７ ２４ ??

14 1 2 3 ??に入る数は４０通りなので、 ４０×６=２４０ (１７，１７，２４)や(１７,２４,２４)など 同じ数字を二つ含む6パターンを
①鍵は３つの数字を順番に正しく入れると開く ②鍵に使われる数字は１から４０まで ③３つのうち、２つは１７と２４であるが順番は分からない Not So Fast, My Friend!!!! 1 2 3 １７ ２４ ?? ??に入る数は４０通りなので、 ４０×６=２４０ １７ ?? ２４ (１７，１７，２４)や(１７,２４,２４)など 同じ数字を二つ含む6パターンを 二重に数え上げている。 よって正しい答えは２４０-６=２３４ ２４ １７ ?? ２４ ?? １７ ?? １７ ２４ ?? ２４ １７

15 約数は2a・5bの形をしている：約数は全部で1002
ex6 １０９９の約数からランダムに選んだ時、 その数が１０８８の倍数である確率は？ 1099=299・599 約数は2a・5bの形をしている：約数は全部で1002 1088=288・588 a,bともに88以上99以下を満たせばよい：１２２

16 ex7：整数aとbの最小公倍数が２３５７１１１３であるような
それぞれのパターン数を数え上げて、掛け合わせる。 ７通り x、sどちらかを3と固定すると、もう片方の取りうるパターンは(3+1)通り 2×4通り考えられるが(3,3)を二度数えていることに注意して、8-1=7通り (2×(3+1)-1)× (2×(7+1)-1)× (2×(13+1)-1) =(2×3+1)× (2×7+1)× (2×13+1)=7×15×27＝2835通り

17 ex６,ex７より：整数の約数・最小公倍数に関する命題
命題１.１. nの約数の個数： 命題１.２. nを最小公倍数に持つ整数の組の数：

18 ちょっと休憩：連絡 もし発表に時間がかかりそうだったら、メインアイディアを示すなどして適宜省略して下さい。
ただし、何が書いてあるのか理解してからその判断を。 どうしてもわからない点があれば人に聞きましょう。

19 ex8:以下のような条件を満たすナンバープレートがある
①アルファベット３文字の後ろに数字が3つならぶ ②Oと０を同時に使わない 何通りのナンバーができるか？ A X O 4 2 2 S1：０を使わないナンバー S2：Oを使わないナンバー |S1|=２６３×９３ |S2|=２５３×１０３ |S1|と|S2|を足せば答えか？ S3：Oと０ともに使わないナンバー →S1とS2の共通部分 |S3|=２５３×９３ 答：|S1|+|S2|-|S3|＝１７０４７２７９ 集合を足し合わせて重なった部分の二重数え上げを取り除くことを包除原理という。 詳しくは６章で。(１カ月半ほど後で。)

20 答：１＋１８＋２５２＝２７１ ex９：１０００より小さい正の整数の中で １０進表記をした時、１を持つ整数の数は？
S＝{１, ２, ３, , ９９８, ９９９} 集合Sを分割する S1＝{１, ２, ３, , ９} S2＝{１０, １１, １２, , ９８, ９９} S3＝{１００, １０１, １０２, , ９９８, ９９９} 答：１＋１８＋２５２＝２７１ A1：S1で少なくとも１を１つもつ数字の集合 A2：S2で少なくとも１を１つもつ数字の集合 A3：S3で少なくとも１を１つもつ数字の集合 →A1={１} |A1|=１ →|A2|=１８ →|A3|=２５２ ８ １ ９ １ ９９ ７２ ７２ ９ ９ ８

21 答：１０００－７２９＝２７１ ex９：１０００より小さい正の整数の中で １０進表記をした時、１を持つ整数の数は？
S’＝{０, １, ２, ３, , ９９８, ９９９} 集合S’全体から１を含まない数を数え上げて引いたほうが簡単 B：１０００未満で１を含まない非負整数の集合 |B|＝９３＝７２９ 答：１０００－７２９＝２７１

22 少なくとも一つがonとなっている場合の数は？
ex１０：１５個のスイッチがある 少なくとも一つがonとなっている場合の数は？ ２１５－１＝３２７６７ 定理１.３ |S|＝n　なる集合Sが与えられた時、 空集合・S自身も含め２n個の部分集合がある。

23 写像に関して 定理1.4：順列 単射、全射、全単射の定義 n, k を正の整数とし、n≧kとする。
である。

24 ex１１：５チームによる総当たり戦 各試合の勝敗確率は５０% 全勝または全敗するチームが無い確率は？ 試合数は全部で10試合
勝ち負けのパターンは全部で２１０であり、 総当たりの結果のパターンは等しい確率で現れる。 A B C D E 全体から条件に合わないパターン数を引く チームAが全勝したと仮定 残り6試合　：　２６パターン　 あるチームが全勝する　：　５× ２６ あるチームが全敗する　：　５× ２６ 全勝のチームと全敗のチームが 同時に存在する場合を二度数え上げている Aが全勝、Bが全敗：残り２３試合 チームの選び方：５P２=２０通り →２０×２３ よって、パターン数は ２１０－２×５×２６＋２０×２３＝２５×１７ 求めるのは確率： この値を２１０で割って、１７/３２=０．５３２１５

25 ex１２：以下の条件を満たす７文字のアルファベット列の数は？
①同じ文字は現れない ②aとbは隣り合わない solutin teruyam soaknbm nouseba

26 first solution(①を満たす列数から②を満たさないものを引く)
ex１２：以下の条件を満たす７文字のアルファベット列の数は？ ①同じ文字は現れない ②aとbは隣り合わない first solution(①を満たす列数から②を満たさないものを引く) ７文字の並べ方全体から、abが隣り合うものをひく。 全体： 26P7 abの順番で隣り合う列の数を数え上げ。 baの順番で隣り合う列について場合の数は同じ よって求める場合の数は、 26P7 － 2×24P5 ×6 = →　24P5 ×6 o p q r s

27 second solution(分割して足し合わせる)
ex１２：以下の条件を満たす７文字のアルファベット列の数は？ ①同じ文字は現れない ②aとbは隣り合わない second solution(分割して足し合わせる) 以下の４つの場合に分けて数え上げる ①a,bともに含まない： ②aは含み，bは含まない： ２４字から６文字並べ、aを入れる　 ③bは含み，aは含まない： ④a,bともに含むが隣り合わない： ２４字から５文字選び，どこにa,bを埋め込むか？ ２４文字から７文字を並べる　→　24P7 →　24P6 ×７ ②と同様　→　24P6 ×７ →　24P5 ×6×5 o p q r s まず、aを6か所から選び、 bを残り5か所から選ぶ。

28 つまり１９Y1Y2年M1M2月D1D2日を[D1D2M1M2Y1Y2]と書く。 D1＋M1＋Y1＝8 かつ D2＋M2＋Y2＝１９を満たし、
ex１３：１９７２年８月１９日を以下のように書くとする [１９０８７２] つまり１９Y1Y2年M1M2月D1D2日を[D1D2M1M2Y1Y2]と書く。 D1＋M1＋Y1＝8　かつ　D2＋M2＋Y2＝１９を満たし、 [D1D2M1M2Y1Y2](D1=０も許す)が １９８で割り切れ、１９８０で割り切れない年月日はいくつあるか？ ヒント：n=amam-1…a１a０：m+1ケタの数 n=am１０m＋am-1１０m-1＋…a１１０＋a０ ｃ＝ D1D2M1M2Y1Y2 →cは９でも１１でも割り切れる：９９の倍数 D2+D1+M2+M1+Y2+Y1＝８＋１９＝２７ D2－D1+M2－M1+Y2－Y1＝－８＋１９＝１１ １９８で割り切れて、１９８０で割り切れないための条件：Y2が０以外の偶数 あとは、実際にあり得る日付を考えて足し合わせていく。

29 [使用する色の数で場合分け] ex１４：２×２のタイルがあって色を塗る。 手元にある色の数は8色、隣り合ったところは同じ色にしてはいけない
何通りの塗り方があるか？　回転して同じものは、同一のものとする Not So Fast My Friend!!!! [使用する色の数で場合分け] A D B C D C A B C B D A B A C D ４色 A C B C A B A B C B A C ３色 A B B A ２色

30 今後の予定 第２回 ５月２１日 堺谷：chap２(p.２５~p.３１)Cor.2.2まで
古川：chap２(p.３２~p.３９)Ex.2.7から 第3回 5月28日 笹沼：chap３(p.４３~p.５３)Ex.3.7まで 西田：chap３(p.５３~p.６６)Ex.3.8から 第4回 6月 4日 厳 ：chap４(~p.７７)Ex.4.8まで 長尾：chap４(p.７８~)Ex.4.9から 以下未定：chap４以降は早いうちにコピーして机に置いておきます。