1 から 6 の目が均等に出るサイコロを 2 回振ったとき、最大値が 4 になる場合の数は 36 個中いくつでしょう。そうですね。7 通りです。どのように計算しましたでしょうか。4 × 4 - 3 × 3 と計算した方、おめでとうございます。高校入試典型完全理解の方ですか？
4 ぴったりではなくて 4 以下を計算するのがポイントです。これならば「サイコロ A が 4 以下」と「サイコロ B が 4 以下」を独立に数えて掛け算すると良いです。
「サイコロが A が 4 以下」というのは、
- 「サイコロ A が 1 ぴったり」または
- 「サイコロ A が 2 ぴったり」または
- 「サイコロ A が 3 ぴったり」または
- 「サイコロ A が 4 ぴったり」
ですから、1 + 1 + 1 + 1 です。結局、各の x について、最大値が x であるサイコロの目の出方を数えようと思うと、 [ 1, 1, 1, 1, 1, 1 ] を累積和して各点 2 乗して累積和の逆をすれば良いということがわかりました。
max-convolution
さてより一般に、a, b が長さ n の配列であるとき、
c ( k ) = sum ( a [ i ], b [ j ] ), max ( i, j ) = k
で定まる関数 c（これを max-convolution といいます。 ）を計算しましょう。これも同様ですね。max ( i, j ) = k を max ( i, j ) ≦ k に取り替えて、あとから累積和の逆で戻すことにしましょう。するとこの条件は i ≦ k かつ j ≦ k と同値ですから、独立に計算できますね。即ち、a, b それぞれ累積和を取り、各点積を取ってその累積和の逆をすると答えになります。
一般化 max-convolution
ところでこれは、添字集合 [ n ] を一般化して局所有限な束にしてもうまく行きます。即ち L を局所有限な束、R を環、f, g: L → R を（台が有限な）関数であるとして、
( f * g ) ( k ) = sum ( f ( i ) g ( j ) ), i ∨ j = k
で定義される関数 f * g: L → R が、同様に計算できます。なぜならば添字の条件を i ∨ j ≦ k に取り替えるとこれは i ≦ k かつ j ≦ k と同値になり、これは独立に計算できるからです。即ち f, g それぞれゼータ変換して、各点積を取って、メビウス変換をするとよいです。
例えば L として整除束を考えると、いわゆる lcm-convution になり、その逆順束を考えると gcd-convolution になります。
subset-convolution
ところで subset convolution というものがあります。これは、関数 f, g: P ( [ n ] ) → R に対して
( f * g ) ( k ) = sum ( f ( i ) g ( j ) ), k は i と j の非交差和
で定まる関数 f * g のことです。添字の条件を束の言葉でいうと、i ∧ j = 0, i ∨ j = k ということで、先程よりは条件が一つ増えております。
これをどう捌くかなのですが、R を多項式環 R [ x ] に取替えて、f, g の値をただのスカラーから単項式に変更です。具体的には
F ( i ) = f ( i ) x ^ i
と定義します。そうしてブール束（包含関係の定める束）上で一般化 max convolution をすると、先程同様に、H ( k ) 的なところには i ∨ j = k なる i, j がすべて寄与してしまうわけですが、この中から i ∧ j = k なるものだけを抽出しましましょう。そのためには x ^ { #k } における係数を取れば良いです。つまり f, g の値をキーとなる集合の要素数を次数とする単項式に取替えて一般化 max-convolution をしたあと、再びキーとなるど集合の要素数次数における係数をとればよいです。
詳しい説明はここ（Subset Convolutionのアルゴリズム – 37zigenのHP）にありますのでぜひです。（あの？）
モジュラー束上の非交差和畳み込み
以上の議論は一般のモジュラー束上でもうまく行きます。というのも i ∨ j = k であるとき、i ∧ j = 0 は r ( i ) + r ( j ) = r ( i ∨ j ) と同値ですから、subset-convolutiojn で「次数」と言っていたところをランクに取り替えればよいです。
例えば L として整除束を考えると、添字の条件が k = i j, gcd ( i, j ) = 1 になります。
