このブログの更新は Twitterアカウント @m_hiyama で通知されます。
Follow @m_hiyama

メールでのご連絡は hiyama{at}chimaira{dot}org まで。

はじめてのメールはスパムと判定されることがあります。最初は、信頼されているドメインから差し障りのない文面を送っていただけると、スパムと判定されにくいと思います。

参照用 記事

デジタルな総和ノルムの表面積関数の例

デジタル・ノルム付き集合と列挙」において:

直積や直和に適当なノルムを入れて、その体積関数を計算することは、組み合わせ的な練習問題になります。

A = (A, Z, ν) がデジタル・ノルム付き集合のとき、Aのn個の直積 An = A× ... ×A (n個) に総和ノルムを入れたデジタル・ノルム付き集合を考えます。総和ノルムは、次のように定義されます。

  • ν(a1, ..., an) := ν(a1) + ... + ν(an)

Aは固定して、Anの体積関数を λk.V(n, k)、表面積関数を λk.S(n, k) とします。念の為に、定義を書いておくと:

  • V(n, k) := card(An[≦ k])
  • S(n, k) := card(An[= k])

V(n, k) と S(n, k) は関連していて、どちらか一方からもう一方を定義できます。

  • V(n, k) = S(n, 0) + S(n, 1) + ... + S(n, k)
  • S(n, k) = V(n, k) - V(n, k -1)

総和ノルムの定義から、次が成立します。

  • An+1[= k] = A[= 0]×An[= k] + A[= 1]×An[= k -1] + ... + A[= k]×An[= 0]

この等式の両辺の基数(cardinality)を取って:

  • S(n+1, k) = S(1, 0)×S(n, k) + S(1, 1)×S(n, k -1) + ... + S(1, k)×S(n, 0)

S(1, i) = 1 という自明な場合を考えてみると:

  • S(n+1, k) = S(n, k) + S(n, k -1) + ... + S(n, 0)

n = 1, 2 の場合は:

  • S(2, k) = 1 + 1 + ... + 1 (k+1 個) = k + 1
  • S(3, k) = S(2, k) + S(2, k -1) + ... + S(2, 0) = (k + 1) + k + ... + 1 = (k + 1)(k + 2)/2

こんなかな? このテの組み合わせの計算は苦手なので、間違っていたら教えてください。