counting_chap1

照山順一
輪講の目的
 B4やM1に英語を読むこと、発表スライドの作成に慣
れてもらう。組み合わせに関しての感覚を養う。
 基本事項
１０：３０～１２：００程度：会議室
一回に２人発表予定。一人一時間弱で。
終わりきらなければ、続きを次週に。
 目標としては、７月の第２週に終わる予定。
(計９回：一回に一章で進むと一回分余る)
A Path to Combinatorics
for Undergraduate
 カウンティングの話
 基礎的な力がついていくと思います。
 高校で習ったような問題もありますが
丁寧に読んでいきましょう。
 流れ：具体的な例題を用いて、解法を与えていく
 各章に約15程度の例題
 １章：和と積
 ２章：組み合わせ
 ３章：二項係数
 ４章：全単射
 ５章：帰納法
 ６章：包除原理
 ７章：ダブルカウンティング
 ８章：生成関数
ex１：12345678910111213 ……….. 9899100
100文字消した時にできる最大の数は何
か？
 何けたの数ができるのか？→192-100=92
 できるだけ左に9が来るようにすればよい。
→9以外の数を左からどんどん削る。
Not So Fast, My Friend!!!!
99202122232425262728293031
999995051525354555657585960……9899100
9101112131415161718192021 ………..
9993031…394041…495051………..
………..
9899100
9899100
99999585960……9899100
99999785960……9899100
8 + 19 + 19 + 19 + 19 27
84
8
46
消した文字数：
 ときどき間違った解法を記述して、後で訂正をしてい
る。
Not So Fast, My Friend!!!!
 書いてあることをうのみにせずに確認しながら読む力
もつく。
 論文にはよく間違いがあったりするもの。
ex２：以下の条件を満たす4人の並び方はいくつあるか？
①父と母は隣同士
②弟は、父または母の隣
父、母、弟の並び方を考える。
父
母
父
弟父
母
弟母
弟
母弟
母
父弟
父
兄
それぞれの並び方に
兄が右か左にくるので、
２+２+２+２=８通り
ex３：１０×１０の格子点
この点から４つを結んで作られる正方形はいくつあるか？
教科書では１０×１０だが、
６×６の格子で考えてみる。
長さkのもの：(６- →(n-k)２
パターン１：
k)２
パターン２：
各正方形はパターン１の正方形の
いずれか一つに内接する
長さkのパターン１の正方形に
内接するパターン２の正方形の数：k－１
１章の内容
 和を使って数え上げるのか、積を使って数え上げる
のか
 ex２,ex３：和を使用
 ex２を積の考え方で解くと、２(父、母)×２(弟)×２
(兄)＝８
 集合の考え方では：
ex４：長さが１～nの棒が１本ずつ
ここから３本選んで三角形はいくつ作れる
か？
合同なものは同一とみなす
 三角形の３辺を短いほうから x, y, z とする
 基本方針は三角不等式 x+y>z を考える
 最長の辺を固定してカウンティング
y
x
z
ex４：長さが１～nの棒が１本ずつ
ここから３本選んで三角形はいくつ作れる
か？
合同なものは同一とみなす
A(k)：最長辺の長さがkである三角形の個数
y
x
kの偶奇で場合分け
k=2m
x+y>2m と x+y>2xからxとmの大小関係で場合分け
z
：①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 通りの数を取り
ex４：長さが１～nの棒が１本ずつ
ここから３本選んで三角形はいくつ作れる
か？
合同なものは同一とみなす
A(k)：最長辺の長さがkである三角形の個数
y
x
kの偶奇で場合分け
k=2m
k=2m+1
z
ex５Ａ君はロッカーのカギ番号を忘れてしまった。
分かっていることは以下の通り。
①鍵は３つの数字を順番に正しく入れると開く
②鍵に使われる数字は１から４０まで
③３つのうち、２つは１７と２４であるが順番は分から
正しい鍵番号として何通り考えられるか？
1
2
3
１
７
２
４
??
①鍵は３つの数字を順番に正しく入れると開く
②鍵に使われる数字は１から４０まで
③３つのうち、２つは１７と２４であるが順番は分
Not So Fast, My Friend!!!!
からない
1
2
3
１
７
１
７
２
４
２
４
２
４
??
??
２
４
１
７
??
??
??
??
１
７
２
４
１
７
２
４
１
７
??に入る数は４０通りなので、
４０×６=２４０
(１７，１７，２４)や(１７,２４,２
同じ数字を二つ含む6パターンを
二重に数え上げている。
よって正しい答えは２４０-６=２３
ex6 １０９９の約数からランダムに選んだ時、
その数が１０８８の倍数である確率は？
1099=299・599
約数は2a・5bの形をしている：約数は全部で100
1088=288・588
a,bともに88以上99以下を満たせばよい：１２２
ex7：整数aとbの最小公倍数が２３５７１１１３であるような
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通り
ex６,ex７より：整数の約数・最小公倍数に関する命題
命題１.１.
nの約数の個数：
命題１.２.
nを最小公倍数に持つ整数の組の数：
ちょっと休憩：連絡
 もし発表に時間がかかりそうだったら、メインアイ
ディアを示すなどして適宜省略して下さい。
 ただし、何が書いてあるのか理解してからその判断
を。
 どうしてもわからない点があれば人に聞きましょう。
ex8:以下のような条件を満たすナンバープレートがある
①アルファベット３文字の後ろに数字が3つならぶ
②Oと０を同時に使わない
何通りのナンバーができるか？
A X O
4 2 2
S1：０を使わないナンバー
S2：Oを使わないナンバー
|S1|=２６３×９３
|S2|=２５３×１０３
|S1|と|S2|を足せば答えか？
S3：Oと０ともに使わないナンバー |S3|=２５３×９３
→S1とS2の共通部分
答：|S1|+|S2|-|S3|＝１７０４７２
集合を足し合わせて重なった部分の二重数え上げを取り除くことを包除原理という。
詳しくは６章で。(１カ月半ほど後で。)
ex９：１０００より小さい正の整数の中で
１０進表記をした時、１を持つ整数の数は？
S＝{１, ２, ３, . . . , ９９８, ９９９}
集合Sを分割する
S1＝{１, ２, ３, . . . , ９}
S2＝{１０, １１, １２, . . . , ９８, ９９}
答：１＋１８＋２５２＝
S3＝{１００, １０１, １０２, . . . , ９９８,
９９９}
→A1={１} |A1|=１
A1：S1で少なくとも１を１つもつ数字の集合
A2：S2で少なくとも１を１つもつ数字の集合
→|A2|=１
→|A3|=２５２
A3：S3で少なくとも１を１つもつ数字の集合
８
１
８
９
１
９
９
７
２
７
２
９
９
８
ex９：１０００より小さい正の整数の中で
１０進表記をした時、１を持つ整数の数は？
S’＝{０, １, ２, ３, . . . , ９９８, ９９９}
集合S’全体から１を含まない数を数え上げて引いたほうが簡単
B：１０００未満で１を含まない非負整数の集合
|B|＝９３＝７２９答：１０００－７２９＝２７１
ex１０：１５個のスイッチがある
少なくとも一つがonとなっている場合の数は？
 ２１５－１＝３２７６７
定理１.３
|S|＝n なる集合Sが与えられた時、
空集合・S自身も含め２n個の部分集合がある。
写像に関して
 単射、全射、全単射の定義
定理1.4：順列
 n, k を正の整数とし、n≧kとする。
 n個からk個を取り出し作られる順列のパターン数は、
である。
ex１１：５チームによる総当たり戦
各試合の勝敗確率は５０%
全勝または全敗するチームが無い確率は？
A
B
C
D
E
A
B
C
D
E
よって、パターン数は
２１０－２×５×２６＋２０×２３＝２５×
１７
求めるのは確率：
この値を２１０で割って、１７/３２=
０．５３２１５
試合数は全部で10試合
勝ち負けのパターンは全部で２１０であり、
総当たりの結果のパターンは等しい確率で現れ
る。
全体から条件に合わないパターン数を引く
チームAが全勝したと仮定
残り6試合：２６パターン
あるチームが全勝する
あるチームが全敗する
：５× ２６
：５× ２６
全勝のチームと全敗のチームが
同時に存在する場合を二度数え上げている
Aが全勝、Bが全敗：残り２３試合
チームの選び方：５P２=２０通り
→２０×２３
ex１２：以下の条件を満たす７文字のアルファベット列の数は？
①同じ文字は現れない
②aとbは隣り合わない
solutin teruyam soaknbm nouseba
ex１２：以下の条件を満たす７文字のアルファベット列の数は？
①同じ文字は現れない
②aとbは隣り合わない
first solution(①を満たす列数から②を満たさないものを引く)
 ７文字の並べ方全体から、abが隣り合うものをひく。
 全体： 26P7
→
 abの順番で隣り合う列の数を数え上げ。
24P5
×6
o p q r s
 baの順番で隣り合う列について場合の数は同じ
 よって求める場合の数は、
26P7
－ 2×24P5 ×6 = 3254106240
ex１２：以下の条件を満たす７文字のアルファベット列の数は？
①同じ文字は現れない
②aとbは隣り合わない
second solution(分割して足し合わせる)
 以下の４つの場合に分けて数え上げる
①a,bともに含まない：
２４文字から７文字を並べる →
②aは含み，bは含まない：
２４字から６文字並べ、aを入れる → 24P6 ×７
③bは含み，aは含まない：
②と同様 → 24P6 ×７
→ 24P5 ×6×5
④a,bともに含むが隣り合わない：
２４字から５文字選び，どこにa,bを埋め込むか？
o p q r s
24P
まず、aを6か所から選び、
bを残り5か所から選ぶ。
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が０以
あとは、実際にあり得る日付を考えて足し合わせていく。
ex１４：２×２のタイルがあって色を塗る。
手元にある色の数は8色、隣り合ったところは同じ色にしてはいけない
何通りの塗り方があるか？回転して同じものは、同一のものとする
Not So Fast My Friend!!!!
 [使用する色の数で場合分け]
４色
３色
２色
A
D
D
C
C
B
B
A
B
C
A
B
D
A
C
D
A
C
C
A
A
B
B
A
B
A
A
B
C
A
A
C
A
B
B
A
B
A
A
B
今後の予定
 第２回５月２１日
堺谷：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４以降は早いうちにコピーして机に置いておき
ます。

Download Report