Осынды және көбейтінді ережелері

Қосындылар ережесі. Егер a заты m тәсілмен таңдап алынатын болса, ал b заты басқа n тәсілмен таңдап алынса, онда “немесе a, немесе b“ таңдауын m + n тәсілін таңдап алуға болады.

Бұл ережені басқаша былай айтуға болады. A және B – ақыры жиындар болсын. Онда n(A È B) = n(A) + n(B).

N(A) бірнеше жиындар үшін бұл ереже былай жалпыланады. Егер X₁, X₂,…, X_k – қос қостан қиылыспалы ақыры жиындар болса, онда n(X₁ È…È X_k) = n(X₁) +…+ n(X_k).

Мысал.Дүкенде 6 түрлі шоколад кәмпит және 10 түрлі карамель кәмпит бар. Кәмпиттің бір түрін неше тәсілмен сатып алуға болады?

А және В – шоколад және карамельді кәмпиттердің жиыны болсын. Бұл жиындар қиылыспайды, сондықтан n(A ÈB) = n(A) + n(B) = 6 + 10 = 16. Кәмпиттің бір түрін 16 тәсілмен сатып алуға болады.

Көбейтінділер ережесі. Егер А заты m түрлі тәсілмен таңдап алынатын болса және осындай әр таңдаудан кейін В заты n тәсілмен таңдап алынса, онда “a және b” таңдауын m×n тәсілмен таңдап алуға болады.

Бұл ережені басқаша былай айтуға болады. A және B – ақырлы жиындар болсын. Онда n(A´B) = n(A) × n(B).

Бірнеше жиындар үшін бұл ереже былай жалпыланады.

Егер X₁, X₂,…, X_k – ақырлы жиындар болса, онда n(X₁´…´ X_k) = n(X₁)× …× n(X_k).

Есеп. А пунктен В пункт арқылы С пунктқа дейін маршруттар санын табу керек. А-дан В-ға дейін 5 жол бар, В-дан С-ға дейін 3 жол бар.

Екі жиынды қараймыз S = {s₁, s₂, s₃, s₄, s₅} – A-дан B-ға баратын жолдар, T = {t₁, t₂, t₃} –B-дан C-ға баратын жолдар. Енді A-дан C-ға баратын жолды (s_i, t_j) түрінде көрсетуге болады, мұнда i = 1, 2,3,4,5; j = 1, 2, 3. Онда, S ´ T – A-дан C-ға баратын барлық жолдардың жиыны

n(S ´ T) = n(S) × n(T) = 5×3 = 15.

Енгізулер және шығарулар формуласы. Бұл формуланы 2 және 3 жиындар үшін қарастырамыз.

n(A) – А жиынның элементер санын білдірсін, онда

n(A È B) = n(A) + n(B) – n(A Ç B)

n(A È B È C) = n(A) + n(B) + n(C) – n(A Ç B) – n(A Ç C) – n(B Ç C) +

+ n(A Ç B Ç C).

Алмастырулар

n- дәрежелі алмастыруы деп n түрлі заттардың белгілі бір ретте орналастыруын айтады.

Бізге заттардың орналасуы ғана қажет, сондықтан 1 2...n сандардың алмастыруын қарастырамыз. n- дәрежелі алмастырулар саны P_n деп белгіленеді.

n = 1, n = 2, n = 3 болғанда 6 алмастыру бар: 123, 132, 213, 231, 312, 321.

Теорема. n- дәрежелі алмастырулар саны n!-ға тең.

Дәлелдемесі n саны индукциясымен дәлелдейміз. n = 1 болғанда жалғыз ғана алмастыру бар: сондықтан P₁ = 1! теңдігі орындалып тұр.

P_n = n! деп болжайық, және 1, 2,…, n, n + 1 сандарының алмастыруын қарастырайық.

n + 1 санын басқа n сандарының ішінде бірінші, екінші, …, n-ші және (n + 1)-ші орынға қоюға болады. Осы нұсқаулардың әрбіреуінде n сандарын, индукцияның болжамы бойынша, n! тәсілімен орналастыруға болады. Бұдан, (n + 1) сандарын (n + 1)×n! тәсілмен орналастыруға болады. Осылайша, P_n+1 = (n + 1)!

Математикалық индукция принципі бойынша P_n = n! формуласы кез келген натурал n үшін орындалады.

Мысал 1. 6 адамды бір қатарға қанша тәсілмен отырғызуға болады?

6 адамның әрбір орналасуы ол 6-дәрежелі алмастыру, сондықтан 6 адамның бір қатарға орналастыру тәсілдер саны 6-дәрежелі алмастырулар санына тең: 6!

Мысал 2. 6 адамды неше әдіспен дөңгелек үстел басына отырғызуға болады?

6 адамды 6! әдіспен дөңгелек үстел басына отырғызуға болады. 6 адамның бәрін бір орынға жылжытатын болсақ, онда олардың орналасуы өзгермейді, өйткені әрбір адамның көршілері сақталады. Дөңгелек үстел басындағы 6 адамды 6 рет жылжытуға болады. Сондықтан дөңгелек үстел басына 6 адамды = 5! тәсілмен отырғызуға болады.

Кейбір есептерде берілген дәреженің барлық алмастыруларын талап етеді. Әдістердің бірі – лексикографикалық (сөздік) ретпен тізбектеу.

A = a₁a₂…a_n және B = b₁b₂…b_n алмастырулары берілсін. Кейбір i, 1 £ i < n үшін a_i = b_i және a_i+1 < b_i+1 болса, онда лексикографикалық ретте A < B деп есептеледі.

Лексикографикалық ретте бірінші алмастыруы 1, 2…, n болып, ал соңғысы n, (n – 1),…, 2, 1 алмастыру болады.

Лексикографикалық ретте алмастыру алгоритмі.

1) Бірінші 1, 2,…, n алмастыруы құрылады.

2) Ағымдағы a₁a₂…a_n алмастыруда a_i+1 >…>a_n және a_i < a_i+1 максимальді азаятын суффикс бар болады.

3) Егер i = 0 болса, онда ағымдағы алмастыру соңғы болады. 7-ші пунктке көшу керек.

4) Егер i > 0 болғанда a_i+1 >…> a_n сандары ішінен a_j санынан үлкен, ең кіші a_i саны ізделеді.

5) a_i және a_j сандарын орындарымен ауыстырамыз: a_ja_i+1…a_j…a_n

6) a_ja_i+1…a_j…a_n сандарын өспелі ретпен орналастырамыз. Шыққан алмастыруды шығарамыз.

7) Алгоритм соңы.

Мысал 3. (Максимальді өспелі іштізбек туралы есеп). a₁, a₂,…, a_n алмастыруы берілген. , ,..., іштізбек өспелі болатындай 1 £ i₁ < i₂ < … < i_k £ n тізбекті табу керек.

a₁, a₂,…, a_n тізбекті кему қасиеттері бар I₁,…, I_s жиыншаларға бөлеміз. I_t жиыншасы “кему” қасиетіне ие болады, егер кез келген i, j Î I_t үшін a_i > a_j теңсіздік орындалатын болса. Басқа сөзбен айтқанда a₁, a₂,…, a_n тізбек кемімелі іштізбектерге бөлінеді.

Бұдан ұзындығы s-ке тең өспелі тізбек құрастырылады. Ол I_t жиындардың әрбіреуінің бір элементінен тұратын болады. s k-ның максимальді мүмкін мәні болады.

Шынымен, өспелі іштізбектің ұзындығы s-тен аспау керек: бұл іштізбек әрбір I_t жиыншасының бір элементінен артық тұра алмайды.

Алмастыруды кемімелі іштізбекке бөлуді қарапайым мысалдан бастайық. Кестенің бірінші жолында алмастырудың өзі, ал төменде пайда болатын іштізбектер орналасады.

Біз өнімді болуға тырысамыз. Әрбір келесі санды, реттін бұзбай және ең кіші соңғы саны бар тізбекті таңдай отырып, орналастыруға болатын тізбекке жазамыз.

Кез келген іштізбекте тәртіп бұзылатын болса, біз жаңасын ашамыз. Осылай 19 саны жаңа тізбекті ашады. 7-ні 19-ға жазамыз, 18 және 19 жаңаны ашады.11-ді 18-ге және 20-ға жазуға болады, бірақ 18-ге тиімдірек. Осылай 5 іштізбек пайда болды.

Соңғы жолдың кез келген санын аламыз, мысалы соңғысын. Неге 12 саны ең соңғы жолда жазылған? Себебі алдыңғы жолда одан кіші сан жазылған, нақтырақ айтсақ 9. Ал 9 саны 4-ші жолға жазылды, себебі 4 саны екінші жолда, ал 4 санының алдында 3 саны 1 жолда. Осылай өспелі іштізбекті құрдық: 3,4,5,9,12.

Жалпы жағдайда да осылай болады: әрбір жолдың әрбір санында біріншісінен басқа, келесі жолға жібермейтін сан болады. Ол сан кіші және алмастыруда бұрынырақ тұрады. Соңғы жолдан жоғарыға қарай тізбектелген сандар бізге өспелі іштізбекті береді. Оның ұзындығы максимальды.

Мысал 4.n- дәрежелі ретсіздік деп барлық i = 1, 2,…, n үшін

a_i ¹ i болатын a₁a₂…a_n алмастыруын айтады. n дәрежесінің барлық ретсіздігінің санын табу керек.