単元一覧 › 大学院数学 代数的組合せ論

代数的組合せ論の問題

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

、 を通常の大小関係による全順序集合(鎖)とし、直積 に

で半順序を入れる。関数 が、すべての に対して

を満たすとき、 の値を求めよ。

この問題で使うもの

この問題を解けるようになるまで(2 技能)
算数中学高校大学大学院

読み込み中…

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

一覧で見る(前提が先)
  1. 半順序集合のメビウス関数
  2. メビウス反転公式と直積の積公式

ヒント

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

ヒント 1

メビウス反転公式で を累積和 の一次結合として表し、メビウス関数の値は直積の積公式で求めましょう。

ヒント 2

鎖 のメビウス関数は 、、それ以外は です。直積では となります。

ヒント 3

でない寄与は の 点だけで、 となります。

答えと解説

答えを見る
結果を記録する(このブラウザにだけ保存されます):
解説を読む

ステップ 1(メビウス反転). とおくと、 なので、メビウス反転公式より

ステップ 2(鎖のメビウス関数). 鎖では、漸化式 , から

となる(例えば )。

ステップ 3(直積の積公式). である。これが でないのは かつ のときだけで、

ステップ 4(計算). よって

別解

とおく。 は 2 つの鎖の直積なので、 を反転すると( の Möbius 関数は で、鎖では 、それ以外は 0)、(範囲外の は 0)。。検算: 包除の考え方どおり であり、直接 、、、 などを求めて、 となることとも整合する(反転公式の恒等性による)。

この問題の確認

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

間違いを報告する

この問題の誤り・分かりにくい点・難易度や学年のずれを知らせる
どこについての報告ですか

報告の内容と問題の番号を保存します。名前やメールアドレスは保存しません。

関連する問題