Орчин үед комбинаторик нь компьютерийн ухаан, кодчилолын онол, магадлал, статистик, программчлал гэх зэрэг олон онолд түгээмэл ашиглагдаж байна. (Бид энэ өгүүлэлд тоолох комбинаторикийн үндсэн дүрмүүдийг жишээ бодлогуудаар тайлбарлахыг зорив.) 

Дэлхий $4$ зааны нуруун дээр тогтдог уу? гэж асуувал хэн ч үгүй гэж хариулах байх. Харин тоолох комбинаторик нь $4$ үндсэн дүрэм дээр тогтоно.

НИЙЛБЭРИЙН ДҮРЭМ

“Комбинаторик” сургууль $A_1, A_2, ... , A_n$ гэсэн $n$ ширхэг ангитай бөгөөд аль ч хоёр ангид зэрэг сурдаг сурагч байхгүй гэж саная. $A_1$ анги $m_1$ сурагчтай, $A_2$ анги $m_2$ сурагчтай гэх мэтээр $A_n$ анги $m_n$ сурагчтай байсан гэе. Тэгвэл энэ сургуулиас $1$ сурагчийг хичнээн янзаар сонгож болох вэ?

Хариу: $m_1+m_2+...+m_n$ буюу сургуулийн нийт сурагчдын тоо байх нь ойлгомжтой. Энэ маш энгийн дүрмийг нийлбэрийн дүрэм гэнэ.

ҮРЖВЭРИЙН ДҮРЭМ

Цэнхэр нүдэн” гариг дээр $n$ улс байдаг ба эдгээр улсуудын цагаан толгой нь $A_1,A_2, ...,A_n$ болог. (Зарим улсууд ижилхэн цагаан толгойтой байж болно шүү дээ!) $A_1$ цагаан толгой $m_1$ үсэгтэй, $A_2$ цагаан толгой $m_2$ үсэгтэй, гэх мэтээр $A_n$ цагаан толгой $m_n$ үсэгтэй байжээ. Улс бүрийн цагаан толгойноос нэг, нэг үсэг авч, хамгийн эхэнд $A_1$-ээс авсан үсгийг , дараа нь $A_2$-оос авсан үсгийг, гэх мэтээр хамгийн сүүлд $A_n$–ээс авсан үсгийг бичиж $n$ урттай “үг” зохиоё. Ийм үгийг хичнээн янзаар зохиож болох вэ?

Хариу: $m_1\cdot{m_2}\cdot...\cdot{m_n}$ янзаар зохиож болно.

Энэ дүрмийг үржвэрийн дүрэм гэнэ. Бид тоолох комбинаторикийн $2$ үндсэн дүрмээ томъёолчихлоо. Чухамхүү энэ $2$ дүрэм дээр комбинаторик маань тогтдог тул маш сайн ойлгож аваарай! Одоо шууд жишээ бодлого авч үзэцгээе.

Бодлого 1. $S={1,2,...,499,500}$ гэсэн олонлогоос хуваарь нь натурал тоо бөгөөд өсдөг геометр прогресс үүсгэдэг $4$ тоог хичнээн аргаар сонгож болох вэ?

Бодолт: $x_1, x_2, x_3, x_4$ нь $S$ олонлогоос сонгогдсон тоонууд бөгөөд $$x_1=a_1,\ x_2=a_1q,$$ $$x_3=a_1q^2,\ x_4=a_1q^3$$ гэсэн геометр прогресс болог. (Энд $q$ натурал тоо ба $q\ge2$ юм.) Тэгвэл энэ прогрессийн хамгийн их гишүүн $x_4=a_1q^3\le500$ байх ёстой.

Өөрөөр хэлбэл, $$q\le\sqrt[3]{\dfrac{500}{a_1}}\le\sqrt[3]{500}\approx7.9.$$ $q$ маань натурал тоо шүү дээ! Иймд $2\le{q}\le7$ буюу $q$ хуваарийн авч болох утга $q\in{1, 2, 3, 4, 5, 6, 7}$ болно. Нөгөө талаас $1\le{a_1}\le\left[\dfrac{500}{q^3}\right]$ байхаар геометр прогрессийн эхний гишүүнийг сонгож болно. $q=2$ байх геометр прогрессийн эхний гишүүн $a_1$-ийг $$\left[\dfrac{500}{2^3}\right]=\left[\dfrac{500}{8}\right]=[62,5]=62$$ янзаар сонгоно.

Прогрессийн эхний гишүүн ба хуваарь мэдэгдэж байхад уг прогресс бүрэн тодорхойлогдоно.

Дээрхитэй адилаар, $q=3$ байх геометр прогрессийн эхний гишүүн $a_1$-ийг $$\left[\dfrac{500}{3^3}\right]=\left[\dfrac{500}{27}\right]=18$$ янзаар гэх мэтээр $q=4$ байхад $a_1$–ийг $7$ янзаар, $q=5$ байхад $a_1$–ийг $4$ янзаар, $q=6$ байхад $a_1$–ийг $2$ янзаар, $q=7$ байхад $a_1$–ийг $1$ янзаар тус тус сонгож болно. Эндээс манай бодлогын хариу: $62+18+7+4+2+1=94$ болов. Сурагчид та бүхэн хойшид бодлогын өгүүлбэрийг уншиж, харсныхаа дараа энэ бодлогод ямар дүрэм ашиглав гэдгийг заавал эргэцүүлэн бодож байгаарай.

Бодлого 1–ийн тухайд бид нийлбэрийн дүрэм ашигласан.

Бодлого 2. Цифрүүд нь ялгаатай $4$ оронтой хичнээн сондгой тоо байх вэ?

Бодолт. $\overline{abcd}$ дөрвөн оронтой тоо болог.

а) $4$ оронтой тоо хэд байх вэ?

$a$ цифрийг $0$–ээс бусад $1, 2, ..., 9$ цифрүүдийн алинаар ч сонгож болно. Ө.х $a$ нь $9$ янзын сонголттой. $b, c, d$ цифрийг $0, 1, ..., 9$ цифрүүдийн алинаар ч сонгож болно. Өөрөөр хэлбэл, $b, c, d$ нь тус бүрдээ $10$ янзын сонголтой. Иймд $\overline{abcd}$ дөрвөн оронтой тоо нийт $9\cdot10\cdot10\cdot10=9000$ байна.

б) $4$ оронтой сондгой тоо хэд байх вэ?

$a$ цифрийг $9$ янзаар, $b, c$ цифрийг тус тус $10$ янзаар сонгоно. Харин $d$ цифрийг $1, 3, 5, 7, 9$ цифрүүдээс сонгож болох тул $d$–ийн сонголтын тоо $5$ болно. Иймд $4$ оронтой сондгой тоо нийт $$9\cdot10\cdot10\cdot5=4500$$ байна. Харин одоо үндсэн бодлогоо бодъё.

Нэгжийн орны $d$ цифрийг $1, 3, 5, 7, 9$–өөс буюу $5$ аргаар сонгож болно. $d$ сонгогдсон гэе. Одоо мянгатын орны $a$ цифрийн сонголтын тоо $8$-тай тэнцүү ($a\ne0$ ба $a\ne{d}$) $d$ ба $a$ сонгогдсон гэе. Зуутын орны $b$ цифрийг $a$ ба $d$–ээс ялгаатай $8$ цифрээс сонгож болно. Ингээд $d, a, b$ цифрүүд сонгогдсон байхад аравтын орны $c$ цифрийг үлдсэн $7$ цифрээс сонгоно. Иймд манай бодлогын хариу: $$5\cdot8\cdot8\cdot7=2240$$ тоо бодлогын нөхцлийг хангана.

Бодлого 2-ын бодолтонд үржвэрийн дүрэм ашигласан.

ЯЛГАВРЫН ДҮРЭМ

Ангийн нийт сурагчдын тоо $m$ бөгөөд энэ ангийн хөвгүүдийн тоо $k$ бол анги хэдэн охидтой вэ?

Хариу: Ангийн хөвгүүдийн тоо $m-k$.

Тэгэхээр ялгаврын дүрмийг цэвэр математик хэлээр ингэж томъёолно. $A$ төгсгөлөг олонлог бөгөөд $B$ түүний дэд олонлог болог. $B$-д ордоггүй хэрнээ $A$-д байдаг элеметүүдээс тогтох олонлогийг $A-B$ ялгавар олонлог гэнэ. Тэгвэл $$|A-B|=|A|-|B|$$ байна. (Энд $|A|$-аар $A$ олонлогийн элементийн тоог тэмдэглэнэ.)

Энэ дүрмийг: Олох ёстой боломжийн тоо нь нийт боломжийн тооноос эсрэг боломжийн тоог хассантай тэнцүү гэж маш энгийнээр ойлгож аваарай.

Бодлого 3. Бичлэгтээ ядаж $2$ ялгаатай цифр агуулсан, $1000$-аас их биш хэдэн натурал тоо байх вэ?

Бодолт: Бид хэрвээ шууд тоолъё гэвэл багагүй бэрхшээлтэй тулгарна. Жишээлбэл, ядаж $2$ ялгаатай цифр агуулсан $3$ оронтой тоо хэд байхыг шууд тооцоолох гээд үзээрэй. Харин ялгаврын аргаар маш хялбархан бодогдоно. Тэгэхээр $A=\{1, 2, ..., 1000\}$ болог. $B$-ээр бүх цифрүүд нь ижилхэн байдаг, $1000$-аас их биш натурал тоонуудын олонлогийг тэмдэглэе. $$B=\{1, 2, ...,9, 11, 22 , ..., 88, 111, ...,999\}$$ болно. Ядаж хоёр цифр нь ялгаатай байх тоонуудын олонлог $A-B$ юм. Эндээс олвол зохих хариу: $$|A-B|=|A|-|B|=1000-27=973$$ болов.

Бодлого 3 –ын бодолтонд ялгаврын дүрэм яалт ч үгүй ашиглагдлаа.

Арифметикт $4$ үйлдэл байдаг. Нэмэх, хасах, үржих,... Нэг үйлдэл үлдсэн нь хуваах шүү дээ. Тэгвэл комбинаторикт хуваахын буюу ногдворын дүрэм гэж бас байна.

НООГДВОРЫН ДҮРЭМ

Үдэшлэгт $n$ зочин ирсэн бөгөөд хүн бүр гадуур хувцсаа өлгүүрт өгчээ. Өлгүүрчин өлгүүр бүрт яг $d$ ширхэг хувцас өлгөсөн бол хэдэн өлгүүр байсан бэ?

Хариу: $\dfrac{n}{d}$ өлгүүр байсан.

Энэ маш энгийн өгүүлбэртэй бодлого яахаараа комбинаторикийн нэг үндсэн дүрэм болчихов? Одоо тайлбарлая. $S$ ба $T$ төгсгөлөг олонлогууд бөгөөд $d$ өгөгдсөн натурал тоо болог. $T$ олонлогийн элемент бүрд $S$ олонлогийн нэг элементийг харгалзуулсан $f$ гэсэн функц нь: $s\in{S}$ гэсэн $s$ элемент бүрийн хувьд $f(t)=S$ байх яг $d$ ширхэг $t\in{T}$ элемент олдоно гэсэн чанартай байвал $f:T\rightarrow{S}$ функцийг $d\rightarrow1$ чанартай гэнэ. Жишээлбэл, $f:T\rightarrow{S}$ нэгийг $\rightarrow$ нэгд $(1\rightarrow1)$ функц байвал $|T|=|S|$ байна. Нэгийг $\rightarrow$ нэгд функцийг харилцан нэг утгатай харгалзаа гэнэ.

Дээрх зурагт $3\rightarrow1$ функцийг дүрслэв. Тэгвэл ногдворын дүрэм маань: $f:T\rightarrow{S}$ бөгөөд $f$ нь $d-1$ функц бол $$|S|=\dfrac{|T|}{d}$$ байна гэж томъёологдоно.

Бодлого 4. a) $n$ ялгаатай өнгийн шүрийг нэг утсанд хичнээн ялгаатай аргаар хэлхэж болох вэ?

б) $n$ ялгаатай өнгийн бөмбөгийг дугуй ширээ тойруулан хичнээн ялгаатай аргаар байрлуулж болох вэ? (Эргүүлэлтээр ижилхэн байрлуудыг ижилд тооцно.)

в) $n$ ялгаатай өнгийн шүрээр хичнээн ялгаатай хүзүүний зүүүлт хийж болох вэ?

Бодолт. Эхлээд бодлогыг $n=3$ байхад авч үзье. Бидэнд улаан, шар, ногоон өнгийн $3$ шүр байсан гэж саная.

a) бодлогын хувьд:

гэсэн 6 аргаар хэлхэж болно.

б) бодлогын хувьд:

в) бодлогын тухайд:

ердөө $1$ л янзын хүзүүний зүүлт хийж болно. Одоо бодлогыг ерөнхий тохиолдолд бодоцгооё.

a) $n$ ширхэг ялгаатай юмсыг нэг эгнээнд байрлуулах байруудыг эхнээс нь $1, 2, ..., n$ гэж дугаарлая. $1$-р байранд, $n$ юмсын аль нь ч байрлаж болох тул $n$ боломжтой. $2$-р байранд, үлдсэн $n-1$ юмсын аль нь ч байрлаж болох тул $n-1$ боломжтой. Нэгийг нь байрлуулсан гэе. $3$-р байранд, үлдсэн $n-2$ юмсын аль нь ч байрлаж болно. Гэх мэтээр хамгийн сүүлийн $n$-р байранд, үлдсэн $1$ юм автоматаар байрлана. Иймд нийт байрлуулалтын тоо $$n\cdot(n-1)\cdot(n-2)\cdot ...\cdot2\cdot1=n!$$ болно. $n$ ялгаатай юмсыг нэг эгнээнд байрлуулах (сэлгэх) боломжийн тоо $$n!=1\cdot2\cdot...\cdot(n-1)\cdot{n}$$ байна.

б) $T$-ээр $n$ ялгаатай өнгөтэй бөмбөгийг нэг эгнээнд байрлуулсан сэлгэмэлүүдийн олонлогийг тэмдэглэе. Өмнөх а) бодлогоос $|T|=n!$ байна. Харин $S$-ээр $n$ ялгаатай өнгөтэй бөмбөгийг дугуй ширээ тойруулан байрлуулсан сэлгэмэлүүдийн олонлогийг тэмдэглэе. $S$–ээс авсан $S=(c_1,c_2,…,c_n)$ сэлгэмэл бүрт $$(c_1,c_2,…,c_n),$$ $$(c_2,c_3,…,c_n,c_1),$$ $$(c_3,c_4,…,c_n,c_1,c_2),$$ $$\vdots$$ $$(c_n,c_1,c_2,…,c_{n-1})$$ гэсэн $T$-ийн $n$ ширхэг сэлгэмэл харгалзана. Ө.х $f:T\rightarrow{S}$ функц $n\rightarrow1$ байх юм. Эндээс ногдворын дүрмээр $$|S|=\dfrac{|T|}{n}=\dfrac{n!}{n}=(n-1)!$$ болов.

в) $T$-ээр өмнөх б) бодлогын $S$ олонлогийг авъя. $S$ олонлогийн нэг тойрог “сэлгэмэл”-ийг эргүүлж харуулаад тавихад хүзүүний зүүлт өөрчлөгдөхгүй. Ө.х $S$-ээр $n$ ширхэг ялгаатай өнгийн шүрээр хийж болох бүх хүзүүний зүүлтүүдийн олонлогийг тэмдэглэвэл, $f:T\rightarrow{S}$ гэсэн $2\rightarrow1$ функц олдоно. Иймд ногдворын дүрмээр $$|S|=\dfrac{|T|}{2}=\dfrac{(n-1)!}{2},\ n\ge3$$ болов.

Бодлого 5. Ангийн эв нэгдлийн хуралдаанаар $6$ хүү, $15$ охин дугуй ширээ тойрч суугаад ангид үүссэн зарим ноцтой асуудлыг хэлэлцэх болжээ. Ингэхдээ дарааллан суух $2$ хүү бүрийн хооронд ядаж $2$ охин суухаар урьдчилж тохиролцсон бол тэд хичнээн ялгаатай аргаар сууцгааж болох вэ? (Эргүүлэлтээр нэг нь нөгөөдөө шилждэг байрлалуудыг ижилд тооцно.)

Бодолт. Хүү бүрийн хувьд түүний баруун болон зүүн талд суух $2$ охин байгаа. Энэ $2$ охиныг дунд нь суугаа хүүгийн “хамгаалагчид ” гэе.

$6$ хүүгийн хувьд тэдний хамгаалагч охидын тоо $6\cdot2=12$ байна. (Дараалан суух $2$ хүүгийн хооронд дор хаяж $2$ охин сууна гэдгийг санаарай!) Хөвгүүдийн хамгаалагч болох $12$ охиныг, нийт байгаа $15$ охидоос сонгох боломжийн тоо нь үржвэрийн дүрмээр $$15\cdot14\cdot...\cdot(15-12+1)=$$$$=\dfrac{15!}{(15-12)!}=\dfrac{15!}{3!}$$ болно. Энд бид $15$ охиноос $12$ охиныг сонгон аваад сонгогдсон $15$ охины байрыг сэлгэж байгааг анхаараарай. Хүү бүрийг $2$ хамгаалагч охидтой нь хамтатган “баг” гэе. Тэгвэл дугуй ширээ тойрон суусан $6$ хүү өөрсдийн хамгаалагч охидынхоо хамт $6$ баг үүсгэнэ. Дээр нь үлдсэн $15-12=3$ охин нэг, нэг “баг” үүсгэж, дугуй ширээ тойрон нийт $6+3=9$ баг сууж байна гэж ойлгож болно.

Энэ $9$ баг ширээ тойрч суух ялгаатай боломжийн тоо нь өмнөх Бодлого 4.(б)-ээс $\dfrac{9!}{9}=8!$ юм. Эндээс үржвэрийн дүрмээр бодлогын хариу: $\dfrac{15!}{3!}\cdot8!$ болно.