Véges elemek átfolyói
4. rész meghatározó tényezők.
Véges elemek átfolyói.
Vegyünk egy olyan véges készletet, amely n elemekből áll.
Definíció 1. Bármely helyét számú S- egy bizonyos sorrendben nevezett egy permutációja n számok és jelöljük Keresztül számát jelöli a permutációk S.
Egy példa. A készlethez az összes permutáció készletét írjuk le:
A készlet összes permutációjának száma.
Tétel. A készlet permutációinak száma. azaz .
Bizonyítás. Az S készlet permutációjának általános alakja a következő formában:
ahol mindegyik az egyik szám. emellett ezen számok egyike sem fordul elő kétszer a (*) kifejezésben.
Az első elemként bármelyik számot megteheti. Ez n különböző permutációt ad. Az elem helyett csak a fennmaradó számok közül választhat. Következésképpen a választék különböző módjainak száma megegyezik a termékkel. Folytatva, a fennmaradó számok közül választhat, és így tovább. Összefoglalva, arra a következtetésre jutunk, hogy a készlet permutációinak száma megegyezik.
Egy példa. Megmutatjuk, hogy a készlet permutációinak száma megegyezik.
2 3 4 1 3 4 1 2 4 1 2 3
3 4 2 4 2 3 3 4 4 1 1 3 2 4 1 4 1 2 2 3 1 3 1 2
4 3 4 2 3 2 4 3 1 4 3 1 4 2 4 1 2 1 3 2 3 1 2 1
Definíció 2. Ha a permutációban két szimbólum van kicserélve, és az összes többi hely marad, új permutációt kapunk. Ezt a műveletet az átültetésnek nevezzük.
Jóváhagyása. Az S készlet bármely permutációjától a készlet bármely más permutációjával több transzpozíció segítségével továbbhaladhatunk.
Egy példa. Hadd legyen. Megmutatjuk, hogy több átültetés révén permutáció érhető el a permutációból:
3. meghatározás. Azt mondják, hogy egy permutációban egy pár szám is inversziót képez, ha. azaz Egy nagyobb értékű szám korábban áll.
Egy példa. Hány inverzió van a permutációban. A permutáció inverze: 32, 31, 85, 82, 84, 86, 87, 81, 52, 54, 51, 21, ), (41), (61), (71). Csak 15 inverzió.
Ha a permutáció inverz számát jelöljük. akkor az előző példához írhat.
Definíció 4. A permutáció egyenletes. ha a szimbólumaik egyenlő számú invertációt eredményeznek, és furcsaak - egyébként.
Jóváhagyása. Bármely átültetés megváltoztatja a permutáció paritását.
Egy példa. Vegyünk egy öt elemből álló permutációt. Ennek a permutációnak három inverziója van (32), (52), (54), azaz. . ezért a permutáció furcsa.
Cseréljük a második és az ötödik elemet. új permutációt kapunk. Ennek a permutációnak négy inverziója van (42), (43), (52), (53), azaz. . ezért a permutáció egyenletes.