文献あり

双対同型な結合構造の数え上げ

120

こんにちは。krutrです。　
今回は、ある組み合わせ対象の特殊なクラスの同型を除いた数え上げについて、解説します。　
前提知識として、対称群の共役類に関する知識や、群作用の理論(バーンサイドの補題など)を仮定します。
また、説明が煩雑になりすぎないため、議論を省略することがあります。予めご了承ください。
まずは、今回数え上げを行う「結合構造」という組み合わせ対象の説明をしていきます。

結合構造とは

結合構造(例)の図示

$I, J$ を共通の元を持たない２つの(空でない)集合とし、Rを直積集合 $I \times J$ の部分集合とするとき、組 $(I, J, R)$ を結合構造という。

結合構造の同型

結合構造の同型(例)
２つの結合構造 $(I, J, R)$ と $(I^{'}, J^{'}, R^{'})$ が同型であるとは、次のときをいう。:
ある２つの全単射 $f : I \to I^{'}, g : J \to J^{'}$ が存在して、
$R^{'} = {(f (i), g (j)) \in I^{'} \times J^{'} | (i, j) \in R)}$ である。

結合構造の双対

結合構造の双対(例)
結合構造 $(I, J, R)$ の双対とは、 $\bar{R} = {(j, i) \in J \times I | (i, j) \in R)}$ としたとき、 $(J, I, \bar{R})$ のことである。

結合構造が双対同型(self-dual)である

双対同型な結合構造(例)
結合構造 $(I, J, R)$ が、その双対 $(J, I, \bar{R})$ と同型であるとき、 $(I, J, R)$ は、双対同型(self-dual)であるという。

双対同型な結合構造の有名な例

位数2の有限射影平面(左)と位数3の有限射影平面(右)の図示

有名な、双対同型な結合構造の例として、デザルグな有限射影平面があります。図はそれぞれ、位数が２，３の有限射影平面を表しています。それぞれの点の集合を $I$ 、それぞれの曲線の集合を $J$ とします。これまでのように図示する事も出来ます。興味のある方はぜひチャレンジしてみてください。

本題ー双対同型な結合構造の数え上げ

この記事では、互いに要素数 $n$ の、共通部分を持たない２つの集合 $I, J$ に対し、 $I \times J$ に含まれる双対同型な結合構造の、同型を除いた(同一視した)数を数えていきます。
ここから先、 $I, J$ はそれぞれ固定された $n$ 点集合とし、 $I \times J$ の部分集合 $R$ について考察するので、結合構造 $(I, J, R)$ を $R$ と同一視して、単に $R$ を結合構造と呼びます。
まず、計算に必要な諸概念を定義します。

写像の演算（

\cdot, *

）

$S_{I}$ を、 $I$ から $I$ への全単射の全体、 $S_{J}$ を $J$ から $J$ への全単射の全体とする。

$α, β \in S_{I} γ, δ \in S_{J}$ に対して、
$S_{I} \times S_{J}$ 上の演算 $\cdot$ を、

$(α, γ) \cdot (β, δ) := (α β, γ δ)$

とする。

$S_{I J}$ を、 $I$ から $J$ への全単射の全体、 $S_{J I}$ を $J$ から $I$ への全単射の全体とする。

$κ, λ \in S_{J I} μ, ν \in S_{I J}$ に対して、
演算 $* : (S_{J I} \times S_{I J}) \times (S_{J I} \times S_{I J}) \to (S_{I} \times S_{J})$ を、

$(κ, μ) * (λ, ν) := (κ ν, μ λ)$

とする。

$I$ と $J$ がどっちがどっちやら紛らわしいですが、ここはあまり重要ではないので、面倒なら飛ばしても全然大丈夫です。 $S_{I}, S_{J}$ はそれぞれ、 $I, J$ 上の置換群と同一視できることを意識しておいてください。
次は重要です。

作用（

*, \times

）

$θ = (α, β) \in S_{I} \times S_{J}, r = (i, j) \in I \times J$ に対して、
$S_{I} \times S_{J}$ の $I \times J$ への作用 $\cdot$ を、

$θ \cdot r := (α (i), β (j))$

とし、さらに、

$θ = (α, β) \in S_{I} \times S_{J}, R \in P (I \times J)$ に対して、
$S_{I} \times S_{J}$ の $P (I \times J)$ への作用 $\cdot$ を、

$θ \cdot R = {θ \cdot r | r \in R} := {(α (i), β (j)) | (i, j) \in R}$

とする。

$ϕ = (τ, σ) \in S_{J I} \times S_{I J}, r = (i, j) \in I \times J$ に対して、
$S_{J I} \times S_{I J}$ の $I \times J$ への(※)作用 $*$ を、

$ϕ * r := (τ (j), σ (i))$

とし、さらに、

$ϕ = (τ, σ) \in S_{J I} \times S_{I J}, R \in P (I \times J)$ に対して、
$S_{J I} \times S_{I J}$ の $R \in P (I \times J)$ への(※)作用 $*$ を、

$ϕ * R = {ϕ * r | r \in R} := {(τ (j), σ (i)) | (i, j) \in R}$

とする。

※これらは群作用ではない。ここでは作用の語を、「 $S_{J I} \times S_{I J}$ の各元 $ϕ$ に対して、 $ϕ *$ が、 $I \times J, P (I \times J)$ 上の置換と同一視できる」意味で用いている。

演算 $*$ をよく観察すると、これを用いて双対同型な結合構造のクラスが定義できそうだと分かりますね。

双対同型な結合構造のクラス

D_{I J}

ある結合構造 $R \in P (I \times J)$ が、

$\exists ϕ \in S_{J I} \times S_{I J}, ϕ * R = R$

を満たす時、 $R$ は双対同型であるという。
また、その全体を、

$D_{I J} := {R \in P (I \times J) | \exists ϕ \in S_{J I} \times S_{I J}, ϕ * R = R}$

で表し、双対同型な結合構造のクラスという。

$D_{I J}$ に対しても、 $(S_{I} \times S_{J}, \cdot), (S_{J I} \times S_{I J}, *)$ は作用することは簡単に分かります。
今回は、この $D_{I J}$ の、同型を除いた数え上げ、すなわち、 $D_{I J} / (S_{I} \times S_{J}, \cdot)$ の大きさを求めます。
ここで、 $D_{I J} / (S_{J I} \times S_{I J}, *)$ は考えられるのか、考えなくてよいのか、と思われるかもしれませんが、実はこれは考えられる上に、 $D_{I J} / (S_{I} \times S_{J}, \cdot)$ と一致します。
証明はしませんが、ここでは双対同型な結合構造全体を考えていて、どちらの作用も結合構造を本質的に変えないので、直感的には明らかです。
次の補題が、今回の数え上げの肝です。

| D_{I J} / (S_{I} \times S_{J}, \cdot) |

の

(S_{J I} \times S_{I J}, *)

固定点表示

$| D_{I J} / (S_{I} \times S_{J}, \cdot) | = \frac{1}{n!^{2}} \sum_{ϕ \in S_{J I} \times S_{I J}} | D_{I J}^{ϕ *} |$
$= \frac{1}{n!^{2}} \sum_{ϕ \in S_{J I} \times S_{I J}} {R \in D_{I J} | ϕ * R = R}$

バーンサイドの補題より、
$| D_{I J} / (S_{I} \times S_{J}, \cdot) | = \frac{1}{n!^{2}} \sum_{θ \in S_{I} \times S_{J}} | D_{I J}^{θ \cdot} |$
$= \frac{1}{n!^{2}} \sum_{θ \in S_{I} \times S_{J}} | {R \in D_{I J} | θ \cdot R = R} |$
$= \frac{1}{n!^{2}} \sum_{R \in D_{I J}} | {θ \in S_{I} \times S_{J} | θ \cdot R = R} |$
ここで、 $R \in D_{I J}$ に対して、
$| {θ \in S_{I} \times S_{J} | θ \cdot R = R} | = | {ϕ \in S_{J I} \times S_{I J} | ϕ * R = R} |$ を示す。
左辺を $A$ 、右辺を $B$ と置き、次の $f$ は全単射であることを示す。

$f : B \to A$
$ϕ \mapsto ϕ * ϕ_{1}$
(ただし、 $ϕ_{1}$ は $ϕ_{1} * R = R$ を満たす $S_{J I} \times S_{I J}$ の元)

まず、 $f$ が写像であること( $ϕ * ϕ_{1}$ がきちんと $A$ に入っていること)を確認します。
$(ϕ * ϕ_{1}) \cdot R = ϕ * (ϕ_{1} * R) = R$
より、 $f$ は写像です。
また、 $f$ の単射性は明らかなので、全射性を示します。
$θ = (α, β) \in S_{I} \times S_{J}$ を任意にとり、 $ϕ_{1} = (τ_{1}, σ_{1})$ とすると、 $ϕ = (α σ_{1}^{- 1}, β τ_{1}^{- 1}) \in B$ (※)
$ϕ * ϕ_{1} = (α σ_{1}^{- 1}, β τ_{1}^{- 1}) * (τ_{1}, σ_{1}) = θ$

※ $ϕ * R = (α σ_{1}^{- 1}, β τ_{1}^{- 1}) * R$
$= (α σ_{1}^{- 1}, β τ_{1}^{- 1}) * ((τ_{1}, σ_{1}) * R)$
$= ((α σ_{1}^{- 1}, β τ_{1}^{- 1}) * (τ_{1}, σ_{1})) \cdot R$
$= θ \cdot R$
$= R$
よって、
$| D_{I J} / (S_{I} \times S_{J}, \cdot) | = \frac{1}{n!^{2}} \sum_{R \in D_{I J}} | {ϕ \in S_{J I} \times S_{I J} | ϕ * R = R} |$
$= \frac{1}{n!^{2}} \sum_{ϕ \in S_{J I} \times S_{I J}} {R \in D_{I J} | ϕ * R = R}$

長かったですね。途中、やや特殊な計算を説明なしに行っています。
非常に申し訳ないのですが、ゆっくり行間を埋めればきちんと読めるようにはなっているはずですので、ここはこのまま進ませてください。
この計算によって、各 $ϕ \in S_{J I} \times S_{I J}$ に対して、 $ϕ *$ によって変化しない $R \in D_{I J}$ の数を求めればよいと分かります。
ここから先は、 $ϕ \in S_{J I} \times S_{I J}$ を任意に一つとって固定し、その固定点集合 $D_{I J}^{ϕ *}$ の大きさを求めていきます。
まず、次のような考察をします。

ϕ *

固定点の構造

$r \in I \times J$ に対し、列 $r, ϕ * r, ϕ * (ϕ * r), ϕ * (ϕ * (ϕ * r)), . . .$ は必ず巡回し、
$[r]_{ϕ} = {r, ϕ * r, ϕ * (ϕ * r), ϕ * (ϕ * (ϕ * r)), . . .}$ とすると、
$(I \times J) / ⟨ ϕ ⟩ := {[r]_{ϕ} | r \in I \times J}$ は $I \times J$ の分割となる。
また、
$| D_{I J}^{ϕ *} | = | P ((I \times J) / ⟨ ϕ ⟩) | = 2^{| I \times J / ⟨ ϕ ⟩ |}$
である。

直感的には、さほど難しい話ではないと思います。
証明はここも省きますが、具体的には、次の全単射を構成すればよいです。
$f : P ((I \times J) / ⟨ ϕ ⟩) \to D_{I J}^{ϕ *}$
$M ⟼ ⨆ M$
ここから、 $(I \times J) / ⟨ ϕ ⟩$ の元をここでは極小固定点と呼び、この極小固定点を任意にいくつか選んだ非交和が、固定点を尽くしているということですから、この数を調べます。この際、次のように考えます。
$ϕ = (τ, σ) \in S_{J I} \times S_{I J}$ の２回作用 $ϕ * (ϕ *)$ は、群の作用 $(ϕ * ϕ) \cdot = (τ σ, σ τ) \cdot$ となっていることを利用します。
次の項目から、厳密性に欠いた定義が出てきます。
私の技術的な問題で、厳密さを重視すると冗長になってしまうためです。
直感的には難しくないと思います。自信のある方は、厳密で綺麗な定義に直して進んで下されば幸いです。

I, J

の各元

$ϕ = (τ, σ) \in S_{J I} \times S_{I J}$ とする。
$τ σ \in S_{I}$ を、巡回置換の積として書く方法を、巡回置換の掛け順と各巡回置換の表示を完全に指定して適当に(好きに)1つ選び、それを、
$τ σ = (i_{0}^{1} i_{1}^{1} . . .) (i_{0}^{2} i_{1}^{2} . . .) . . . (i_{0}^{u} i_{1}^{u} . . .) . . . (i_{0}^{m} i_{1}^{m} . . .)$ (ただし $m = | I / ⟨ τ σ ⟩ |$ )
とする。(各 $u$ に対して、 $I^{u} := {i_{0}^{u}, i_{1}^{u} . . .}$ と定め、 $i_{k}^{u}$ の下添え字 $k$ は、 $Z / | I^{u} | Z$ の元であるとする。)
また、任意の $u \in {1, 2, . . ., m}$ に対し、
$σ (I^{u}) := J^{u}$ とし、さらに、任意の $k \in Z / | I^{u} | Z = Z / | J^{u} | Z$ に対して、
$σ (i_{k}^{u}) := j_{k}^{u}$
とする。

各

i, j

の動き

任意の $j \in J$ に対し、 $j = j_{k}^{u}$ となる $u \in {1, 2, . . ., m}, k \in Z / | J^{u} | Z = Z / | I^{u} | Z$ が一意に存在し、
$σ τ = (j_{0}^{1} j_{1}^{1} . . .) (j_{0}^{2} j_{1}^{2} . . .) . . . (j_{0}^{u} j_{1}^{u} . . .) . . . (j_{0}^{m} j_{1}^{m} . . .)$ (ただし $m = | I / ⟨ τ σ ⟩ |$ )
であり、さらに、
$τ (j_{k}^{u}) = i_{k + 1}^{u}$
である。

一行目は明らかとしてよい。
$σ (i_{k}^{u}) = j_{k}^{u}$ の両辺に $τ$ を作用させると、
$τ σ (i_{k}^{u}) = τ (j_{k}^{u})$ より、
$i_{k + 1}^{u} = τ (j_{k}^{u})$
さらに両辺に $σ$ を作用させると、
$j_{k + 1}^{u} = σ τ (j_{k}^{u})$
これによって $σ τ$ の表示が定まる。

次は、 $I \times J$ を、都合の良い大まかな固定点に分解していきます。

I \times J

の固定点分解

$I \times J = (⨆_{1 \leq u \leq m} (I^{u} \times J^{u})) ⊔ (⨆_{1 \leq u < v \leq m} ((I^{u} \times J^{v}) ⊔ (I^{v} \times J^{u})))$
と分解でき、それぞれの $I^{u} \times J^{u}, (I^{u} \times J^{v}) ⊔ (I^{v} \times J^{u})$ は、 $ϕ *$ による固定点となっている。

$I, J$ それぞれの分解を考えれば、式自体は明らかです。
固定点になっていることも、 $ϕ *$ によって、 $(I^{u} \times J^{u})$ は動きませんし、 $(I^{u} \times J^{v})$ は $(I^{v} \times J^{u})$ と交換されることを考えれば分かります。
次は、これらの二種類の固定点が、いくつの極小固定点に分解されるか、をそれぞれ観察します。

分解された固定点に含まれる極小固定点の数

任意の $u, v \in {1, 2, . . ., m}$ (ただし $m = | I / ⟨ τ σ ⟩ |$ )に対し、
１. $I^{u} \times J^{u}$ に含まれる極小固定点は、 $⌈ \frac{| I^{u} |}{2} ⌉$ 個
２. $(I^{u} \times J^{v}) ⊔ (I^{v} \times J^{u}) (u \neq v)$ に含まれる極小固定点は、 $gcd (| I^{u} |, | I^{v} |)$ 個

$1. I^{u} \times J^{u}$ の場合
$r = (i, j) \in I^{u} \times J^{u}$ を任意にとる。
$[r]_{ϕ} = {r, ϕ * r, ϕ * (ϕ * r), ϕ * (ϕ * (ϕ * r)), . . .}$
ある $k, l \in Z / | I^{u} | Z$ がそれぞれ一意に定まり $r = (i_{k}^{u}, j_{l}^{u})$ であり、
$[r]_{ϕ} = {(i_{k}^{u}, j_{l}^{u}), (i_{l + 1}^{u}, j_{k}^{u}), (i_{k + 1}^{u}, j_{l + 1}^{u}), (i_{l + 2}^{u}, j_{k + 1}^{u}), . . .}$
ここで、 $[r]_{ϕ}$ は第一成分が $i_{0}^{u}$ である元を必ず持つことに注意すると、
$[r]_{ϕ} = {(i_{0}^{u}, j_{l^{'}}^{u}), (i_{l^{'} + 1}^{u}, j_{0}^{u}), (i_{1}^{u}, j_{l^{'} + 1}^{u}), (i_{l^{'} + 2}^{u}, j_{1}^{u}) . . .}$
と書き直せる。新たに、 $r^{'} = (i_{0}^{u}, j_{l^{'}}^{u})$ とおき、
次の二つの集合 $[r^{'}]_{ϕ}^{e}, [r^{'}]_{ϕ}^{o}$ を考える:
$[r^{'}]_{ϕ}^{e} = {r^{'}, ϕ * (ϕ * r^{'}), ϕ * (ϕ * (ϕ * (ϕ * r^{'})), . . .}$
$[r^{'}]_{ϕ}^{o} = {ϕ * r^{'}, ϕ * (ϕ * (ϕ * r^{'})), ϕ * (ϕ * (ϕ * (ϕ * (ϕ * r^{'})))) . . .}$
すると、 $[r^{'}]_{ϕ}^{e} = [r^{'}]_{ϕ}^{o} = [r^{'}]_{ϕ}$ または、 $[r^{'}]_{ϕ}^{e} ⊔ [r^{'}]_{ϕ}^{o} = [r^{'}]_{ϕ}$ であり、また、
$[r^{'}]_{ϕ}^{e} = {(i_{0}^{u}, j_{l^{'}}^{u}), (i_{1}^{u}, j_{l^{'} + 1}^{u}), (i_{2}^{u}, j_{l^{'} + 2}^{u}) . . .}$
$[r^{'}]_{ϕ}^{o} = {(i_{l^{'} + 1}^{u}, j_{0}^{u}), (i_{l^{'} + 2}^{u}, j_{1}^{u}), (i_{l^{'} + 3}^{u}, j_{2}^{u}) . . .}$
より、 $| [r^{'}]_{ϕ}^{e} | = | [r^{'}]_{ϕ}^{o} | = | I^{u} |$ である。

$[r^{'}]_{ϕ}^{e} = [r^{'}]_{ϕ}^{o} = [r^{'}]_{ϕ}$ を仮定する。
このとき、 $r^{'}$ が $[r^{'}]_{ϕ}^{o}$ に入っていることが必要十分であり、
$\begin{array}{r} {\begin{cases} 0 = l^{'} + 1 + h \\ l^{'} = h \end{cases} \end{array}$
をみたす $h \in Z / | I^{u} | Z$ があればよいが、 $2 h + 1 = 0, 2 l^{'} + 1 = 0$ より、 $| I^{u} |$ は奇数であるしかなく、さらにそのとき $h = l^{'} = \frac{| I^{u} | - 1}{2}$ より、このような極小固定点はただ一つ存在し、その大きさは $| [r^{'}]_{ϕ} | = | [r^{'}]_{ϕ}^{e} | = | [r^{'}]_{ϕ}^{o} | = | I^{u} |$ である。
それ以外の場合は自動的に $[r^{'}]_{ϕ}^{e} ⊔ [r^{'}]_{ϕ}^{o} = [r^{'}]_{ϕ}$ であり、極小固定点の大きさは
$| [r^{'}]_{ϕ} | = | [r^{'}]_{ϕ}^{e} | + | [r^{'}]_{ϕ}^{o} | = 2 | I^{u} |$ となるので、
$| I^{u} |$ が奇数のとき、 $I^{u} \times J^{u}$ に含まれる極小固定点の数は、
$\frac{| I^{u} \times J^{u} | - | I^{u} |}{2 | I^{u} |} + 1 = \frac{| I^{u} | + 1}{2}$
$| I^{u} |$ が偶数のとき、 $I^{u} \times J^{u}$ に含まれる極小固定点の数は、
$\frac{| I^{u} \times J^{u} |}{2 | I^{u} |} = \frac{| I^{u} |}{2}$

$2, (I^{u} \times J^{v}) ⊔ (I^{v} \times J^{u}) (u \neq v)$ の場合
$r = (i, j) \in (I^{u} \times J^{v}) ⊔ (I^{v} \times J^{u}) (u \neq v)$ を任意にとる。
$r \in I^{u} \times J^{v}$ または $r \in I^{v} \times J^{u}$ なので、
まず $r \in I^{u} \times J^{v}$ の場合を考える。
$[r]_{ϕ} = {r, ϕ * r, ϕ * (ϕ * r), ϕ * (ϕ * (ϕ * r)), . . .}$
ここで次の二つの集合 $[r]_{ϕ}^{e}, [r]_{ϕ}^{o}$ を考える:
$[r]_{ϕ}^{e} = {r, ϕ * (ϕ * r), ϕ * (ϕ * (ϕ * (ϕ * r)), . . .}$
$[r]_{ϕ}^{o} = {ϕ * r, ϕ * (ϕ * (ϕ * r)), ϕ * (ϕ * (ϕ * (ϕ * (ϕ * r)))) . . .}$
ある $k \in Z / | I^{u} | Z, l \in Z / | I^{v} | Z$ がそれぞれ一意に定まり $r = (i_{k}^{u}, j_{l}^{v})$ であり、
$[r]_{ϕ}^{e} = {(i_{k}^{u}, j_{l}^{v}), (i_{k + 1}^{u}, j_{l + 1}^{v}), (i_{k + 2}^{u}, j_{l + 2}^{v}) . . .}$
$[r]_{ϕ}^{o} = {(i_{l + 1}^{v}, j_{k}^{u}), (i_{l + 2}^{v}, j_{k + 1}^{u}), (i_{l + 3}^{v}, j_{k + 2}^{u}) . . .}$
明らかに $[r]_{ϕ}^{e} ⊔ [r]_{ϕ}^{o} = [r]_{ϕ}$ であり、また、
$| [r]_{ϕ}^{e} | = | [r]_{ϕ}^{o} | = lcm (| I^{u} |, | I^{v} |)$
よって $| [r]_{ϕ} | = | [r]_{ϕ}^{e} | + | [r]_{ϕ}^{o} | = 2 lcm (| I^{u} |, | I^{v} |)$
$r \in I^{v} \times J^{u}$ の場合も同様なので、
すべての極小固定点の大きさは等しく、 $2 lcm (| I^{u} |, | I^{v} |)$
よって、 $(I^{u} \times J^{v}) ⊔ (I^{v} \times J^{u})$ に含まれる極小固定点の数は、
$\frac{| (I^{u} \times J^{v}) ⊔ (I^{v} \times J^{u}) |}{2 lcm (| I^{u} |, | I^{v} |)} = gcd (| I^{u} |, | I^{v} |)$

大変でしたね、、、
しかし、とても興味深い観察だったと思います。
さて、詰めです。
$I^{u}$ たちの大きさは、 $ϕ = (τ, σ)$ として、 $τ σ$ の示す $I$ の分割に依存していたことを思い出しましょう。

双対同型な結合構造の数

| D_{I J} / (S_{I} \times S_{J}, \cdot) |

$σ \in S_{n}$ に対し、 $σ$ の示す $n$ の分割を $a_{1}, a_{2}, . . . a_{m}$ とするとき、
$f (σ) = \sum_{1 \leq u \leq m} ⌈ \frac{a_{u}}{2} ⌉ + \sum_{1 \leq u < v \leq m} gcd (a_{u}, a_{v})$
とする。
$| D_{I J} / (S_{I} \times S_{J}, \cdot) | = \frac{1}{n!} \sum_{σ \in S_{n}} 2^{f (σ)}$

$| D_{I J} / (S_{I} \times S_{J}, \cdot) |$
$= \frac{1}{n!^{2}} \sum_{ϕ \in S_{J I} \times S_{I J}} | D_{I J}^{ϕ *} |$
$= \frac{1}{n!^{2}} \sum_{ϕ \in S_{J I} \times S_{I J}} 2^{| I \times J / ⟨ ϕ ⟩ |}$
$= \frac{1}{n!^{2}} \sum_{ϕ \in S_{J I} \times S_{I J}} 2^{| ((⨆_{1 \leq u \leq m} (I^{u} \times J^{u})) ⊔ (⨆_{1 \leq u < v \leq m} ((I^{u} \times J^{v}) ⊔ (I^{v} \times J^{u})))) / ⟨ ϕ ⟩ |}$

$= \frac{1}{n!^{2}} \sum_{ϕ \in S_{J I} \times S_{I J}} 2^{| (⨆_{1 \leq u \leq m} (I^{u} \times J^{u}) / ⟨ ϕ ⟩) | + | (⨆_{1 \leq u < v \leq m} ((I^{u} \times J^{v}) ⊔ (I^{v} \times J^{u})) / ⟨ ϕ ⟩) |}$
$= \frac{1}{n!^{2}} \sum_{τ, σ \in S_{n}} 2^{f (τ σ)}$
$= \frac{1}{n!} \sum_{σ \in S_{n}} 2^{f (σ)}$

これにて、証明終了となります。
この数列を $D_{n}$ とし、少し計算してみると、
$D_{1} = 2, D_{2} = 5, D_{3} = 16, D_{4} = 67, D_{5} = 660, . . .$ と続きます。
この数列自体について考察してみるのも面白いかもしれませんね。

最後に、気になっている関連問題について書かせてください。

dualityとpolarity

$R \in P (I \times J)$ に対し、 $ϕ \in S_{J I} \times S_{I J}$ が、
$ϕ * R = R$ を満たすとき、 $ϕ$ を $R$ のdualityという。
さらに、 $R$ のduality $ϕ$ が、 $ϕ * ϕ = e = (1_{I}, 1_{J})$ を満たすとき、
$ϕ$ を $R$ のpolarityという。

ここで疑問なのですが、「duarityを持つ結合構造 $R$ は、必ずpolarityを持つ」のでしょうか？
これはおそらく偽であると私は考えているのですが、いまだに証明できていません。
また、「 $| I | = | J | = p$ (素数)であって、2-デザイン(※)の構造をもつ、 $I \times J$ そのものでなく、空でない結合構造がduarityを持つとき、それは必ずpolarityになる」でしょうか？
こちらは真な気がしていますが、まだ考え始めたばかりでなんとも言えません。