Агуулгыг алгасах

Од ба таславч

Од ба таславч бол зарим комбинаторикийн бодлого бодох математик арга юм. Энэ нь ижил объектуудыг бүлэглэх аргын тоог тоолохыг хүсэх бүрд тохиолддог.

Теорем

$n$ ижил объектыг $k$ шошготой хайрцагт хийх аргын тоо нь

$$\binom{n + k - 1}{n}.$$

Баталгаа нь объектуудыг од болгож, хайрцгуудыг таславчаар тусгаарлахад оршино (тиймээс ийм нэртэй). Жишээ нь $\bigstar | \bigstar \bigstar |~| \bigstar \bigstar$-аар бид дараах нөхцөл байдлыг илэрхийлж болно: эхний хайрцагт нэг объект, хоёр дахь хайрцагт хоёр объект, гурав дахь нь хоосон, сүүлийн хайрцагт хоёр объект байна. Энэ бол 5 объектыг 4 хайрцагт хуваах нэг арга юм.

Хуваалт бүрийг $n$ од ба $k - 1$ таславч ашиглан илэрхийлж болох ба $n$ од, $k - 1$ таславч ашигласан од ба таславчийн сэлгэмэл бүр нэг хуваалтыг илэрхийлдэг нь нэлээд ойлгомжтой. Тиймээс $n$ ижил объектыг $k$ шошготой хайрцагт хуваах аргын тоо нь $n$ од ба $k - 1$ таславчийн сэлгэмэлийн тоотой ижил. Биномын коэффициент бидэнд хайж буй томьёог өгнө.

Сөрөг биш бүхэл тоон нийлбэрийн тоо

Энэ бодлого бол теоремын шууд хэрэглээ юм.

Та дараах тэгшитгэлийн шийдийн тоог тоолохыг хүсэж байна

$$x_1 + x_2 + \dots + x_k = n$$

$x_i \ge 0$ байхад.

Дахин бид шийдийг од ба таславч ашиглан илэрхийлж болно. Жишээ нь $n = 4$, $k = 3$-ийн хувьд $1 + 3 + 0 = 4$ шийдийг $\bigstar | \bigstar \bigstar \bigstar |$-аар илэрхийлж болно.

Энэ нь яг од ба таславчийн теорем гэдгийг харахад амархан. Тиймээс шийд нь $\binom{n + k - 1}{n}$.

Эерэг бүхэл тоон нийлбэрийн тоо

Хоёр дахь теорем нь эерэг бүхэл тоонуудын хувьд сайхан тайлбар өгдөг. Дараах тэгшитгэлийн шийдүүдийг авч үзье

$$x_1 + x_2 + \dots + x_k = n$$

$x_i \ge 1$ байхад.

Бид $n$ одыг авч үзэж болох ч энэ удаад бид одуудын хооронд хамгийн ихдээ нэг таславч тавьж болно, учир нь одуудын хооронд хоёр таславч байвал $x_i=0$ буюу хоосон хайрцгийг илэрхийлнэ. $k-1$ таславч тавихад одуудын хооронд $n-1$ зай байх тул шийд нь $\binom{n-1}{k-1}$.

Доод хязгаартай бүхэл тоон нийлбэрийн тоо

Үүнийг өөр өөр доод хязгаартай бүхэл тоон нийлбэрт амархан өргөтгөж болно. Өөрөөр хэлбэл бид дараах тэгшитгэлийн шийдийн тоог тоолохыг хүсэж байна

$$x_1 + x_2 + \dots + x_k = n$$

$x_i \ge a_i$ байхад.

$x_i' := x_i - a_i$ орлуулсны дараа бид өөрчилсөн тэгшитгэлийг олж авна

$$(x_1' + a_i) + (x_2' + a_i) + \dots + (x_k' + a_k) = n$$
$$\Leftrightarrow ~ ~ x_1' + x_2' + \dots + x_k' = n - a_1 - a_2 - \dots - a_k$$

$x_i' \ge 0$ байхад. Ингэснээр бид бодлогыг $x_i' \ge 0$ байх энгийн тохиолдол болгон бууруулж, дахин од ба таславчийн теоремыг хэрэглэж болно.

Дээд хязгаартай бүхэл тоон нийлбэрийн тоо

Оруулах-хасах зарчим-ийн тусламжтайгаар та бүхэл тоонуудыг дээд хязгаараар мөн хязгаарлаж болно. Холбогдох өгүүлэл дэх Дээд хязгаартай бүхэл тоон нийлбэрийн тоо хэсгийг үзнэ үү.

Дасгал бодлогууд