Pólya-tétel

1. Sablon:Label

Pólya-tétel

A **Pólya-tétel** (más néven **Pólya-számlálási tétel**) egy fontos eredmény a kombinatorikában és a csoportelméletben. A tétel lehetővé teszi az egyedi konfigurációk számlálását, amelyek szimmetriacsoportok hatása alatt állnak.

A tétel megfogalmazása

Legyen $X$ egy véges halmaz, amelyen egy $G$ csoport működik (például forgatások vagy tükrözések szimmetriacsoportja). A Pólya-tétel szerint az $X$ halmazon a $G$ csoport által generált különböző orbitok (vagyis szimmetria szerint megkülönböztethetetlen konfigurációk) száma a következőképpen határozható meg:

$|X/G|=\frac{1}{|G|}\sum _{g\in G}|\mathrm{F}\mathrm{i}\mathrm{x}(g)|,$

ahol:

• $|G|$ a $G$ csoport rendje (azaz elemeinek száma),
• $\mathrm{F}\mathrm{i}\mathrm{x}(g)$ azon elemek halmaza $X$-ben, amelyek fixek a $g$ transzformáció alatt (vagyis $g(x)=x$).

Magyarázat

A tétel azt írja le, hogy egy halmaz különböző szimmetrikus elrendezései (orbitjai) hogyan számíthatók ki a csoport hatása alapján. Ez az ún. **Burnside-lemma** kiterjesztése.

• **Orbit:** Egy halmaz azon elemeinek osztálya, amelyek szimmetria szerint ekvivalensek.
• **Fixpont:** Egy elem fix, ha egy adott transzformáció alkalmazása után is önmagába megy át.

A Pólya-tétel kiterjeszti ezt az elvet, és alkalmazható például színezési problémákban, ahol egyes konfigurációk szimmetria szerint ekvivalensek.

Példa

Vegyük egy háromszög csúcsainak színezését két színnel (mondjuk fekete és fehér). Itt a háromszög szimmetriacsoportja $G$ a forgatások és tükrözések összes kombinációját tartalmazza, vagyis $|G|=6$ (ez a diédercsoport, $D_3$).

1. A lehetséges színezések száma szimmetria nélkül: $2^3=8$. 2. A szimmetriacsoport transzformációi:

  * Az identitás: minden konfiguráció fix (8 darab).
  * Forgatások: nincs fix színezés.
  * Tükrözések: 2 fix színezés.

A Pólya-tétel alapján a szimmetria szerint különböző színezések száma: $|X/G|=\frac{1}{6}(8+0+0+2+2+2)=2.$

Tehát két különböző szimmetrikus színezés létezik.

Következmények és alkalmazások

A Pólya-tétel alkalmazható:

• Kombinatorikus problémák szimmetriák szerinti egyszerűsítésére.
• Kémiai molekulák lehetséges konfigurációinak számlálására.
• Színezési és csempézési problémák vizsgálatára.
• Algoritmusok optimalizálására szimmetriák figyelembevételével.

A Pólya-tétel a kombinatorikai csoportelmélet egyik legfontosabb eredménye, és jelentős hatással volt az algebrai kombinatorika fejlődésére.