前回のその１では四元数群$Q_8$の乗積表 Q8mult を作りました。
今回はこれを使って色々な$Q_8$の要素の積を求めます。
例題 １．iijjkkの値を求めよ
ijkの文字列からその積を求める関数 prodQ を作り、$iijjkk=-1$ が求まりました。
Q8mult = [[0, 1, 2, 3, 4, 5, 6, 7], [1, 0, 3, 2, 5, 4, 7, 6], # 1, -1
[2, 3, 1, 0, 7, 6, 4, 5], [3, 2, 0, 1, 6, 7, 5, 4], # i, -i
[4, 5, 6, 7, 1, 0, 3, 2], [5, 4, 7, 6, 0, 1, 2, 3], # j, -j
[6, 7, 5, 4, 2, 3, 1, 0], [7, 6, 4, 5, 3, 2, 0, 1]] # k, -k
from functools import reduce
S2Q = {"i":2, "j":4, "k":6}
def prodQ(qstr):
nstr = list(map(lambda x: S2Q[x], s)) # "ijk" -> [2,4,6]
return N2Quat[reduce(lambda x, y: Q8mult[x][y], nstr)]
s = "iijjkk"
print(f"'{s}' = {prodQ(s)}")
# 'iijjkk' = -1
例題 ２．iijjkkのすべての順列で積が１になる数を求めよ
同じものを含む順列の生成と数で紹介した distinct_permutationsを使ってすべての答えを求めます。
from more_itertools import distinct_permutations
ctr = Counter([prodQ(''.join(p)) for p in distinct_permutations("iijjkk")])
print(dict(ctr))
# {'-1': 48, '1': 42}
42という答えが得られましたが、なぜそうなるのかを以下のステップで考察します。
- ijkの2つの積は順序を変えると符号が変わる
- iijjkkのすべての順列の積は$1$か$-1$になる
- 長さ２のグループに分けて各々がペアになっているかを見る
1. ijkの2つの積は順序を変えると符号が変わる
前回の$Q_8$の累積表からijkだけを抜き出すと2つの積は順序を変えると符号が変わることが分かります。
| i | j | k | |
|---|---|---|---|
| i | -1 | -k | j |
| j | k | -1 | -i |
| k | -j | i | -1 |
従ってijkの積の隣り合う２つを入れ替えると全体の符号が反転します
\begin{align}
&i\color{red}{ij}jkk = -1\\
&i\color{red}{ji}jkk = 1
\end{align}
2. iijjkkのすべての順列の積は1か-1になる
これは以下の様に説明できます
- 前で求めたように$iijjkk = -1$となる
- すべての順列は隣り合う２つの入れ替えの繰り返しで得られる
- ijkの２のを入れ替えると全体の積の符号が反転する
- 従ってiijjkkのすべての順列の積は1か-1になる
3.長さ２のグループにして各々がペアになっているかを見る
例えば$ikijkj \rightarrow (ik)(ij)(kj) $のように2つづづをグループにします。
A. すべてのグループがペアになっているケース
$(ii)(jj)(kk)$のようにすべてがペアになる場合の積は、ペアの個数を$P$とすると$(-1)^P$になりこの場合は$P=3$なので$-1$になります。Aはこの場合には$3!=6$個あります。
B. ペアでないグループが1つ以上あるケース
$(ii)(jk)(jk)$のような場合、最初にペアでないグループの順序を逆にした順列が必ず存在して、その$\pm$が逆です。すなわち$1$と$-1$が1対1対応になるので、同じ数だけ存在します。
\begin{align}
&(ii)\color{red}{(jk)}(jk) = 1 \leftarrow \rightarrow
(ii)\color{red}{(kj)}(jk) = -1
\end{align}
AとBの数から答えを求める
iijjkkのすべての順列の数は$T=6!/(2!2!2)!=90$なので、
\begin{align}
&A + B = T = 90 \\
&A = 6 \\
&B = 90 - 6 = 84 \\
&Bの半分が1なので、\\
&1になるのは84/2 = 42
\end{align}
となり無事42という答えが出ました。この結果を用いてもっと長い積を求めます。
例題 ３．i,j,kをそれぞれ10個含むすべての順列の積が１になる数を求めよ
前節で得られたものを一般化します。i,j,kの個数をそれぞれI, J, Kとすると、（ただしI, J, Kはすべて偶数）
$T$と$A$を同じものを含む順列の生成と数で作った dpermを使って求めます。
from math import factorial, prod
def dperm(rl): # run length --> number of distinct permutations
return factorial(sum(rl)) // prod([factorial(r) for r in rl])
I= J = K = 10
T = dperm([I, J, K])
B = dperm([I//2, J//2, K//2])
C = 1 if (I+J+K)//2 % 2 == 0 else -1
print(f"T = {T}, B = {B}, C = {C}, Answer= (T+C*B)//2 ={(T+C*B)//2}")
# T = 5550996791340, B = 756756, C = -1, Answer= (T+C*B)//2 =2775498017292
今回はI, J, Kはすべて偶数の場合だけを考えましたが、それ以外のケースも同様に考えていけば難しくはないと思います。
（開発環境：Google Colab）
この考え方はProject Euler, Problem 981: The Quaternion Group IIを解くのに役に立ちます。