ネックレス（組合せ論）

赤いビーズ3個と緑のビーズ3個が付いたブレスレット3本。真ん中のものはキラルなので、ネックレスは4本あります。
三角形のボックス(6,9)と比較してください。

赤ビーズ2個、黄ビーズ2個、緑ビーズ2個が付いたブレスレット11個。左端の1個と右端の4個はキラルなので、ネックレスは16個あります。
三角形の枠(6,7)と比較してください。

組合せ論において、長さnのk元ネックレスとは、サイズkのアルファベット上のn文字列の同値類であり、すべての回転を同値とみなします。これは、 k色の利用可能なn個のビーズが環状に連結された構造を表します。

k元ブレスレットは、ターンオーバーネックレス（またはフリーネックレス）とも呼ばれ、鏡映写によって弦が同値となるネックレスです。つまり、2本の弦が与えられ、それぞれがもう1本の弦の裏表の関係にある場合、それらは同じ同値類に属します。このため、ターンオーバーネックレスと区別するために、固定ネックレスと呼ばれることもあります。

正式には、ネックレスはサイズkのアルファベット上のn文字列に作用する巡回群の軌道として表すことができ、ブレスレットは二面体群の軌道として表すことができます。これらの軌道、つまりネックレスとブレスレットは、ポリアの列挙定理を用いて数えることができます。

同値類

ネックレスの数

がある

N_{k}(n)={\frac {1}{n}}\sum _{d\mid n}\varphi (d)k^{n/d}={\frac {1}{n}}\sum _{i=1}^{n}k^{\,{\rm {gcd}}(i,n)}

長さnの異なるk元ネックレス。ここでオイラーのトーティエント関数。^[1] ビーズが特定の色の多重集合に制限されている場合、ここで色のビーズの数であるとき、 $\varphi$ ${\mathcal {B}}=\{1^{n_{1}},\ldots ,k^{n_{k}}\}$ $n_{i}$ $i\in \{1,\ldots ,k\}$

N({\mathcal {B}})={\frac {1}{|{\mathcal {B}}|}}\sum _{d|{\rm {gcd}}(n_{1},\ldots ,n_{k})}{|{\mathcal {B}}|/d \choose n_{1}/d,\ldots ,n_{k}/d}\phi (d)

のビーズすべてで作られた異なるネックレス。^[2]ここで、とは多項式係数である。これらの2つの式は、すべての関数の集合に作用する巡回群の作用に適用されるポリアの列挙定理から直接導かれる。k色すべてを使用しなければならない場合、その数は ${\mathcal {B}}$ $|{\mathcal {B}}|:=\sum \limits _{i=1}^{k}n_{i}$ ${m \choose m_{1},\ldots ,m_{k}}:={\frac {m!}{m_{1}!\cdots m_{k}!}}$ $C_{n}$ $f:\{1,\ldots ,n\}\to \{1,\ldots ,k\}$

L_{k}(n)={\frac {k!}{n}}\sum _{d\mid n}\varphi (d)S\left({\frac {n}{d}},k\right)\;,

第二種スターリング数はどこですか？ $S(n,k)$

$N_{k}(n)$ ( OEISのシーケンスA054631 )と( OEISのシーケンスA087854 )は二項係数を介して関連しています。 $L_{k}(n)$

N_{k}(n)=\sum _{j=1}^{k}{\binom {k}{j}}L_{j}(n)

そして

L_{k}(n)=\sum _{j=1}^{k}(-1)^{kj}{\binom {k}{j}}N_{j}(n)

ブレスレットの数

長さnのk元ブレスレット（OEISの配列A081720）の異なる数は、

B_{k}(n)={\begin{cases}{\tfrac {1}{2}}N_{k}(n)+{\tfrac {1}{4}}(k+1)k^{n/2}&{\text{nが偶数の場合}}\\[10px]{\tfrac {1}{2}}N_{k}(n)+{\tfrac {1}{2}}k^{(n+1)/2}&{\text{nが奇数の場合}}\end{cases}}\quad ,

ここで、N _k ( n ) は長さnのk元ネックレスの数である。これは、二面体群の作用にポリア法を適用した結果である。 $D_{n}$

異なるビーズの場合

すべて異なるn個のビーズの集合に対して、回転したネックレスを同じものとして数えて、これらのビーズから作られた異なるネックレスの数は、⁠ん！/n⁠ = ( n − 1)! となる。これは、ビーズをn通りの線形順序で並べることができ、そのような順序でn回回転させても同じネックレスができるためである。同様に、回転したブレスレットと鏡映したブレスレットを同じものとして数えた、異なるブレスレットの数は ⁠ん！/2 n⁠、n ≥ 3の場合。

ビーズがすべて異なる色ではなく、繰り返しの色を持つ場合、ネックレス（およびブレスレット）の数は少なくなります。上記のネックレス計数多項式は、あらゆるビーズの多重集合から作られるネックレスの数を与えます。ポリアのパターンインベントリ多項式は、各ビーズの色を変数として計数多項式を改良したもので、各単項式の係数は、与えられた多重集合のビーズから作られるネックレスの数を数えます。

非周期的なネックレス

長さnの非周期ネックレスとは、サイズnの回転同値類です。つまり、このような類のネックレスの 2 つの異なる回転はどれも等しくありません。

モローのネックレスカウント関数によれば、

M_{k}(n)={\frac {1}{n}}\sum _{d\mid n}\mu (d)k^{n/d}

長さnの異なるk元非周期ネックレス。ここでμはメビウス関数である。2つのネックレス計数関数は次のように関係している。ここで、和はnのすべての約数にわたっており、これはメビウス反転によって次のように表される。 ${\textstyle N_{k}(n)=\sum _{d|n}M_{k}(d),}$ ${\textstyle M_{k}(n)=\sum _{d|n}N_{k}(d)\,\mu {\bigl (}{\tfrac {n}{d}}{\bigr )}.}$

それぞれの非周期ネックレスには 1 つのLyndon ワードが含まれており、Lyndon ワードは非周期ネックレスの代表を形成します。

参照

参考文献

^ Weisstein, Eric W.「ネックレス」. MathWorld .
^ Ruskey, Frank (2006). 「ネックレス、リンドンの言葉、デ・ブリュインのシーケンスに関する情報」。2006年10月2日時点のオリジナルよりアーカイブ。

外部リンク

Polya, Georg; Read, RC; Aeppli, Dorothee (1987).グループ、グラフ、化合物の組み合わせ列挙. Springer-Verlag. ISBN 9780387964133。
Ruskey, Frank; Savage, Carla; Wang, Terry Min Yih (1992). 「ネックレス生成」. Journal of Algorithms . 13 (3): 414– 430. doi :10.1016/0196-6774(92)90047-G.

[1] Weisstein, Eric W.「ネックレス」. MathWorld .

[2] Ruskey, Frank (2006). 「ネックレス、リンドンの言葉、デ・ブリュインのシーケンスに関する情報」。2006年10月2日時点のオリジナルよりアーカイブ。