ネックレス（組み合わせ論）

組合せ論では、長さnのk元ネックレスとは、サイズkのアルファベット上のn文字列の同値類であり、すべての回転を等価と見なします。これは、 k色の利用可能なn 個の円形に接続されたビーズを持つ構造を表します。

k元ブレスレットは、ターンオーバー(または自由)ネックレスとも呼ばれ、弦が反射によって等価になるネックレスです。つまり、2 本の弦があり、それぞれがもう一方の弦の逆である場合、それらは同じ同値類に属します。このため、ネックレスはターンオーバー ネックレスと区別するために固定ネックレスと呼ばれることもあります。

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

がある

${\displaystyle 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] ビーズが特定の色の多重集合に制限されている場合、ここで、色のビーズの数、は、 ${\displaystyle \varphi}$ ${\displaystyle {\mathcal {B}}=\{1^{n_{1}},\ldots ,k^{n_{k}}\}}$${\displaystyle n_{i}}$${\displaystyle i\in \{1,\ldots ,k\}}$

${\displaystyle 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色すべてを使用する必要がある場合、カウントは ${\displaystyle {\mathcal {B}}}$${\displaystyle |{\mathcal {B}}|:=\sum \limits _{i=1}^{k}n_{i}}$${\displaystyle {m \choose m_{1},\ldots ,m_{k}}:={\frac {m!}{m_{1}!\cdots m_{k}!}}}$${\displaystyle C_{n}}$${\displaystyle f:\{1,\ldots ,n\}\to \{1,\ldots ,k\}}$

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

第二種スターリング数はどこですか。 ${\displaystyle S(n,k)}$

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

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

そして

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

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

${\displaystyle B_{k}(n)={\begin{cases}{\tfrac {1}{2}}N_{k}(n)+{\tfrac {1}{4}}(k+1)k^{n/2}&{\text{if }}n{\text{ is even}}\\[10px]{\tfrac {1}{2}}N_{k}(n)+{\tfrac {1}{2}}k^{(n+1)/2}&{\text{if }}n{\text{ is odd}}\end{cases}}\quad ,}$

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

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

ビーズがすべて異なるわけではなく、色が繰り返されている場合は、ネックレス (およびブレスレット) の数は少なくなります。上記のネックレスを数える多項式は、すべての可能なビーズの多重セットから作られたネックレスの数を示します。Polya のパターン インベントリ多項式は、各ビーズの色に変数を使用して、カウント多項式を改良し、各単項式の係数が、特定のビーズの多重セット上のネックレスの数を数えるようにします。

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

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

${\displaystyle 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 ワードは非周期ネックレスの 代表を形成します。

• リンドンの言葉
• 反転（離散数学）
• ネックレスの問題
• ネックレスの分裂問題
• 順列
• フェルマーの小定理の証明#ネックレスを数えることによる証明
• フォルテ数。無調音楽で使用される長さ 12 の 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.