35-dars: Kombinatorika

5-darajaOlimpiada — musobaqa mahorati33–40 darslar

HayotdaSinf

O’ttiz kishilik sinfdan olimpiadaga uch kishi boradi. Nechta har xil uchlik tuzish mumkin? Javob to’rt mingdan ortiq — va uni sanab chiqmasdan, bitta ifoda bilan topish mumkin.

Bu darsdan keyin siz

• ko’paytirish va qo’shish tamoyillarini ajratasiz
• kombinatsiya va o’rin almashtirishni farqlaysiz
• katta javoblarni modul ostida hisoblaysiz

Avval qo’lda

Avval qo‘lda

~6 daqiqa·juftlikda·Qog'oz va qalam

To’rtta harf bor: A, B, C, D. Uchta savolga qog’ozda javob bering, har safar variantlarni sanab chiqing.

Birinchi: ulardan ikkitasini tartib bilan nechta usulda tanlash mumkin (AB va BA har xil)? Ikkinchi: tartibsiz nechta (AB va BA bir xil)? Uchinchi: birinchi javob ikkinchisidan necha barobar katta?

Nimani sezishingiz kerak

12 va 6 — nisbat aynan 2, ya’ni ikkita narsani tartiblash usullari soni. Kombinatsiya shu yerdan chiqadi: tartibli variantlarni ortiqcha tartiblashlarga bo’lish.

Kompyuter yopiq. Bu mashq tugamaguncha kod ochilmaydi.

Ikki tamoyil

ko'paytirish tamoyiliproduct rule

Ketma-ket mustaqil tanlovlar bo’lsa, variantlar soni ko’paytiriladi. Uch xil ko’ylak va to’rt xil shim — 12 xil kiyim.

qo'shish tamoyilisum rule

Bir-birini istisno qiladigan holatlar bo’lsa, variantlar qo’shiladi. Avtobusda 3 yo’l, poyezdda 2 yo’l — jami 5 yo’l.

Deyarli har sanash masalasi shu ikkisining kombinatsiyasi. Qiyinligi odatda «bu ketma-ketmi yoki alohidami» degan savolda.

Uchta formula

Nima	Formula	Ma’nosi
Faktorial	n!	n narsani tartiblash
O’rin almashtirish	n! / (n−k)!	k tasini tartib bilan tanlash
Kombinatsiya	n! / (k! · (n−k)!)	k tasini tartibsiz tanlash

?Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qilingNusxalash

1from math import comb, factorial, perm2print(factorial(4), perm(4, 2), comb(4, 2))3print(comb(30, 3))

Sizning bashoratingizTekshirish

Javobni ko'rish

24 12 6
4060

To'rtta harfdan ikkitasini tartib bilan 12 usulda, tartibsiz 6 usulda tanlash mumkin. O'ttiz kishidan uchtasi — 4060 ta uchlik.

Sekin yechim

Katta sonlar uchun math.comb sekinlashadi va javob juda uzun bo’lib ketadi. Shuning uchun modul ostida ishlanadi. Eng oddiy yo’l — Paskal uchburchagi.

sekin.pyNusxalash

1N = 52c = [[0] * (N + 1) for _ in range(N + 1)]3for i in range(N + 1):4  c[i][0] = 15  for j in range(1, i + 1):6      c[i][j] = c[i - 1][j - 1] + c[i - 1][j]7for i in range(N + 1):8  print(c[i][:i + 1])

?Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qilingNusxalash

1N = 52c = [[0] * (N + 1) for _ in range(N + 1)]3for i in range(N + 1):4  c[i][0] = 15  for j in range(1, i + 1):6      c[i][j] = c[i - 1][j - 1] + c[i - 1][j]7for i in range(N + 1):8  print(c[i][:i + 1])

Sizning bashoratingizTekshirish

Javobni ko'rish

[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]
[1, 5, 10, 10, 5, 1]

Har katak tepasidagi ikki katakning yig'indisi. Hech qanday bo'lish yo'q — shuning uchun modul bilan ishlash oson.

Nega sekin

Jadval n² katakdan iborat. n = 2000 da bu 4 million — sig’adi. n = 10⁶ da esa xotira ham, vaqt ham yetmaydi.

Sig‘adimi?

Bir soniyada taxminan 10⁸ oddiy amal bajariladi.

Yechim	n = 2 000	n = 10⁶
Paskal jadvalin^2	10⁶sig‘adi	10¹²sig‘maydi
Faktoriallarn	2 000sig‘adi	10⁶sig‘adi

Yashil — yechim o‘tadi. Sariq — chegarada, konstanta va til muhim bo‘lib qoladi. Qizil — bu yechim bilan bormaydi, boshqasini qidiring.

Tez yechim

C(a, b) = a! / (b! · (a−b)!). Modul ostida bo’lish yo’q, lekin teskari element bor (34-dars).

Faktoriallar bir marta hisoblanadi, teskari faktoriallar esa oxiridan orqaga bir yurishda — shunda pow faqat bir marta chaqiriladi.

tez.pyNusxalash

1MOD = 10**9 + 72n = 303fakt = [1] * (n + 1)4for i in range(1, n + 1):5  fakt[i] = fakt[i - 1] * i % MOD6teskari = [1] * (n + 1)7teskari[n] = pow(fakt[n], MOD - 2, MOD)8for i in range(n, 0, -1):9  teskari[i - 1] = teskari[i] * i % MOD10def C(a, b):11  if b > a or b < 0:12      return 013  return fakt[a] * teskari[b] % MOD * teskari[a - b] % MOD14print(C(4, 2), C(30, 3), C(5, 0), C(3, 5))

?Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qilingNusxalash

1MOD = 10**9 + 72n = 303fakt = [1] * (n + 1)4for i in range(1, n + 1):5  fakt[i] = fakt[i - 1] * i % MOD6teskari = [1] * (n + 1)7teskari[n] = pow(fakt[n], MOD - 2, MOD)8for i in range(n, 0, -1):9  teskari[i - 1] = teskari[i] * i % MOD10def C(a, b):11  if b > a or b < 0:12      return 013  return fakt[a] * teskari[b] % MOD * teskari[a - b] % MOD14print(C(4, 2), C(30, 3), C(5, 0), C(3, 5))

Sizning bashoratingizTekshirish

Javobni ko'rish

6 4060 1 0

Javoblar math.comb bilan bir xil. Teskari faktoriallar oxiridan orqaga yig'iladi: teskari[i-1] = teskari[i] * i — chunki (i-1)! ning teskarisi i! ning teskarisiga i ni ko'paytirgan.

◆Asosiy g'oya

b > a holatini alohida ishlash shart: teskari[a - b] da manfiy indeks Python’da ro’yxat oxiridan olinadi va yechim xato bermay tasodifiy son qaytaradi.

Sinab ko’r

Vizualda Paskal uchburchagi qator-qator to’ladi. Chekkalar har doim bir bo’lishini kuzating.

Paskal uchburchagi

Har katak tepasidagi ikki katakning yig'indisi. Chekkalari har doim 1.

C(n, k) = C(n-1, k-1) + C(n-1, k) qoidasi bilan jadval qator-qator to'ldiriladi.

Algoritmning har qadami quyidagi ro‘yxatda matn sifatida ham berilgan — vizual faqat shu qadamlarni chizadi, yangi ma’lumot qo‘shmaydi.

1. Har katak C(n, k) — n ta narsadan k tasini tanlash usullari soni. Qator raqami n, ustun raqami k.
2. Nol narsadan nol tasini tanlash — bitta usul (hech narsa olmaslik).
3. n = 1 qatori: har katak tepasidagi ikki katakning yig'indisi. Chekkalari har doim 1 — hammasini yoki hech narsani olish.
4. n = 2 qatori: har katak tepasidagi ikki katakning yig'indisi. Chekkalari har doim 1 — hammasini yoki hech narsani olish.
5. n = 3 qatori: har katak tepasidagi ikki katakning yig'indisi. Chekkalari har doim 1 — hammasini yoki hech narsani olish.
6. n = 4 qatori: har katak tepasidagi ikki katakning yig'indisi. Chekkalari har doim 1 — hammasini yoki hech narsani olish.
7. n = 5 qatori: har katak tepasidagi ikki katakning yig'indisi. Chekkalari har doim 1 — hammasini yoki hech narsani olish.
8. n = 6 qatori: har katak tepasidagi ikki katakning yig'indisi. Chekkalari har doim 1 — hammasini yoki hech narsani olish.
9. Jadval 21 ta qo'shish bilan qurildi. Bo'lish umuman ishlatilmadi — shuning uchun modul bilan ishlash oson va xato qilish qiyin.

n=0

n=1

n=2

n=3

n=4

n=5

n=6

Har katak C(n, k) — n ta narsadan k tasini tanlash usullari soni. Qator raqami n, ustun raqami k.

Qo'shish0

OrqagaO‘ynatishOldinga1/9Qayta boshlash

Xatoni toping

▲Tuzoq — xatoni toping

35 / 40

MasalaBeshta har xil kitobni uch o'quvchiga tarqating, har biriga bittadan.

Taklif qilingan yechim

1. 1Birinchi o‘quvchiga 5 xil kitob berish mumkin.
2. 2Ikkinchisiga qolgan 4 tadan bittasi.
3. 3Uchinchisiga qolgan 3 tadan bittasi.
4. 4Demak javob C(5, 3) = 10.

Bu javobning 4-qismi noto'g'ri. Uch qadam ko'paytirish tamoyilini to'g'ri qo'llagan va ular 5 · 4 · 3 = 60 beradi. C(5, 3) esa tartibsiz tanlov — u kim qaysi kitobni olganini ajratmaydi. Bu yerda o'quvchilar har xil, demak tartib muhim: javob 60.

Javobning qaysi qismi noto'g'ri? Bosib belgilang.

Javobni ko'rsatish

O’zingizni sinang

1Ko'paytirish va qo'shish tamoyillari qachon ishlatiladi?

Javobni ko'rish

Ketma-ket mustaqil tanlovlarda — ko’paytiriladi. Bir-birini istisno qiladigan holatlarda — qo’shiladi.

2C(n, k) va n!/(n−k)! farqi nima?

Javobni ko'rish

Birinchisi tartibsiz tanlov, ikkinchisi tartibli. Nisbat k! ga teng — tanlanganlarni tartiblash usullari soni.

3Nega modul ostida bo'lish o'rniga teskari element ishlatiladi?

Javobni ko'rish

Chunki qoldiq olingandan keyin bo’linish xossasi buziladi. Teskari element esa ko’paytirish orqali bo’lishning o’rnini bosadi.

4Teskari faktoriallar nega oxiridan orqaga hisoblanadi?

Javobni ko'rish

(i−1)! ning teskarisi i! ning teskarisiga i ni ko’paytirganga teng. Shu sababli pow faqat bir marta chaqiriladi.

5b > a holati nega alohida ishlanadi?

Javobni ko'rish

teskari[a - b] da manfiy indeks paydo bo’ladi va Python uni ro’yxat oxiridan oladi — yechim xato bermay noto’g’ri son qaytaradi.

Masalalar

Masalalar

3 ta

• Binomial CoefficientsCSES 1079o'rta

  Darsdagi masalaning o‘zi, n ≤ 10⁶. Faktoriallarni bir marta oldindan hisoblang.

• Creating Strings IICSES 1715o'rta

  Takrorlanuvchi harflar bor: n! ni har harf takrorlanish sonining faktorialiga bo‘ling.

• Distributing ApplesCSES 1716qiyin

  «Yulduzlar va tayoqchalar» usuli. Javob bitta kombinatsiyaga aylanadi.

Lokal mashq: mashqlar/35-kombinatorika/ — masala matni, testlar va tekshir.py. Avval sekin.py ni o‘zingiz yozing, keyin tayyorini oching.

Topshiriq

Topshiriq — darajangizni tanlang

Asos5–7-sinfMustahkam8–9-sinfChuqur10–11-sinf

Asos · 5–7-sinf — Vizual va aniq ko'rsatmali

C(6, k) qiymatlarini k = 0 dan 6 gacha Paskal uchburchagi bilan hisoblang. Ularning yig’indisi qancha chiqdi? Bu son nimani anglatishini o’ylab ko’ring.

Mustahkam · 8–9-sinf — Matnli masala, o'zingiz tuzasiz

35-kombinatorika masalasini yeching. b > a va b = 0 holatlarini alohida sinang.

Chuqur · 10–11-sinf — Algoritmik, chegara holatlari bilan

Yulduzlar va tayoqchalar usulini o’rganing: n bir xil olmani k bolaga necha usulda bo’lish mumkin (kimdir hech narsa olmasligi ham mumkin)? Javobni kombinatsiya orqali yozing va kichik holatlarda qo’lda tekshiring.

Darsni belgilash uchun JavaScript kerak. Bu progressni saqlash uchun ishlatiladi — darslikning o'zi JavaScript'siz ham to'liq o'qiladi.

Darsni tugatdim