Zyklisches Sieben

Zyklisches Sieben ist ein mathematisches Phänomen aus der Kombinatorik. Es tritt dann auf, wenn das Berechnen der erzeugenden Funktion an den Stellen der Einheitswurzeln gleichzeitig ein Abzählen von Symmetrieklassen von Objekten ist, auf die eine zyklische Gruppe wirkt.

Definition

Sei $X$ eine endliche Menge und $C_n=⟨a⟩$ eine zyklische Gruppe der Ordnung $n$, welche auf $X$ operiert. Sei $P(q)\in \mathbb{Z}[q]$ ein Polynom mit ganzzahligen Koeffizienten in $q$. Für ein $d\in \mathbb{Z}$ bezeichnen wir mit ${\zeta }^d$ die Einheitswurzeln

${\zeta }^d:=\exp \left(2\pi \mathrm{i}\frac{d}{n}\right).$

Das Triple $(X,P(q),C_n)$ besitzt das Zyklisches-Sieben-Phänomen (CSP von Vorlage:EnS) falls für alle $d\in \mathbb{Z}$ die Gleichung

$|\{x\in X:g^d\circ x=x\}|=P({\zeta }^d)$

gilt. Das heißt, das Polynom ausgewertet an den Einheitswurzeln ${\zeta }^d$ ist gleich der Anzahl der Element in $X$, für die $g^d\circ x=x$ gilt.

Da $P(1)=|X|$ gilt, ist $P(q)$ eine erzeugende Funktion von $X$ genannt das q-Analogon von $X$.

Beispiel

Sei $n,k\in \mathbb{N}$ mit $0\le k\le n$. Bezeichne mit $M_k=i_1{i}_2\dots i_k$ eine Multimenge auf $[n]:=\{1,2,\dots ,n\}$ mit $k$ Elementen und $1\le i_1\le i_2\le \cdots \le i_k\le n$. Dann sei $X$ die Familie

$X=\left((\genfrac{}{}{0ex}{}{[n]}{k})\right):=\{M_k:M_k\text{ist eine }k\text{-Multimenge von }[n]\}$

und für die Kardinalität gilt

$|X|=(\genfrac{}{}{0ex}{}{n+k-1}{k}).$

Betrachte die zyklische Gruppe $C_n=⟨(1,2,\dots ,n)⟩$. Dann wirkt die Gruppenoperation $g\in C_n$ auf $M_k$ wie folgt

$g{M}_k=g(i_1)g(i_2)\dots g(i_k).$

Als $P(q)$ wählen wir den q-Binomialkoeffizient

$P(q)={(\genfrac{}{}{0ex}{}{n+k-1}{k})}_q:=\frac{[n+k-1{]}_q!}{[k{]}_q![n-1{]}_q!}$

wobei $[k{]}_q!:=[k{]}_q[k-1{]}_q\cdots [1{]}_q$ und $[k{]}_q:=1+q+q^2+\dots +q^{k-1}$ das q-Analogon von $k$ bezeichnet. Es lässt sich zeigen, dass das Tripel $(X,P(q),C_n)$ das CSP besitzt.

Als konkretes Beispiel wähle $n=3,k=2$. Es gilt $X=\{11,22,33,12,13,23\}$ und $C_3=\{e,(1,2,3),(1,3,2)\}$. Sei $g=(1,2,3)$ dann ist

$(1,2,3)11=22,(1,2,3)22=33(1,2,3)33=11,(1,2,3)12=23,(1,2,3)13=12,(1,2,3)23=13.$

Dann ist das entsprechende Polynom

$P(q)={(\genfrac{}{}{0ex}{}{4}{2})}_q=\frac{[4{]}_q!}{[2{]}_q![2{]}_q!}=1+q+2q^2+q^3+q^4.$

Literatur

• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur