Permutasiya və Kombinezon

Qeyd. Bu dərsdə nələr öyrənəcəyik? Dərs 1-də biz toplama və vurma qaydaları vasitəsilə düstursuz saymağı öyrəndik. İndi isə həmin qaydaların ən çox rast gəlinən iki tətbiqi ilə tanış olacağıq: permutasiya (düzülüş/ardıcıllıq) və kombinezon (seçim). Lakin bu dərsin əsas hədəfi sadəcə $n!$ və $C(n,k)$ düsturları deyil. Əsas hədəfimiz bu suala cavab tapmaqdır: Bu suala düzgün cavab verə bilən şagird düsturları sərbəst şəkildə özü müstəqil çıxara bilir; cavab verə bilməyən şagird isə düsturları əzbərləsə belə, onları səhv yerlərdə tətbiq edir. Buna görə də aşağıda hər bir düsturu Dərs 1-də öyrəndiyimiz vurma qaydası əsasında yenidən quracağıq — yəni heç bir düsturu göydəndüşmə kimi qəbul etməyəcəyik.

Qeyd. «Hər bir obyekt düz $d$ dəfə» — bu şərti unutmayın. Bölmə prinsipi yalnız artıq sayılan hallar bütün obyektlər üçün bərabər (eyni) olduqda işləyir. Əgər bəzi obyektlər $6$ dəfə, bəziləri isə $3$ dəfə sayılıbsa, nə $6$-ya, nə də $3$-ə bölmək olmaz — əvvəlcə məsələni hallara ayırmaq lazımdır. Bu incəlik dairəvi düzülüşlərdə və «təkrarlı obyektlər» tipli məsələlərdə dəfələrlə qarşımıza çıxacaq.

Qeyd. Niyə $0!=1$ qəbul edilir? Bu sadəcə ixtiyari bir qərar deyil, riyazi uyğunluq tələbidir. $n!=(n-1)!\cdot n$ münasibətini $n=1$ üçün yazsaq: $1!=0!\cdot 1$, yəni $0!=1$ alınır. Bunun kombinatorik mənası da var: $0$ ədəd obyekti düzməyin sadəcə bir üsulu var — «heç nə düzməmək». Aşağıdakı bütün düsturlarda $0!=1$ kimi qəbul edilməsi, kənar hallarda da düsturların doğru işləməsini təmin edir.

Qeyd. Niyə məhz «əvvəlcə sərbəstləri düz»? Çünki məhdudiyyət qızların bir-birinə nəzərən mövqelərindədir. Oğlanları düzdükdən sonra qızların hansı mövqelərə düşə biləcəyi tam aydın olur və heç bir hal nəzərdən qaçmır. Əksinə, qızlardan başlasaydıq, hər addımda «indi bura oğlan lazımdırmı?» sualı ilə baş-başa qalardıq. Ümumi qayda: məhdudiyyəti olmayan obyektləri əvvəlcə düz, məhdud olanları isə yaranmış boşluqlara yerləşdir.

Qeyd. Vuruqların sayını diqqətdə saxlayın. $P(n,k)$-nı hesablayarkən $n$-dən başlayaraq aşağıya doğru düz $k$ sayda vuruq yazın. Ən çox buraxılan texniki səhv vuruqların sayını qarışdırmaqdır: $P(7,3)=7\cdot 6\cdot 5=210$, ancaq $7\cdot 6\cdot 5\cdot 4$ yox. Kənar hallar: $P(n,n)=n!$ (çünki $0!=1$), $P(n,1)=n$, $P(n,0)=1$.

Qeyd. Bu isbatın məğzini bir cümlə ilə yadda saxlayın: seçmək $=$ seçib düzmək, sonra isə həmin düzülüşlərin sayına bölmək. Kombinatorikada qarşılaşacağınız onlarla düstur məhz bu məntiq əsasında çıxarılır — əvvəlcə sıralı olanı tap (bu asandır), sonra isə artıq sayılmış (təkrarlanan) hallara böl.

Qeyd. Faydalı qısaltma. $C(n,k)=C(n,n-k)$. Bunun səbəbi isə çox sadədir: $k$ element seçmək — əslində yerdə qalan $n-k$ elementi seçməklə eyni şeydir. Buna görə də $C(20,18)$-i hesablamaq üçün $18$ vuruq yazmağa heç bir ehtiyac yoxdur: $C(20,18)=C(20,2)=190$. Bu tipli eyniliklərin sistemli öyrənilməsi (Paskal üçbucağı, Vandermonde və s.) Dərs 3-ün mövzusudur. Kənar hallar: $C(n,0)=C(n,n)=1$, $C(n,1)=n$.

Qeyd. Ən çox yol verilən səhv — «əvvəlcə birini seçim, sonra digərlərini». Bu səhvi bir dəfə anlayan şagird bir daha onu təkrarlamır, ona görə də çox diqqətlə nəzər yetirin.Məsələ. $6$ oğlan və $4$ qızdan ibarət qrupdan $3$ nəfərlik komissiya seçilir. Komissiyada ən azı bir qız olmalıdır. Bu seçimi neçə üsulla etmək olar?Yanlış həll. «Əvvəlcə bir qız seçirəm: $4$ imkan var. Sonra isə yerdə qalan $9$ nəfərdən (istənilən) $2$ nəfəri seçirəm: $C(9,2)=36$. Cavab: $4\cdot 36=144$.»Bəs səhv haradadır? Bu hesablama $\{Q_1,Q_2,O_1\}$ komissiyasını tam iki dəfə sayır: bir dəfə «seçilmiş qız $Q_1$, yerdə qalanlar $Q_2,O_1$» kimi, bir dəfə də «seçilmiş qız $Q_2$, yerdə qalanlar $Q_1,O_1$» kimi. Halbuki komissiya eyni komissiyadır! Üstəlik, artıq sayma hər dəfə bərabər miqdarda olmur (bir qızlı komissiyalar bir dəfə, iki qızlı olanlar iki dəfə, üç qızlı olanlar isə üç dəfə artıq sayılır), buna görə də tapılmış ədədi sadəcə başqa bir ədədə bölməklə doğru cavabı almaq mümkün deyil.Düzgün həll — tamamlayıcı sayma. Bütün komissiyaların sayı: $C(10,3)=120$; tərkibində heç bir qız olmayanların (yəni yalnız $3$ oğlandan ibarət olanların) sayı: $C(6,3)=20$. Cavab: $120-20=100$.Alternativ yol — hallara ayırma. Qızların sayına uyğun olaraq məsələni hallara bölək: $1$ qız: $C(4,1)C(6,2)=4\cdot 15=60$; $2$ qız: $C(4,2)C(6,1)=6\cdot 6=36$; $3$ qız: $C(4,3)=4$. Cəmi: $60+36+4=100$. dəqiqdirYadda saxlayın: «ən azı bir» şərtini gördükdə ya tamamlayıcı saymadan, ya da məsələni hallara ayırmaqdan istifadə edin — amma heç vaxt «birini əvvəlcədən seçim» məntiqi ilə hərəkət etməyin.

Qeyd. Gözəl bir müşahidə: $C(n,k)$ əslində iki növ obyektdən ibarət düzülüşdür. Yuxarıdakı nümunədə cavab $35=C(7,3)$ alındı — bu isə heç də təsadüf deyil.

$$\frac{n!}{k!\,(n-k)!}$$

ifadəsi eyni zamanda həm $n$ elementdən $k$-nı seçmək, həm də $k$ ədəd «Q» (qırmızı) və $n-k$ ədəd «M» (mavi) hərfini düzmək deməkdir. Bunun səbəbi çox aydındır: belə bir düzülüşü təyin etmək üçün sadəcə hansı mövqelərin qırmızı olacağını demək kifayətdir — bu isə $n$ mövqedən $k$-nı seçməyə bərabərdir.Bu müşahidə praktikada çox geniş istifadə olunur: «$10$ dəfə sikkə atıldı, tam $3$ dəfə üz (gerb) gəldi — belə neçə fərqli ardıcıllıq var?» sualının cavabı da məhz $C(10,3)=120$-dir.

Qeyd. Əvvəlcə aydınlaşdıraq: hansı hallar «eyni» sayılır? Dairəvi masa ətrafındakı oturuşlarda əsas məsələ kimin kiminlə qonşu olmasıdır. Bütün masanı (və ya oturanları) bir addım fırlatsaq belə, hər kəsin qonşusu yenə də eyni qalır — deməli bu, heç də yeni bir oturuş variantı deyil. Standart qəbul edilmiş qayda budur: masanı fırlatmaqla bir-birinə çevrilə bilən düzülüşlər (oturuşlar) eyni hesab olunur. (Əgər stullar öncədən nömrələnibsə, onda bu razılaşma pozulur və məsələ adi cərgə məsələsinə çevrilir — buna görə də şərti diqqətlə oxuyun!)

Qeyd. Boyunbağı (bilərzik) halı. Əgər obyektlər ipə düzülüb boyunbağı formasını alırsa, onda həmin boyunbağını məkanda çevirmək (tərsinə fırlatmaq) olar — yəni fəzada güzgü əksi də eyni sayılır. Onda ($n\ge 3$ üçün) yekun cavab $\dfrac{(n-1)!}{2}$ olur: çünki hər düzülüş bir də özünün güzgü əksi ilə cütləşir. Məsələn, $7$ fərqli muncuqdan $\frac{6!}{2}=360$ müxtəlif boyunbağı düzəltmək olar. Məsələnin şərtində «boyunbağı», «bilərzik», «çevirmək olar» sözlərini gördükdə bu ikiyə bölmə prinsipini unutmayın.

Qeyd. $k$ obyektin dairəvi seçimi. Əgər $n$ obyektdən $k$-sını seçib ardınca dairə üzrə düzmək lazımdırsa, onda əvvəlcə sıralı olaraq seçirik ($P(n,k)$), daha sonra isə fırlanmalara bölürük: $\dfrac{P(n,k)}{k}$.

Qeyd. Cərgədə $m+1$, dairədə isə $m$ qədər boşluq. Boşluqların sayındakı bu fərqi nəzərə almamaq dairəvi məsələlərdə ən çox rast gəlinən səhvdir. Bunun səbəbi vizual olaraq aydındır: cərgənin iki ucu var, dairənin isə heç bir ucu yoxdur.

Qeyd. Altı klassik səhv.

1. 1. Sıranın önəmini səhv müəyyənləşdirmək. «Komissiya» sözünü görüb $P(n,k)$ yazmaq (və ya əksinə). Yoxlanması: seçilmiş hər hansı iki obyektin yerini dəyişin — vəziyyət (nəticə) dəyişdimi?
2. 2. «Əvvəlcə birini seçim, sonra qalanları» yanaşması. Yuxarıdakı $144$ əvəzinə $100$ alınan nümunəyə baxın. «Ən azı bir» şərti $\Rightarrow$ mütləq tamamlayıcı sayma və ya hallara ayırma.
3. 3. Eyni obyektləri fərqli kimi hesablamaq. Eyni rəngli topları nömrələnmiş kimi saymaq cavabı qeyri-ixtiyari olaraq $n_1!\,n_2!\cdots$ dəfə şişirdir.
4. 4. Bərabər olmayan artıq saymalara bölmək. Bölmə prinsipi yalnız hər bir obyekt eyni sayda artıq sayıldıqda keçərlidir.
5. 5. Dairəvi düzülüşdə $n!$ yazmaq. Fırlanmalar eyni sayılırsa, cavab həmişə $(n-1)!$-dir. Əgər stullar öncədən nömrələnibsə, isə əksinə — adi $n!$ olur.
6. 6. Blokun daxilini unutmamaq. «Yan-yana olsun» məsələsində ən sonda bloka aid $k!$ vuruğunu yazmağı unutmamaq lazımdır.

Qeyd. Həll alqoritmi — dörd mühüm sual.

1. 1. Nəyi sayıram? Özünüz üçün bir tipik obyekti kağızda yazın (məsələn, konkret bir komissiya, konkret bir söz).
2. 2. Sıra (ardıcıllıq) önəmlidirmi? İki elementin yerini dəyişərək nəticəni yoxlayın.
3. 3. Təkrarlanma varmı? Eyni (identik) obyektlər varsa — bölmə prinsipindən istifadə edin; əgər eyni obyekti təkrar seçmək icazəsi verilirsə — onda cavab $n^k$ tipində olur.
4. 4. Məhdudiyyət hansı tipdədir? «Yan-yana olsun» $\Rightarrow$ blok (yapışdırma); «yan-yana olmasın» $\Rightarrow$ boşluq (aralıq) və ya tamamlayıcı sayma; «ən azı bir» $\Rightarrow$ tamamlayıcı sayma; «dəqiq olaraq $k$ dənə» $\Rightarrow$ birbaşa (diqqətli) seçim.

Qeyd. Xülasə cədvəli.

Qeyd. Blok metodunun incəliyi. Blokun içindəki obyektlər bir-birindən fərqlidirsə nəticə $k!$-a vurulur; eynidirsə, vurulmur. Bu bir cümləni yadda saxlamaq sizi onlarla səhvdən xilas edəcək.