-дәріс тақырыбы: Комбинаторика. Орналастыру және теру(2 сағат)

9-дәріс тақырыбы: Комбинаторика. Орналастыру және теру(2 сағат)

Комбинаториканың негізгі есебі – қайта санау және ақырлы жиын элементтерін тізбектеу.

Егер берілген ақырлы жиын элементтерінің қаншасының берілген бір қасиетке ие екендігін анықтау қажет болса бұл қайта санау есебі, ал берілген қасиетке ие барлық элементтерді анықтау керек болса, бұл тізімдеу есебі Комбиторика есебін дәлелдеуде екі ереже жиі қолданылады. Олар: қосу және көбейту ережелері.

Егер Х n элементтерден тұратын ақырлы жиын болса, Х объектісін Х тен n тәсілмен алуға болады дейді және Х=n болып белгіленеді.

Бұл ережені k=2 үшін былай жазуға болады: Егер х объектісі m тәсілмен таңдалса, ал у басқа n тәсілмен таңдалса, онда "не х, не у" таңдау m+n тәсілмен іске асырылады (х және у элементтерін бір уақытта таңдау болмайды).

Көбейту ережесі. Егер х объектісін m тәсілмен таңдауға болса, және осындай таңдаудан кейін у объектісін өз кезегінде n тәсілмен таңдауға болса, онда реттелген (х, у) жұбын mn тәсілмен таңдауға болады.(х, у – таңдаулары тәуелсіз).

Жалпы жағдайда, егер х₁ объектілері n₁ тәсілмен таңдалса, одан кейін х₂ n₂ тәсілмен таңдалса және кез келген 2 i  m-1 үшін х₁, х₂, …, х_i объектілерін таңдағаннан кейін х_i+1 объектісін n_i+1 тәсілмен таңдауға боллатын болса, онда m объектіден құралған (х₁, х₂, …, х_m) реттелген тізбегі n₁  n₂ … n_m тәсілмен таңдалады.

Х={х₁, …, х_n} жиынынан алынған х_i1, …, х_ir элементтерінің жиынтығы n элементтен алынған r көлемді таңдама деп аталады.

Егер элементтердің орналасу тәртібі берілген болса, таңдама реттеген деп, ал орналасу тәртібіне белгілі бір шарт қойылмаса, таңдама реттелмеген деп аталады.

Таңдамаларда элементтердің қайталануы да, қайталанбауы да мүмкін.

Элементтері қайталануы мүмкін (n, r) - таңдамасы (n, r)-қайталама таңдамасы деп аталады. Ал егер реттелген (n, r) таңдаманың элементтері қос қостап әр түрлі болса, (n, r) қайталанбайтын таңдама немесе жай ғана (n, r)-орналасу деп аталады.

(n, n)-қайталанбайтын орналасу Х жиынын алмастыру деп аталады.

Элементтері қайталануы мүмкін реттелмеген (n, r)-таңдама, қайталанба (n, r)-теру деп аталады. Егер реттелмеген (n, r) таңдаманың элементтері қос қостан әр түрлі болса, онда ол қайталанбайтын (n, r)-теруі немесе жай ғана (n, r) теруі деп аталады. Кез келген (n, r)-теруін n-элементті жиынның r-элементті ішкі жиыны деп қарауға болады.

Мысал, айталық Х={1, 2, 3} болсын.

1) (1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3) - (3, 2)-қайталама орналастырулар.

2) (1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2) - (3, 2)-қайталама орналасу;

3) (1, 2, 3), (1, 3, 2), (3, 2, 1), (2, 1, 3), (3, 1, 2), (2, 3, 1) – Х жиынын алмастыру;

(Дербес жағдайда бұл өрнек негізі n санау жүйесінде r позицияда жазылған әр түрлі сандардың нешеу екендігін анықтайды.).

Шынында, r элементтен тұратын реттелген тізбектің бірінші мүшесі n тәсілмен таңдалады, екіншісі - (n-1) тәсілмен, соңғысы - (n – r + 1) тәсілмен. Жалпыланған көбейту ережесінен ізделінді формуланы аламыз.

Шынында да Х = {x₁, …, x_n} жиынының элементтерінен құрылған әрбір қайталанба (n, r)- В теруі үшін, r нөл мен n-1 1-ден тұратын (i-1)-ші және i бірлердің (мұндағы 2 i  n-1) арасындағы нөлдердің саны В теруіндегі x_i элементтерінің санына тең, ал бірінші бірдің алдындағы нөлдердің саны В-ға енетін x_i элементтерінің санына тең болатын ұзындығы (В) болатын векторды сәйкестендіруге болады.

Комбинаторикалық классикалық есептерінің бірі, қандай да бір объектілердің «жәшіктерде» белгілі бір шектеулер орындалатындай орналастыру санын анықтау болып табылады. Бұл есепті төмендегідей тұжырымдауға болады:

Шынында, Х = {x₁, …, x_r} болсын. Олай болса кез келген бейнелеуді f : ХY реттелген (f(x₁), f(x₂), …, f(x_r)), мұндағы f(x_i)Y, тізбегі түрінде кескіндеуге болады, яғни біз функционал бейнелеулер мен саны n^r-ге тең, көлемі n болатын Y жиынынан алынған қайталанба реттелген таңдамалар жиынының арасында өзара бір мәнді сәйкестік орнаттық.

(Егер Х - объектілер, Y- "жәшіктер" болса, онда f функция әрбір хХ объектісі үшін объект орналасқан f(x)Y жәшігін көрсетеді).

Бірден артық емес объект орналасқан жәшігі бар орналасудың санын табу қиын емес, ондай теру бір мәнді функцияларға сәйкес (инъективті бейнелеу).

Шынында да, бұл жағдайда реттелген тізбек (f(x₁), f(x₂), …, f(x_r)) әр түрлі болуы керек, яғни бұл тізбек қайталанбайтын теру болып табылады.

Негізгі әдебиет: 1[130-134]; 2[159-164].

Қосымша әдебиет: 7[50-80] .

Бақылау сұрақтары:

1. 
   Қосу, көбейту ережелерін атаңыз.
   
2. 
   Реттелген, реттелмеген таңдамалар қалай аталады?
   
3. 
   Орналасу, теру сандарын қандай формулалармен есептеуге болады?
   
4. 
   Қанша функционал бейнелеулер f : X  Y бар?
   
5. 
   Өзіне өзін бейнелейтін қанша биективті бейнелеу құрастыруға болады?