Kombinatorika masalalari
Kombinatorikaning asosiy savoli — «necha usul bilan?». Variantlarni sanashda ularni tartib bilan yozib chiqamiz, shunda birortasi tushib qolmaydi va takrorlanmaydi. Qo‘shish qoidasi: A ni m usulda yoki B ni boshqa n usulda tanlash mumkin bo‘lsa, «A yoki B» ni m + n usulda tanlash mumkin. Ko‘paytirish qoidasi: A ni m usulda, undan keyin B ni n usulda tanlash mumkin bo‘lsa, «A va B» mn usulda amalga oshadi; qadamlar ketma-ket bo‘lsa, qadamlardagi usullar sonlari ko‘paytiriladi. n ta elementdan k tadan takrorsiz o‘rinlashtirishlar soni Aₙᵏ = n(n − 1)…(n − k + 1); takrorli bo‘lsa n^k. Barcha n elementni tartiblash usullari soni (o‘rin almashtirishlar) n! = 1 · 2 · … · n, bunda 0! = 1. n elementli to‘plamning qism to‘plamlari soni 2ⁿ, chunki har bir element qism to‘plamga kiradi yoki kirmaydi.
| Tanlash | Formula |
|---|---|
| o‘rin almashtirish | Pₙ = n! |
| joylashtirish | Aₙᵏ = n!/(n − k)! |
| guruhlash | Cₙᵏ = n!/(k!(n − k)!) |
Maktab konserti dasturida 5 ta chiqish bor. Ularni 5! = 120 xil tartibda qo‘yish mumkin. Ochuvchi chiqish oldindan belgilangan bo‘lsa, qolgan 4 tasi 4! = 24 xil tartibda joylashadi. Ko‘paytirish qoidasi variantlarni ro‘yxatga olmay sanash imkonini beradi.
Tadbir tashkilotchilari dastur tartibini rejalashtiradi, xavfsizlik mutaxassislari parol va kodlarning nechta variant borligini baholaydi, logistikachilar yetkazib berish marshrutlarini sanaydi.
To‘rtta qog‘oz parchasiga 1, 2, 3, 4 raqamlarini yozing. Hammasini ro‘yxatga olmay, har bir parchadan bir martadan foydalanib nechta turli to‘rt xonali son tuzish mumkinligini toping (4 · 3 · 2 · 1). Keyin 1 dan boshlanadiganlarini yozib chiqing: ular jami sonning to‘rtdan biri bo‘lishi kerak.
«Ismingiz harflari»: ismingizdagi harflar turlicha bo‘lsa (masalan, KITOB so‘zi), 3 ta harfni ro‘yxatga yozib barcha tartiblarni qo‘lda sanang va 3! = 6 ni tekshiring. So‘ng 5 ta harf uchun 5! ni formula bilan hisoblang.