ブログ名

ながたかなです!

サイコロの目の最大値から理解する subset convolution

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 になります。