競技数学解説

一般化simasima special（重み付き集合編）

組み合わせ,OMC,競技数学

396

はじめに

この記事は前の記事の続きです。先にそちらを見ることをおすすめします。

前提知識

この記事と次回の記事は集合論の基礎事項と、群の定義と部分群に関する知識があれば~~理論上は~~読めます。

集合論の基礎事項については、以下を参照ください。

群論の基礎事項については、以下を参照ください。

重み付き集合の定義

集合 $X$ と可換環 $R$ (可換環がわからない人は $R$ を整数全体の集合 $Z$ や有理数全体の集合 $Q$ だと思ってください) をとる。

このとき、 $X$ から $R$ への写像全体の集合を $Set (X, R)$ で表し、この元を $X$ の重み付き部分集合と呼ぶ。

また特に $f \in Set (X, R)$ であって、有限個の $x \in X$ を除いて $f (x) = 0$ となるものを $X$ の重み付き有限部分集合と呼ぶ。また $X$ の重み付き有限部分集合全体の集合を ${Set}_{finsupp} (X, R)$ で表すことにする。

$Set (X, R)$ の元は写像を表しているが、集合のように扱えることが多い。そのため心理学的な側面から集合のように扱うときは $A$ , 写像として扱うときは $f_{A}$ で表すことにする。

また $A \in Set (X, R)$ に対して $supp A = {x \in X ∣ f_{A} (x) \neq 0}$ と定め、 $A$ の台と呼ぶことにする。特に $f_{A} = 0$ ならば $supp A = \emptyset$ となる。
以降しばしば $a \in supp A$ を省略して $a \in A$ と表し、 $A$ の元と呼ぶことにする。

また $A, B \in Set (X, R)$ に対して $supp A \subset supp B$ を省略して $A \subset B$ と表し、 $A$ は $B$ の重み付き部分集合と呼ぶことにする。

さらに通常の意味での $X$ の部分集合 $B$ に対して、 $X$ から $R$ への写像 $f_{B}$ を
$f_{B} (x) = {\begin{cases} 1 & (x \in B) \\ 0 & (x \notin B) \end{cases}$
と定めることで、 $B$ を $Set (X, R)$ の元と見なせる。

重み付き集合における演算

集合 $X, Y$ と可換環 $R$ を取る。 $A \in {Set}_{finsupp} (X, R)$ に対して
$| A | = \sum_{a \in A} f_{A} (a)$ と定め、これを $A$ の濃度と呼ぶことにする。

次に $A, B \in Set (X, R)$ に対して和 $A + B \in Set (X, R)$ を
$x \in X$ に対して $f_{A + B} (x) = f_{A} (x) + f_{B} (x)$ を満たす写像 $f_{A + B}$ により定める。

また $A \in Set (X, R)$ , $c \in R$ に対してスカラー倍 $c A \in Set (X, R)$ を
$x \in X$ に対して $f_{c A} (x) = c f_{A} (x)$ を満たす写像 $f_{c A}$ により定める。

次に $A \in Set (X, R)$ , $B \in Set (Y, R)$ に対して、直積 $A \times B \in Set (X \times Y, R)$ を任意の $x \in X$ , $y \in Y$ に対して
$(f_{A} \times f_{B}) (x, y) = f_{A} (x) f_{B} (y)$
を満たす写像 $f_{A \times B} : = f_{A} \times f_{B}$ により定める。

余談であるが上記の演算によって
$⨁_{n \geq 0} Set (X^{n}, R), ⨁_{n \geq 0} {Set}_{finsupp} (X^{n}, R)$
は次数付き環となる。ただし $Set (X^{0}, R)$ は $R$ を表すものとする。

話を戻して $A, B \in Set (X, R)$ に対してドット積 $A \cdot B \in Set (X, R)$ を
$x \in X$ に対して $f_{A \cdot B} (x) = f_{A} (x) f_{B} (x)$ を満たす写像 $f_{A \cdot B}$ により定める。

以下 $A \in Set (X, R)$ に対して $A^{n}$ と書いたときは、 $A$ の $n$ 個の直積を表し、ドット積を表すものではないとする。

このとき、次の性質が成立する。

$A, B \in {Set}_{finsupp} (X, R)$ に対して次が成立する。
(1) $| A + B | = | A | + | B |$
(2) $R$ が整域ならば $supp A \cap supp B = supp (A \cdot B)$

証明は容易なので各々確かめられたい。整域が何かわからない人は飛ばしてもよい。

また、次の性質も成立する。

$A \in {Set}_{finsupp} (X, R)$ , $B \in {Set}_{finesupp} (Y, R)$ に対して次が成立する。
(1) $| A \times B | = | A | \cdot | B |$
(2) $R$ が整域ならば $supp A \times supp B = supp (A \times B)$

重み付き集合の写像

$X, Y$ を集合とし、 $R$ を可換環とする。
このとき $A \in {Set}_{finsupp} (X, R)$ , $B \in {Set}_{finsupp} (Y, R)$ に対して、写像 $ϕ : supp A \to supp B$ を省略して $ϕ : A \to B$ と表し、 $A$ から $B$ への写像ということにする。

$A^{'} \in {Set}_{finsupp} (X, R)$ に対して、 $A^{'}$ の像（順像） $ϕ (A^{'}) \in {Set}_{finsupp} (Y, R)$ を
$f_{ϕ (A^{'})} (y) = {\begin{cases} \sum_{ϕ (x) = y} f_{A^{'}} (x) & (y \in B) \\ 0 & (y \notin B) \end{cases}$
を満たす写像 $f_{ϕ (A^{'})}$ により定める。

一方 $B^{'} \in {Set}_{finsupp} (Y, R)$ に対して、 $B^{'}$ の逆像 $ϕ^{- 1} (B^{'}) \in {Set}_{finsupp} (X, R)$ を
$f_{ϕ^{- 1} (B^{'})} (x) = {\begin{cases} f_{A} (x) f_{B^{'}} (ϕ (x)) & (x \in A) \\ 0 & (x \notin A) \end{cases}$
を満たす写像 $f_{ϕ^{- 1} (B^{'})}$ により定める。

次に $A^{'} \subset A$ を満たす $A^{'} \in {Set}_{finsupp} (X, R)$ に対して
$ϕ |_{supp A^{'}} : supp A^{'} \to supp B$
を省略して $ϕ |_{A^{'}}$ と表し、 $ϕ$ の $A^{'}$ への制限とよぶことにする。

ある $d \in R$ が存在して、任意の $y \in B$ に対し
$| ϕ^{- 1} (y) | = d$
となるとき $ϕ$ は $d$ 対 $1$ 写像であるという。ここで $ϕ^{- 1} (y)$ とは上記の意味での逆像 $ϕ^{- 1} ({y})$ のことである。

このとき、次のような性質が成立する。

$A, A_{1}, A_{2} \in {Set}_{finsupp} (X, R)$ , $B, B_{1}, B_{2} \in {Set}_{finsupp} (Y, R)$ と写像 $ϕ : A \to B$ について次が成立する。
(1) $ϕ (A_{1} + A_{2}) = ϕ (A_{1}) + ϕ (A_{2})$
(2) $ϕ^{- 1} (B_{1} + B_{2}) = ϕ^{- 1} (B_{1}) + ϕ^{- 1} (B_{2})$
(3) $A \cdot ϕ^{- 1} (B_{1} \cdot B_{2}) = ϕ^{- 1} (B_{1}) \cdot ϕ^{- 1} (B_{2})$
(4) $ϕ (ϕ^{- 1} (B_{1})) = | A | \cdot B_{1}$