「デジタル・ノルム付き集合と列挙」において:
直積や直和に適当なノルムを入れて、その体積関数を計算することは、組み合わせ的な練習問題になります。
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
こんなかな? このテの組み合わせの計算は苦手なので、間違っていたら教えてください。