代数的組合せ論の問題
、 を通常の大小関係による全順序集合(鎖)とし、直積 に
で半順序を入れる。関数 が、すべての に対して
を満たすとき、 の値を求めよ。
この問題で使うもの
- メビウス反転公式と直積の積公式(説明と入口の問題)
この問題を解けるようになるまで(2 技能)
読み込み中…
右端(太枠)がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。
一覧で見る(前提が先)
ヒント
行き詰まったら、上から順に 1 つずつ開いてください。
ヒント 1
メビウス反転公式で を累積和 の一次結合として表し、メビウス関数の値は直積の積公式で求めましょう。
ヒント 2
鎖 のメビウス関数は 、、それ以外は です。直積では となります。
ヒント 3
でない寄与は の 点だけで、 となります。
答えと解説
答えを見る
どこでつまずきましたか?(選ぶと、戻る場所を案内します)
解説を読む
ステップ 1(メビウス反転). とおくと、 なので、メビウス反転公式より
ステップ 2(鎖のメビウス関数). 鎖では、漸化式 , から
となる(例えば )。
ステップ 3(直積の積公式). である。これが でないのは かつ のときだけで、
ステップ 4(計算). よって
別解
とおく。 は 2 つの鎖の直積なので、 を反転すると( の Möbius 関数は で、鎖では 、それ以外は 0)、(範囲外の は 0)。。検算: 包除の考え方どおり であり、直接 、、、 などを求めて、 となることとも整合する(反転公式の恒等性による)。