Permutáció és a helyettesítés
Számítási meghatározói 4. és magasabb rendű nem képviseli elég egyszerű „mértani rajz”, mint ahogyan azt a meghatározó a 2. és 3. sorrendben.
Azonosítani, és megvizsgálja a meghatározó rend n használjuk a kapcsolódó fogalmak véges készlet elemekkel.
Fontolja meg a készlet M egész számok: 1, 2, .... n. A halmaz elemeit M lehet elhelyezni különböző módokon.
Definíció. bármely elrendezése az 1, 2, ..., n valamilyen sorrendben az úgynevezett ne-permutációját n számok. Az általános nézet az a felvétel permutációinak n elemek:
ahol minden az egyik 1, 2, .... n, és ezek közül egyik sem a számok nem fordul elő kétszer, és hiányzott.
Mivel i1 bármelyike kiválasztható az 1, 2, .... n. Ez ad n különböző lehetőségeket. Ha i1 már kiválasztott, majd mint I2 választhat csak az egyik a maradék (N -1) szám, azaz a különböző módon, hogy válasszon egy számot (karakter) I1 és I2 terméke n # 8729; (N -1), stb A bizonyos permutációi n szimbólumok jelentése megegyezik a termék:
Ha néhány permutáció felcserélni két karakter (nem feltétlenül közel álló), és mindenki másnak a helyén marad, akkor kap egy új permutáció. Egy ilyen átalakítás az úgynevezett permutációs átültetés.
1. Tétel. Minden permutációi n szimbólumok lehet elhelyezni oly módon, hogy az egymást követő permutáció kapott az előzőtől átültetése, és elkezdhetjük bármelyik permutáció.
► Ha n = 2 igaz, 1: 2 → 2: 1;
Tekintsük az összes permutációinak n elem, amelyben az első helyen egy szimbólum I1. Az ilyen permutációk és lehet elhelyezni összhangban tétel (n -1) szimbólumok. Hagyja, hogy a legutóbbi ilyen permutációk (tekintettel arra, hogy a szimbólum i1 tartottuk mozdíthatatlan) a formája:
A permutációs (43), amely tartalmaz n szimbólumok, karakterek I1 átültetés elkövetni más (például, a szimbólum i2), és újra-sorrendben minden permutációját a (n-1) szimbólumok egy rögzített helyen a földön i2 stb Így megy végig a permutációt n szimbólumok. ◄
Következmény. bármely permutáció n karaktert, akkor megy minden más permutáció azonos karakter néhány átültetés.
Ha a permutációs szimbólum i1 előtt áll a szimbólum i2. de. Azt mondják, a szimbólumok I1 és I2 make inverzió (megsértése érdekében), egyébként ezek a karakterek alkotják a sorrendben. Permutáció nevezik még. ha a karakterek páros fordítások számát, és furcsa - egyébként.
Megjegyzés. 1) minden átültetés megváltoztatja a paritás a permutáció.
2) az összeg a megrendelések és inverzió állandó és egyenlő
# 9786; 31. példa. Mi határozza meg a paritás a permutációs 1, 2, .... n.
Határozat. Egy adott permutáció páros, mert nincs inverzió (kb megsértése).
32. példa. Adjuk Parity permutációs 4 5 1 3 6 2.
Határozat. Ahhoz, hogy számolja meg a inverziók használat 1. táblázat, amely azt mutatja, az inverzió a kiválasztható elemek minden ezt követő (regisztrációs érdekében megsértését).
33. példa. Határozza meg a fordítások számát, a permutációs: 1, 9, 6, 3, 2, 5, 4, 7, 8.
34. példa. Egyes permutációja az 1, 2, 3, ..., 99 a legnagyobb fordítások számát, és mi még mindig?
35. példa. Mi határozza meg a fordítások számát 99, 50, álló helyet a permutációs 1, 2, ..., 99.
1. átrendezése - a mátrix?
2. Mi az a „átültetése” a két permutáció az elemek?
3. Mi a „inverzió” a két kiválasztott permutáció az elemek?
4. Mi a „rend” a két kiválasztott permutáció az elemek?
5. Mi az az összeg, a fordítások számát, és a megrendelések száma bármely permutációja az 1, 2, .... 99.
Definíció. Írunk egy permutációja alapján más :. ezt a bejegyzést
nevezett szubsztitúció. ami azt jelenti, ez a leképezés (levelezés) több ábra, amely az első n szám 1, 2, ..., n, önmagára. ; . . ...,
Ha figyelembe vesszük, hogy a helyettesítés, mint egy térképet a számsor 1, 2, .... n nem változik átültetésével oszlopok, válassza ki a legegyszerűbb kifejezés is:
ahol # 945; i - a számot, amely a számot i.
Olyan expressziós (44) helyettesítve az n rend különböznek csak az alsó sorban permutációk felvétel, azaz szubsztitúciós egyértelműen meghatározza egy permutációs. Nye jegyezni a lényeg. Ez azt jelenti, hogy az összes permutációt n rend annyi, hogyan kell és permutáció, hogy van, .
Mi határozza meg a fogalmát paritás helyettesítések:
A. alapján közös meghatározása helyettesítés:
- helyettesítés még. Ha a paritás a felső és az alsó permutációk egybeesnek;
- páratlan permutáció. ha a paritás a felső és az alsó szemközti permutációk.
B. Tekintettel a helyettesítése privát felvételt (44):
- helyettesítés még. ha úgy dönt, a páros permutációk;
- páratlan permutáció. Ha azt észleli, páratlan permutáció.
Szintén megszámlálásából inverzió a permutációk, hogy meghatározzuk paritás helyettesítések is használják a növekedési ciklus. Mi használja ezt a technikát (anélkül, hogy azt igazoló veszünk), tekintsünk egy konkrét példát.
# 9786; 36. példa. Mi határozza meg a paritás a helyettesítés.
Határozat. Annak megállapításához, a paritás szubsztitúciós bontsa be egy termék ciklus:
ahol a zárójelek után "=" jel képviseli ciklusok: (1 → 6 → 3 → 1), (2 → 5 → 2), (4 → 4) és (7 → 7), (8 → 8), (9 → 9 ) megjelenítő szimbólumok 1,2, ..., 9, definíció szerint, kiindulási anyagként (ciklusokban szimbólumok „fennmaradó helyben” is szerepelnek). A terjeszkedés a helyettesítés ciklusok számának megállapítására csökkentéshez. d = n - s, ahol n - a sorrendben a szubsztitúció, s - ciklusok száma az expanziós permutáció. Ebben a példában: d = 9-6 = 3 - → páratlan számú páratlan permutáció.
37. példa Annak meghatározására, a paritás szubsztitúciós bontsa be egy termék ciklus:
ahol a zárójelek után "=" jel képviseli ciklusok: (1 → 5 → 1), (2 → 8 → 4 → 6 → 2), (3 → 9 → 7 → 3) megjelenítő szimbólumok 1,2, ..., 9, definíció szerint, helyettesítés. Számítsuk decrement a figyelembe vett szubsztituáló: d = 9 - 3 = 6 - → páros permutáció is.
38. példa. Határozza meg a fordítások számát, a permutációs: 1, 9, 6, 3, 2, 5, 4, 7, 8.
39. példa. Egyes permutációja az 1, 2, 3, ..., 99 a legnagyobb fordítások számát, és mi még mindig?
40. példa. Mi határozza meg a fordítások számát 99, 50, álló helyet a permutációs 1, 2, ..., 99.
6. Helyettesítés - a mátrix?
7. Mit jelent a „átültetés” lookup oszlopokat?
8. Mi a „inverzió” a helyettesítés?
9. Mi a „rend” a helyettesítés?
10. Mi az az összeg, a fordítások számát, és a megrendelések száma bármely permutációja az 1, 2, .... 99.
Meghatározói az N-edrendű
Tegyük fel, hogy egy négyzetes mátrix a rend n:
elemek aij. amely lehet elemei tetszőleges számú mezőt. Tekintsük az összes lehetséges termék az n elem található különböző sorok és oszlopok különböző:
ahol - képezik egy permutációja a számok 1, 2, .... n. A számos ilyen termékek száma permutáció, azaz .
Forma helyettesítése n karakter. . (47)
Meg kell azonban jegyezni, hogy a meghatározó a 2. és 3. rend „plusz” azok tagjai a meghatározó, az indexek, amelyek még permutáció, és a „mínusz” - tagjai páratlan permutáció az indexek. Ez a tulajdonság tárolja a meghatározása a meghatározó az n-ed rendű.
Definíció. meghatározója érdekében megfelelő n a mátrix (45) egy algebrai összege kifejezések összetétele a következő:
- minden egyes tagja a meghatározója (külön összeget kifejezés a fenti) a terméket, az N a meghatározó elem, vett egy-egy oszlopot, és minden sorban a mátrix;
- tagja a meghatározó veszik be a „plusz”. ha az index még permutáció, és a „mínusz”. ha páratlan:
Megnevezése a meghatározó (48)
Alkalmazása meghatározására meghatározója n rend gyakorlati számítások nehéz lenne. Azt vizsgáljuk, annak tulajdonságait, közvetlenül eredő meghatározása.
Mivel svoystvo1 meghatározó 3. sorrendben létrehozó egyenlőség sorok és oszlopok a meghatározó, ültessék át az A mátrix és írd be:
Hagyja, hogy a determináns egy előkelő tagja:
meghatározására a jel, amely egy permutációs rend n:
ez tükrözi a számát permutációs felső sorok a meghatározó, amelyben a mátrix elemek vannak elhelyezve az expressziós (50); és az alsó - az oszlop számokat.
Átültetése után a mátrix ugyanazokat az elemeket részt vesz tagja a meghatározója a kifejezést:
és meghatározására szolgáló jele, hogy lesz ez a kifejezés a meghatározó permutációs kell használni:
Nyilvánvalóan paritás permutációs (51) és (53) egybeesik (lásd. A meghatározás paritás helyettesítés).
Bebizonyítottuk, az egyik legfontosabb tulajdonságait meghatározó n-edrendű (most minden n = 2, 3, ...):
Az ingatlan 1. A meghatározó nem változtatja meg átültetése mátrixok :.
Az ingatlan 2. Ha az egyik sort a meghatározó áll nullák meghatározó nullával egyenlő (ez abból a tényből következik, hogy néhány nullák ebben a sorban feltétlenül írja be a kifejezést minden egyes tagjának a meghatározó).
3. Az ingatlan minden tagja a kapott meghatározó Ha meghatározó cserélték két sor (oszlop) ugyanazok, mint az eredeti, de ellenkező előjellel, azaz cseréje két sor determináns előjelváltása (következik a következő meghatározó átalakító áramkörhöz és a megfelelő helyettesítések: a paritás megváltozott!):
Tulajdonság 4 Determiner, amely két azonos sorban eltűnik (a csomópont a tulajdonságai ezeket a sorokat 3, ebből következik, hogy d = -d, azaz d = 0).
Tulajdonság 5 Ha minden elemét meghatározó i-edik sorának szorozva K tetszőleges számú. a meghatározó megszorozzuk a k szám (az expressziós (48) általános kifejezés meghatározó Felvétel: minden egyes tagja a determináns tartalmaz pontosan egy eleme az i-edik sorának, így minden egyikük szerez k tényezőt, hogy az a meghatározó maga megszorozzuk k ..
6 tulajdonság determináns, amely két arányos vonal nulla (ez következik a tulajdonságait az 5. és 4).
Az ingatlan 7 Ha minden elem i-edik meghatározó vonalak formájában :. ahol j = 1, 2, .... n. a meghatározó egyenlő az összeg két determinánsok, melyek az összes sor, kivéve az i -edik, mint például egy előre meghatározott meghatározó, és az i-edik sora egyik meghatározója állnak az elemek bij. és a másik - az elemek CIJ.
Tulajdonság 8 Ha az egyik sorban a determináns egy lineáris kombinációja a többi sor, a meghatározó nullával egyenlő (meg kell egy következetes alkalmazása tulajdonságok 7, 6, 5, 4).
9 meghatározó tulajdonság nem változik, ha az egyik eleme a megfelelő sorban hozzáadunk más elemek szorozva az azonos számú (7 következik tulajdonságok és 6). Általánosítás. meghatározója nem változik, ha az egyik vonal egészíti lineáris kombinációja a többi vonalon.
Számítsuk determináns alapján annak meghatározását, azaz a írásban n! tagjait és meghatározza a jelek, nehéz lenne. A módszerek lehetővé teszik, hogy kiszámítja a meghatározó az n-edik rendű keresztül meghatározói alacsonyabb rendű.
Tegyük fel, hogy a meghatározó n-ed rendű. Számos k. válassza a meghatározó k sora és k oszlopok. Elements metszéspontjában ezen sorok és oszlopok, mátrix a rend k. A determinánsa ez a mátrix minoromk rendű determináns d. Fordítva, ez lehetséges, és a C (n-k) oszlopok - maradnak kisebb k-adik érdekében. Az alábbiakban elosztási rendszer kisebb k-adik érdekében feltűnő k sora és k oszlopok: