代数的組合せ論の問題

難易度 4大学院入試の難問レベル証明問題大学院数学代数的組合せ論

$n$ を $0$ 以上の整数とし、 $[n] = {1, 2, \dots, n}$ （ $[0] = \emptyset$ ）とする。 $[n]$ の部分集合のうち、要素の個数が偶数であるものすべてからなる集合
$P_{n} = {S \subseteq [n] : ∣ S ∣ は偶数}$
を包含関係 $\subseteq$ で順序づけた有限半順序集合を考える（ $\emptyset \in P_{n}$ である）。 $P_{n}$ のメビウス関数 $μ$ は、 $S \subseteq T$ をみたす $S, T \in P_{n}$ に対して
$μ (S, S) = 1, U \in P_{n}, S \subseteq U \subseteq T \sum μ (S, U) = 0 (S ⊊ T)$
で定める。

また、有理数係数の形式的冪級数環 $Q [[x]]$ において $cos x = \sum_{i \geq 0} \frac{( - 1 ) ^{i} x ^{2 i}}{( 2 i )!}$ とし、その逆元を
$sec x = \frac{1}{cos x} = m \geq 0 \sum E_{2 m} \frac{x ^{2 m}}{( 2 m )!}$
と書く（ $cos x$ の定数項は $1$ なので逆元が存在し、それが偶数次の項のみからなることは用いてよい）。

$S \subseteq T$ をみたす任意の $S, T \in P_{n}$ に対して、 $∣ T ∖ S ∣$ は偶数であり、
$μ (S, T) = (- 1)^{∣ T ∖ S ∣/2} E_{∣ T ∖ S ∣}$
が成り立つことを証明せよ。

この問題で使うもの

半順序集合のメビウス関数（説明と入口の問題）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

$μ (S, T)$ を $T ∖ S$ の大きさだけで決まる数列に帰着させ、その数列と $(- 1)^{m} E_{2 m}$ が同じ漸化式と初期値をみたすことを示す方針をとる。

ヒント 2

区間 $[S, T]$ は $U \mapsto U ∖ S$ によって「 $T ∖ S$ の偶数個の部分集合全体」と順序同型になる。また $cos x \cdot sec x = 1$ の係数比較から $\sum_{j} (2 j 2 m) (- 1)^{m - j} E_{2 j} = 0 (m \geq 1)$ が得られる。

ヒント 3

$∣ D ∣ = 2 m$ のときの $μ (\emptyset, D)$ を $a_{m}$ とおくと、メビウス関数の定義式で $∣ U ∣ = 2 j$ の $U$ が $(2 j 2 m)$ 個あることから $\sum_{j = 0}^{m} (2 j 2 m) a_{j} = 0 (m \geq 1)$ , $a_{0} = 1$ となる。あとは $b_{j} = (- 1)^{j} E_{2 j}$ がこれをみたすことを確かめ、帰納法で比べる。

採点の観点と模範解答

自分で証明を書いてから、採点の観点で見比べてください。

採点の観点を見る

$∣ T ∖ S ∣$ が偶数であることと、 $U \mapsto U ∖ S$ が区間 $[S, T]$ から $T ∖ S$ の偶数部分集合全体への順序同型であること（逆写像・パリティの保存を含む）を示している（2 点）
メビウス関数が区間の順序構造だけで決まることから、 $μ (S, T)$ が $∣ T ∖ S ∣$ だけの関数 $a_{m}$ になることを述べている（1 点）
メビウス関数の定義式で大きさ $2 j$ の部分集合を数え、 $a_{0} = 1$ , $\sum_{j = 0}^{m} (2 j 2 m) a_{j} = 0 (m \geq 1)$ を導いている（2 点）
$cos x \cdot sec x = 1$ の $x^{2 m}$ の係数比較から $\sum_{j} (2 j 2 m) (- 1)^{m - j} E_{2 j} = δ_{m 0}$ を正しく導いている（2 点）
$(- 1)^{j} E_{2 j}$ が $a_{m}$ と同じ漸化式・初期値をみたすことを符号まで正しく確かめている（2 点）
最高次の係数が $1$ で漸化式が値を一意に定めることを用いた帰納法で $a_{m} = (- 1)^{m} E_{2 m}$ を結論している（1 点）

結果を記録する（このブラウザにだけ保存されます）:

模範解答を読む

記号. 有限集合 $D$ に対し、 $D$ の部分集合で要素の個数が偶数のものすべてを包含関係で順序づけた半順序集合を $Q_{D}$ と書く（ $P_{n} = Q_{[n]}$ ）。

ステップ 1（ $E_{2 m}$ のみたす漸化式）. $cos x \cdot sec x = 1$ の両辺の $x^{2 m}$ の係数を比べる。左辺の $x^{2 m}$ の係数は
$i + j = m \sum \frac{( - 1 ) ^{i}}{( 2 i )!} \cdot \frac{E _{2 j}}{( 2 j )!}$
であり（ $sec x$ は偶数次の項のみなので、 $x^{2 m}$ をつくるのは $x^{2 i} \cdot x^{2 j}$ , $i + j = m$ の積だけ）、右辺の係数は $m = 0$ のとき $1$ 、 $m \geq 1$ のとき $0$ である。両辺に $(2 m)!$ を掛けると
$E_{0} = 1, j = 0 \sum m (2 j 2 m) (- 1)^{m - j} E_{2 j} = 0 (m \geq 1) (1)$
を得る。

ステップ 2（区間の同型）. $S, T \in P_{n}$ , $S \subseteq T$ とし、 $D = T ∖ S$ とおく。 $∣ D ∣ = ∣ T ∣ - ∣ S ∣$ は偶数から偶数を引いたものなので偶数である。 $P_{n}$ における区間 $[S, T] = {U \in P_{n} : S \subseteq U \subseteq T}$ から $Q_{D}$ への写像 $φ (U) = U ∖ S$ を考える。 $S \subseteq U$ より $∣ U ∖ S ∣ = ∣ U ∣ - ∣ S ∣$ は偶数なので $φ (U) \in Q_{D}$ である。逆に $V \in Q_{D}$ に対し $ψ (V) = V \cup S$ とおくと、 $V \cap S = \emptyset$ より $∣ V \cup S ∣ = ∣ V ∣ + ∣ S ∣$ は偶数で、 $S \subseteq V \cup S \subseteq T$ なので $ψ (V) \in [S, T]$ 。 $ψ (φ (U)) = (U ∖ S) \cup S = U$ （ $S \subseteq U$ のため）、 $φ (ψ (V)) = V$ （ $V \cap S = \emptyset$ のため）なので $φ$ は全単射で、 $U \subseteq U^{'} ⟺ U ∖ S \subseteq U^{'} ∖ S$ （ $\Leftarrow$ は両辺に $S$ を合併すればよい）なので $φ$ は順序同型である。

メビウス関数 $μ (S, T)$ の定義式は区間 $[S, T]$ の中の元と順序だけを用いて $μ (S, U)$ （ $U \in [S, T]$ ）を下から順に定めるものなので、順序同型な区間ではメビウス関数の値が一致する。よって
$μ_{P_{n}} (S, T) = μ_{Q_{D}} (\emptyset, D) .$
さらに $∣ D ∣ = ∣ D^{'} ∣$ ならば全単射 $D \to D^{'}$ が順序同型 $Q_{D} \to Q_{D^{'}}$ を誘導するので、 $μ_{Q_{D}} (\emptyset, D)$ は $∣ D ∣$ だけで決まる。 $∣ D ∣ = 2 m$ のときのこの値を $a_{m}$ とおく。示すべきことは、すべての $m \geq 0$ に対して $a_{m} = (- 1)^{m} E_{2 m}$ であることである。

ステップ 3（ $a_{m}$ のみたす漸化式）. $a_{0} = μ (\emptyset, \emptyset) = 1$ である。 $m \geq 1$ とし、 $∣ D ∣ = 2 m$ とする。 $\emptyset ⊊ D$ なので定義から
$U \in Q_{D} \sum μ_{Q_{D}} (\emptyset, U) = 0.$
$U \in Q_{D}$ に対し、 $Q_{D}$ における区間 $[\emptyset, U]$ は $U$ の偶数個の部分集合全体 $Q_{U}$ そのものなので、 $μ_{Q_{D}} (\emptyset, U) = μ_{Q_{U}} (\emptyset, U) = a_{∣ U ∣/2}$ である。 $∣ U ∣ = 2 j$ となる $U \subseteq D$ はちょうど $(2 j 2 m)$ 個あるから
$a_{0} = 1, j = 0 \sum m (2 j 2 m) a_{j} = 0 (m \geq 1) (2)$
を得る。

ステップ 4（ $b_{j} = (- 1)^{j} E_{2 j}$ も同じ漸化式をみたす）. $b_{j} = (- 1)^{j} E_{2 j}$ とおく。 $b_{0} = E_{0} = 1$ 。 $m \geq 1$ のとき、 $(- 1)^{j} = (- 1)^{2 m - j} = (- 1)^{m} (- 1)^{m - j}$ なので、 $(1)$ より
$j = 0 \sum m (2 j 2 m) b_{j} = (- 1)^{m} j = 0 \sum m (2 j 2 m) (- 1)^{m - j} E_{2 j} = 0.$
よって $(b_{j})$ も $(2)$ をみたす。

ステップ 5（帰納法）. $m$ に関する強い帰納法で $a_{m} = b_{m}$ を示す。 $m = 0$ では $a_{0} = 1 = b_{0}$ 。 $m \geq 1$ とし、 $j < m$ のすべてで $a_{j} = b_{j}$ と仮定する。 $(2)$ で $j = m$ の項の係数は $(2 m 2 m) = 1$ なので
$a_{m} = - j = 0 \sum m - 1 (2 j 2 m) a_{j} = - j = 0 \sum m - 1 (2 j 2 m) b_{j} = b_{m}$
（最後の等号はステップ 4 で $(b_{j})$ が $(2)$ をみたすことによる）。よってすべての $m$ で $a_{m} = b_{m}$ 。

（確認: $a_{1} = - 1 = - E_{2}$ , $a_{2} = - (1 - 6) = 5 = E_{4}$ 。）

結論. ステップ 2 とステップ 5 より、 $S \subseteq T$ をみたす任意の $S, T \in P_{n}$ について $∣ T ∖ S ∣ = 2 m$ は偶数で
$μ (S, T) = a_{m} = (- 1)^{m} E_{2 m} = (- 1)^{∣ T ∖ S ∣/2} E_{∣ T ∖ S ∣}$
が成り立つ。 $■$

この問題の確認

AI が作成した問題です。公開前に次の確認を行いました。

別の AI が模範解答を見ずに 3 回証明を試み、3 回証明できました
2 つの AI が独立に、模範解答の証明を 1 ステップずつ確かめました
AI の査読で、条件・解説・表記を確認しました
答えの正しさについて慎重に扱うべき点が見つからなかったため、自動で公開しました

確認の方法について

間違いを報告する

この問題の誤り・分かりにくい点・難易度や学年のずれを知らせる