練習問題

Aliceアリス は \(1\) 以上 \(1000\) 以下の整数 \(x\) を思い浮かべている。「はい」または「いいえ」で答えられる質問を通して \(x\) を特定するとき、\(x\) を確実に見つけられると保証される質問の最小回数は何回か？ Alice は質問に正直に答えるとする。

ある試験が次の問題からなるとき、何通りの解答が存在するか？

• 「はい」または「いいえ」を選ぶ \(4\) 個の問題

• \(4\) 個の選択肢の中から \(1\) 個を選ぶ問題

• \(15\) 以上 \(20\) 以下の整数が解答となる問題

集合 \(A\), \(B\) が \(|A| = 3\) と \(|B| = 7\) を満たすとき、\(A\) から \(B\) への全域関数はいくつあるか？

\(X\) を \(6\) 要素集合 \(\left\{ x_{1}, x_{2}, x_{3}, x_{4}, x_{5}, x_{6} \right\}\) とする。

1. \(x_{1}\) を含む \(X\) の部分集合の個数を求めよ。

2. \(x_{2}\) と \(x_{3}\) を含み、\(x_{6}\) を含まない \(X\) の部分集合の個数を求めよ。

ナンバープレートの文字列には次の三種類がある:

• \(3\) 個のアルファベットと \(3\) 個の数字

• \(5\) 個のアルファベット

• \(2\) 個のアルファベットまたは数字

これらの文字列全体の集合を \(L\) とする。

1. 次の \(\mathcal{A}\), \(\mathcal{D}\) を使って \(L\) を表せ:

   \[ \begin{aligned} \mathcal{A} &= \left\{ A, B, C, \ldots, Z \right\} \\ \mathcal{D} &= \left\{ 0, 1, 2, \ldots, 9 \right\} \end{aligned} \]

   演算子には和集合 \(\cup\) と直積 \(\times\) だけを使うこと。

2. 加算則と乗算則を使って \(|L|\) を求めよ。

1. 整数区間 \([1..10^{9}]\) に属する \(10\) 億個の整数の中に、いずれかの桁に \(1\) を含む整数はいくつあるか？

   ヒント: どの桁にも \(1\) を含まない整数はいくつあるか？

2. 本棚に \(20\) 冊の本が並んでいる。この中から任意の \(2\) 冊が隣り合わないように \(6\) 冊を選ぶ方法全体の集合から、ちょうど \(6\) 個の \(1\) を含む長さ \(15\) のビット列全体の集合への全単射を説明せよ。

1. \(\mathcal{S}_{n,k}\) を次の不等式の非負整数解全体の集合とする:

   \[ x_{1} + x_{2} + \cdots + x_{k} \leq n \tag{15.8}\]

   言い換えれば、次のように定める:

   \[ \mathcal{S}_{n,k} ::= \left\{ (x_{1}, x_{2}, \ldots, x_{k}) \in \mathbb{N}^{k} \; | \; \text{不等式 } \href{#eq-15-8}{(15.8)} \text{ が成り立つ} \right\} \]

   \(n\) 個の \(0\) と \(k\) 個の \(1\) が並んだビット列全体の集合から \(S_{n,k}\) への全単射を説明せよ。

2. \(\mathcal{L_{n,k}}\) を \(n\) 以下の非負整数からなる長さ \(k\) の広義増加列全体の集合とする:

   \[ \mathcal{L}_{n,k} ::= \left\{ (y_{1}, y_{2}, \ldots, y_{k}) \in \mathbb{N}^{k} \; | \; y_{1} \leq y_{2} \leq \cdots \leq y_{k} \leq n \right\} \]

   \(\mathcal{L}_{n,k}\) から \(\mathcal{S}_{n,k}\) への全単射を説明せよ。

頂点集合が \([1..n]\) (\(n > 2\)) の木を \(n\) 頂点の番号付き木 (numbered tree) と呼ぶ。番号付き木の符号 (code) を、次の手続きで得られる \(1\) 以上 \(n\) 以下の異なる整数が並んだ長さ \(n - 2\) の列と定義する:

番号付き木と符号の例を図 \(\text{15.7}\) に示す。

1. 符号から番号付き木を復元する手続きを説明せよ。

2. \(n\) 頂点の番号付き木全体の集合から \(1\) 以上 \(n\) 以下の異なる整数が並んだ長さ \(n-2\) の列全体の集合への全単射が存在すると結論付けよ。\(n\) 頂点の番号付き木の個数を答えよ。

\(X\), \(Y\) を有限集合とする。

1. \(X\) から \(Y\) への二項関係の個数を答えよ。

2. \(X\) から \(Y\) への全域関数全体の集合を \([X \to Y]\) とする。\([X \to Y]\) から集合 \(Y^{|X|}\) への全単射を説明せよ (\(Y^{n}\) は \(n\) 個の \(Y\) の直積を意味する)。全単射の存在を利用して \(|[X \to Y]|\) を求めよ。

3. \(\text{b}\) の結果を利用して、\(X\) から \(Y\) への (全域でないものを含む) 関数の個数を答えよ。全域関数の個数と関数の個数の比は \(X\) が大きくなるにつれてどのように変化するか？ \(O(1)\), \(O(|X|)\), \(O(2^{|X|})\), \(\ldots\) のどれか？

4. \(X\) から \(\left\{ 0, 1 \right\}\) への全域関数全体の集合を \([X \to \left\{ 0, 1 \right\}]\) とする。冪集合 \(\operatorname{pow} (X)\) から \([X \to \left\{ 0, 1 \right\}]\) への全単射を説明せよ。

5. \(X\) を \(n\) 要素集合、\(B_{X}\) を \(X\) から \(X\) への全単射全体の集合とする。\(B_{X}\) から \(X\) の置換²全体の集合への全単射を説明せよ。\(X\) から \(X\) への全単射の個数を答えよ。

数学的帰納法を使って、\(n\) 要素集合の部分集合が \(2^{n}\) 個あること (定理 4.5.5) を証明せよ。

Fermatフェルマー の小定理³ (系 9.10.8) は、任意の素数 \(p\) と非負整数 \(a\) に対して次の合同関係が成り立つと主張する:

この合同関係は \(a = 0,1\) のとき明らかなので、以降では \(a \geq 2\) と仮定する。

この問題では、\(a\) 個の文字からなるアルファベットを固定したときの文字列を数えることで合同関係 \(\text{(15.9)}\) を証明する。

1. \(a\) 個の文字からなるアルファベット上の長さ \(k\) の文字列の個数を答えよ。

2. \(\text{(a)}\) で考えた文字列の中に、\(2\) 種類以上のアルファベットを使うものはいくつあるか？

\(z\) を長さ \(k\) の文字列とする。\(z\) の長さ \(n\) 回転 (length-\(n\) rotation) を、\(z = xy\) と \(|x| = \operatorname{rem}(n, k)\) を満たす文字列 \(x\), \(y\) に対する文字列 \(yx\) と定義する。

3. \(u\) が \(z\) の長さ \(n\) 回転であり、\(v\) が \(u\) の長さ \(m\) 回転であるとき、\(v\) は \(z\) の長さ \((n + m)\) 回転だと示せ。

4. \(\approx\) を「回転である」を意味する文字列上の二項関係として次のように定義する:

   \[ v \approx z \ \ \overset{\text{def}}{\longleftrightarrow}\ \ \exists n \in \mathbb{N}.\ (\text{\(v\) が \(z\) の長さ \(n\) 回転}) \]

   \(\approx\) が同値関係だと示せ。

5. \(xy = yx\) が成り立つとき、\(x\) と \(y\) は両方とも何らかの文字列 \(u\) の反復だと示せ。つまり、\(xy = yx\) なら \(x, y \in u^{\ast}\) となる文字列 \(u\) が存在すると示せ。

6. \(p\) が素数で \(z\) が少なくとも \(2\) 種類のアルファベットを含む長さ \(p\) の文字列なら、二項関係 \(\approx\) の下で \(z\) はちょうど \(p\) 個の文字列 (\(z\) を含む) と同値になると示せ。

7. \(\text{(a)}\) と \(\text{(f)}\) の結果を使って、素数 \(p\) と整数 \(a \geq 2\) に対して \(p \; | \; (a^{p} - a)\) が成り立つと示せ。これで Fermat の小定理は証明された。

\(8\) 人の学生 ── Annaアンナ, Brianブライアン, Caineケイン, \(\ldots\) ── が円形の部屋に置かれた円形のテーブルの周りに座っている (席はテーブルの周りに等間隔で並んでいる)。二つの座り方においてそれぞれの学生の両隣にいる学生が同じとき、その二つの座り方は同じ席順 (arrangement) を持つと言う。様々な制約の下で \(8\) 人の学生の席順の個数を求めよう。

1. まず、制約が存在しないとき \(8\) 人の学生の異なる席順はいくつあるか？

2. Anna が Brian の正面に座る必要があるとき、\(8\) 人の学生の異なる席順はいくつあるか？

3. Brian が Anna と Caine の両人の隣に座る必要があるとき、\(8\) 人の学生の異なる席順はいくつあるか？

4. Brian が Anna または Caine の隣に座る必要があるとき、\(8\) 人の学生の異なる席順はいくつあるか？

赤、黄、ピンク、白、オレンジのバラが使えるとき、\(3\) ダース (\(36\) 本) のバラを使った花束は何種類作れるか？ 花束でバラは順序付かないと仮定する。解答を説明せよ。解答を実際に計算する必要はない。

\(n\) 冊の本が本棚に並んでいる。選択した任意の \(2\) 冊が少なくとも \(3\) 冊の選択されていない本によって隔てられるように \(m\) 冊の本を選択する方法の個数は、ちょうど \(m\) 個の \(1\) を含む長さ \(k\) のビット列の個数と等しい。

1. \(k\) の値を答えよ。

2. ちょうど \(m\) 個の \(1\) を含む長さ \(k\) のビット列全体の集合から、上述の条件を満たす本の選び方全体の集合への全単射を説明せよ。

ある大学の電子情報工学科には \(6\) 人の女性教員と \(9\) 人の男性教員がいる。それぞれの人物は区別可能である。少なくとも \(1\) 人の女性が含まれるように \(5\) 人の委員会を作るとき、委員会のメンバーは何通り考えられるか？

\(12\) 人の学生が出席する少人数講義があり、次回の講義では生徒を \(4\) 個の \(3\) 人グループに分ける必要がある。TA は学生たちが各グループの学力を平等にすることに時間をかけすぎると昨年の経験から知っていたので、事前にグループを決めておくことにした。

1. TA は \(12\) 人の学生が一列に並んだリストを持っている。このリストを \(3\) 人ずつ取ってグループにしていけば、\(4\) 個の \(3\) 人グループが並んだ列となる。例えばリストが \(ABCDEFGHIJKL\) なら、\((\left\{ A, B, C \right\}, \left\{ D, E, F \right\}, \left\{ G, H, I \right\}, \left\{ J, K, L \right\})\) というグループの列が得られる。この操作は \(12\) 人の学生の列全体の集合から \(4\) 個の \(3\) 人グループの列への \(k\) 対 \(1\) の写像を定める。\(k\) を答えよ。

2. グループの割り当ては同じグループに属する学生を定めるものの、その順序は意味を持たない。\(4\) 個のグループの列、例えば

   \[ (\left\{ A, B, C \right\}, \left\{ D, E, F \right\}, \left\{ G, H, I \right\}, \left\{ J, K, L \right\}) \]

   をグループの割り当て、例えば

   \[ \left\{ \left\{ A, B, C \right\}, \left\{ D, E, F \right\}, \left\{ G, H, I \right\}, \left\{ J, K, L \right\} \right\} \]

   に移す写像は \(j\) 対 \(1\) の写像である。\(j\) を求めよ。

3. \(3n\) 人の学生を \(n\) 個の \(3\) 人グループに分ける方法は何通り存在するか？

近所のピザ屋が特別キャンペーンを実施している。CM によると:

この広告ライターは Harvard の元学生で、トッピングの選び方の個数を \((2^{9})^{3}/3!\) と計算して \(22{,}369{,}621\) に近い値を得たようである。しかし \((2^{9})^{3}/3!\) は整数でないので、どこかで何かが間違っている。この広告ライターが犯したであろう間違いを指摘し、間違いを修正した正しい解答を示せ。

次の設問に一般化された乗算則を使って答えよ。

1. あなたはこれからの一週間で集中的に体重を落とすことにした。そのために、今日は \(5\) 分運動する。明日以降は、前日より \(0\) 分、\(1\) 分、\(2\) 分、\(3\) 分のいずれかだけ長く運動する。例えば、今日からの \(7\) 日間における運動時間を並べた列は \((5, 6, 9, 9, 9, 11, 12)\) になるかもしれない。こういった列には全部で何通りの可能性があるか？

2. 集合の \(r\)-置換 (\(r\)-permutation) とは、その集合の異なる \(r\) 要素を並べた列を意味する。例えば、\(\left\{ a, b, c, d \right\}\) の全ての \(2\)-置換を次に示す:

   \[ \begin{aligned} (a, b) && \quad (a, c) && \quad (a, d) \quad (b, a) && \quad (b, c) && \quad (b, d) \\ (c, a) && \quad (c, b) && \quad (c, d) \quad (d, a) && \quad (d, b) && \quad (d, c) \\ \end{aligned} \]

   \(n\) 要素集合の \(r\)-置換はいくつあるか？ 解答では階乗の記法を使って構わない。

3. 正整数 \(p\), \(n\) が \(p \geq n^{2}\) を満たすとき、各要素が \(\left\{ 1, \ldots, p \right\}\) の異なる要素である \(n \times n\) 行列はいくつあるか？

1. 本棚に \(30\) 冊の本が並んでいる。選択した任意の \(2\) 冊が少なくとも \(2\) 冊の選択されていない本によって隔てられるように \(8\) 冊の本を選択する方法は何通りあるか？

2. 次の等式を満たす非負整数 \(x_{1}\), \(x_{2}\), \(\ldots\), \(x_{m}\) は何通りあるか？

   \[ x_{1} + x_{2} + \cdots + x_{m} = k \tag{15.10}\]

3. 次の不等式を満たす非負整数 \(x_{1}\), \(x_{2}\), \(\ldots\), \(x_{m}\) は何通りあるか？

   \[ x_{1} + x_{2} + \cdots + x_{m} \leq k \tag{15.11}\]

4. \(k\) 以下の非負整数からなる長さ \(m\) の広義増加列はいくつあるか？

区間 \([1..15]\) に属する整数の中から、和が \(3\) で割り切れるように異なる \(3\) 個の整数を選ぶ方法は何通りあるか？

1. 頂点集合が \(\left\{ 1, 2, \ldots, n \right\}\) である有向グラフはいくつあるか？

2. 頂点集合が \(\left\{ 1, 2, \ldots, n \right\}\) である単純グラフはいくつあるか？

3. \(\left\{ 1, 2, \ldots, n \right\}\) 上の対称性を持つ二項関係はいくつあるか？

4. \(\left\{ 1, 2, \ldots, n \right\}\) 上の線形狭義半順序はいくつあるか？

次の設問に数値・階乗・二項係数からなる算術式を答えよ。解答を簡単に説明すること。

1. 母音 \(\texttt{a}\), \(\texttt{e}\), \(\texttt{i}\), \(\texttt{o}\), \(\texttt{u}\) が連続して並ばないように \(26\) 個のアルファベットを一列に並べる方法は何通りあるか？

2. \(2n\) 人の学生を \(n\) 個の \(2\) 人グループに分割する方法は何通りあるか？

3. 一桁の数字 \(\texttt{0}\), \(\texttt{1}\), \(\ldots\), \(\texttt{9}\) が並んだ長さ \(n\) の二つの列が同種 (same type) とは、一方が他方の置換であることを言う。例えば \(n = 8\) のとき \(\texttt{03088929}\) と \(\texttt{00238899}\) は同種である。長さ \(n\) の列における種類の個数 (「同種」関係の同値類の個数) を求めよ。

通常の \(52\) 枚からなるトランプ一式において、それぞれのカードは数字と絵柄を持つ。数字は次の集合 \(R\) の要素であり、絵柄は次の集合 \(S\) の要素である:

\(5\) 枚の手札 (hand) とは、\(52\) 枚のカードから選ばれた \(5\) 枚のカードを意味する。

手札に関する性質を次にいくつか示す。それぞれについて、第 15.1 節で説明した乗算則と加算則を使って簡単に要素数を数え上げられる集合から、その性質を持つ手札全体の集合への全単射を説明せよ。手札の個数を表す式ではなく全単射の説明を解答すること。

1. ワンペア (スリーカード、フォーカード、ツーペアではない)

2. \(3\) 枚以上のエースを含む

例えば、性質が「\(4\) 種類の絵柄を全て含む」だったとする。そういった手札は同じ絵柄のカードをちょうど \(2\) 枚だけ含むことに注目すれば、この性質を持つ手札全体の集合から \(S \times R_{2} \times R^{3}\) への全単射が存在すると分かる。ここで \(R_{2}\) は \(R\) の \(2\) 要素部分集合全体の集合を表す。具体的には、\(S \times R_{2} \times R^{3}\) の要素

は次の手札に対応する:

• 絵柄が \(s \in S\) のカードが \(2\) 枚ある。

• 絵柄が \(s\) のカードの数字は \(\left\{ r_{1}, r_{2} \right\} \in R_{2}\) である。

• 残りの \(3\) 枚のカードの数字はそれぞれ \(r_{3}\), \(r_{4}\), \(r_{5}\) である。対応する絵柄は次の順序に応じて決定する:

  \[ \clubsuit \prec \diamondsuit \prec \heartsuit \prec \spadesuit \]

この全単射における対応関係の例を次に示す:

\(7\) 個のサイコロがあり、それぞれ虹の各色で塗られているとする。これらのサイコロの目 (roll) とは、それぞれのサイコロを振ったときの目を虹と同じ順番 (ROYGBIV) で並べたもの言う。例えば \((3,1,6,1,4,5,2)\) は赤いサイコロが \(3\) の目を出し、オレンジ色のサイコロが \(1\) の目を出し、 \(\cdots\) という結果を意味する。

目に関する性質を次にいくつか示す。それぞれについて、その性質を持つ目全体の集合から、加算則や乗算則を使って簡単に要素数を数え上げられる集合への全単射を説明せよ。それから、考えている目の個数を表す数値と階乗と二項係数などからなる算術式を答えよ。解答する対応関係が実際に全単射だと示す必要はない。また、算術式を単純化する必要はない。

1. ちょうど \(2\) 個の目が \(6\) であり、他の目が全て異なる。

   例: この性質を \((6,2,6,1,3,4,5)\) は持つのに対して、\((1,1,2,6,3,4,5)\) と \((6,6,1,2,4,3,4)\) は持たない。

2. ちょうど \(2\) 個の目が同じであり、他の目が全て異なる。

   例: この性質を \((4,2,4,1,3,6,5)\) は持つのに対して、\((1,1,2,6,1,4,5)\) と \((6,6,1,2,4,3,4)\) は持たない。

3. \(2\) 個の目が同じであり、異なる \(2\) 個の目が同じであり、さらに残りの \(3\) 個の目も同じ目を持つ。ただし \(3\) 種類の目は全て異なる。

   例: この性質を \((6,1,2,1,2,6,6)\) は持つのに対して、\((4,4,4,4,1,3,5)\) と \((5,5,5,6,6,1,2)\) は持たない。

例えば、性質が「\(4\) 個の目が同じであり、残りの \(3\) 個の目も同じである。ただし \(2\) 種類の目は異なる」だとする。この性質を満たす目全体の集合を \(A\) として、\(R\) を虹の七色全体の集合、\(S ::= \left\{ 1,2, \ldots, 6 \right\}\) をサイコロの目全体の集合と定める。

\(B ::= P_{S,2} \times R_{3}\) と定義する。ここで \(P_{S,2}\) は \(S\) の \(2\)-置換全体の集合、\(R_{3}\) は \(R\) の \(3\) 要素部分集合を表す。このとき次の対応関係を使うと \(A\) から \(B\) への全単射を構築できる:

• 第 \(1\) 要素の組は、最初の要素が \(3\) 回現れる目、最後の要素が \(4\) 回現れる目に対応する。

• 第 \(2\) 要素の集合は、目が同じ \(3\) 個のサイコロの色に対応する。

例えば、次の目

は、次の \(B\) の要素に対応する:

後は全単射則より \(|A| = |B|\) が分かり、一般化された乗算則と部分集合則から \(|B|\) が求まる:

[木の数え上げ] \(n\) 個の頂点を持つ異なる木の個数 \(T_{n}\) はいくつだろうか？ この質問の解答は Cayleyケイリー の公式 (Cayley's formula) と呼ばれる:

この等式の証明の一つを問題 15.8 に示した。Aignerアイグナー & Zieglerジーグラー (1998) には、これ以外に \(3\) 個の証明が示されている。その中で「最も美しい」とコメントされているのは Jimジム Pitmanピットマン が発見したものであり、この問題ではその証明を見ていく⁴。

Pitman の証明は、\(n\) 頂点の空グラフに有向辺を追加して根付き木を構築する操作において、有向辺を追加される順に並べた列の個数を二つの方法で数え上げる。一つ目の方法は \(T_{n}\) 個ある無向木の中から一つを任意に取り、その木の任意の頂点を根として選び、その根から遠ざかるように辺を (一意に) 向き付けて得られる有向辺を任意の方法で並べた列の個数を数える。根の選択肢は \(n\) 個あり、\(n - 1\) 個の有向辺を並べた列は \((n - 1)!\) 個ある。よって、この数え方では考えている列の個数が次に等しいと分かる:

もう一つの方法は、空グラフから始めて有向辺を追加しながら根付き木の全域森を成長させていくときに追加される有向辺を並べた列の個数を数え上げる。\(n - k\) 個の有向辺が追加されたとき、全域森には \(k\) 個の根付き木が含まれる。その全域森に次の有向辺を追加するには、任意に頂点 \(v\) を選び、\(v\) を含まない \(k - 1\) 個の根付き木の根のいずれかに向かう \(v\) からの有向辺を加えればよい。つまり、新しい有向辺を追加して \(k - 1\) 個の根付き木からなる新しい全域森を構築する選択肢は \(n(k - 1)\) 個ある。

よって、空グラフから最終的な根付き木を構築するまでに追加される有向辺を順番に並べた列の個数は次のように計算できる:

同じ個数を表す二つの式を等号で結べば \(T_{n} n! = n^{n-2} n!\) が分かり、ここから Cayley の公式を得る:

Pitman の議論を一般化して、\(k\) 個の木からなる \(n\) 頂点の森の個数を求めよ。

\(52\) 枚のトランプ一式が \(2\) セットある。合計 \(104\) 枚のカードの異なる置換の個数を表す単純な式を示せ。\(2\) セットのトランプ一式は同一で区別できないとする。

\(\text{BOOKKEEPER}\) の道タオ: 悟りに近づくために、\(\text{BOOKKEEPER}\) という単語について思索を深めよう。

1. 単語 \(\text{POKE}\) に含まれる文字を並び替えて得られる異なる単語はいくつあるか？

2. 単語 \(\text{BO\(_{1}\)O\(_{2}\)K}\) に含まれる文字を並び替えて得られる異なる単語はいくつあるか？ 二つの \(\text{O}\) に添え字を付けて異なる文字としていることに注意せよ。

3. \(\text{BO\(_{1}\)O\(_{2}\)K}\) を並び替えた単語から添え字を消去することで \(\text{BOOK}\) を並び替えた単語とする写像を考える。この写像を表す矢印を次の図に書き入れよ:

   \[ \begin{aligned} \text{\LARGE\mathstrut} \vdots \ \ \ \ \ \ \ && \\ \text{\LARGE\mathstrut} \text{O\(_{2}\)BO\(_{1}\)K} && \text{\small \(\vdots\)} \ \ \ \ \ \\ \text{\LARGE\mathstrut} \text{KO\(_{2}\)BO\(_{1}\)} && \qquad \qquad \qquad \text{BOOK} \\ \text{\LARGE\mathstrut} \text{O\(_{1}\)BO\(_{2}\)K} && \qquad \qquad \qquad \text{OBOK} \\ \text{\LARGE\mathstrut} \text{KO\(_{1}\)BO\(_{2}\)} && \qquad \qquad \qquad \text{KOBO} \\ \text{\LARGE\mathstrut} \text{BO\(_{1}\)O\(_{2}\)K} && \text{\small \(\vdots\)} \ \ \ \ \ \\ \text{\LARGE\mathstrut} \text{BO\(_{2}\)O\(_{1}\)K} && \\ \text{\LARGE\mathstrut} \vdots \ \ \ \ \ \ \ && \end{aligned} \]

4. この写像は \(k\) 対 \(1\) である。\(k\) を答えよ。

5. 除算則の光の下で、\(\text{BOOK}\) を並び替えて得られる単語はいくつあるか？

6. 順調だ、若き師よ！ では、\(\text{KE\(_{1}\)E\(_{2}\)PE\(_{3}\)R}\) を並び変えて得られる異なる単語はいくつあるか？

7. \(\text{KE\(_{1}\)E\(_{2}\)PE\(_{3}\)R}\) を並び替えた単語から添え字を消去することで \(\text{KEEPER}\) の文字を入れ替えた単語とする写像を考える。この写像で \(\text{REPEEK}\) に移される \(\text{KE\(_{1}\)E\(_{2}\)PE\(_{3}\)R}\) の並び替えを全て答えよ。

8. この写像はどんな写像か？

9. \(\text{KEEPER}\) を並び替えて得られる単語はいくつあるか？

これで \(\text{BOOKKEEPER}\) の真の姿を捉える準備が整った！

10. \(\text{BO\(_{1}\)O\(_{2}\)K\(_{1}\)K\(_{2}\)E\(_{1}\)E\(_{2}\)PE\(_{3}\)R}\) を並び替えて得られる単語はいくつあるか？

11. \(\text{BOOK\(_{1}\)K\(_{2}\)E\(_{1}\)E\(_{2}\)PE\(_{3}\)R}\) を並び替えて得られる単語はいくつあるか？

12. \(\text{BOOKKE\(_{1}\)E\(_{2}\)PE\(_{3}\)R}\) を並び替えて得られる単語はいくつあるか？

13. \(\text{BOOKKEEPER}\) を並び替えて得られる単語はいくつあるか？

14. \(\text{VOODOODOLL}\) を並び替えて得られる単語はいくつあるか？

15. \(2\) を \(17\) 個、\(5\) を \(23\) 個、\(9\) を \(12\) 個含む長さ \(52\) の列はいくつあるか？

\(\text{MISSISSIPPI}\) に含まれる文字を並び替えて得られる異なる文字列はいくつあるか？

次の値を求めよ:

1. \((1 + x)^{11}\) における \(x^{5}\) の係数

2. \((3x + 2y)^{17}\) における \(x^{8}y^{9}\) の係数

3. \((a^{2} + b^{3})^{5}\) における \(a^{6}b^{6}\) の係数

\(p\) を素数とする。

1. \(k_{1}\), \(k_{2}\), \(\ldots\), \(k_{n}\) が \(p\) 未満の非負整数のとき、多項係数

   \[ \binom{p}{k_{1},\,k_{2},\,\ldots,\,k_{n}} \]

   が \(p\) で割り切れることを示せ。

2. \(\text{(a)}\) の結果を使って次の合同関係を示せ:

   \[ (x_{1} + x_{2} + \cdots + x_{n})^{p} \equiv x_{1}^{p} + x_{2}^{p} + \cdots + x_{n}^{p} \quad (\text{mod } p) \tag{15.12}\]

   Fermat の小定理を使ってはいけない。この問題は Fermat の小定理の別証明を示すためにある。

3. 次に示す Fermat の小定理 (系 9.10.8) が合同関係 \(\text{(15.12)}\) から直ちに得られることを示せ:

   \[ n^{p-1} \equiv 1 \quad (\text{mod } p) \]

   ここで \(n\) は \(p\) の倍数でない整数を表す。

単純グラフの次数列 (degree sequence) とは、各頂点の次数を並べた広義減少列を意味する。例えば、図 \(\text{15.7}\) にある \(5\) 頂点の木の次数列は \((2,2,2,1,1)\) であり、\(7\) 頂点の木の次数列は \((3,3,2,1,1,1,1)\) である。

与えられた次数列を持つ番号付き木 (頂点集合が \([1..n]\) の木) の個数を計算してみよう。この計算では、問題 15.8 で考えた \(n\) 頂点の番号付き木から \(1\) 以上 \(n\) 以下の整数が並んだ長さ \(n - 2\) の符号への全単射を利用する。

単語における特定の文字の登場回数 (occurrence number) とは、その文字がその単語に現れる回数を意味する。例えば、単語 \(\texttt{65622}\) における文字 \(\texttt{6}\) の登場回数は \(2\) であり、文字 \(\texttt{5}\) の登場回数は \(1\) である。また、単語の登場回数列 (occurrence sequence) とは、単語に含まれる文字の登場回数を並べた広義減少列を意味する。例えば、単語 \(\texttt{65622}\) の登場回数列は \((2,2,1)\) である。

1. \(n\) 頂点の番号付き木の次数列と、その符号の登場回数列の間には単純な関係がある。どのような関係か説明し、その関係が成り立つ理由を説明せよ。特定の次数列を持つ \(n\) 頂点の番号付き木の個数を数え上げる問題は、特定の登場回数列を持つ長さ \(n - 2\) の符号の個数を数え上げる問題に等しいと結論付けよ。

   ヒント: 次数 \(d\) の頂点は符号で何回現れるか？

議論を簡単にするために、特定の次数列を持つ \(9\) 頂点の番号付き木の数え上げを考えよう。\(\text{(a)}\) の結果より、これは特定の登場回数列を持つ長さ \(7\) の符号の数え上げに等しい。

任意の長さ \(7\) の符号に対して、\(\texttt{a}, \texttt{b}, \texttt{c}, \texttt{d}, \texttt{e}, \texttt{f}, \texttt{g}\) が並んだ長さ \(7\) の列であって登場回数列が同じものを、その符号のパターン (pattern) と呼ぶ。ただし、登場回数列は使われていない文字に対応する \(0\) を持つとする。

2. \(\texttt{a}\) を \(3\) 個、\(\texttt{b}\) を \(2\) 個、\(\texttt{c}\) と \(\texttt{d}\) を \(1\) 個含む長さ \(7\) のパターンはいくつあるか？

3. 登場回数列が \((3, 2, 1, 1, 0, 0, 0, 0, 0)\) となるように整数 \(1\), \(2\), \(\ldots\), \(9\) の登場回数を割り当てる方法は何通りあるか？

4. \(7\) を \(3\) 個、\(8\) を \(2\) 個、\(2\) と \(9\) を \(1\) 個含み、パターンが \(\texttt{abacbad}\) である長さ \(7\) の符号を答えよ。

5. 次数列 \((4, 3, 2, 2, 1, 1, 1, 1, 1)\) を持つ \(9\) 頂点の番号付き木の個数が \(\text{(b)}\) と \(\text{(c)}\) の解答の積に等しい理由を説明せよ。

\(6\) 個の頂点を持ち、任意の二頂点が辺で結ばれたグラフを \(G\) とする (つまり、\(G\) は完全グラフ \(K_{6}\) である)。\(G\) に含まれる長さ \(3\) の閉路を三角形 (triangle) と呼ぶ。

頂点を共有する二つの辺からなる集合を隣接組 (incident pair) と呼び、共有される頂点を隣接組の中心 (center) と呼ぶ。つまり、隣接組は異なる三頂点 \(u\), \(v\), \(w\) を使って次のように表せる:

この隣接組の中心は \(v\) である。

1. \(G\) は何個の三角形を持つか？

2. \(G\) は何個の隣接組を持つか？

\(G\) の各辺に赤または青の色を塗ったとする。異なる色の辺を含む三角形または隣接組を多色 (multicolored) と呼ぶことにする。

3. 隣接組を三角形に移す次の写像 \(f\) を考える:

   \[ f\colon \left\{ \langle u\>\text{---}\>v \rangle,\ \langle v\>\text{---}\>w \rangle \right\}\ \ \mapsto\ \ \left\{ \langle u\>\text{---}\>v \rangle, \langle v\>\text{---}\>w \rangle, \langle w\>\text{---}\>u \rangle \right\} \]

   \(f\) は多色な隣接組を多色な三角形に移すことに注目してほしい。そういった多色な隣接組および三角形だけを考えるとき、この写像が \(2\) 対 \(1\) だと示せ。

4. 同じ中心を持つ多色な隣接組の個数は常に \(6\) 個以下だと示せ。その事実を使って、多色な隣接組は最大でも \(36\) 個だと結論付けよ。

   ヒント: \(r\) 個の赤い辺と \(b\) 個の青い辺が接続する頂点は、\(r \cdot b\) 個の異なる多色な隣接組の中心となれる。

5. 友人でない二人を他人 (stranger) と呼ぶことにする。グループ内の全ての二人組が友人である、またはグループ内の全ての二人組が他人であるとき、そのグループを一様 (uniform) と定める。

   \(\text{(a)}\), \(\text{(c)}\), \(\text{(d)}\) の結果から次の命題が導ける理由を説明せよ:

   任意の \(6\) 人グループには、一様な \(3\) 人グループが二つ存在する。

三次元空間の整数座標を移動できるロボットがある。このロボットはステップごとに現在座標のいずれか一つの座標を \(1\) だけ増加させた点に移動できる (それ以外の二つの座標は変化しない)。

1. このロボットが \((0, 0, 0)\) から \((3, 4, 5)\) に移動するときに使用できる経路は何通りあるか？

2. このロボットが \((i, j, k)\) から \((m, n, p)\) に移動するときに使用できる経路は何通りあるか？

\(5\) 枚のトランプカードからなる手札であって次の性質を持つものがいくつあるかそれぞれ答えよ。通常の \(52\) 枚のトランプ一式を仮定する。

1. シーケンス (sequence) とは、\(5\) 枚のカードの数字が連続することを意味する。例えば、次の手札はシーケンスである:

   \[ 5 \heartsuit \quad 6 \heartsuit \quad 7 \spadesuit \quad 8 \diamondsuit \quad 9 \clubsuit \]

   ただし、エースは \(K\) の後ろにも \(2\) の前にもなれるとする。つまり、数字の並びが \(10-J-Q-K-A\) と \(A-2-3-4-5\) の手札はどちらもシーケンスである。ただし、エースは「端」にしかなれないので、数字の並びが \(Q-K-A-2-3\) の手札はシーケンスでない。

   シーケンスの手札はいくつあるか？

2. マッチングスート (matching suit) とは、特定の絵柄が揃うことを意味する。数字はどんなものでも構わない。

   マッチングスートの手札はいくつあるか？

3. ストレートフラッシュ (straight flush) は「シーケンスかつマッチングスート」を意味する。

   ストレートフラッシュの手札はいくつあるか？

4. ストレート (straight) は「マッチングスートでないシーケンス」を意味する。

   ストレートの手札はいくつあるか？

5. フラッシュ (flush) は「シーケンスでないマッチングスート」を意味する。

   フラッシュの手札はいくつあるか？

次に示す設問の答えを次の選択肢から選び、それを選んだ理由を簡単に説明せよ:

1. \(\displaystyle \frac{n!}{(n - m)!}\)
2. \(\displaystyle \binom{n + m}{m}\)
3. \(\displaystyle (n - m)!\)
4. \(\displaystyle m^{n}\)
5. \(\displaystyle \binom{n - 1 + m}{m}\)
6. \(\displaystyle \binom{n - 1 + m}{n}\)
7. \(\displaystyle 2^{mn}\)
8. \(\displaystyle n^{m}\)

設問:

1. 各文字を \(1\) 度まで使用できるとき、\(n\) 個のアルファベットで作成できる長さ \(m\) の単語はいくつあるか？

2. 各文字を何度でも使用できるとき、\(n\) 個のアルファベットで作成できる長さ \(m\) の単語はいくつあるか？

3. 集合 \(A\), \(B\) が \(|A| = m\) と \(|B| = n\) を満たすとき、\(A\) から \(B\) への二項関係はいくつあるか？

4. 集合 \(A\), \(B\) が \(|A| = m\) と \(|B| = n \geq m\) を満たすとき、\(A\) から \(B\) への全域単射関数はいくつあるか？

5. \(m\) 個の区別可能なボールを \(n\) 個の区別可能な壺に入れるとき、入れ方は何通りあるか？ 空の壺や複数のボールが入る壺が生じても構わない。

6. \(m\) 個の区別不能なボールを \(n\) 個の区別可能な壺に入れるとき、入れ方は何通りあるか？ 空の壺や複数のボールが入る壺が生じても構わない。

7. \(m\) 個の区別可能なボールを \(n\) 個の区別不能な壺に入れるとき、入れ方は何通りあるか？ 空の壺や複数のボールが入る壺が生じても構わない。

1. 次の不等式に正整数解は何通りあるか？

   \[ x_{1} + x_{2} + \cdots + x_{10} \leq 100 \]

2. Grumpersonグランパーソン 夫妻は \(3\) 人の子供たちへのクリスマスプレゼントに全部で \(13\) 個の区別できない石炭片を贈ろうと考えている。どの子供も少なくとも \(1\) 個以上の石炭片を手にする必要があるとき、石炭片の贈り方は何通りあるか？

\(C_{41}\) を頂点集合が \(\left\{ 0, 1, \ldots, 40 \right\}\) で辺集合が次の集合であるグラフとする:

また、\(K_{41}\) を同じ頂点集合上の完全グラフとする。

次の設問に答えよ。冪乗、二項係数、階乗を使った式を解答すること。

1. \(K_{41}\) は何本の辺を持つか？

2. \(K_{41}\) から \(K_{41}\) への同型写像はいくつあるか？

3. \(C_{41}\) から \(C_{41}\) への同型写像はいくつあるか？

4. 彩色数 \(\chi(K_{41})\) を求めよ。

5. 彩色数 \(\chi(C_{41})\) を求めよ。

6. \(K_{41}\) の全域木は何本の辺を持つか？

7. \(41\) 個の頂点を持つ木の隣接しない二頂点の間に辺を加えたグラフを \(G\) とする。\(G\) は最大で何個の閉路を持つか？

8. \(K_{41}\) の全域木が持つ葉の最小個数を答えよ。

9. \(K_{41}\) の全域木は最大で何個の葉を持つか？

10. \(C_{41}\) は何個の全域木を持つか？

11. \(K_{41}\) は何個の全域木を持つか？

12. \(K_{41}\) に長さ \(10\) の路はいくつあるか？

13. \(K_{41}\) に長さ \(10\) の閉路はいくつあるか？

グループ (人の集まり) に関する性質を次に示す。それぞれについて、その性質が満たされると保証される最小のグループの人数を答えるか、どんな大きなグループでも成り立たない可能性があることを示せ。\(1\) 年の長さは \(365\) 日と仮定する (うるう年は考えない)。また、「誕生日」と「誕生月」は誕生年を考慮しないと定める。

1. 誕生日が同じ \(2\) 人がいる。

2. 誕生日が \(1\) 月 \(1\) 日の人がいる。

3. 誕生日の曜日が同じ人が \(3\) 人いる。

4. 誕生月が同じ人が \(4\) 人いる。

5. 誕生日がちょうど \(7\) 日だけ離れている \(2\) 人がいる。

鳩の巣原理を使って次の設問に答えよ。それぞれの問題について、「鳩」と「巣穴」、そして鳩を巣穴に対応付ける規則が何かを意識して解答を作成すること。

1. ある工科大学では、全ての学生が \(9\) で始まる \(9\) 桁の学生番号を持つ。講義に \(75\) 人が出席しているとき、各桁の和が同じ学生番号を持つ \(2\) 人の学生がいる理由を説明せよ。

2. 整数の \(100\) 要素集合には差が \(37\) の倍数である組が含まれる理由を説明せよ。

3. 単位円の内部 (境界含まず) にある \(5\) 個の点の中には、距離が \(1/\sqrt{2}\) 未満の二点が含まれる理由を説明せよ。

4. 集合 \(\left\{ 1, 2, 3, \ldots, 2n \right\}\) の任意の \(n + 1\) 要素部分集合には連続する (ある \(k\) を使って \(k\), \(k + 1\) と書ける) 二要素が含まれる理由を説明せよ。

1. 任意の正整数は \(70\), \(700\), \(7770\) のように一つ以上の \(7\) の後ろに一つ以上の \(0\) が続く正整数のいずれかを割り切ることを示せ。

   ヒント: \(7\), \(77\), \(777\), \(7777\), \(\ldots\)

2. \(2\) でも \(5\) でも割り切れない正整数の倍数には、十進表記が \(7\) だけからなる整数が存在すると結論付けよ。

この問題では、\(3^{n}\) の十進表記が \(2013\) 個の連続する \(0\) を持つような \(n\) の存在を証明する。

1. 次の条件を満たす非負整数 \(n\) が存在すると示せ:

   \[ 3^{n} \equiv 1 \quad (\text{mod } 10^{2014}) \]

   ヒント: 鳩の巣原理または Euler の定理を使う。

2. \(3^{n}\) の十進表記が \(2013\) 個の連続する \(0\) を持つような \(n\) が存在すると示せ。

1. \(125\) 枚のカードを使うとき、手品師は第 15.8.3 項で説明した手品を実行できないことを示せ。

   ヒント: \(n\) 枚のカードから選ばれる \(5\) 枚の手札の個数と、\(4\) 枚のカードの列の個数を比較する。

2. カードの枚数が \(124\) 枚以下なら、少なくとも理論上は手品を実行可能だと示せ。

   ヒント: Hall の定理と次数制約 (定義 12.5.5) の性質を利用する。

第 15.8.3 項では、助手から \(4\) 枚のカードを見せられた手品師が \(5\) 枚目のカードを当てる手品を説明した。これと同様の手法を使って、聴衆が \(9\) 枚のカードを選び、助手がそこから \(7\) 枚を選んで手品師に見せ、手品師が残りの \(2\) 枚のカードを当てる手品を説明せよ。

集合 \(\left\{ 1, 2, 3, \ldots, 4n \right\}\) の任意の \(2n + 1\) 要素部分集合には差が \(2\) の二要素が含まれることを鳩の巣原理で示せ。何が「鳩」と「巣穴」に対応するか、そして鳩を巣穴に対応付ける規則が何かを明確に説明すること。

\(101\) 個の整数の列を

とする。\(0 \leq m < n \leq 101\) を満たす二整数 \(m\), \(n\) に対する列

を部分列 (subsequence) と呼ぶ。和が \(100\) で割り切れる部分列が存在すると示せ。

1. \(10^{9} < x < 2 \cdot 10^{9}\) を満たす任意の奇数を \(x\) とする。\(x\) の十進表記が \(0\), \(1\), \(\ldots\), \(9\) を全て含むなら、その十進表記で偶数が連続することを示せ。

   ヒント: 最初の桁と最後の桁の偶奇性について何が言えるか？

2. \(n \geq 2\) 個の頂点を持つ有限無向グラフには次数が等しい二頂点が存在すると示せ。

   ヒント: 次数が \(0\) の頂点が存在するかどうかで場合を分ける。

集合 \(\left\{ 1, 2, 3, \ldots, 2n \right\}\) の任意の \(n + 1\) 要素部分集合には、大きい方を小さい方で割ったときの商が \(2\) の冪である二要素が存在すると鳩の巣原理を使って示せ。何が「鳩」と「巣穴」に対応するか、そして鳩を巣穴に対応付ける規則が何かを明確に説明すること。

ヒント: それぞれの整数を奇数と \(2\) の冪の積で表す。

1. 各要素が赤・白・青のいずれかで塗られた \(82 \times 4\) の矩形行列を \(R\) とする。\(R\) を構成する \(82\) 個の行の中に、全く同じ順番で各要素に色が塗られた二つの行が存在する理由を説明せよ。

2. \(R\) には同じ色の \(4\) 要素であって矩形の四隅を構成するものが存在すると結論付けよ。

3. \(\text{(b)}\) の結論は \(R\) が行を \(19\) 個しか持たないときでも成り立つと示せ。

   ヒント: 長さ \(4\) の行から \(2\) 個の位置を選び、それらを同じ色に塗る方法は何通りあるか？

第 15.8.6 項では、隠されたカードを当てる手品は聴衆の選ぶカードが \(4\) 枚のとき不可能だと示した。ただ、方式を少し変えると手品は可能になる: 助手が隠されたカードを除く \(3\) 枚を手品師に伝えるとき、隠されたカードを裏返しにした計 \(4\) 枚のカードの列を手品師に見せるなら、裏返しになったカードの数字と絵柄を手品師に伝えることができる。これを「裏返し方式の \(4\) 枚カード手品」と呼ぶことにする。

例えば、聴衆の選んだカードが \(\left\{ 9 \heartsuit,\ 10 \diamondsuit,\ A \clubsuit,\ 5 \clubsuit \right\}\) のとき、助手は \(4\) 枚のカードの任意の置換において任意のカードを裏返しにした列を手品師に見せることができる。例を二つ示す:

1. 裏返し方式の \(4\) 枚カード手品を二部マッチング問題としてモデル化せよ。二部マッチングが存在し、理論上は助手が手品師に裏返しのカードが何かを伝えられると示せ。

2. 裏返し方式の \(4\) 枚カード手品を人間が実行する手法⁵を次に示す:

   Case 1:

   [同じ絵柄のカードが \(2\) 枚以上あるとき] その絵柄を \(x\) とする。このとき、助手は以前の方式と同様の方法で手品師に情報を伝える: 絵柄が \(x\) の \(2\) 枚の中で数字が「時計回り」に関して前にある方を列の \(1\) 枚目として表向きに配置し、もう一方を裏向きに配置する。後は、\(1\) 枚目のカードの数字から時計回りにどれだけ進んだ位置に裏向きのカードの数字があるかを伝える \(1\) 以上 \(6\) 以上のオフセットを、絵柄が \(x\) の裏向きカードと残りの \(2\) 枚の表向きカードの順序を使って伝える。

   Case 2:

   [\(4\) 枚のカードが全ての異なる絵柄を持つとき] \(4\) 種類の絵柄に前もって \(0\), \(1\), \(2\), \(3\) の数字を割り当て、手品師と助手でその割り当てに合意しておく。助手は \(4\) 枚のカードの数字の和を \(4\) で割った余り \(s\) を計算し、絵柄が \(s\) のカードを \(1\) 枚目として裏向きに並べる。後は、裏返しになったカードの数字を表向きに並べる残りの \(3\) 枚で伝える。

   二つ目の場合において、助手から \(4\) 枚のカードの列を見せられた手品師が裏返しになったカードをどのように言い当てるか説明せよ。

3. 裏返し方式の \(4\) 枚カード手品を実行する任意の手法を応用すると、以前に説明した方式 (聴衆が \(5\) 枚を選び、助手がそこから \(4\) 枚を手品師に見せる方式) の手品を \(52\) 枚の通常のトランプカード一式にジョーカーを加えた \(53\) 枚のカードを使って実行できる。その方法を説明せよ。

集合 \(\left\{ 1, 2, 3, \ldots, 4n \right\}\) の任意の \(2n + 1\) 要素部分集合を \(X\) とする。\(2n\) を割り切る任意の正整数 \(j\) に対して、差が \(j\) の \(X\) の二要素が存在すること鳩の巣原理を使って示せ。何が「鳩」と「巣穴」に対応するか、そして鳩を巣穴に対応付ける規則が何かを明確に説明すること。

円周が \(1\) の円を考える。その円周上の任意の点に印をつける。続いて、そこから時計回りに \(\sqrt{2}\) だけ円周を進んだ位置に印を付ける。\(\sqrt{2}\) だけ進むと円を \(1\) 周以上するので、この点は初期位置から \(\sqrt{2} - 1\) だけ進んだ位置に等しい。これと同様の処理を続けるとする。つまり、初期位置から時計回りに次の距離だけ進んだ位置に印を付ける:

これから鳩の巣原理を使って、印の付いた点が稠密ちゅうみつ (dense) である事実を証明する: つまり、円周上の任意の点 \(p\) と任意の \(\varepsilon > 0\) に対して、\(p\) からの距離が \(\varepsilon\) 以下である印の付いた点が存在することを示す。

1. 印が二回付けられる点が存在しないことを示せ。つまり、初期位置から時計回りに計った距離が \(k \sqrt{2}\) および \(m \sqrt{2}\) である印の付いた二点について、それらが等しいのは \(k = m\) のときに限ると示せ。

2. 印が付けられる最初の \(n > 1\) 個の点の中に、距離が \(1/n\) 以下の \(2\) 点が存在することを示せ。

3. 円周上の任意の点は印の付いた点からの距離が \(1/n\) 以内だと示せ。ここから、円周上で印の付いた点が稠密だと分かる。

通常の \(52\) 枚のトランプ一式には、\(4\) 種類の絵柄のカードが \(13\) 枚ずつ含まれる。鳩の巣原理を使って、命題「通常のトランプ一式から取った \(k\) 枚のカードには、絵柄が同じ \(5\) 枚のカードが必ず含まれる」が真になる最小の \(k\) を求めよ。何が「鳩」と「巣穴」に対応するか、そして鳩を巣穴に対応付ける規則が何かを明確に説明すること。

鳩の巣原理を使って、命題「整数を要素とする任意の \(n\) 要素集合には、\(211\) を法として合同な \(3\) 個の整数が含まれる」が成り立つ最小の \(n\) を求めよ。何が「鳩」と「巣穴」に対応するか、そして鳩を巣穴に対応付ける規則が何かを明確に説明すること。

集合 \(A_{1}\), \(A_{2}\), \(A_{3}\) が \(|A_{1}| = 100\), \(|A_{2}| = 1{,}000\), \(|A_{3}| = 10{,}000\) を満たすとする。次に示すそれぞれのケースにおいて、値 \(|A_{1} \cup A_{2} \cup A_{3}|\) を求めるか、この値が一意に決定しないことが分かる例を示せ。

1. \(A_{1} \subset A_{2} \subset A_{3}\)

2. どの二集合も共通部分を持たない。

3. 任意の二集合がちょうど \(1\) 個の共通要素を持つ。

4. 任意の二集合が \(2\) 個の共通要素を持ち、三つ全ての集合に共通する要素が \(1\) 個ある。

来年に仕事を何日休めるかを考えているあなたは、来年の平日に \(1\), \(2\), \(3\), \(\ldots\), \(300\) と番号を付け、次のように決心した:

• 番号が偶数の日は「体調が悪くて」と言って休む。

• 番号が \(3\) の倍数の日は「電車が止まっちゃって」と言って休む。

• 番号が \(5\) の倍数の日は布団から出られないので、仕事に行くのを諦める。

来年、あなたが一年間に仕事を休む日数を答えよ。

\(20\) 人の従業員が働く冴えないスタートアップ企業 CantorCorpカントールコープ は、\(6\) 人からなる新しい部署を立ち上げようとしている (連続体仮説の証明が唯一のタスクとなる予定である)。

1. 新しい部署のメンバーの選び方全体の集合を \(D\) とする。\(|D|\) を求めよ。

2. 二人の従業員 Alephアレフ と Bethベス はお互いに気が合わないので、同じ部署に配置されることを好まない。

   Aleph と Beth が含まれるようなメンバーの選び方全体の集合を \(P\) とする。\(|P|\) を求めよ。

3. Beth は Ferdinandフェルディナンド と Georgゲオルグ の両方が所属する部署に配置されることも好まない。

   Beth, Ferdinand, Georg が含まれるようなメンバーの選び方全体の集合を \(Q\) とする \(Q\) を求めよ。

4. \(|P \cap Q|\) を求めよ。

5. 配置に不満を持つ従業員が \(1\) 人以上いるメンバーの選び方全体の集合を \(S\) とする。\(S\) を \(P\) と \(Q\) だけを使って表せ。Aleph と Beth 以外の従業員はどんなメンバーが選ばれても不満を持たないとする。

6. \(|S|\) を求めよ。

7. 配置に不満を持つ従業員が \(1\) 人もいないようなメンバーの選び方は何通りあるか？

8. 突然、CEO は \(6\) 人の部署を \(2\) 個作るべきだと言い出した (もう一つの部署は連続体仮説の反証を唯一のタスクとするらしい)。それぞれの従業員は最大 \(1\) 個の部署に所属できる。従業員の満足度を考えに入れないとき、新しい二つの部署のメンバーの選び方は何通りあるか？

ある企業では、パスワードのセキュリティを高めるために従業員が自分でパスワードを設定するように定めている。次の文字からなる長さ \(10\) の単語を cword と呼ぶ:

パスワードには「\(\text{fail}\)」「\(\text{failed}\)」「\(\text{drop}\)」を部分単語として含まない任意の cword を設定できる。例えば \(\text{adefiloprs}\) と \(\text{srpolifeda}\) はパスワードに設定できる一方で、\(\text{a\underline{drop}eflis}\), \(\text{\underline{failedrop}s}\), \(\text{\underline{drop}e\underline{fails\vphantom{p}}}\) はどれもパスワードに設定できない。

1. \(\text{drop}\) を含む cword はいくつあるか？

2. \(\text{drop}\) と \(\text{fails}\) の両方を含む cword はいくつあるか？

3. 包除則を使って、パスワードに設定可能な文字列の個数を表す簡単な算術式を求めよ。解答には階乗が含まれていても構わない。

平面上の整数座標間を移動する点がたどる経路の個数を考えよう。各ステップで可能な動作は「\(x\) 方向に \(1\) だけ移動する」と「\(y\) 方向に \(1\) だけ移動する」の二つだけとする。

1. \((0, 0)\) から \((20, 30)\) まで移動する経路はいくつあるか？

2. \((0,0)\) から \((20, 30)\) まで移動する経路であって \((10, 10)\) を通過するものはいくつあるか？

3. \((0,0)\) から \((20, 30)\) まで移動する経路であって \((10, 10)\) と \((15, 20)\) を通過しないものはいくつあるか？

   ヒント: \(P\) を \((0, 0)\) から \((20, 30)\) まで移動する経路全体の集合、\(N_{1}\) を \((10, 10)\) を通過する \(P\) の要素全体の集合、\(N_{2}\) を \((15, 20)\) を通過する \(P\) の要素全体の集合とする。

高校レベルの代数だけを使って包除則 (規則 15.9.3) を導出してみよう。

1. 多くの高校生は次の等式を見ただけで震え上がってしまうだろう:

   \[ \prod_{i=1}^{n} (1 + x_{i}) = \sum_{I \subseteq \left\{ 1, \ldots, n \right\}} \prod_{j \in I} x_{j} \tag{15.13}\]

   しかし、この等式の意味を高校生は知っているはずである。その事実を伝えるために、具体的な \(n\) に対する例を示せ。

\(S_{1}\), \(S_{2}\), \(\ldots\), \(S_{n}\) を有限集合の列、\(U ::= \bigcup S_{i} \) をそれらの和集合とする。包除則は次の等式である:

では包除則の証明に取り掛かろう。任意の集合 \(S\) に対して、そのメンバーシップ関数 (membership function) を \(M_{S}\) で表すことにする:

さらに、\(M_{S_{i}}\) を \(M_{i}\) と略記する。また、集合の補集合は \(U\) に関する補集合を意味すると定める。つまり、\(T \subseteq U\) に対して次のように定義する:

2. \(T \subseteq U\) と \(I \subseteq [1..n]\) に対して次の等式が成り立つことを確かめよ:

   \[ M_{\overline{\mathstrut T}} = 1 - M_{T} \tag{15.14}\]
   \[ M_{(\bigcap\limits_{i \in I} \! S_{i})} = \prod_{i \in I} M_{i} \text{\LARGE\mathstrut} \tag{15.15}\]
   \[ M_{(\bigcup\limits_{i \in I} \! S_{i})} = 1 - \prod_{i \in I} (1 - M_{i}) \tag{15.16}\]

等式 \(\text{(15.15)}\) は \(I\) が空集合でも成り立つ点に注意してほしい。なぜなら、慣習的に \(0\) 個の項の積は \(1\) と定義され、\(0\) 個の集合の共通部分 \(\bigcap_{\ i \in \varnothing} S_{i}\) は \(\overline{\mathstrut \varnothing} ::= U\) と定義されるからである。

3. 等式 \(\text{(15.13)}\), \(\text{(15.16)}\) を使って次の等式を示せ:

   \[ M_{U} = \sum_{\varnothing \neq I \subseteq \left\{ 1, \ldots, n \right\}} (-1)^{|I| + 1} \prod_{j \in I} M_{j} \tag{15.17}\]

4. 全ての \(T \subseteq U\) に対する次の等式を示せ:

   \[ |T| = \sum_{u \in U} M_{T} (u) \tag{15.18}\]

5. ここまでの結果を使って等式 \(\text{(I-E)}\) を示せ。

6. 最後に、等式 \(\text{(I-E)}\) から次の等式が直ちに導かれることを示せ:

   \[ |U| = \sum_{i=1}^{n} (-1)^{i+1} \sum_{\substack{I \subseteq [1..n] \\[3pt] |I| = i}} \left| \, \bigcap_{j \in I} S_{i} \, \right| \tag{15.19}\]

   包除原理 (inclusion-exclusion principle) が意味するのは等式 \(\text{(15.19)}\) である場合が多い。

集合 \(\left\{ 1, 2, \ldots, n \right\}\) の置換 \((x_{1}, x_{2}, \ldots, x_{n})\) であって全ての \(i\) で \(x_{i}\neq i\) が成り立つものを攪乱 (derangement) と呼ぶ。例えば \((2,3,4,5,1)\) は攪乱であり、\((2,1,3,5,4)\) は第 \(3\) 要素に \(3\) を持つので攪乱ではない。攪乱の個数を計算してみよう。

この計算は攪乱でない置換の個数に注目すると簡単になる。\(x_{i} = i\) が成り立つ (そのため攪乱でない) 置換 \((x_{1}, x_{2}, \ldots x_{n})\) 全体の集合を \(S_{i}\) とする。このとき、攪乱でない置換全体の集合は次のように表せる:

1. \(|S_{i}|\) を求めよ。

2. 異なる \(i\), \(j\) に対する \(|S_{i} \cap S_{j}|\) を求めよ。

3. 相異なる \(i_{1}\), \(i_{2}\), \(\ldots\), \(i_{k}\) に対する \(|S_{i_{1}} \cap S_{i_{2}} \cap \cdots \cap S_{i_{k}}|\) を求めよ。

4. 包除則を使って、攪乱でない置換の個数を表す式を求めよ。解答する式は集合 \(S_{1}\), \(S_{2}\), \(\ldots\), \(S_{n}\) の任意個の共通部分の要素数を持っていて構わない。

5. \(\text{(d)}\) で解答した式は \(|S_{i_{1}} \cap S_{i_{2}} \cap \cdots \cap S_{i_{n}}|\) の形をした項をいくつ持つか？

6. ここまでの結果を使って、攪乱でない置換の個数が次の式で表されると示せ:

   \[ n! \left( \frac{1}{1!} - \frac{1}{2!} + \frac{1}{3!} - \cdots (-1)^{n-1} \frac{1}{n!} \right) \]

   攪乱の個数が次の式で表されると結論付けよ:

   \[ n! \left(1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \cdots (-1)^{n} \frac{1}{n!} \right) \]

7. \(n\) が無限大に向かうとき、置換全体に占める攪乱の割合は特定の定数に向かう。この定数を求めよ。

   ヒント: 次の等式が成り立つ:

   \[ e^{x} = 1 + x + \frac{x^{2}}{2!} + \frac{x^{3}}{3!} + \cdots \]

\(n\) 以下の整数に素数はいくつあるだろうか？ \(n\) が大きいときの解答を計算する有用な手段が包除則によって提供される。正確に言えば、包除則を使うと \(n\) 以下の合成数 (素数でない整数) の個数を表す式が得られる。その値を \(n\) から引けば素数の個数となる。

\(C_{n}\) を \((1..n]\) に含まれる合成数全体の集合、\(A_{m}\) を \((m..n]\) に含まれる \(m\) の倍数全体の集合とする。この定義より \(m \geq n\) なら \(A_{m} ::= \varnothing\) が分かる。よって次の等式が成り立つ:

1. \(m \; | \; k\) なら \(A_{m} \supseteq A_{k}\) だと示せ。

2. 等式 \(\text{(15.20)}\) の右辺が次の式に等しいと示せ:

   \[ \bigcup_{\text{素数 } p\ \leq \sqrt{n}} \hspace{-8pt} A_{p} \tag{15.21}\]

3. \(m \geq 2\) なら \(|A_{m}| = \left\lfloor n/m \right\rfloor - 1\) だと示せ。

4. \(a\), \(b\) を \(n\) 以下の互いに素な二整数とする。\((A_{a} \cap A_{b}) - A_{ab}\) に含まれる唯一の整数を答えよ。

5. 素数を \(2\) 個以上集めた集合を \(\mathcal{P}\) とする。次の式を単純化せよ:

   \[ \left| \, \bigcap_{p \in \mathcal{P}} A_{p}\, \right| \]

6. 包除則を使って、\(|C_{150}|\) を集合 \(A_{2}\), \(A_{3}\), \(A_{5}\), \(A_{7}\), \(A_{11}\) およびこれらの共通部分の要素数を使って表せ。空集合である共通部分の要素数は無視してよい。例えば、上記の集合の任意の \(4\) 個の共通部分は空集合である。

7. \(\text{(f)}\) の結果を使って、\(150\) 以下の素数の個数を求めよ。

系 9.10.11 は Euler の \(\phi\) 関数が次の等式を満たすと示す:

ここで \(n\) は整数、\(p_{1}\), \(p_{2}\), \(\ldots\), \(p_{m}\) は \(n\) の素因数分解である。包除則を使うと、この事実の別証明が得られる。

この証明では、和の総乗に関する次の単純な代数的恒等式が利用される:

1. 等式 \(\text{(15.23)}\) が \(n = 3\) のとき成り立つことを確かめよ。

2. 等式 \(\text{(15.23)}\) が成り立つ理由を簡単に説明せよ。

等式 \(\text{(15.22)}\) を証明するために、整数 \(n\) と互いに素でない \([0..n)\) の要素全体の集合を \(S\) とする。このとき \(\phi(n) = n - |S|\) である。

3. \(C_{a}\) を \([0..n)\) に含まれる \(a\) の倍数全体の集合とする:

   \[ C_{a} ::= \left\{ k \in [0..n) \; | \; k \text{ は } a \text{ の倍数} \right\} \]

   次の等式が成り立つ理由を説明せよ:

   \[ S = \bigcup_{i=1}^{m} C_{p_{i}} \tag{15.24}\]

\(C_{p_{i}}\) 同士の共通部分の要素数は簡単に求まるので、包除則を使えば和集合 \(\text{(15.24)}\) の要素数を計算できる。

4. \(p\), \(q\), \(r\) を \(n\) を割り切る異なる素数とする。次の等式が成り立つと示せ:

   \[ |C_{p} \cap C_{q} \cap C_{r}| = \frac{n}{pqr} \]

\(\text{(d)}\) で示した等式は当然ながら任意個の \(C_{p}\) の共通部分に一般化できる。ここからは、任意の非空部分集合 \(I \subseteq [1..m]\) に対して次の等式が成り立つと仮定する:

なお、等式 \(\text{(15.25)}\) は実際には \(I = \varnothing\) のときも成り立つ。なぜなら、慣習的に \(0\) 個の集合の共通部分は \(\overline{\mathstrut \varnothing} ::= [0..n)\) と定義され、\(0\) 個の項の積は \(1\) と定義されるからである。

5. \(S\) の要素数は次のように変形できる。各行の式変形を正当化せよ:

   \[ \begin{align*} |S| &= \left|\, \bigcup_{i=1}^{m} C_{p_{i}}\, \right| \\ &= \sum_{\varnothing \neq I \subseteq [1..m]} (-1)^{|I| + 1} \left| \, \bigcap_{i \in I} C_{p_{i}} \, \right| \\ &= n + \sum_{ I \subseteq [1..m]} (-1)^{|I| + 1} \left| \, \bigcap_{i \in I} C_{p_{i}} \, \right| \\ &= n - \sum_{ I \subseteq [1..m]} (-1)^{|I| } \left| \, \bigcap_{i \in I} C_{p_{i}} \, \right| \\[20pt] &= n - \sum_{ I \subseteq [1..m]} (-1)^{|I| } \frac{n}{\displaystyle \ \,\prod_{j \in I} p_{j}\ \,} \\[20pt] &= n - n \sum_{ I \subseteq [1..m]} \frac{1}{\displaystyle \ \,\prod_{j \in I} (-p_{j})\ \,} \\[20pt] &= n - n \sum_{ I \subseteq [1..m]} \prod_{j \in I} \left( - \frac{1}{p_{j}} \right) \\[20pt] &= n - n \prod_{i=1}^{m} \left( 1 - \frac{1}{p_{i}} \right) \end{align*} \]

6. \(\text{(e)}\) の結果を使って等式 \(\text{(15.22)}\) を示せ。

\(\texttt{011}\) を部分文字列に持つ長さ \(n\) のビット列の個数を計算しよう。例えば、次の長さ \(14\) の文字列は位置 \(4\) と位置 \(8\) から始まる部分文字列 \(\texttt{011}\) を持つ:

慣習により、長さ \(n - 1\) の文字列は位置 \(0\) から始まって位置 \(n - 1\) で終わることに注意してほしい。以降の議論では \(n \geq 7\) と仮定する。

1. 位置 \(4\) から部分文字列 \(\texttt{011}\) が始まる長さ \(n\) のビット列の個数を \(r\) とする。\(n\) を使って \(r\) を表せ。

2. 位置 \(i\) から部分文字列 \(\texttt{011}\) が始まる長さ \(n\) のビット列全体の集合を \(A_{i}\) とする (\(i > n - 3\) のとき \(A_{i} = \varnothing\) である)。異なる \(i\), \(j\) に対して、共通部分 \(A_{i} \cap A_{j}\) は空集合または \(s\) 要素集合のいずれかとなる。\(n\) を使って \(s\) を表せ。

3. \(A_{i} \cap A_{j}\) が非空集合となる組 \((i, j)\) (\(0 \leq i < j\)) の個数を \(t\) とする。\(n\) を使って \(t\) を二項係数で表せ。

4. 部分文字列 \(\texttt{011}\) を含む長さ \(9\) のビット列はいくつあるか？ 整数または式を解答せよ。式を解答する場合は、これまでに定義した定数 \(r\), \(s\), \(t\) の \(n = 9\) に対する値を使って構わない。

   ヒント: \(\displaystyle \left| \, \bigcup_{i=0}^{8} A_{i} \, \right|\) に包除則を適用する。

\(10\) 人の学生 \(A\), \(B\), \(\ldots\), \(J\) が左から右に一列に並んでいる。この並び順に関する三つの規則を次のように定める:

• 規則 \(\text{I}\): 学生 \(A\) は左端ではない。

• 規則 \(\text{II}\): 学生 \(B\) は学生 \(C\) の隣 (右隣または左隣) にいる。

• 規則 \(\text{III}\): 学生 \(D\) は \(2\) 番目である。

次の設問に答えよ。解答は階乗を含む式で構わない。

1. 三つの規則全てを満たす並び方は何通りあるか？

2. 少なくとも一つの規則を満たす並び方は何通りあるか？

三次元の整数座標上に設置されたロボットがあり、ステップごとにいずれかの軸の正方向に単位長だけ移動できるとする。言い換えれば、ロボットは \((x, y, z)\) から \((x + 1, y, z)\), \((x, y + 1, z)\), \((x, y, z + 1)\) のいずれかに移動できる。二つの三次元整数座標 \(P\), \(Q\) に対して、ロボットが \(P\) から \(Q\) に移動するとき利用できる経路の個数を \(n(P, Q)\) とする。

三次元整数座標 \(A\), \(B\), \(C\), \(D\) を次のように定義する:

1. \(n(A, B)\) を単一の多項係数として表せ。

以降の設問には \(P, Q \in \left\{ A, B, C, D \right\}\) に対する \(n(P,Q)\) だけを使った算術式を答えよ。定数を使ってはいけない。

2. \(B\) を経由して \(A\) から \(C\) に移動する経路はいくつあるか？

3. \(C\) を経由しないで \(B\) から \(D\) に移動する経路はいくつあるか？

4. \(B\) と \(C\) のいずれも経由しないで \(A\) から \(D\) に移動する経路はいくつあるか？

\(52\) 枚のカードからなる通常の (数字が \(13\) 種類、絵柄が \(4\) 種類の) トランプ一式からランダムに引いた \(5\) 枚のカードを手札と呼ぶ。次の設問に対して、階乗・二項係数・多項係数を使った式を答えよ。

1. 手札全体の集合を \(H\) とする。\(|H|\) を求めよ。

2. ペアを持たない手札全体の集合を \(H_{NP}\) とする。つまり、\(H_{NP}\) に属する手札は数字が全て異なる。\(|H_{NP}|\) を求めよ。

3. ストレートの手札全体の集合を \(H_{S}\) とする。つまり、\(H_{S}\) に属する手札は数字が連続する。数字の順序は \((A, 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K, A)\) である。\(A\) が二回現れることに注意してほしい。\(|H_{S}|\) を求めよ。

4. フラッシュの手札全体の集合を \(H_{F}\) とする。つまり、\(H_{F}\) に属する手札は \(5\) 枚全てが同じ絵柄を持つ。\(|H_{F}|\) を求めよ。

5. ストレートフラッシュの手札全体の集合を \(H_{SF}\) とする。つまり、\(H_{SF}\) に属する手札はストレートかつフラッシュである。\(|H_{SF}|\) を求めよ。

6. ハイカードの手札全体の集合を \(H_{HC}\) とする。つまり、\(H_{HC}\) に属する手札はペア・ストレート・フラッシュのいずれでもない。\(|H_{NP}|\), \(|H_{S}|\), \(|H_{F}|\), \(|H_{SF}|\) を使って \(|H_{HC}|\) を表せ。

次の等式の代数的証明と組合せ論的証明を示せ:

次の等式の組合せ論的証明を示せ:

多項定理 (定理 15.6.5) によれば、\((w + x + y + z)^{n}\) は次の項の和として表される:

1. \((w + x + y + z)^{n}\) を表す和では何個の項が足されるか？

2. 多項係数の和は簡単な式で表せる。どんな式か？

   \[ \sum_{\substack{r_{1} + r_{2} + r_{3} + r_{4}\,=\,n \\[3pt] r_{1},\, r_{2},\, r_{3},\, r_{4}\,\in\,\mathbb{N}}} \binom{n}{r_{1},\, r_{2},\, r_{3},\, r_{4}} =\ ? \tag{15.26}\]

   ヒント: \((w + x + y + z)^{n}\) を展開して同じ次数の項をまとめない状態の式は、項をいくつ持つか？

1. \(c\) をちょうど \(1\) 個含み、その他の部分には \(a\) または \(b\) が並んだ長さ \(n\) の列全体の集合を \(S\) とする。\(|S|\) を二つの異なる方法で数え上げることで、次の等式の組合せ論的証明を示せ:

   \[ n 2^{n-1} = \sum_{k=1}^{n} k \binom{n}{k} \tag{15.27}\]

2. \((1 + x)^{n}\) に二項定理を適用して得られる等式の両辺を微分することで、代数的に等式 \(\text{(15.27)}\) を示せ。

次の式に等しいさらに単純な式を答えよ。解答が正しいことの代数的証明と組合せ論的証明の両方を示せ。

1. \(\displaystyle \sum_{i=0}^{n} \binom{n}{i}\)
2. \(\displaystyle \sum_{i=0}^{n} \binom{n}{i} (-1)^{i}\)

   ヒント: 偶数個の \(1\) を含む長さ \(n\) のビット列の集合と、奇数個の \(1\) を含む長さ \(n\) のビット列の集合を考える。

整数列の第 \(k\) 列が整数 \(k\) であるとき、その要素は定位置にある (in place) と言うことにする⁶。例えば、次の整数列

では、ちょうど \(1\), \(2\), \(6\), \(7\), \(8\) だけが定位置にある。\([1..n]\) の置換を定位置にない要素の個数で分類することを考えよう。ここから次の等式の組合せ論的証明が得られる:

\([1..n]\) の置換 \(\pi\) に対して、\(\pi\) で定位置にない最大の整数を \(\operatorname{mnp}(\pi)\) で表すと定める。例えば \(n = 8\) なら次の等式が成り立つ:

1. 全ての要素が定位置にある \([1..n]\) の置換はいくつあるか？

2. \(\operatorname{mnp} (\pi) = 1\) を満たす \([1..n]\) の置換はいくつあるか？

3. \(\operatorname{mnp} (\pi) = k\) を満たす \([1..n]\) の置換はいくつあるか？

4. 等式 \(\text{(15.28)}\) が成り立つと結論付けよ。

次の等式の組合せ論的証明を示せ:

1. 次の等式の組合せ論的証明を示せ:

   \[ \sum_{i=0}^{n} \binom{n}{i} = 2^{n} \]

   代数的証明は解答として認めない。

2. ある等式の組合せ論的証明を次に示す。この証明が示す等式を答えよ。

   証明 Stinkyスティンキー Petersonピーターソン は \(n\) 匹のイモリ、\(t\) 匹のカエル、\(s\) 匹のカタツムリを飼っている。都合の良いことに、彼が生活している寮には彼を除いて \(n + t + s\) 人の学生がいる (学生は区別可能で、同じ種類の生き物は区別不能だと仮定する)。Stinky はそれぞれの学生のベッドに生き物を置くことを計画している。ベッドに対する生き物の置き方全体の集合を \(W\) とする。

   1. カタツムリを置くベッドを最初に選び、残ったベッドからカエルを置くベッドを選び、最後に残ったベッドにイモリを置く方法が考えられる。この方法からは、\(|W|\) が等式の左辺に等しいと分かる。

   2. イモリまたはカタツムリがふさわしいベッドを最初に選び、その中からイモリを置くベッドを選ぶ方法も考えられる (このときカタツムリとカエルを置くベッドも決定する)。この方法からは、\(|W|\) が等式の右辺に等しいと分かる。

   以上より、二つの式は等しい。 ■

(組合せ論的証明は本当の証明である。他の手法による証明と同じように厳密であるだけではなく、代数的証明では得られない直感的な理解が得られることも多い。ただ、組合せ論的証明がここに示した証明ほど愉快なことは少ない。)

次の等式の組合せ論的証明を示せ:

ヒント: \(n\) 個の \(\texttt{0}\) と \(k + 1\) 個の \(\texttt{1}\) 個が並んだビット列の個数を、最も右にある \(\texttt{1}\) より前にある \(\texttt{0}\) の個数 \(i\) に注目して数え上げる。

多項定理 (定理 15.6.5) によれば、\((w + x + y + z)^{n}\) は次の項の和として表される:

1. \((w + x + y + z)^{n}\) を表す和では何個の項が足されるか？

2. 多項係数の和は簡単な式で表せる:

   \[ \sum_{\substack{r_{1} + r_{2} + \cdots + r_{k} = n \\[3pt] r_{1},\, r_{2},\, \ldots,\, r_{k} \in \mathbb{N}}} \binom{n}{r_{1},\, r_{2},\, \ldots,\, r_{k}} = k^{n} \tag{15.29}\]

   この等式の組合せ論的証明を示せ。

   ヒント: \((w + x + y + z)^{n}\) を展開して同じ次数の項をまとめない状態の式は、項をいくつ持つか？

あなたはスタートアップ企業の採用担当であり、\(n\) 人の応募者の中から \(m\) 人のチームを選び、さらにその \(m\) 人の中から \(k\) 人のマネージャーを選ぼうとしている。あなたは「情報科学のための数学」の講義を取っていたので、チームとマネージャーの選び方の個数は

だと分かっていた。しかし、Harvard Business School 卒の CFO は次の式が正しいと主張してきた:

あなたは当然のことをする ── CFO あるいは Harvard Business School を馬鹿にする ── 前に、CFO が示した式が合っているかどうかを確認することにした。

1. あなたの式と CFO の式が等しいことの組合せ論的証明を示せ。

2. 組合せ論的証明が正しいことの確認として、同じ事実の代数的証明を示せ。

毎日、MIT の学生は朝食を \(b\) 個の選択肢の中から選び、昼食を \(l\) 個の選択肢の中から選び、夕食を \(d\) 個の選択肢の中から選ぶ。全ての食事でドリトスが選択肢の一つに含まれているものの、健康のためドリトスを食事としていいのは一日に一食までと決まっている。可能な三食の選び方の個数に注目することで、次の等式の組合せ論的証明を示せ:

代数的証明は解答として認めない。

次の等式の組合せ論的証明を示せ:

ヒント: \([0..n]\) の \(3\) 要素部分集合を、最大要素ごとに数える。