圏論の問題
半順序集合 は、対象を の元とし、 のときに限り から への射がちょうど つ存在する(それ以外のときは射が存在しない)圏とみなす。
集合 の分割(空でない互いに素な部分集合(ブロック)への分け方)全体を とし、分割 について「 の各ブロックが のあるブロックに含まれる」ときに と定める(細分による順序)。この半順序集合 を圏とみなしたとき、射(恒等射も含む)の総数を求めよ。
この問題で使うもの
- 圏の定義と有限の圏(説明と入口の問題)
- 組合せ(説明と入口の問題)
- 和の法則・積の法則と樹形図(説明と入口の問題)
この問題を解けるようになるまで(6 技能)
読み込み中…
右端(太枠)がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。
ヒント
行き詰まったら、上から順に 1 つずつ開いてください。
ヒント 1
半順序集合を圏とみなすと、射の個数は を満たす組 の個数に等しい。
ヒント 2
を固定すると、 より細かい分割は の各ブロックを独立に分割して得られるので、その個数はブロックの大きさのベル数の積になる。
ヒント 3
の元をブロックの大きさの型 で分類し、それぞれの個数と、その下にある分割の個数を求める。
答えと解説
答えを見る
どこでつまずきましたか?(選ぶと、戻る場所を案内します)
解説を読む
射の総数は となる組 の個数である。 を固定すると、 となる は の各ブロックをそれぞれ独立に分割して得られるので、その個数は の各ブロックの大きさ に対するベル数 の積である。ここで , , , である。
をブロックの大きさの型で分類する。
- 型 ( 個): 。小計 。
- 型 ( 個): 。小計 。
- 型 ( 個): 。小計 。
- 型 ( 個): 。小計 。
- 型 ( 個): 。小計 。
(確認: 分割の個数は 。)
よって射の総数は
別解
半順序集合を圏とみなしたとき、射 は のときちょうど 1 つなので、射の総数は (恒等射 を含む)に等しい。\n\n各 について、 の細分 の個数は、各ブロックを独立に分割する方法の数なので 。ベル数は 。\n\n の型ごとに:\n- (1 個): → 15。\n- 型 (4 個): → 。\n- 型 (3 個): → 。\n- 型 (6 個): → 。\n- 型 (1 個): 1 → 1。\n\n分割の総数は で整合する。合計 。