代数的組合せ論の問題

難易度 1大学院の講義の例題レベル大学院数学代数的組合せ論

集合 $[6] = {1, 2, 3, 4, 5, 6}$ の集合分割全体を $Π_{6}$ とし、細分による順序（ $σ \leq τ ⟺ σ$ の各ブロックが $τ$ のあるブロックに含まれる）で半順序集合とみなす。 $Π_{6}$ の最大元（ブロックが $[6]$ ただ 1 つの分割）を $1^$ とし、 $μ$ を $Π_{6}$ のメビウス関数とする。

分割
$σ = {{1, 2}, {3, 4}, {5}, {6}}$
に対して、 $μ (σ, 1^)$ の値を求めよ。

この問題で使うもの

ブール束・約数束・分割束のメビウス関数（説明と入口の問題）

この問題を解けるようになるまで（3 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

ヒント

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

ヒント 1

区間 $[σ, 1^]$ がどの分割束と同型かを考える。

ヒント 2

$σ$ より粗い分割は、 $σ$ のブロックをまとめてできる分割である。 $σ$ のブロック全体を 4 個の「点」とみなすとよい。

ヒント 3

$[σ, 1^] ≅ Π_{4}$ であり、 $Π_{n}$ では $μ (0^, 1^) = (- 1)^{n - 1} (n - 1)!$ である。

答えと解説

答えを見る

- 6

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

解説を読む

使う事実. $n$ 元集合の分割束 $Π_{n}$ では
$μ_{Π_{n}} (0^, 1^) = (- 1)^{n - 1} (n - 1)!$
が成り立つ。

区間 $[σ, 1^]$ の形を読む. $σ$ のブロックは $B_{1} = {1, 2}, B_{2} = {3, 4}, B_{3} = {5}, B_{4} = {6}$ の 4 個である。 $τ \geq σ$ となる分割 $τ$ は、 $σ$ のブロックをいくつかずつまとめてできる分割にほかならない。そこで $τ$ に「 ${B_{1}, B_{2}, B_{3}, B_{4}}$ をどうまとめたか」という 4 元集合の分割を対応させると、これは順序を保つ全単射になり
$[σ, 1^] ≅ Π_{4}$
である。このとき $σ$ は $Π_{4}$ の最小元 $0^$ （すべて 1 元ブロック）に、 $1^$ は $Π_{4}$ の最大元に対応する。

値を求める. メビウス関数の値は区間の同型で変わらないので
$μ (σ, 1^) = μ_{Π_{4}} (0^, 1^) = (- 1)^{4 - 1} (4 - 1)! = - 6.$

漸化式による確認. $Π_{4}$ で $μ (0^, x)$ を下から順に求める。
- $0^$ 自身: $μ (0^, 0^) = 1$ 。
- 階数 1 の元（型 $(2, 1, 1)$ ）は $(2 4) = 6$ 個で、各 $μ (0^, x) = - 1$ 。
- 階数 2 の元のうち、型 $(3, 1)$ は $4$ 個で、区間 $[0^, x] ≅ Π_{3}$ より各 $μ (0^, x) = 2$ 。型 $(2, 2)$ は $3$ 個で、区間 $[0^, x] ≅ Π_{2} \times Π_{2}$ より各 $μ (0^, x) = (- 1) \cdot (- 1) = 1$ 。

したがって
$μ (0^, 1^) = - (1 + 6 \cdot (- 1) + 4 \cdot 2 + 3 \cdot 1) = - (1 - 6 + 8 + 3) = - 6$
となり、上の結果と一致する。

別解

区間 $[σ, 1^]$ は、 $σ$ のブロックを併合してできる分割全体である。 $σ$ は 4 個のブロック ${1, 2}, {3, 4}, {5}, {6}$ をもつので、これら 4 個のブロックの集合分割全体と順序同型であり、 $[σ, 1^] ≅ Π_{4}$ となる。メビウス関数は区間のみで決まるので $μ (σ, 1^) = μ_{Π_{4}} (0^, 1^)$ 。\n\n一般に $μ_{Π_{n}} (0^, 1^) = (- 1)^{n - 1} (n - 1)!$ である。確認として漸化式 $\sum_{0^\leq τ \leq 1^} μ (0^, τ) = 0$ を $n = 4$ で用いる。 $μ_{Π_{1}} = 1$ , $μ_{Π_{2}} = - 1$ , $μ_{Π_{3}} = 2$ であり、 $0^$ 以外の $τ$ の区間 $[0^, τ]$ は、型ごとに次の積と同型である。\n- $0^$ （1 個）: $1$ \n- 型 $2 + 1 + 1$ （6 個）: $μ = - 1$ \n- 型 $2 + 2$ （3 個）: $(- 1) (- 1) = 1$ \n- 型 $3 + 1$ （4 個）: $2$ \n- 型 $4$ （ $1^$ 、1 個）: $x$ \n\nよって $1 + 6 (- 1) + 3 (1) + 4 (2) + x = 0$ より $x = - 6$ 。公式 $(- 1)^{3} \cdot 3! = - 6$ とも一致する。\n\n以上より $μ (σ, 1^) = - 6$ 。

この問題の確認

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

別の AI が答えを見ずに 3 回解き、3 回とも同じ答えになりました
プログラムで答えを計算し直し、一致を確認しました
AI の査読で、条件・解説・表記を確認しました
答えの正しさについて慎重に扱うべき点が見つからなかったため、自動で公開しました

確認の方法について

間違いを報告する

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