counting_chap7_2

7章後半
M1 鈴木洋介
Example 7.8.
正n角形(n≧3)P1P2…Pnの3頂点を結んでできる三角形はいくつ存在するか。
ただし、合同なものは1つと数える。
三角形の頂点の１つをP1 に固定する。
N1：正三角形の数
N2：正三角形でない二等辺三角形の数
N3：不等辺三角形の数
としてN=N1+N2+N3を求める。
P1を頂点とする三角形は
個。
S={P1PiPj|2≦i＜j≦n}とすると|S|=
Sのうちに、
同じ形の不等辺三角形はそれぞれ3!=6個存在する。
P1
Example 7.8.
正n角形(n≧3)P1P2…Pnの3頂点を結んでできる三角形はいくつ存在するか。
ただし、合同なものは1つと数える。
三角形の頂点の１つをP1 に固定する。
N1：正三角形の数
N2：正三角形でない二等辺三角形の数
N3：不等辺三角形の数
としてN=N1+N2+N3を求める。
P1を頂点とする三角形は
個。
S={P1PiPj|2≦i＜j≦n}とすると|S|=
Sのうちに、
同じ形の不等辺三角形はそれぞれ3!=6個存在する。
同じ形の二等辺三角形はそれぞれ3個存在する。
P1
Example 7.8.
正n角形(n≧3)P1P2…Pnの3頂点を結んでできる三角形はいくつ存在するか。
ただし、合同なものは1つと数える。
三角形の頂点の１つをP1 に固定する。
N1：正三角形の数
N2：正三角形でない二等辺三角形の数
N3：不等辺三角形の数
としてN=N1+N2+N3を求める。
P1を頂点とする三角形は
個。
S={P1PiPj|2≦i＜j≦n}とすると|S|=
Sのうちに、
同じ形の不等辺三角形はそれぞれ3!=6個存在する。
同じ形の二等辺三角形はそれぞれ3個存在する。
同じ形の正三角形は（存在するなら）1個存在する。
よって
=N1+3N2+6N3
・・・(*)
P1
Example 7.8.
正n角形(n≧3)P1P2…Pnの3頂点を結んでできる三角形はいくつ存在するか。
ただし、合同なものは1つと数える。
P1を含む正三角形は最大１個なのでN1=1-p。
（pを正三角形が存在するとき0、しないとき1とする）
P1Pi=P1Pjとなる二等辺三角形（正三角形含む）の数は、
nが偶数の場合 (n-2)/2、奇数の場合(n-1)/2
よってN1+N2=(n-2+q)/2
・・・(**)
(nが偶数ならq=0 奇数なら 1)
(*)(**)より
p,q∈{0,1}。-4≦3q-4p≦3なのでNはn2/12に最も近い整数。
すなわち、
Example 7.9.
平面上にn個の点の集合Tがある。どの3点も一直線上になく、
各点に対して等距離の点がk個以上存在する。
このとき、
を証明せよ。
A=T={P1,P2,…,Pn}とする。
B={li,j|1≦i＜j≦n li,jは線分PiPjの垂直二等分線}とする。
このとき|B|=
S={(Pi,lj,k)|点Piは垂直二等分線lj,k上にある}とする。
どの3点も一直線上にないという条件から、|S(*,lj,k)|≦2。
よって
Pi
li,j
Pj
Example 7.9.
平面上にn個の点の集合Tがある。どの3点も一直線上になく、
各点に対して等距離の点がk個以上存在する。
このとき、
を証明せよ。
ある点Piは少なくともk本の二等分線上にあるはずなので|S(Pi,*)|≧
以上の２式よりk2-k-2(n-1)≦0
よって問題の不等式が成り立つ。
Pi
Example 7.10.
一直線上にn個の点がある。2点間の距離を考える。
各距離の値は最大2回しか現れない。このとき、
少なくとも
個の距離は1回だけ現れることを示せ。
x,yをそれぞれ1,2回だけ現れる距離の数とする。
x+yの下限を求めよう。
P1 P2
各点を左から右の順番にP1,…Pnとする。
プロセス1： P1を左の端点とする線分を考える。
このときP1はn-1個の線分の左の端点となる。
プロセス2： P2を左の端点とする線分を考える。
P2はn-2個の線分の左の端点となるが、
このうちいくつかの距離はすでにプロセス1で現れている可能性がある。
もしP1Pi=P2PjかつP1Pk=P2Plのとき、P1P2=PiPj=PkPlとなり、
同じ距離が3回以上は現れないという条件に矛盾する。
よって2回以上同じ長さはP1を含む距離に現れない。
つまり、n-3以上の新しい距離が現れることになる。
Example 7.10.
一直線上にn個の点がある。2点間の距離を考える。
各距離の値は最大2回しか現れない。このとき、
少なくとも
個の距離は1回だけ現れることを示せ。
プロセス3： P3を左の端点とする線分を考える。
これ以降も同様の議論を行えて、n-5以上の新しい距離が現れる。
よって距離の種類の合計x+y≧(n-1)+(n-3)+(n-5)+・・・
nが奇数ならx+y≧(n2-1)/4、偶数ならx+y≧n2/4となる。
同じ距離を許した距離の総数x+2y=n(n-1)/2より、
Example 7.11.
p(n)をnの整数分割の数とする。
p(n,m)を分割数mのnの整数分割の数とする。
h(n,m)を最大値mのnの整数分割の数とする。
p(n,m)=h(n,m)を示せ。
例：n=6,m=3
6を3つの自然数に分割する。
6=1+1+4
6=1+2+3
6=2+2+2
6を最大値3の自然数に分割する。
6=3+3
6=1+2+3
6=1+1+1+3
p(6,3)=h(6,3)=3
Example 7.11.
p(n)をnの整数分割の数とする。
p(n,m)を分割数mのnの整数分割の数とする。
h(n,m)を最大値mのnの整数分割の数とする。
p(n,m)=h(n,m)を示せ。
分割(a1,…,am)をn×m行列で表現する。
各i列ごとに上からai個を1,それ以外を0にする。
(2,3,4,4,5,5,6,6,6)
この行列を裏返して90度傾けると
一意に最大値mの分割を示すm×n行列となる。
この変換は全単射なので
p(n,m)=h(n,m)。
(3,5,7,8,9,9)
Example 7.12.
πがnの整数分割であるとき、α(π)をπに含まれる1の数とする。
β(π)をπに含まれる値の種類数とする。
∑を全てのnの整数分割についての和とするとき、
∑ α(π)= ∑β(π)を示せ。
例：n=4
4=4
4=3+1
4=2+2
4=2+1+1
4=1+1+1+1
α(π)=0
α(π)=1
α(π)=0
α(π)=2
+ α(π)=4
α(π)=7
β(π)=1
β(π)=2
β(π)=1
β(π)=2
β(π)=1
β(π)=7
Example 7.12.
πがnの整数分割であるとき、α(π)をπに含まれる1の数とする。
β(π)をπに含まれる値の種類数とする。
∑を全てのnの整数分割についての和とするとき、
∑ α(π)= ∑β(π)を示せ。
A={1,2,…,n}、B={π|πはnの整数分割}とする。
p(n)をnの整数分割の個数とすると、|B|=p(n)。
S={(a,π)|a∈A,π∈B,aはπに含まれる}とする。
このときβ(π)=|S(*,π)|。
フビニの法則より
π=(a1,a2,…am)とする。
a=akがπに含まれるとき(a1,a2,…,ak-1,ak+1,…,am)はn-aの整数分割となる。
よって|S(a,*)|=p(n-a)。
ただしp(0)=1と定める。するとフビニの定理より
Example 7.12.
πがnの整数分割であるとき、α(π)をπに含まれる1の数とする。
β(π)をπに含まれる値の種類数とする。
∑を全てのnの整数分割についての和とするとき、
∑ α(π)= ∑β(π)を示せ。
帰納法で以下の式を示す。
n=1のときπ={1}のみなので明らか。Bnをnの分割の集合として
を仮定し、n+1の分割を考える。
あるnの分割に対して、1を追加するとそれはn+1の分割となる。
これによって、nの分割のうちに存在した
個の1に
p(n)個の1が追加されることになる。よって
以上の帰納が成り立つので∑ α(π)= ∑β(π)が言える。
Example 7.13.
Xをn (≧7)要素の集合とする。
A1,…Amを相異なる、5要素のXの部分集合とする。
なるmに対してインデックスi1,…,i6が存在して
Ai1,…,Ai6の和集合はちょうど6要素を含むことを示せ。
何が言いたいのか？
n要素の集合から５要素の部分集合をいろいろ作っていく。
ある程度たくさん(m＞・・・)集合を作りだしたら、
１２３４５
１２４５６
１２３４６
１３４５６
１２３５６
２３４５６
このような関係の６集合が見つかるはず。
ちなみに、各部分集合はそれぞれ異なるので、
２つ以上の和集合をとればその要素数は必ず6以上になる。
これから、どの６要素の和集合も要素数が６より多くなると仮定して、矛盾を導く。
記号をどのように設定するか？S に含まれる要素をQに加えると、
Q
A
A1
X
⊃
Q
Q
⊃
A2
⊃
・
・
・
⊃
対応
和集合
Q
SQ
A2
・
・
・
Q
・
・
・
SQ
・
・
・
Am
⊃
・
・
・
Am
×n個
QA1
Aに含まれる集合に「復元」できる。
A
SQ
A1
⊃
記号をどのように設定するか？S に含まれる要素をQに加えると、
Q
A
A1
X
⊃
Q
Q
⊃
・
・
・
⊃
対応
Q
・
・
・
Q
⊃
和集合
SQ
A2
・
・
・
SQ
・
・
・
Am
×
⊃
・
・
・
Am
×n個
×
⊃
A2
VA1
Aに含まれる集合に「復元」できる。
A
SQ
A1
直積
Example 7.13.
Xをn (≧7)要素の集合とする。
A1,…Amを相異なる、5要素のXの部分集合とする。
なるmに対してインデックスi1,…,i6が存在して
Ai1,…,Ai6の和集合はちょうど6要素を含むことを示せ。
フビニの法則より
x∈AならVA(*,x)={(A-{x},x)}なので|VA(*,x)|=1。
x∈X-Aなら|VA(*,x)|≦4。
∵5以上だと、和集合が６要素となる６つの部分集合
A,Q1∪{x},Q2∪{x},Q3∪{x},Q4∪{x},Q5∪{x}
が存在することになるので矛盾。
以上より
Example 7.13.
Xをn (≧7)要素の集合とする。
A1,…Amを相異なる、5要素のXの部分集合とする。
なるmに対してインデックスi1,…,i6が存在して
Ai1,…,Ai6の和集合はちょうど6要素を含むことを示せ。
TQ={A|A∈A,Q⊂A}とするとSQとTQは一対一対応する。
|SQ|=|TQ|より
|TQ|は上式の左辺の和の中で|TQ|回現れる。よって
二乗平均平方根に関する不等式より、
|Q|≦
より、上記の式を合わせて
記号をどのように設定するか？SQに含まれる値をQに加えると、
A
A1
X
⊃
U
直積
⊃
×
A2
⊃
・
・
・
⊃
Q
Q
対応
和集合
Q
SQ
A2
・
・
・
Q
・
・
・
SQ
・
・
・
Am
⊃
・
・
・
Am
×n個
Aに含まれる集合に「復元」できる。
A
SQ
A1
⊃
Example 7.13.
Xをn (≧7)要素の集合とする。
A1,…Amを相異なる、5要素のXの部分集合とする。
なるmに対してインデックスi1,…,i6が存在して
Ai1,…,Ai6の和集合はちょうど6要素を含むことを示せ。
U={(A,Q)|A∈A,Q∈Q,Q⊂A}とするとU(*,Q)=TQ。
T(A,*)はAに含まれる全ての４つ組なので| T(A,*) |=5
フビニの法則より
よって
となり前提条件の式に矛盾する。
Example 7.14.
一部砂糖入りの異なるケーキミックスを使って、68個のケーキを作る。
(1)各ケーキは5種類の異なるケーキミックスから作られる。
(2)各ケーキを作るケーキミックスのうち1つ以上は砂糖入りである。
(3)どのケーキミックスを３つ選んでも、それら全てを含むケーキがただ1つある。
このとき1つ以上は砂糖入りのケーキミックスが４つ以上使われた
甘すぎるケーキであることを証明せよ。
甘すぎるケーキは存在しないと仮定して、矛盾を導く。
全てのケーキミックスをs1,s2,…,sn 、
そのうち砂糖入りのものをs1,s2,…,smとする。(n≧m)
ケーキミックスの３つ組を考えたとき、全体で
個の３つ組が存在する。
また、それぞれのケーキに対して、３つ組は
=10個含まれる。
68・10=
より、n=17。
Example 7.14.
一部砂糖入りの異なるケーキミックスを使って、68個のケーキを作る。
(1)各ケーキは5種類の異なるケーキミックスから作られる。
(2)各ケーキを作るケーキミックスのうち1つ以上は砂糖入りである。
(3)どのケーキミックスを３つ選んでも、それら全てを含むケーキがただ1つある。
このとき1つ以上は砂糖入りのケーキミックスが４つ以上使われた
甘すぎるケーキであることを証明せよ。
1つのケーキミックスsiが使われるケーキの数ciを求めよう。
各ケーキの中でsiを含む３つ組の数は
=6。
⇒siを含む３つ組の数は6ci。
また、全体では、siを含む３つ組の総数は
=120
6ci=120より、ci=20
・・・1つのケーキミックスは20個のケーキに使われる。
Example 7.14.
一部砂糖入りの異なるケーキミックスを使って、68個のケーキを作る。
(1)各ケーキは5種類の異なるケーキミックスから作られる。
(2)各ケーキを作るケーキミックスのうち1つ以上は砂糖入りである。
(3)どのケーキミックスを３つ選んでも、それら全てを含むケーキがただ1つある。
このとき1つ以上は砂糖入りのケーキミックスが４つ以上使われた
甘すぎるケーキであることを証明せよ。
2つのケーキミックスsi,sjが両方使われるケーキの数ci,jを求めよう。(1≦i ≦ j ≦ 17)
各ケーキの中でsi,sjを含む３つ組の数は
=3。
⇒si,sjを両方含む３つ組の数は3ci,j。
また、全体で、si,sjを両方含む３つ組の総数は
=15
3ci,j=15より、ci,j=5
・・・2つのケーキミックスの組は5個のケーキに使われる。
Example 7.14.
一部砂糖入りの異なるケーキミックスを使って、68個のケーキを作る。
(1)各ケーキは5種類の異なるケーキミックスから作られる。
(2)各ケーキを作るケーキミックスのうち1つ以上は砂糖入りである。
(3)どのケーキミックスを３つ選んでも、それら全てを含むケーキがただ1つある。
このとき1つ以上は砂糖入りのケーキミックスが４つ以上使われた
甘すぎるケーキであることを証明せよ。
3つのケーキミックスsi,sj,skが全て使われるケーキの数ci,j,kを求めよう。
(1≦i ≦ j ≦k ≦ 17)
問題文より、 ci,j,k=1。
4つのケーキミックスsi,sj,sk,slが全て使われるケーキの数ci,j,k,lを求めよう。
仮定より、 1≦i≦j≦k≦l≦mならば ci,j,k,l=0。
Example 7.14.
一部砂糖入りの異なるケーキミックスを使って、68個のケーキを作る。
(1)各ケーキは5種類の異なるケーキミックスから作られる。
(2)各ケーキを作るケーキミックスのうち1つ以上は砂糖入りである。
(3)どのケーキミックスを３つ選んでも、それら全てを含むケーキがただ1つある。
このとき1つ以上は砂糖入りのケーキミックスが４つ以上使われた
甘すぎるケーキであることを証明せよ。
どのケーキにも砂糖入りケーキミックスが１つは入っていることを考慮する。
s1
×11
=ミックス
=ケーキ
sn （ノンシュガー）
sm
s2
×11
×11
Example 7.14.
一部砂糖入りの異なるケーキミックスを使って、68個のケーキを作る。
(1)各ケーキは5種類の異なるケーキミックスから作られる。
(2)各ケーキを作るケーキミックスのうち1つ以上は砂糖入りである。
(3)どのケーキミックスを３つ選んでも、それら全てを含むケーキがただ1つある。
このとき1つ以上は砂糖入りのケーキミックスが４つ以上使われた
甘すぎるケーキであることを証明せよ。
どのケーキにも砂糖入りケーキミックスが１つは入っていることを考慮する。
包除原理より
以上の方程式を満たすm≦17は存在しないので、矛盾する。
よって必ず甘すぎるケーキが存在する。スイーツ（笑）
Example 7.13.
Xをn (≧7)要素の集合とする。
A1,…Amを相異なる、5要素のXの部分集合とする。
なるmに対してインデックスi1,…,i6が存在して
Ai1,…,Ai6の和集合はちょうど6要素を含むことを示せ。
問題の前提条件において、どの6つの部分集合をとっても
その和集合は6以上
A={A1,…,Am}
Q={ Q | |Q|=4,あるA∈Aに対してQ⊂A}
QAをA(∈A)から４つ要素を取り出した組（４つ組）の集合とする。
このときQは全ての４つ組の集合となる。
この定義より、Qの要素となる各Qに対して1つ以上はXの要素xが存在して
Q∪{x}∈Aとなる。
SQ={x|x∈X,Q∪{x}∈A}とする。
Aの要素Aに対して、直積QA ×Xを考える。
VA={(Q,x)|Q∈QA,x∈X, Q∪{x}∈A}とする。
このとき|VA(Q,*)|=|SQ|。
フビニの定理より、

Download Report