Kombinatorikus tárgyak - studopediya
Téma 2. elemei kombinatorika
Célok és célkitűzések a tanulmány témája
Ez a téma magában foglalja az alapjait a kombinatorika és algoritmusok a generációs kombinatorikus tárgyakat.
Kombinatorika - az egyik szakaszt diszkrét matematika, amely megszerezte nagy jelentőséget miatt alkalmazása az elmélet a valószínűség, matematikai logika, számelmélet, számítástechnika, kibernetika.
Itt a legegyszerűbb példa a kombinatorikus probléma. Hagyja, hogy a város egy a város B, akkor elérheti hajóval, vonattal, busszal, repülővel; B-től C city - hajóval és busszal. Hányféleképpen lehet tenni az utazást A - B - C?
Határozat. Nyilvánvaló, hogy a számos különböző útvonalakat az A-C 4 × 2 = 8, úgy, amellyel kiválasztható a négy lehetséges módon utazni ból B, van két lehetséges az utazás módja a B C.
E megfontolások alapján, az alapvető szabály megfogalmazása kombinatorikus - általában dolgozik.
Szabály működik. Ha néhány tartományban hajthatjuk végre módszerekkel m, és minden egyes ilyen módszerek, néhány más kiválasztási végezhetjük B n módon, a választás a „A és B”, ebben a sorrendben végezhetjük m × n módon.
Ezt a szabályt a következőképpen foglalható össze.
Tegyük fel, hogy szeretne végrehajtani egymás után k intézkedéseket. Ha az első lépéseket, hogy végre n1 módon, a második felvonás - n2 módon, a harmadik út - n3 módon, és így tovább, amíg a k-adik műveletet el lehet végezni nk módon, minden k műveleteket lehet végrehajtani n1 × n2 × n3 × ... × nk módon.
Amikor számítva a számos különböző kombinációk is használják koncentrációja általában.
Szabály összeget. Ha néhány tartományban hajthatjuk végre m a módszerek, és a választás B n más módon, a választás a „egyik vagy A. B” végezhetjük m + n módon.
összege szabály általánosítható tetszőleges számú művelet.
A razd.1.1.1 kapta meg a koncepció készlet. A véges S kap egy listát eleme: S = S1, S2, ..., Sn>, ahol az S1, S2, ..., sn - elemek S (feltétlenül különböző).
Bemutatjuk a koncepció multihalmazt. Multiset unió nem feltétlenül különböző tárgyakat. Meg lehet tekinteni készletet, amelyben minden elem van rendelve egy pozitív egész szám, az úgynevezett sokfélesége.
Véges multiset S lesz írva a következő formában:
Itt minden más, és si ki - sokaságának si elem. Ezután kapcsolja S.
Most úgy néhány kombinatorikai tárgyakat.
Részhalmazok. A készlet M egy részhalmaza S (megjelölés M ÌS vagy S ÉM; M olvasható belép az S, S tartalmaz M), ha és csak akkor, ha minden eleme a készlet M tartozik a beállított S.
Tétel. A száma részhalmazainak n -element S halmaz egyenlő 2 N.
Bizonyítás. Mi minden egyes a részhalmaza S M bináris sor hossza n a következő szabály szerint: si ÎM. akkor és csak akkor, ha az i -edik bit egyenlő eggyel. A számú bináris vektorok n hosszúságú. egy szabály szerint működik, 2 × 2 × ... × 2 = 2 n. Következésképpen, a szám minden részhalmazok -element beállítva n értéke 2 n.
Változatai. Permutáció hívják a helyét a halmaz elemeit egy meghatározott sorrendben.
Tétel. N permutációinak számát azaz -element beállítva S. A számos módon szervezni által adott Pn = n !.
Symbol n. (Read -faktorial n) jelöli a termék a természetes számok 1-től n :! N = 1 × 2 ×. × n. Úgy véljük, hogy 0! = 1.
Bizonyítás. Mi következetesen válassza halmaz elemeit S és gondoskodik azok egy adott sorrendben n a területen. Az első helyen, akkor tegye bármely n eleme. Miután megtöltötte a első helyről a második helyre lehet tenni bármely, a fennmaradó N -1 elemek, stb Ezután a szabály működik minden n helyeken kitöltheti n × (n -1) × (n -2) ×. × 2 × 1 = n. módon. Track-képpen n elemű halmaz lehet egyszerűsíteni n! Módjai.
Elhelyezés. Rendezett k -element részhalmaza az n elem úgynevezett elhelyezése n elemek k.
Tétel. Száma elrendezésére n k formula határozza meg:
.
Bizonyítás. Mi következetesen válassza ki a k-elemeit n -element készlet, és gondoskodik azok egy bizonyos sorrendben k helyeken. Az első helyen tudunk akár az n elem, akkor a második - vagy N -1ostavshihsya stb A szabály pro-magatartás egyáltalán
.
Kombinációk. Elemek kombinációja k n k -element nevezett részhalmaza az n elem.
Tétel. A kombinációk száma az n elem által kifejezett K-sín képlet:
.
Bizonyítás. Az n -element készlet, amelyben különféle rendezett k -element alcsoportok. Minden k elemű részhalmaza is rendelhető Pk módon. Ezután a kombinációk száma n k - száma rendezetlen k elemű részhalmazát egy n -element beállítva, hogy egyenlő
.
A kombinációk száma az egyenletek
,
,
.
Az utolsó tulajdonság következik tétel számának részhalmazainak egy véges halmaza (miért).
Permutációk ismétlésekkel. Permutáció ismétlésekkel nevezzük elrendezés multihalmazok egy bizonyos sorrendben.
Tétel. Permutációinak számát a ismétléssel multihalmazok képlete
,
Proof 1. Tekintsünk egy permutációja multihalmaz és cserélje ki az összes azonos elemeket különböző. Ezután a számos különböző permutációk, amelyek összetétele a helység permutáció is k1! × k2! × ... × km !. Ehhez minden permutáció, megkapjuk n. változatai. ezért
A szám Cn (K1, K2, ..., km) nevezzük polinom együtthatót. Itt egy újabb bizonyíték ennek a tételnek.
Proof 2. szervezi a szükséges multihalmaz n helyek közül lehet választani k1 helyeken s1 elem, amely lehet tenni oly módon, akkor n K1 fennmaradó helyeket választani k2 helyek s2 elem. oly módon, hogy nem lehet tenni, stb Ezután a számos módon szervezni multihalmazt S a szabály ugyanúgy működik (Emlékeztetünk arra, hogy 0! = 1)
.
Kombinációk ismétlés. Kombinációi m elemek n elemek úgynevezett ismétlések csoportok n eleme, ahol minden egyes elem közé tartozik, m típusok.
Példa. A három elem (m = 3) a. b. c teheti egy ilyen kombináció a két ismétlésekkel: AA. ab. al. bb. bc. cc.
Tétel. A számos különböző kombinációi m elemek egyenlő n-nel ismétlésben
.
Bizonyítás. Minden kombináció teljesen meghatározható, ha meghatározza, hogy hány eleme az m típusú értünk. Minden ötvözi sorozata nullák és egyesek által alkotott szabályt soraként egységek, mint az elemek az első típusú szerepel a pályára, majd állítsa nullára, és miután sok írási egységek hány elem a második típusú kombinációját tartalmazza etc . Például, a fenti írásos kombináció a három betű felel majd meg két ilyen szekvenciák:
1100, 1010, 1001, 0110, 0101, 0011.
Így minden egyes kombinációja m N szekvenciának felel meg a N egységek, és m -1 nullák. A szekvenciák száma egyenlő a számos módon, hogy kiválassza m -1 helyezi nullák n + m -1 összesen ülések (), vagy azonos n helyezi szelekciós módszerek egység n + m -1mest (). Egyenlőség következik az egyenletet.
A készítmények és a partíció. Legyen a feladat generáló válaszfalak egy n pozitív egész szám, hogy a szekvencia egész számok p1, p2, ..., pk>, úgy, hogy P1 + P2 + ... + PK = n és pi lehet kiszabni különböző akadályok.
Ha a számok sorrendjében pi fontos, akkor (P1, P2, ..., pk) nevezzük a kompozíció n. Zeneszámok keresése a korlátozás pi> 0.
Ha k van rögzítve, akkor az ilyen készítmény az úgynevezett összetétele n k részek. Ha a keresési kényszer pi> 0 lehet eltávolítani, azaz engedélyezve pi = 0.
Hadd magyarázzuk a különbség a készítmény összetétele a k egységek és a válaszfalak a következő példa:
készítmény (3), (1,2), (2,1), (1,1,1)
az összetétele a két rész (pi> 0): (1,2), (2,1),
az összetétele a két rész (pi ³0): (0,3), (1,2), (2,1), (3,0),
Tétel. Zeneszámok száma n = 2 n -1.
Bizonyítás. Osszuk egy szegmens n hosszúságú n db egységnyi hosszúságú alkalmazásával (n -1) pont. Ezután n kölcsönösen készítmény között megfelel egyedileg tagging bizonyos elválasztási pontokat. Elements-ter készítmény ebben az esetben lesz a távolság a szomszédos pontok. Például, a készítmény (2,2,1), n = 5 ábrán látható 2.1.
Ezért minden készítmény n megfelel egy eljárás kiválaszt egy részhalmazt (n -1) pixel. Azaz, a sávok száma n = 2 n -1.
Tétel. Zeneszámok száma n k darab korlátozott pi> 0 egyenlő.
Bizonyítás. Mi képviseli a készítmény, valamint az igazolás az előző tétel. Mindegyik készítményt a n k darab (pi> 0) felel meg a kiválasztási eljárás (k-1) - eleme részhalmazát pontok n -1 pontot. Azaz, a számát az ilyen készítmények azonosak.
Tétel. N számú dal a k darab pi ³0 ellátást.
Bizonyítás. Mindegyik készítményt az N komponensek, míg k pi ³0 egyik levelezés a bináris be, hogy az első ciklus egyenlő egységek számát felé néző első nulla a készlet, a második - az egységek száma felé néző első és második nullák, stb Egy példa erre reprezentáció készítmények n = 4, k = 3 táblázat tartalmazza 2.1.
beállított hossza n + k -1, a nullák száma egyenlő k -1, ezért a készletek száma (a kívánt készítmények) a számos módon K -1 helyezi nullákat választás n + k -1 ülések (), vagy azonos számú módja választott N ülések egységek n + k -1mest ().
Illusztráció a tétel a száma készítmények n k részek