この記事は 重み付き集合の記事 の続きです。先にそちらを見ることをおすすめします(前回の記事の記号を踏襲しているので、そもそも見ないと理解するのがかなり難しいと思います)。
まず、simasima specialを適用する規格を定める。
以下のデータからなる組$(U, X, G, K, \mathcal{P})$をsimasima dataと呼ぶ。
(標数$0$の体 $K$ が何かわからない人は有理数全体の集合 $\mathbb{Q}$ や実数全体の集合 $\mathbb{R}$、複素数全体の集合 $\mathbb{C}$ だと思ってください)
また、特にいい性質を示すsimasima dataも定めておく。
simasima data $\mathcal{S} = (U, X, G, K, \mathcal{P})$ に対して、$\mathcal{S}$ がgoodであるとは $\phi(B) \subset \bigcap_{i = 1}^r H_i$ を満たすことをいう。すなわち任意の $b \in B$ に対して $h \in \bigcap_{i = 1}^r H_i$ が存在して $\phi(b) = h$ となることである。
$\mathcal{S}$ がgoodであるとは $r = 1$ のときは $\phi(B) \subset H_1$ であり $r \geq 2$ においては、定義1の最後の性質から $\phi(\mathrm{supp}\, B) = \varnothing, \{ 0_G \}$ と同値であることに注意せよ。
それではいよいよ一般化simasima specialの主張を述べよう。
以下のように記号を定める。
この定理では $H_i \neq \{ 0_G \}$ というsimasima dataの条件はなくても成立する。
また $X$ が通常の集合と同一視できるときは $X^n \cdot Q_n(g)$ は
$$
\left\{ (x_1, \ldots, x_n) \in X^n \, ; \, \sum_{i = 1}^{n} \phi(x_i) = g \right\}
$$
と同一視できる。この集合の濃度はsimasima specialで計算したいものであった。
$$
X^n \cdot Q_n(g) = (A_1 + \dots + A_r + B)^{n} \cdot Q_n(g)
$$
であるので $(A_1 + \dots + A_r + B)^{n}$ を展開した各項を $E$ とすると
$$
|X^n \cdot Q_n(g)| = \sum_{E} |E \cdot Q_n(g)|
$$
である。$E$ に現れる $A_i$ の個数が $a_i$、$B$ の個数が $b$ であるとき、$n=a_1 + \dots + a_r + b$ であり、このような $E$ の個数は $\displaystyle \frac{n!}{a_1! \cdots a_r!b!}$ 個ある。
$\sigma:X^n \to X^n$ を任意の成分の並び替えとすると、任意の $x\in Q_n(g)$ に対して $\sigma(x) \in Q_n(g)$ である。よって
$$
|E\cdot Q_n(g)| = |(A_1^{a_1} \times \dots \times A_{r}^{a_r} \times B^b) \cdot Q_n(g)|
$$
である。よって、$E$ の直積の順番を入れ替えても値が変わらないので
$$
\sum_{E} |E \cdot Q_n(g)| = \sum_{a_1 + \dots + a_r + b = n} \frac{n!}{a_1! \cdots a_r!b!} \, |(A_1^{a_1} \times \dots \times A_{r}^{a_r} \times B^b)\cdot Q_n(g)|
$$
である。よって
$$
E = A_1^{a_1} \times \dots \times A_{r}^{a_r} \times B^b
$$
に対して
$$
|E \cdot Q_n(g)| = |B^b \cdot Q_{a_1, \ldots , a_r, b}(g)|
\prod_{i\, ; \, a_i > 0} \frac{|A_i|^{a_i}}{|H_{i}|}
$$
を示せば十分。$r = 0$ のときは自明に成り立つ。
$r-1$ までで成立しているなら $r$ のときも成立することを示す。
$a_1, \ldots, a_r$ のうち$0$であるものが存在するなら $r-1$ までの場合に帰着されるので成立。よって以下では $a_1, \ldots, a_r > 0$ のときを示す。
$$
|E \cdot Q_n(g)| = \sum f_B(y_1) \cdots f_B(y_b) \prod_{i = 1}^r f_{A_i}(x_1^{(i)}) \cdots f_{A_i}(x_{a_i}^{(i)})
$$
となる。ただし $\sum$ は $x_j^{(i)} \in A_i \, (1\leq i \leq r, \, 1 \leq j \leq a_i)$, $y_k \in B \, (1 \leq k \leq b)$ で
$$
\sum_{i, j} \phi(x_j^{(i)}) + \sum_{k} \phi(y_k) = g
$$
となるものを走る。
この条件式を満たすとき、特に
$$
\sum_{k} \phi(y_k) \in g + \sum_{i = 1}^r H_i
$$
である。また $h_i \in H_i$ で
$$
\frac{|A_i|}{|H_i|} = d = |\phi|_{A_i}^{-1}(h_i)|
= \sum_{\phi(x) = h_i} f_{A_i}(x)
$$
である。よって $h \in H_i$ に対して
\begin{align*}
\sum_{\sum_j \phi(x_{j}^{(i)}) = h} f_{A_i}(x_{1}^{(i)})\dots f_{A_i}(x_{a_i}^{(i)})
&= \sum_{x_2^{(i)}, \ldots, x_{a_i}^{(i)} \in A_i} f_{A_i}(x_2^{(i)}) \cdots f_{A_i}(x_{a_i}^{(i)}) \sum_{\phi(x_1^{(i)}) = h - \phi(x_2^{(i)}) - \cdots - \phi(x_{a_i}^{(i)})} f_{A_i}(x_1^{(i)}) \\
&= |A_i|^{a_i - 1} \cdot \frac{|A_i|}{|H_i|} = \frac{|A_i|^{a_i}}{|H_i|}
\end{align*}
が成立する。以上から
\begin{align*}
\sum f_B(y_1) \cdots f_B(y_b) \prod_{i = 1}^r f_{A_i}(x_1^{(i)}) \cdots f_{A_i}(x_{a_i}^{(i)})
&=
\sum_k \sum_{h_k\in H_k} \ \sum_{\sum_{j}\phi(y_{j})= g + \sum_i h_i} f_B(y_1) \cdots f_B(y_b) \prod_{i = 1}^r
\sum_{\sum_j \phi(x_{j}^{(i)}) = -h_i } f_{A_i}(x_{1}^{(i)})\dots f_{A_i}(x_{a_i}^{(i)}) \\
&= \sum_k \sum_{h_k\in H_k} \ \sum_{\sum_{j}\phi(y_{j})=g + \sum_i h_i} f_B(y_1) \cdots f_B(y_b) \prod_{i = 1}^r \dfrac{|A_i|^{a_i}}{|H_i|}\\
&=\sum_{\sum_{j}\phi(y_{j})\in g + \sum_i H_i} f_B(y_1) \cdots f_B(y_b) \prod_{i = 1}^r \dfrac{|A_i|^{a_i}}{|H_i|} \\
&= |B^b\cdot Q_{a_1, \ldots, a_r, b}(g)|\cdot \prod_{i = 1}^r \dfrac{|A_i|^{a_i}}{|H_i|}
\end{align*}
となり、定理は示される。
記号を定理1の通りとする。さらに $\mathcal{S}$ がgoodであるとする。このとき
\begin{align*}
&|X^n \cdot Q_n(0_G)| \\
&= |B^n \cdot Q_n(0_G)| - |B|^n + \prod_{i} \left( 1 - \frac{1}{|H_i|}\right) \left\{ |B|^n + \sum_{i} \frac{|A_i + B|^n}{|H_i| - 1} + \sum_{i < j} \frac{|A_i + A_j + B|^n}{(|H_i| - 1)(|H_j| - 1)} + \cdots \right\}
\end{align*}
が成立する。特に $\phi(\mathrm{supp} B) = \{ 0_G \}$ となるときは
$$
|X^n \cdot Q_n(0_G)|
= \prod_{i} \left( 1 - \frac{1}{|H_i|}\right) \left\{ |B|^n + \sum_{i} \frac{|A_i + B|^n}{|H_i| - 1} + \sum_{i < j} \frac{|A_i + A_j + B|^n}{(|H_i| - 1)(|H_j| - 1)} + \cdots \right\}
$$
と表せる。
$\mathcal{S}$ がgoodであるとき $(a_1, \ldots, a_r, b) \neq (0, \ldots, 0, n)$ ならば
$$
B^b \cdot Q_{a_1, \ldots, a_r, b}(0_G) = B^b
$$
であり、さらに $\phi(\mathrm{supp} B) = \{ 0_G \}$ であれば $B^n \cdot Q_n(0_G) = B^n$ となることに注意すると定理1から
$$
\sum_{a_1 + \cdots + a_r + b = n} \frac{n!}{a_1! \cdots a_r!b!} \, |B|^b
\prod_{i\, ; \, a_i > 0} \frac{|A_i|^{a_i}}{|H_i|}
=
\prod_{i} \left( 1 - \frac{1}{|H_i|}\right) \left\{ |B|^n + \sum_{i} \frac{|A_i + B|^n}{|H_i| - 1} + \sum_{i < j} \frac{|A_i + A_j + B|^n}{(|H_i| - 1)(|H_j| - 1)} + \cdots \right\}
$$
を示せば十分であることがわかる。
$r = 0$ のとき自明に成立する。$r$ のとき成立すると仮定して $r + 1$ のとき成立することを示す。
\begin{align*}
&\sum_{a_1 + \cdots + a_{r + 1} + b = n} \frac{n!}{a_1! \cdots a_{r + 1}!b!} \, |B|^b
\prod_{i\, ; \, a_i > 0} \frac{|A_i|^{a_i}}{|H_i|} \\
&= \sum_{a_1 + \cdots + a_r + b = n} \frac{n!}{a_1! \cdots a_r!b!} \, |B|^b
\prod_{i\, ; \, a_i > 0} \frac{|A_i|^{a_i}}{|H_i|}
+ \sum_{a_{r + 1} = 1}^{n} \binom{n}{a_{r + 1}}\frac{|A_{r + 1}|^{a_{r + 1}}}{|H_{r + 1}|} \sum_{a_1 + \cdots + a_r + b = n - a_{r + 1}} \frac{(n - a_{r + 1})!}{a_1! \cdots a_r!b!} \, |B|^b
\prod_{i\, ; \, a_i > 0} \frac{|A_i|^{a_i}}{|H_i|} \\
&= \prod_{i \leq r} \left( 1 - \frac{1}{|H_i|}\right) \left\{ |B|^n + \sum_{i \leq r} \frac{|A_i + B|^n}{|H_i| - 1} + \sum_{i < j \leq r} \frac{|A_i + A_j + B|^n}{(|H_i| - 1)(|H_j| - 1)} + \cdots \right\} \\
&\quad + \sum_{a_{r + 1} = 1}^{n} \binom{n}{a_{r + 1}}\frac{|A_{r + 1}|^{a_{r + 1}}}{|H_{r + 1}|}
\prod_{i \leq r} \left( 1 - \frac{1}{|H_i|}\right) \left\{ |B|^{n - a_{r + 1}} + \sum_{i \leq r} \frac{|A_i + B|^{n - a_{r + 1}}}{|H_i| - 1} + \sum_{i < j \leq r} \frac{|A_i + A_j + B|^{n - a_{r + 1}}}{(|H_i| - 1)(|H_j| - 1)} + \cdots \right\} \\
&= \prod_{i \leq r} \left( 1 - \frac{1}{|H_i|}\right) \left\{ |B|^n + \sum_{i \leq r} \frac{|A_i + B|^n}{|H_i| - 1} + \sum_{i < j \leq r} \frac{|A_i + A_j + B|^n}{(|H_i| - 1)(|H_j| - 1)} + \cdots \right\} \\
&\quad + \prod_{i \leq r} \left( 1 - \frac{1}{|H_i|}\right) \left\{ \frac{|A_{r + 1} + B|^n - |B| ^n}{|H_{r + 1}|} + \sum_{i \leq r} \frac{|A_i + A_{r + 1} + B|^n - |A_i + B|^n}{|H_{r + 1}|(|H_i| - 1)} + \sum_{i < j \leq r} \frac{|A_i + A_j + A_r + B|^n - |A_i + A_j + B|^n}{|H_{r + 1}|(|H_i| - 1)(|H_j| - 1)} + \cdots \right\} \\
&= \prod_{i \leq r} \left( 1 - \frac{1}{|H_i|}\right)
\left\{ \left(1 - \frac{1}{|H_{r + 1}|}\right) |B|^n + \left(1 - \frac{1}{|H_{r + 1}|}\right) \sum_{i} \frac{|A_i + B|^n}{|H_i| - 1} + \left(1 - \frac{1}{|H_{r + 1}|}\right) \sum_{i < j \leq r} \frac{|A_i + A_j + B|^n}{(|H_i| - 1)(|H_j| - 1)} + \cdots \right\} \\
&= \prod_{i} \left( 1 - \frac{1}{|H_i|}\right) \left\{ |B|^n + \sum_{i} \frac{|A_i + B|^n}{|H_i| - 1} + \sum_{i < j} \frac{|A_i + A_j + B|^n}{(|H_i| - 1)(|H_j| - 1)} + \cdots \right\}
\end{align*}
以上から示された。
この定理の一般化を述べるために、まず新たな次の記号を導入する。
simasima data $\mathcal{S}$ と $\{1, 2, \ldots, r\}$ の通常の意味での部分集合 $T$ に対して
$$
\mathcal{N}(\mathcal{S}, T) \coloneqq \prod_{i \not\in T} \left( 1 - \frac{1}{|H_i|}\right) \left\{ |B|^n + \sum_{i \not\in T} \frac{|A_i + B|^n}{|H_i| - 1} + \sum_{\substack{i, j \not\in T \\i < j}} \frac{|A_i + A_j + B|^n}{(|H_i| - 1)(|H_j| - 1)} + \cdots \right\}
$$
と定める。
記号を定理1の通りとする。さらに $\mathcal{S}$ がgoodであるとする。
また相異なる $i_1, \ldots, i_k \in \{ 1, \ldots, r\}$ と$h_{i_1} \in H_{i_1} \setminus \{ 0_G \}, \ldots , h_{i_k} \in H_{i_k} \setminus \{ 0_G \}$ を用いて $g = h_{i_1} + \cdots + h_{i_k}$ と表せるとする。このとき $S = \{ i_1 , \ldots, i_k \}$ とすると
$$
|X^n \cdot Q_n(g)| = |B^n \cdot Q_n(g)| - |B|^n + \sum_{T \subset S} (-1)^{|T|} \mathcal{N}(\mathcal{S}, T)
$$
が成立する。ただし $T$ は $S$ の通常の意味での部分集合全体を走る。
$\mathcal{S}$ がgoodであるとき $(a_1, \ldots, a_r, b) \neq (0, \ldots, 0, n)$ かつ $a_{i_1}, \ldots, a_{i_k} > 0$ ならば
$$
|B^b \cdot Q_{a_1, \ldots, a_r, b}(g)| = |B|^b
$$
となり, $(a_1, \ldots, a_r, b) \neq (0, \ldots, 0, n)$ かつ $a_{i_1}, \ldots, a_{i_k}$ のうち少なくとも1つが$0$ならば
$$
|B^b \cdot Q_{a_1, \ldots, a_r, b}(g)| = 0
$$
となる。これと定理2の証明の過程で示した
$$
\sum_{a_1 + \cdots + a_r + b = n} \frac{n!}{a_1! \cdots a_r!b!} \, |B|^b
\prod_{i\, ; \, a_i > 0} \frac{|A_i|^{a_i}}{|H_i|}
=
\prod_{i} \left( 1 - \frac{1}{|H_i|}\right) \left\{ |B|^n + \sum_{i} \frac{|A_i + B|^n}{|H_i| - 1} + \sum_{i < j} \frac{|A_i + A_j + B|^n}{(|H_i| - 1)(|H_j| - 1)} + \cdots \right\}
$$
を用いると包除原理的に定理1から従う。
結論を言うと可能である。そのことを説明するためにsimasima specialによる解法と多項式による解法との比較を行う。
具体例として次の問題を再び考える。
さいころを$n$回続けて投げるとき、出た目の和が$7$で割り切れる場合の数を求めよ。
これをsimasima specialで解く方法は
$X = \{ 1, 2, 3, 4, 5, 6\}$, $A = \{0, 1, 2, 3, 4, 5, 6 \}$, $B = - \{ 0\}$
として対称性を生み出す $A$ とそれ以外 $B$ に分けて計算する方法である。
このことを多項式的に解釈する。
まず本問題は $(x + x^2 + x^3 + x^4 + x^5 + x^6)^n$ を $x^7 - 1$ で割った余りの定数項を求めることに帰着できる。そこで
$$
(x + x^2 + x^3 + x^4 + x^5 + x^6)^n
= \{ (1 + x + x^2 + x^3 + x^4 + x^5 + x^6) - 1 \}^n
$$
を二項展開することを考える。ただし $A$ は $1 + x + x^2 + x^3 + x^4 + x^5 + x^6$ に $B$ は $-1$ に対応していることに注意。
各項は $(1 + x + x^2 + x^3 + x^4 + x^5 + x^6)^k$ の定数倍で表されるが、$k > 0$ ならば
$$
(1 + x + x^2 + x^3 + x^4 + x^5 + x^6)^k
= (1 + x + x^2 + x^3 + x^4 + x^5 + x^6)^{k - 1} \cdot(1 + x + x^2 + x^3 + x^4 + x^5 + x^6)
$$
と分解できる。
二式目の第一項を展開したときの各項はその次数によらず、二項目との積を考えると $x$ の指数が$7$の倍数になるものがただ一つだけできる。
よって $(1 + x + x^2 + x^3 + x^4 + x^5 + x^6)^{k - 1}$ を展開したときの係数の和を求めればよく、これは $7^{k - 1}$ となる。これを足し合わせると答えを得る。
このようにsimasima specialを解釈できる。
次にこの問題を考えよう。
$a_1, \ldots, a_n \in \{ 0, 1\}$であって、総和が4の倍数になるものは何個存在するか求めよ。
この問題は
simasimaさんの記事
にも取り上げられている。
まず $n$ が偶数ならば $n = 2k$ とすると $a_1 + a_2, \ldots, a_{2k - 1} + a_{2k} \in \{ 0, 1, 1, 2\}$ の総和と考えられる。よって
$X = \{ 0, 1, 1, 2\}$, $A = \{ 0, 2\}$, $B = 2 \{ 1\}$
とすればsimasima specialから答えを求めることができる。
$n$ が奇数のときは $n = 2k + 1$ とすると $a_1 + a_2, \ldots, a_{2k - 1} + a_{2k} \in \{ 0, 1, 1, 2\}$ の総和を$4$で割った余りが$0, 3$のいずれかになる場合の数と一致するので、偶数の場合と同様simasima specialが適用できる。
では、$n$ の偶奇を分けずにsimasima specialを適用できるような分割を構成できるだろうか。上記で一般化したsimasima specialそのままでは太刀打ちできない。ではどのような一般化すればsimasima specialを使えるようになるだろうか。
まず、この問題を多項式で解釈しよう。
$(1 + x)^n$ を $x^4 - 1$ で割った余りの定数項が求める答えである。
次のような変形を考える。
$$
(1 + x)^n
= \left\{ \frac{1}{2} (1 + x + x^2 + x^3)
+ \frac{1 - i}{4} (1 + (ix) + (ix)^2 + (ix)^3)
+ \frac{1 + i}{4} (1 + (-ix) + (-ix)^2 + (-ix)^3)
\right\}^n
$$
ここで
\begin{align*}
1 + x + x^2 + x^3 &= (x + 1)(x -i)(x + i)\\
1 + (ix) + (ix)^2 + (ix)^3 &= i^3(x - 1)(x + 1)(x - i)\\
1 + (-ix) + (-ix)^2 + (-ix)^3 &= (-i)^3(x - 1)(x + 1)(x + i)
\end{align*}
となることに注意すると $(1 + x)^n$ を $x^4 - 1$ で割った余りは
$$
\left(\frac{1}{2} \right)^n (1 + x + x^2 + x^3)^n
+ \left(\frac{1 - i}{4}\right)^n (1 + (ix) + (ix)^2 + (ix)^3)^n
+ \left(\frac{1 + i}{4}\right)^n (1 + (-ix) + (-ix)^2 + (-ix)^3)^n
$$
を $x^4 - 1$ で割った余りに等しい。よって、この定数項は先ほどと同じ議論をすると
$$
\left(\frac{1}{2} \right)^n \cdot 4^{n - 1}
+ \left(\frac{1 - i}{4}\right)^n \cdot 4^{n - 1}
+ \left(\frac{1 + i}{4}\right)^n \cdot 4^{n - 1}
= \frac{2^n + (1 + i)^n + (1 -i)^n}{4}
$$
と求められる。これを群論的な解釈に落とし込めば、おそらく一般化できるだろう(従来の方法では $\{ 0, 1, 2, 3\}$ という形のものが対称性を作り出していたが、$0$を$1$個、$1$を$i$個、$2$を$-1$個、$3$を$-i$個持っている重み付き集合なども対称性を生み出すと言うことだ)。
ちなみに
$$
1 + x
= \frac{1}{2} (1 + x + x^2 + x^3)
+ \frac{1 - i}{4} (1 + (ix) + (ix)^2 + (ix)^3)
+ \frac{1 + i}{4} (1 + (-ix) + (-ix)^2 + (-ix)^3)
$$
という分割の導出であるが、これは $f(x) = 1 + x + x^2 + x^3$ として
$$
1 + x = a f(x) + b f(ix) + c f(-x) + d f(-ix)
$$
の両辺に $x = \pm1, \pm i$ を代入すると $a, b, c, d$ が直ちに求められる。
すなわち、これは実質的に $(1 + x)^n$ の $x$ の指数が$4$の倍数となる係数の和だから $f(x) = (1 + x)^n$ として
$$
\frac{f(1) +f(i) + f(-1) + f(-i)}{4} = \frac{2^n + (1 + i)^n + (1 -i)^n}{4}
$$
とする解法と同じである。
以上のことから、この方針でさらなる一般化をするならば、多項式による解法とsimasima specialを融合させることになるだろう。
これを思いついたのがこの記事を執筆している途中だったので、また気が向いたらまとめてみたい(いつになるのやら)。
くぅ~疲れましたw これにて完結です!
せっかく一般化したので、気が向いたらsimasima specialの問題をたくさん扱う記事を書くのもありですね(やるとは言っていない)。また、面白い一般化ができた方は教えてくださると喜びます。