Kombinatorika: o'rin almashtirish, o'rinlashtirish, guruhlash: matematika darsi

$10$ o'quvchidan sardor va yordamchi tanlash $90$ usulda, ikkita navbatchi tanlash esa $45$ usulda bajariladi. Sonlar bir xil, javob ikki baravar farq qiladi, chunki birinchi holda tartib muhim, ikkinchisida emas. Kombinatorika masalasining deyarli hammasi to'g'ri savol berishga bog'liq: tartib muhimmi, takrorlash mumkinmi, shart qaysi tanlovga tegishli?

Ko'paytirish va qo'shish qoidasi

Ko'paytirish qoidasi: tanlovlar ketma-ket bajarilsa va har bir bosqichdagi usullar soni oldingi tanlovga bog'liq bo'lmasa, usullar soni ko'paytiriladi. Qo'shish qoidasi: tanlov bir-birini istisno qiladigan holatlarga bo'linsa, holatlar soni qo'shiladi.

$4$ xil ko'ylak va $3$ xil shimdan bir kiyim $4\cdot 3=12$ usulda tanlanadi, chunki ikkala narsa birga olinadi. Manzilga $5$ ta avtobus yoki $2$ ta poyezddan biri bilan borilsa, $5+2=7$ usul bor, chunki faqat bittasi tanlanadi. So'z «va» bo'lsa ko'paytiramiz, «yoki» bo'lsa qo'shamiz.

Ikki kishi uchun ham shu qoida. $4$ ta kirish va $6$ ta chiqish eshigi bor, ikki do'st bir eshikdan kirib, turli eshiklardan chiqsa: kirish $4$ usulda, chiqish tartibli juftlik sifatida $6\cdot 5$ usulda, jami $4\cdot 6\cdot 5=120$ usul.

Sonlar tuzish

Eng avval eng cheklangan o'rinni to'ldiramiz. Son noldan boshlanmaydi, juft son juft raqam bilan tugaydi. $0,\ 1,\ 2,\ 3,\ 4$ raqamlaridan uch xonali sonlar:

Shart	Hisob	Soni
Shartraqamlar takrorlanmaydi	Hisob $4\cdot 4\cdot 3$	Soni $48$
Shartraqamlar takrorlanishi mumkin	Hisob $4\cdot 5\cdot 5$	Soni $100$
Sharttakrorlanmaydi va juft	Hisob $4\cdot 3+2\cdot 3\cdot 3$	Soni $30$

Juft sonlarda oxirgi raqam $0$ bo'lsa, birinchi raqamga $4$ ta, $2$ yoki $4$ bo'lsa, $3$ ta imkoniyat qoladi, shuning uchun holatlarga bo'linadi. Bo'linish sharti ham shu tarzda hisobga olinadi: $4$ ga bo'linish uchun oxirgi ikki raqamdan tuzilgan son $4$ ga bo'linishi, $5$ ga bo'linish uchun oxirgi raqam $0$ yoki $5$ bo'lishi, $3$ ga bo'linish uchun raqamlar yig'indisi $3$ ga bo'linishi kerak.

Raqamlari qaytarilgan yozuvda faqat erkin raqamlar tanlanadi. $\overline{abab\ldots ab}$ ko'rinishdagi son, bunda $a\ne b$ , xonalari soni berilgan bo'lsa, $a$ va $b$ bilan to'la aniqlanadi: $a$ ga $9$ ta imkoniyat (noldan boshqa), $b$ ga ham $9$ ta ( $a$ dan boshqa, nol ham mumkin), jami $81$ ta. Xonalar soni qancha bo'lishining ahamiyati yo'q. Xuddi shunday, turli $a$ , $b$ , $c$ raqamli $\overline{abcb}$ sonlar $9\cdot 9\cdot 8=648$ ta: oxirgi raqam alohida tanlanmaydi.

Noldan farqli turli raqamlardan tuzilgan barcha sonlar yig'indisini ham hisoblash mumkin: uch raqamli holatda har bir raqam har bir xonada $2!$ marta turadi. $1,\ 4,\ 7$ dan: $(1+4+7)\cdot 2\cdot 111=2664$ .

O'rin almashtirish

P_n=n!=1\cdot 2\cdot\ldots\cdot n

n

ta turli narsani bir qatorga joylash,

0!=1

Birinchi o'ringa $n$ ta, ikkinchisiga $n-1$ ta, oxirgisiga bitta narsa qoladi. Masalan, $5$ ta kitob javonga $5!=120$ usulda teriladi. Faktoriallar: $1!=1$ , $2!=2$ , $3!=6$ , $4!=24$ , $5!=120$ , $6!=720$ , $7!=5040$ .

O'rinlashtirish

A_n^k=\frac{n!}{(n-k)!}

=n(n-1)\cdot\ldots\cdot(n-k+1)

0\le k\le n

n

tadan

k

tasini tanlab, tartib bilan joylash

Ko'paytmada $n$ dan boshlab kamayib boruvchi $k$ ta ko'paytuvchi bor. Masalan, $7$ kishidan rais, o'rinbosar va kotib tanlash: $A_7^3=7\cdot 6\cdot 5=210$ usul. $k=n$ da $A_n^n=P_n$ .

Guruhlash

C_n^k=\frac{n!}{k!\,(n-k)!}=\frac{A_n^k}{k!}

0\le k\le n

n

tadan

k

tasini tanlash, tartib muhim emas

Har bir guruhni $k!$ xil tartibda yozish mumkin, shuning uchun o'rinlashtirishlar soni $k!$ ga bo'linadi. $7$ kishidan uch kishilik guruh: $C_7^3=\dfrac{210}{6}=35$ usul. Hisobda surat ham, maxraj ham $k$ ta ko'paytuvchidan iborat: $C_8^3=\dfrac{8\cdot 7\cdot 6}{3\cdot 2\cdot 1}=56$ .

Ma'ruzaning davomi kirgandan keyin ochiladiBu — ma'ruzaning boshi. To'liq matn, ovozli doska, yechimli misollar va topshiriqlar Premium bilan.Davomini o'qish