スポンサードリンク
こんにちは、ももやまです。
今日は離散数学で大切な数え上げについてまとめました。
今回は離散数学で習った様々な知識を使って様々な条件を満たすものの個数を求めていく練習問題方式となっています。
スポンサードリンク
１．部分集合、直積集合
わからない場合は、こちらのページで復習をしましょう。
問題1
\( n \geqq 2 \) の自然数 \( n \) に対し、集合 \( S \) を \( S = \{1,2,3, \cdots n\} \) とする。 このとき、次の問いに答えなさい。
(1) 集合 \( S \) のべき集合 \( 2^S \) の要素数は？
(2) \( \{1,2\} \subseteq X \subseteq S \) を満たす集合 \( X \) の要素数は？
(3) \( \{1,2\} \not \subseteq X \subseteq S \) を満たす集合 \( X \) の要素数は？
(4) 集合 \( S \) と \( S \) の直積集合 \( S \times S \) の要素数は？
練習1
\( S \) 部分集合とは、\( S \) の要素の一部（全部使ってもよいし使わなくてもよい）を新たに要素にした集合のことです。
(1) \( S \) のべき集合はとは、\( S \) から作られる部分集合をすべて集めたものとなります。
部分集合の数は、それぞれの要素を選ぶか選ばないかの2つが \( S \) の要素数である \( n \) 個あるため、べき集合は \( 2^n \) 個存在します。
(2) \( \{1,2\} \subseteq X \) ということは、集合 \( X \) には、1と2が含まれていることを表します。また、 \( X \subseteq S \) を満たす集合 \( S \) の個数は、集合 \( S \) の要素を選ぶか選ばないかの2つが \( S \) の要素数である \( n \) 個から1,2を固定した2つを引いた \( n-2 \) 個存在するため、答えは \( 2^{n-2} \) 個あります。
(3) \( \{1,2\} \not \subseteq X \) ということは、集合 \( X \) には、1と2のうちの少なくとも1つが含まれていないことを表します。やり方は2通り
(i) 1と2が含まれていない場合は、(2)の場合の余事象である。つまり、もともとの部分集合の数 \( 2^n \) から(2)の \( 2^{n-2} \) を引けばよいので、答えは \( 3 \cdot 2^{n-2} \) *1となる。
(ii) 場合分けをする。
(a) 集合1が含まれない場合：1以外を選ぶか選ばないかの2通りがある。つまり、\( n-1 \) 個の要素に対して2通りの組み合わせがあるので \( 2^{n-1} \)
(b) 集合2が含まれない場合：1以外を選ぶか選ばないかの2通りがある。つまり、\( n-1 \) 個の要素に対して2通りの組み合わせがあるので \( 2^{n-1} \)
この(a),(b)の和が(3)の答えと思うかもしれませんが、集合1,2の両方が含まれていない場合をダブルカウントしてしまっているので、集合1,2の両方が含まれていない場合を引く必要があります。
(c) 集合1,2の両方が含まれていない場合：集合1,2以外を選ぶか選ばないかの2通りなので、\( 2^{n-2} \) 個あります。
よって (a) + (b) - (c) を計算すると求められます。答えは \( 3 \cdot 2^{n-2} \) *2となる。
(4) 直積集合の要素数はそれぞれの要素数の積となる。よって \( n^2 \) 個。
スポンサードリンク
２．二項関係
わからない場合は、こちらのページで二項関係の復習をしましょう。
練習2
集合 \( S \) を \( S = \{1,2,3,…,n\} \) とする。（問題1と同じ条件）
(1) \( S \) の二項関係の総数は？
(2) \( S \) の二項関係のうち、反射性を満たすものは何個？
(3) \( S \) の二項関係のうち、対称性を満たすものは何個？
(4) \( S \) の二項関係のうち、反射性かつ対称性を満たすものは何個？
(5) \( S \) の二項関係のうち、反射性かつ反対称性を満たすものは何個？
(6) \( S \) の二項関係のうち、反対称性を満たすものは何個？
(7) \( S \) の二項関係のうち、比較可能なもの（完全性を満たすもの）は何個？
(8) \( S \times S \) の二項関係の総数は？
(9) \( S \times S \) の二項関係のうち、反射性を満たすものは何個？
(10) \( S \times S \) の二項関係のうち、対称性を満たすものは何個？
解説2
第4羽にある例題や練習問題と同じ問題を一部出しています。同じ問題の場合は解説を省略しています。解説がみたい人はこちらから飛んでください。
(1) \( 2^{n^{2}} \)
(2) \( 2^{n^{2} - n} \)
(3) \( 2^{\frac{n^{2}+n}{2}} \)
(4) \( 2^{\frac{n^{2}-n}{2}} \)
(5) 関係 \( R \) が反対称性を満たすということは、「\( xRy \) が成立し、\( x,y \) を入れ替えた \( yRx \) が成立する場合、その \( x \) と \( y \) は等しい」というのを表す。つまり、反対称性を満たすためには、\( x \) と \( y \) が等しくない場合は、\( xRy \) と関係を入れ替えた \( yRx \) がともに成立していけないということになる。
ここで \( n = 4 \) として表を書いてみます。さらにペアごとに色をつけてみました。
反射性は、それぞれの対角成分になります。反射性を満たすためには着色されていない部分が必ず含まれている必要があります。
| (1,1) | (1,2) | (1,3) | (1,4) |
| (2,1) | (2,2) | (2,3) | (2,4) |
| (3,1) | (3,2) | (3,3) | (3,4) |
| (4,1) | (4,2) | (4,3) | (4,4) |
この同じ色がついた2つの要素がともに含まれないようにすれば反対称性は満たせますね。つまり、それぞれのペアに対して、3つのパターンが考えられます。
- 同じ色のペアが両方とも存在しないとき
- \( xRy \) だけが存在するとき
- \( yRx \) だけが存在するとき
以上の3パターンを個数は \( n^{2} - n \) 個、ペアで \( \frac{n^{2}-n}{2} \) ペア存在する。他の問題と同じように強制的に選ばれる部分と自由に選べる部分を色で分けると下の図のようになります。
| (1,1) | (1,2) | (1,3) | (1,4) |
| (2,1) | (2,2) | (2,3) | (2,4) |
| (3,1) | (3,2) | (3,3) | (3,4) |
| (4,1) | (4,2) | (4,3) | (4,4) |
それぞれのペアに対して3通りの選び方があるので、答えは \( 3^{\frac{n^{2}-n}{2}} \) 個となります！
(6)
(5)の問題の、反射性を考えないバージョンです。
反対称性の成立のためには、対角成分 ( (1,1),(2,2),(3,3),…,(n,n) )は一切影響しませんよね*3。
なので、(5)の答えが対角成分の選び方の数だけありますね。
つまり、答えは、次の2つの積で求めることができます。
- 2項関係内で反射性かつ反対称性をともに満たすもの
- 対角成分の選び方の総数
1は(5)で求めた通り、\( 3^{\frac{n^{2}-n}{2}} \) 個あります。
2は対角成分の個数は \( n \) 個、それを選ぶか選ばないかの2通りあるため、総数は \( 2^n \) 個あります。
よって答えは \( 2^n \cdot 3^{\frac{n^{2}-n}{2}} \) 個あります。
(7) \( 3^{\frac{n^{2}-n}{2}} \)
(8) \( 2^{n^{4}} \)
(9) 反射性を満たすということは、対角成分は必ず満たす必要がある。対角成分の個数は、\( S \times S \) の要素数個分ある。つまり、対角成分以外の \( n^{4} - n^{2} \) 個を選ぶか選ばないかの2通りあるため、答えは \( 2^{n^{4} - n^{2}} \) 個ある。
(10) 対称性は、\( xRy \) が成り立てば必ず \( yRx \) も成立するという関係である。
なので、\( xRy \) と \( yRx \) の2つをペアにして考える。
ここで対角成分（反射性満たす部分）は関係ないため、今回は除外する。つまり、\( n^{4} - n^{2} \) 個について考える。このペアは \( \frac{n^{4}-n^{2}}{2} \) 個存在する。これに反射性部分の \( n^2 \) 個を足す*4ので、\( \frac{n^{4}+n^{2}}{2} \) 個の要素に対して、選ぶか選ばないかの2パターンがあるので、答えは \( 2^{\frac{n^{4}+n^{2}}{2}} \) 個となる*5。
（考え方は(3)と全く同じです。）
スポンサードリンク
３．関数（写像）
わからない場合は、こちらのページで復習をしましょう。
練習3
集合 \( S \) を \( S = \{1,2,3,…,n\} \) とする。（問題1,2と同じ条件）
(1) 集合 \( \{a,b,c\} \) から集合 \( S \) への全域関数は何個？
(2) 集合 \( S \) から集合 \( \{a,b,c\} \) への部分関数は何個？
(3) 集合 \( S \) から集合 \( S \) への1対1対応（全単射）は何個？
(4) 集合 \( S \) からべき集合 \( 2^S \) への全域関数は何個？
(5) 直積集合 \( S \times S \) から集合 \( \{1,2\} \) へのうち、全射であるものは何個？
(6) \( S \) から \( S \) への関数 \( f \) で、\( f(1) = 1 \) かつ \( f(2) = 2 \) を満たすのは全部で何個？
(7) \( S \) から \( S \) への関数 \( f \) で、任意の \( k \in S \) に対し、\( f(k) \leqq k \) を満たすものは全部で何個？
解説3
第6羽にある例題や練習問題と同じ問題を一部出しています。同じ問題の場合は解説を省略しています。解説がみたい人はこちらから飛んでください。
(1) 3つそれぞれの要素に \( n \) 通りの関係がある。つまり、\( n \cdot n \cdot n = n^3 \) となり、\( n^3 \) 個となる。
(2) (1)の逆パターン、さらに全域関数ではなく部分関数であることに要注意。
\( n \) 個それぞれの要素に、\( a,b,c \) と未定義 \( K \) と合計4パターンの関係がある。つまり、4を\( n \) 回掛けた個数だけ存在する。よって答えは \( 4^n \) 個。
(3) \( n! \) 個
(4) \( n \) 個の要素に対し、2のべき乗の要素数である \( 2^n \) パターンの関係がある。よって \( ( (2^{n})^{n} = 2^{n^{2}} \) 個存在する。
(5) 直積集合 \( S \times S \) の要素数は \( n^2 \) 個あります。
\( n^2 \) 個の要素に、1か2の2通りの関係がある。つまり、\( S \times S \) から集合 \( {1,2} \) への関数の数は \( 2^{n^{2}} \) 個ある。
つぎに前者について考えます。全射であるということは、「対応先の要素に矢印が向けられていない状態」にならないようにしないといけません。そのような場合は、
(i) すべての要素が \( a \) に対応付けられている
(ii) すべての要素が \( b \) に対応付けられている
この2パターン以外です。よって答えは \( 2^{n^{2}} - 2 \) 個です。
(6) \( f(1) = 1 \), \( f(2) = 2 \) が確定しているため、この2つについては何も考える必要がありません。残りの \( n-2 \) 個の要素に対して \( n \) パターンの関係があるため、答えは \( n^{n-2} \) 個となります。
(7) \( f(1) \) の場合は、1通りのパターン、\( f(2) \) の場合は2通りのパターン、3パターン、4パターン、… \( n \) パターンとパターン数が増えていく。これらのパターンの積が条件を満たす個数となるので答えは \( n! \) 個。
４．数え上げの極限
数え上げの問題では、\( n \) が十分に大きい場合はどうなるかという問題が出ることがあります。このような問題は、関数のオーダーを考える場合にも大切になってきます。1問練習してみましょう。
この分野については、こちらのサイトに詳しく説明をしています。
怪しいなと思った人はこちらのサイトで復習しましょう。
未知 \( n \) が入った2変数の大小の比べ方などもこちらのサイトにまとめています。
練習4
(1) \( n \) が十分大きいとする。つぎのア～エの関数を大きい順に並べなさい。
ア：\( n^4 \) イ：\( 4^n \) ウ：\( n! \) エ：\( n^n \)
(2) \( n \) が十分大きいとする。つぎのア～エの関数を大きい順に並べなさい。
ア：\( n! \) イ：\( 2^{n^{2}} \) ウ：\( 2^{2^{n}} \) エ：\( n^n \)
解説4
(1)
答え：エ > ウ > イ > ア
(2)
このように指数の上に指数がついている場合は対数をとってあげると大きさがわかりやすくなる。イ～エの対数をとると、
イ：\( n^2 \log_2 2 = n^2 \)
ウ：\( 2^n \log_2 2 = 2^n \)
エ：\( n \log n \)
となる。すると、答えは：ウ > イ > エ > ア と見えてくる。（エ > アは(1)より。）
５．さいごに
今回は、離散数学では必須の「数え上げ」の手法を、離散数学の様々なジャンルの知識を使って数え上げていくことをしました。
また、\( n \) 個のような未知数の数え上げの結果から、\( n \) が十分に大きい場合は、どの答えが一番大きくなるかについてもまとめました。これらはアルゴリズムのオーダーを判別する際に非常に大切になるため覚えておきましょう。
*1:計算過程\[ 2^n - 2^{n-2} = 4 \cdot 2^{n-2} - 2^{n-2} = 3 \cdot 2^{n-2}\]となる。
*2:計算過程\[ 2^{n-1} + 2^{n-1} - 2^{n-2} = 4 \cdot 2^{n-2} - 2^{n-2} = 3 \cdot 2^{n-2} \]となる。
*3:対角成分の場合、\( xRy \) かつ \( yRx \) ならば \( x = y \) を満たしますよね。
*4:対称性を満たす場合、対角成分はあってもなくてもOKだから。
*5:余談ですが、反射性かつ対称性を満たす場合は対角成分が必須なので固定する必要がある。この場合の個数は \( 2^{\frac{n^{4}-n^{2}}{2}} \) 個となる。
関連広告・スポンサードリンク
