Kombinatoorika töölaud

Kombinatsioonide ja permutatsioonide kalkulaator

Arvuta nCr ja nPr, kordustega valikud, multihulkade järjestused, pallid kastidesse, kaasamis-välistamisprintsiip, segadused ja võreteed.

Näidisarvutus — Kombinatoorika töölaud

Täpne arv	120
Ligikaudu	120
Numbrikohad	3
log10	2,0792

Need on väärtused, mida kalkulaator lehe avamisel näitab. Muuda ülal mõnda sisendit, et need ümber arvutada.

Interaktiivse simulatsiooni laadimine...

Loendusteooria — juhtum juhtumi haaval

Kaks jah/ei küsimust liigitavad iga loendamisülesande

Valimine (kordusteta) C(n,k) = n! / (k!(n − k)!)

Järjestamine (kordusteta) P(n,k) = n! / (n − k)!

Järjestatud kordustega n^k

Valimine kordustega C(n + k − 1, k)

Valimine (kordusteta)

Valem: C(n,k) = n! / (k!(n − k)!)

Lahendatud näide: Vali 10 inimese seast 3. Kuna järjekord ei loe, on C(10,3) = 120 komisjoni.

Ava see näide: komisjoni valimine

Valimine (kordusteta). Järjestamata valik: valitud kiibid moodustavad hulga, mitte jada. Vali 10 inimese seast 3: järjekord ei ole oluline. — Järjestamata valik: valitud kiibid moodustavad hulga, mitte jada.

Järjestamine (kordusteta)

Valem: P(n,k) = n! / (n − k)!

Lahendatud näide: Jaga 10 finalisti vahel kuld, hõbe ja pronks. Kuna kohad erinevad, on P(10,3) = 720 võimalikku poodiumi.

Ava see näide: poodiumi järjekord

Järjestamine (kordusteta). Järjestatud kohad: positsioonide vahetamine loob uue tulemuse. Esikolmik 10 seast: järjekord on oluline. — Järjestatud kohad: positsioonide vahetamine loob uue tulemuse.

Järjestatud kordustega

Valem: n^k

Lahendatud näide: Koosta 4-kohaline PIN 10 numbrist. Järjekord loeb ja numbrid võivad korduda: 10^4 = 10 000 PIN-koodi.

Ava see näide: PIN-kood

Järjestatud kordustega. Iga koht valib sõltumatult samast hulgast. 4-kohaline PIN-kood: kordused on lubatud. — Iga koht valib sõltumatult samast hulgast.

Valimine kordustega

Valem: C(n + k − 1, k)

Lahendatud näide: Vali 8 maitse seast 3 palli, eirates järjekorda ja lubades kordusi. C(10,3) = 120 maitsete multihulka.

Ava see näide: jäätisepallid

Valimine kordustega. Tärnid ja kriipsud: eraldajad kodeerivad korduvaid valikuid. 3 kuulikest 8 maitse seast: järjekord ei loe, kordused lubatud. — Tärnid ja kriipsud: eraldajad kodeerivad korduvaid valikuid.

Multihulga permutatsioon

Valem: N! / (n₁! · n₂! · … · n_r!)

Lahendatud näide: MISSISSIPPI-s on 11 tähte: I×4, S×4, P×2 ja M×1. Identsete vahetuste jagamisel saame 11!/(4!4!2!) = 34 650 järjestust.

Ava see näide: MISSISSIPPI

Multihulga permutatsioon. Korduvad sümbolid jagavad permutatsioonide koguarvu dubleerimisvahetustega. Üksteist tähte, neli S-i, neli I-d, kaks P-d. Avaldis 11! jagatud 4!·4!·2!-ga annab vastuseks 34 650. Ilma kordumisteta oleks tulemus 39 916 800. Seega eemaldavad duplikaadid üle 99,9% kõikvõimalikest järjestustest.. — Korduvad sümbolid jagavad permutatsioonide koguarvu dubleerimisvahetustega.

Pallid kastidesse

Valem: Σ_i=0^m (−1)ⁱC(m,i)(m − i)ⁿ

Lahendatud näide: Jaga 6 erinevat ülesannet 3 nimetatud inimese vahel nii, et keegi ei jää tühjaks. Kaasamis–välistamisprintsiip annab 3^6 − 3·2^6 + 3 = 540 jaotust.

Ava see näide: erinevad kastidesse (sürjektiivne)

Pallid kastidesse. Pallide ja kastide vaade paigutus-/jaotuspiirangute jaoks. Jaga 6 erinevat ülesannet 3 töötaja vahel, igaüks saab vähemalt ühe. — Pallide ja kastide vaade paigutus-/jaotuspiirangute jaoks.

Kaasamise-välistamise printsiip

Valem: C(n,k) − C(b,k)

Lahendatud näide: Vali järjestamata 5-kaardine käsi, milles on vähemalt üks äss. C(52,5) − C(48,5) = 886 656 kätt.

Ava see näide: vähemalt üks äss

Kaasamise-välistamise printsiip. Hulkade kattumise pilt liitmis-lahutamise loendamiseks. 5-kaardiline käsi, milles on vähemalt üks äss – arvutatud vastandsündmuse kaudu. — Hulkade kattumise pilt liitmis-lahutamise loendamiseks.

Erijuhud

Valem: !n = n! Σ_i=0ⁿ (−1)ⁱ / i!

Lahendatud näide: Jaga 8 Secret Santa nime nii, et keegi ei tõmba ennast. Püsipunktita permutatsioonide arv on !8 = 14 833.

Ava see näide: salajane jõuluvana

Erijuhud. Klassikalised piiratud loendusjuhud: ring, püsipunktita permutatsioon ja võreteed. Kaheksa inimest, kellest keegi ei tõmba enda nime: 14 833 võimalust. See on 8! jagatud e-ga ja ümardatud. Paigaltnihete arv on alati lähim täisarv n!/e väärtusele. Siit pärinebki allpool esitatud kolmas tähelepanek.. — Klassikalised piiratud loendusjuhud: ring, püsipunktita permutatsioon ja võreteed.

Allikad (1)

The last case in the guide above is Secret Santa, and insight block 3 finds e hiding in it. That is the matching problem, and it is three centuries old: P. Gorroochurn, "Rencontres with Montmort (1708)", chapter 7 of Classic Problems of Probability, 54–61. Wiley, 2012 — the probability that nobody draws their own name tends to 1/e.

Harjutus

Kontrolli ennast

Ennusta vastust esmalt ise ja kasuta siis ülal olevaid juhtelemente. Ava lahendus alles siis, kui oled otsustanud — just see teebki sellest harjutuse.

Vali 10 inimese seast 3 komiteesse. Seejärel vali samade 10 hulgast 1., 2. ja 3. koht. Sama n, sama k — kas kaks arvu erinevad, ja kui, siis täpselt mitu korda? Kontrolli kahe esimese mudeliga.

Näita vastust

120 versus 720, kordaja 6. Neid lahutab üksainus küsimus, ja need pole arvud: kas järjekord loeb? Iga järjestamata 3-liikmelise komitee saab rivistada 3! = 6 erinevaks poodiumiks, seega on järjestamine alati valimine korda k!. Kordaja on k! ja mitte kunagi midagi muud — just seepärast erinevad kaks valemit täpselt selle ühe jagamise võrra.
4-kohaline PIN 10 numbrist, ja 4 jäätisekuuli 10 maitse seast, kus üks maitse võib korduda. Mõlemad lubavad kordumist. Ennusta, kumb arv on suurem, ja kontrolli.

Näita vastust

10,000 versus 715. Kordumine on lubatud mõlemas, seega ei lahuta neid kordumine — vaid järjekord. PIN on järjestatud kordumisega, n^k = 10⁴. Kuulid on järjestamata kordumisega, C(n + k − 1, k) = C(13,4) = 715. Kaks „kordumisega“ mudelit on teineteisest sama kaugel kui kaks ilma, ja just seepärast ei piisa küsimusest „kas asjad võivad korduda?“ kunagi üksi. Alati on vaja mõlemat.
Kuus erinevat auhinda kolme erinevasse kasti annab 729. Muuda variant nii, et iga kast peab saama vähemalt ühe auhinna, ja arv langeb 540-ni. Kuhu kadus puuduolev 189 jaotust?

Näita vastust

Need on täpselt need jaotused, mis jätavad mõne kasti tühjaks, ja nende loendamine nõuab valemi asemel vahelduva märgiga summat. Tühja kasti saab valida 3 moel ja ülejäänu täita 2⁶ = 64 moel: 3 × 64 = 192. Kuid need 3 juhtu, kus kõik kuus auhinda satuvad ühte kasti, loeti seal kaks korda, seega lahuta 3. Jääb 192 − 3 = 189 tühja kastiga jaotust, ja 729 − 189 = 540. See on töölaua ainus mudel, mille vastus on vahelduv summa — kõige aeglasem arvutada ja käsitsi kõige kergemini valesti minev.

Ülesanded täielikult lahendatud

3 valimine 10 hulgast ja vastus 7 valimisele 5 sammu
3 elemendi valimine 10 hulgast annab 120 võimalust. Tuleta see järjestatud valikute arvust ning leia seejärel, miks 120 on vastuseks ka 7 elemendi valimisel.
1. Loenda kõigepealt järjestatud valikud, sest neid on lihtsam arvutada: kümme valikut, seejärel üheksa, seejärel kaheksa.
  
  $P (10, 3) = 10 \times 9 \times 8 = 720 = 3! (3 10)$
2. See loendab iga kolmeliikmelise hulga mitmekordselt — ühe korra iga järjekorra kohta, milles samad kolm elementi võiksid esineda, mis on 3! = 6.
3. Jagamine annab tulemuseks 120 ning jagamine k!-ga ongi kogu erinevus permutatsiooni ja kombinatsiooni vahel.
  
  $(3 10) = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = \frac{720}{6} = 120$
4. Sümmeetria tuleneb valimise tähendusest. 3 elemendi valimine on sama tegevus mis 7 elemendi mahajätmine, seega ei saa need kaks arvu erineda.
  
  $(3 10) = (7 10) = 120 (choosing 3 is choosing which 7 to omit)$
5. Paneeli log₁₀ väärtusest 2,0792 on praktiline kaaslane: kolm numbrit. Suure n korral ületab valikute arv mistahes esitusvõime ning logaritm on see, mis jääb arvutatavaks.
  
  $lo g_{10} 120 = 2.0792 ⟹ 3 digits$
Vastus

Tööriist kuvab 120, 3 numbrit ja log₁₀ = 2,0792. Sümmeetriat tasub meeles pidada, sest see vähendab töö hulka poole võrra: keegi ei peaks C(10, 7) arvutamist alustama nullist. Kogu rida annab summaks 2¹⁰ = 1024 — iga kümne elemendi alamhulk, loendatuna suuruse järgi —, mis on kiireim kontroll mistahes binoomarvutuse puhul. Suurim väärtus on C(10, 5) = 252, seega hõlmab rea keskosa umbes veerandi kõigist alamhulkadest, samal ajal kui kummaski otsas on vaid üks.

$(k n) = \frac{P ( n , k )}{k !} : order costs a factor of k! = 6$
2 598 960 võimalust jagada viiest kaardist koosnev mast 5 sammu
Viie kaardiga käe saab jagada 2 598 960 viisil. Tuleta see järjestatud jagamisest ning kasuta seda seejärel mastikäe arvu leidmiseks. See on Vali (kordumiseta) parameetritega n = 52 ja k = 5.
1. Jaga kõigepealt järjestatult. Esimesel kaardil on 52 võimalust, järgmisel 51 ja nii edasi kuni arvuni 48 — viis tegurit, ilma jagamiseta selles etapis.
  
  $P (52, 5) = 52 \times 51 \times 50 \times 49 \times 48 = 311875200$
2. Käsi on hulk ja järjestatud loendus on iga hulga kirja pannud 120 korda — üks kord iga järjekorra kohta, milles samad viis kaarti võisid saabuda. Jagamine arvuga 5! on ainus samm, mis muudab jagamise käeks.
  
  $(5 52) = \frac{311 875 200}{5 !} = \frac{311 875 200}{120} = 2598960$
3. Nüüd loenda selles ruumis mastikäed: vali mast neljal viisil, seejärel viis kaarti selle kolmeteistkümnest kaardist.
  
  $flushes = 4 (5 13) = 4 \times 1287 = 5148$
4. Mis selgitabki, miks mastikäsi on haruldane. Asi pole selles, et 5 148 oleks väike käte arv — vaid selles, et ruum, milles see asub, on viissada korda suurem.
  
  $P (flush) = \frac{5148}{2 598 960} = 0.00198 \approx \frac{1}{505}$
5. Ja see ruum on siiski piisavalt väike, et olla füüsiliselt hoomatav. Üks käsi igas sekundis ilma peatumata, ning iga erinev käsi on jagatud vähem kui kuu jooksul.
  
  $\frac{2 598 960}{86 400} = 30.1 days, at one hand per second$
Vastus

Tööriist väljastab 2 598 960, 7 numbrit ja log₁₀ = 6,4148. Pokkeri käte tugevusjärjestus ongi see arvutus ja ei midagi muud. Loenda read samamoodi — kümme algusastet, neli masti iga viie kaardi kohta, 10 × 4⁵ = 10 240 — ja ridu on kaks korda rohkem kui maste, mis on täpselt see põhjus, miks mast on reast kõrgem. Järjestust ei mõeldud välja; see loendati.

$(5 52) = 2598960 P (flush) \approx \frac{1}{505}$
Korduvate tähtedeta kaheksatähelise parooli 62 990 928 000 varianti 5 sammu
Kordumatute tähtedega kaheksatähelisel paroolil on 62 990 928 000 kuju. Arvuta see, seejärel arvuta sama parool ilma selle reeglita ja otsusta, kumba sa pigem kaitseda sooviksid. See on Järjesta (kordumiseta) parameetritega n = 26 ja k = 8.
1. Täida kohad vasakult paremale. Esimene võtab mis tahes 26 tähest; teine võtab 25, sest ära kasutatud täht on läinud.
  
  $P (26, 8) = \frac{26 !}{18 !} = 26 \times 25 \times 24 \times 23 \times 22 \times 21 \times 20 \times 19$
2. Kaheksa kahanevat tegurit ja see korrutis ongi kogu vastus. See on permutatsioon, mitte kombinatsioon, sest tähtede järjekord on parool.
  
  $= 62990928000$
3. Nüüd eemalda reegel. Iga koht on taas sõltumatu ja iga koha jaoks on olemas kõik 26 tähte, seega on arvutuseks lihtne aste.
  
  $2 6^{8} = 208827064576 (repeats allowed)$
4. Võrdlus ongi tuum: kordumise keelamine jätab alles 30,2% sõnedest. Reegel, mis kõlab kui tugevdamine, on eemaldanud seitse sõnet kümnest.
  
  $\frac{62 990 928 000}{208 827 064 576} = 0.302$
5. Ründaja aja skaalal, miljardi pakkumise korral sekundis, on need kaks ruumi vastavalt üks minut ning kolm ja pool minutit. Kumbki pole kaitse — ja reegel tegi lühema neist veelgi lühemaks.
  
  $1 0^{9} guesses/s : 63 s vs 209 s$
Vastus

Kui n = 26, k = 8 ja mudeliks on valitud Järjesta (kordumiseta), väljastab tööriist 62 990 928 000, 11 numbrit ja log₁₀ = 10,7993. Iga parooli koostamise reegel vähendab ruumi ilma erandita, sest reegel saab ainult keelata. Kas see oma koha ära teenib, sõltub millestki, mida see arvutus ei näe: kas keelatud sõned on sellised, mida inimesed valivad juhuslikkusest palju sagedamini. Ühe kurikuulsa parooli keelamine maksab ühe sõne. Kõigi korduvate tähtede keelamine maksab neid 145 836 136 576.

$P (26, 8) = 0.302 \times 2 6^{8} : forbidding repeats deletes 69.8% of the strings$
Kolm katset sularahaautomaadis neljakohalise PIN-koodiga 5 sammu
Neljakohalisel PIN-koodil on 10 000 väärtust. Arvuta välja, mida väärt on kolm katset pangaautomaadis ja mida korduvate numbrite vältimise tuttav soovitus tegelikult maksab. See on Järjestatud kordustega parameetritega n = 10 ja k = 4.
1. Neli kohta, igas kümme numbrit ja miski ei seo neid — numbrit, mida just kasutasid, saab uuesti kasutada ka järgmises kohas.
  
  $10 \times 10 \times 10 \times 10 = 1 0^{4} = 10000$
2. Kolm katset ühtlaselt valitud PIN-koodi vastu tähendab seega kolme võimalust kümnest tuhandest. Kolme katse piirang ei ole piiramatu arvaamise täiustus; selle ruumi vastu ongi see kogu kaitse.
  
  $3 attempts : \frac{3}{10 000} = 0.03%$
3. Nüüd kehtesta korduvate numbrite puudumise reegel: kümme valikut, siis üheksa, siis kaheksa, siis seitse.
  
  $no repeated digit : 10 \times 9 \times 8 \times 7 = 5040$
4. Reegel jätab alles 5 040 PIN-koodi ja hävitab 4 960. Pool ruumist on läinud — ja läinud poole hulgas oli 1111 koos kõige muuga.
  
  $\frac{5040}{10 000} = 0.504$
5. Kaks lisanumbrit ei tähenda kahte lisapakkumist. Iga number korrutab kümnega, seega kuuekohaline PIN-kood tähendab sada korda suuremat ruumi.
  
  $six digits : 1 0^{6} = 1000000 = 100 \times 1 0^{4}$
Vastus

Tööriist väljastab 10 000 parameetrite n = 10 ja k = 4 korral. Mõlemad faktid kehtivad üheaegselt: ruum on pisike ja PIN-kood on tavaliselt ikkagi piisav — sest kolme katse piirang annab ründajale sellest 0,03%, mitte kogu ruumi. Muuda ohtu ja vastus pöördub vastupidiseks. Varastatud PIN-koodide failil pole katsete piirangut ning kümme tuhat kandidaati on murdosa sekundi töö, mistõttu PIN-koodi turvalisus ei tugine kunagi PIN-koodil endal.

$n^{k} = 1 0^{4} = 1000010 \times 9 \times 8 \times 7 = 5040$
Kolm palli kaheksast maitsest ja kolm inimest kümnest 5 sammu
Kolm pallikest kaheksast maitsest, kordused lubatud, on 120 — sama arv mis kolme inimese valimine kümnest. Näidake, et see ei ole juhus. See on Valik kordustega, kui n = 8 ja k = 3.
1. Kirjutage tellimus sümbolite reana: tärn iga pallikese kohta, kriips iga sammu kohta järgmise maitseni. Kolm pallikest kaheksa maitse hulgas vajavad kolme tärni ja seitset kriipsu.
  
  $3 scoops ⋆ ⋆ ⋆ and 7 bars ∣ ∣ ∣ ∣ ∣ ∣ ∣$
2. Nende kümne sümboli iga paigutus on üks tellimus ja iga tellimus on üks paigutus. Seega on küsimus vaid selles, millised 3 positsiooni 10-st sisaldavad tärne — mis on 1. ülesande küsimus teiste nimisõnadega.
  
  $(3 3 + 7) = (3 10) = 120$
3. Keelake kordused ja arv langeb 56-ni. Luba maitset korrata annab 64 lisatellimust, mis enam kui kahekordistab menüü.
  
  $(3 8) = 56 (no repeats allowed)$
4. Nüüd laske ka järjekorral lugeda, nii et vanill-vanill-münt erineb münt-vanill-vanillist: kaheksa sõltumatut valikut, kolm korda järjest.
  
  $8^{3} = 512 (ordered, repeats allowed)$
5. Nende kahe suhe on 4,27, mitte 3! = 6. Korduva pallikesega tuutul on vähem erinevaid järjestusi kui kolme erineva pallikesega tuutul, seega on 3!-ga jagamine täpselt see samm, mida te siin teha ei tohi.
  
  $\frac{512}{120} = 4.27 \neq = 3! = 6$
Vastus

Tööriist kuvab 120, 3 kohta ja log₁₀ = 2,0792 — sama näit mis 1. ülesandes, kuid teisest küsimusest. Tärnid ja kriipsud on pigem tõlge kui valem: see muudab korduse positsiooniks, kus te juba teate, mida teha. Lõks, mida see seab, on samm 5. Kui kordused on lubatud, ei ole järjestused enam omavahel asendatavad ning ükski ainus tegur ei teisenda järjestatud ja järjestamata arvu vahel.

$(k n + k - 1) : k stars, n - 1 bars$
Sõna MISSISSIPPI 34 650 erinevat kuju, kus neli S-i ei asu kõrvuti 5 sammu
Sõna MISSISSIPPI tähtedest saab moodustada 34 650 erinevat sõna. Tuletage see, seejärel vastake raskemale küsimusele, mille jaoks tööriistal väli puudub: kui tihti neli S-tähte teineteist väldivad? See on Multihulga permutatsioon arvega 1, 4, 4, 2.
1. Alustage eeldusest, et iga täht on eristatav — tähistage S-d kui S₁ kuni S₄. Siis on see üheteistkümne objekti tavaline permutatsioon.
  
  $11! = 39916800$
2. Nüüd eemaldage tähised. Nelja S-i saab permuteerida 4! viisil ilma kirjutatut muutmata ning sama kehtib nelja I ja kahe P kohta, seega loendati iga nähtavat sõna 1 152 korda.
  
  $\frac{11 !}{1 ! 4 ! 4 ! 2 !} = \frac{39 916 800}{1152} = 34650$
3. Mis annab otse tõenäosuse: segage need üksteist plaati ja üks paigutus 34 650-st kirjutab osariigi nime.
  
  $P (a shuffle spells MISSISSIPPI) = \frac{1}{34 650} = 0.0000289$
4. Raskema küsimuse jaoks paigutage esmalt ülejäänud seitse tähte — M, neli I-d, kaks P-d — ja loendage nende paigutused. See jätab kaheksa vahet, kaasa arvatud kaks otsa, ja iga S peab võtma erineva vahe.
  
  $\frac{7 !}{1 ! 4 ! 2 !} = 105, (4 8) = 70$
5. Korrutage ja jagage: 7 350 sõna 34 650-st hoiavad S-d eraldi, mis on 21,2%.
  
  $\frac{105 \times 70}{34 650} = \frac{7350}{34 650} = 0.2121 = \frac{7}{33}$
Vastus

Tööriist kuvab 34 650, 5 kohta ja log₁₀ = 4,5397. Vahemeetod sammudes 4 ja 5 on väärt rohkem kui vastus. See on üldine võte mis tahes tingimuse mitte kaks neist koos korral: paigutage piiranguteta elemendid, seejärel valige vahed piirangutega elementide jaoks. Kõrvutiasuvus on tingimus, mida ükski faktoriaal ei suuda väljendada, ning vahed muudavad selle positsioonide valikuks — mis on ainus asi, mida iga selle lehe valem juba loendada oskab.

$\frac{n !}{n _{1} ! n _{2} ! \dots} : divide by the orderings you cannot see$
Kuue erineva ülesande jagamine kolmele töötajale nii, et keegi ei jää jõude 5 sammu
Kuue eristatava ülesande jagamine kolmele töötajale nii, et keegi ei jää tegevuseta, on 540 jaotust. Tuletage see halbu juhtumeid eemaldades, selle asemel et heid loendada. See on Kuulid kastidesse, eristatavad objektid, iga kast kasutusel, kui n = 6 ja m = 3.
1. Eirake esmalt nõuet. Iga ülesanne valib sõltumatult ühe kolmest töötajast, seega on piiranguteta arv astmeavaldis — ja seda on palju kergem leida kui piirangutega arvu.
  
  $3^{6} = 729 (no restriction)$
2. Nüüd lahutage jaotused, mis jätavad kellegi ilma ülesandeta: valige tegevuseta töötaja kolmel viisil, seejärel andke kõik kuus ülesannet ülejäänud kahele.
  
  $one worker idle : (1 3) 2^{6} = 3 \times 64 = 192$
3. See lahutamine läks liiga kaugele. Jaotust, mis kasutab vaid ühte töötajat, lahutati kaks korda — üks kord iga tegevuseta jäänud kolleegi kohta —, seega tulevad need kolm tagasi.
  
  $two idle, added back : (2 3) 1^{6} = 3$
4. Vahelduv lahutamine ja liitmine on kaasamine ja väljaarvamine, ning vahelduvate märkidega summa on see, mida näitab tööriista valemarida.
  
  $729 - 192 + 3 = 540$
5. Nõnda kasutavad kolm neljandikku kõigist jaotustest juhuslikult kõiki töötajaid. Jagage 3!-ga, et muuta töötajad omavahel asendatavaks, ning saate S(6, 3) = 90, teist liiki Stirlingi arvu — samad tükeldused, loendated ilma nimedeta.
  
  $\frac{540}{729} = 0.7407, S (6, 3) = \frac{540}{3 !} = 90$
Vastus

Tööriist kuvab 540, 3 kohta ja log₁₀ = 2,7324. Samm 3 on koht, kus see ülesanne tavaliselt kaotatakse. Sisetunne ütleb, et halbade juhtumite lahutamine ongi meetod, kuid see pole nii: lahutamine kattuvate hulkade korral laskub alati liiga madalale ning parandusterminid pole dekoratsioon. Sammus 5 olev 90 on sama objekt teise nurga alt — nimeliste töötajatega on 540 jaotust, ilma nimedeta 90 tükeldust ning vahe nende vahel on täpselt nimede jagamise 3! viisi.

$i = 0 \sum m (- 1)^{i} (i m) (m - i)^{n} = 540 = 3! S (6, 3)$
Kaksteist identset žetooni nelja märgistatud karpi nii, et ükski poleks tühi 5 sammu
Kaheteistkümne samase žetooni paigutamine nelja tähistatud kasti nii, et ükski pole tühi, on 165. Jõua selleni, täites kitsenduse kohe alguses. See on Kuulid kastidesse, samased objektid, ükski kast pole tühi, kus n = 12 ja m = 4.
1. Nõue on, et iga kast saaks vähemalt ühe, seega täida see kohe: pane igasse kasti üks žetoon ja ära sellele enam mõtle. Järele jääb kaheksa žetooni ning nüüd pole enam mingeid reegleid.
  
  $pay the floor first : 12 - 4 = 8 units still free$
2. Samaste esemete vabalt jaotamine on tähed ja kriipsud — kaheksa tähte, kolm kriipsu nelja kasti eraldamiseks — ja võimaluste arv on see, millised kohad kriipsud võtavad.
  
  $(4 - 1 8 + 4 - 1) = (3 11) = 165$
3. Loobu nõudest, et ükski kast ei tohi olla tühi, ja sama meetod annab tulemuseks 455, sest kõik kaksteist žetooni on vabad.
  
  $without the floor : (3 12 + 4 - 1) = (3 15) = 455$
4. Seega maksab alampiir üks peaaegu kaks kolmandikku jaotustest: 455-st jääb sellest alles 165.
  
  $\frac{165}{455} = 0.363$
5. Muuda žetoonid selle asemel eristatavaks ja arv hüppab väärtuseni 16 777 216. Samasus on kallis — viis suurusjärku kaheteistkümne objekti kohta.
  
  $distinct units instead : 4^{12} = 16777216$
Vastus

Tööriist kuvab 165, 3 numbrit ja log₁₀ = 2,2175. Samm 1 on ülekantav samm: iga osa alampiiri saab ette ära tasuda, sest selle tasumine jätab sama kujuga ülesande väiksema n-iga. Tõsta alampiir kolmeni igas kastis ja järele jääb kaksteist miinus kaksteist, seega on vastus üks. See ei toimi ülespoole ja see asümmeetria ongi põhjus, miks kõige rohkem kaks kasti kohta on raskem küsimus kui vähemalt üks.

$(m - 1 n - 1) : a floor of one is a constant, not a new formula$
886 656 viiest kaardist koosnevat kätt, mis sisaldavad vähemalt üht ässa 5 sammu
886 656 viiekaardilises käes on vähemalt üks äss. Loenda käed, kus ässa pole, ja lahuta — seejärel konstrueeri kontrolliks sama arv pikemat teed pidi. See on Kaasamine-eraldamine, vähemalt-üks, kus n = 52, k = 5 ja 48 kaarti ei ole ässad.
1. Vähemalt ühte ässa sisaldavate käte otse loendamine tähendab käte jaotamist ühe, kahe, kolme ja nelja ässaga juhtudeks. Täiendi loendamine on vaid üks arvutus, seega alusta sellest.
  
  $(5 52) = 2598960$
2. Ässata käsi on viis kaarti, mis on võetud 48 mitteässa hulgast.
  
  $(5 48) = 1712304 (not one ace)$
3. Lahuta, ja igas järelejäänud käes on äss — sest käes kas pole ühtegi ässa või on mõni, ilma ühegi vahepealse võimaluseta.
  
  $2598960 - 1712304 = 886656$
4. Seega sisaldab peaaegu kolmandik kõigist kätest vähemalt ühte ässa, mida on palju rohkem kui fraas neli ässa viiekümne kahes kaardis osutab.
  
  $P = \frac{886 656}{2 598 960} = 0.3412$
5. Nüüd kontroll. Loenda täpselt üks äss, täpselt kaks, täpselt kolm ja täpselt neli, ning seejärel liida. Neli eraldi arvutust ja kogusumma klapib viimase numbrini.
  
  $4 (4 48) + 6 (3 48) + 4 (2 48) + (1 48) = 778320 + 103776 + 4512 + 48 = 886656$
Vastus

Tööriist kuvab 886 656, 6 numbrit ja log₁₀ = 5,9478. Samm 5 pole pelgalt iluasi. Vähemalt üks on fraas, mida loendatakse kõige sagedamini kujul 4 × C(48, 4) = 778 320 — vali äss, seejärel täida ülejäänud kohad — ja see arv on vale, sest kahe ässaga käsi tekib selle retsepti järgi kaks korda, üks kord kummagi ässa kaudu. Täiend ei saa kunagi seda viga teha, mistõttu on see esimene asi, mille poole haarata, kui küsimuses on vähemalt üks.

$∣ A ∣ = N - ∣ A^{c} ∣ : count the easy side and subtract$
Nelikümmend, kolmkümmend viis ja kakskümmend kaheksa liiget kolmes klubis 5 sammu
Nelikümmend, kolmkümmend viis ja kakskümmend kaheksa liiget kolmes klubis ei tee kokku 103 inimest. Leia tegelik inimeste arv ja jaota see nendeks, kes kuuluvad ühte, kahte või kõiki kolme klubisse. See on Kaasamine-eraldamine, kolme hulga ühend, kus paarikaupa ühisosi on 12, 10 ja 9 ning kolmikühisosa on 4.
1. Liida kolm nimekirja. Igaüks, kes on kahes klubis, on nüüd loendatud kaks korda, ja igaüks, kes on kõigis kolmes, on loendatud kolm korda, mistõttu 103 on vaid ülempiir ega midagi enamat.
  
  $40 + 35 + 28 = 103$
2. Lahuta iga paarikaupa ühisosa. Keegi, kes on täpselt kahes klubis, on nüüd loendatud õigesti — kuid keegi, kes on kõigis kolmes, on loendatud kolm korda ja lahutatud kolm korda, mistõttu on ta täielikult kadunud.
  
  $103 - (12 + 10 + 9) = 103 - 31 = 72$
3. Liida kolmikühisosa tagasi, et nad taastada. Selles seisnebki kolme hulga kaasamine ja eraldamine: liida üksikud, lahuta paarid, liida kolmik.
  
  $72 + ∣ A \cap B \cap C ∣ = 72 + 4 = 76$
4. Ühend ei ütle, kuidas need 76 jagunevad, kuid samad kolm sisendandmed annavad vastuse ka sellele. Kaalu paare kahega ja kolmikut kolmega, et eemaldada kõik, kellel on rohkem kui üks liikmesus.
  
  $exactly one = 103 - 2 (31) + 3 (4) = 53$
5. Ülejäänu järgneb sellest: täpselt kahte klubisse kuulub 19 inimest ja need kolm rühma annavad kokku taas 76.
  
  $exactly two = 31 - 3 (4) = 19, 53 + 19 + 4 = 76$
Vastus

Tööriist kuvab 76, 2 numbrit ja log₁₀ = 1,8808. Vahelduvad märgid on parandus, mitte mälureegel: iga liige korrigeerib eelmise liikme ülepakkumist, ja see vaheldub, sest iga parandus pakub teises suunas üle. Seetõttu kasvab valem ka nii kiiresti — neli hulka vajavad viisteist liiget ja n hulka vajavad 2ⁿ − 1 liiget. Ammu enne seda, kui see muutub praktiliseks, on ülesande 9 täiend parem tööriist.

$∣ A \cup B \cup C ∣ = Σ_{1} - Σ_{2} + Σ_{3} = 76$
Kaheksa inimest tõmbavad Secret Santa nimesid nii, et keegi ei saa oma nime 5 sammu
Kaheksa inimest tõmbavad salajase jõuluvana jaoks nimesid ning 40 320 võimalikust loosimisest 14 833 korral ei tõmba keegi enda nime. Tuletage see arv ning seejärel küsige, kui palju inimesi tavaliselt enda nime tõmbab. See on Erijuhud, derangering, kui n = 8.
1. Derangering on ilma püsipunktita permutatsioon. Kaasamise-väljaarvamise printsiip kaheksa sündmuse see inimene tõmbas enda nime korral annab vahelduvate märkidega summa.
  
  $! n = n! i = 0 \sum n \frac{( - 1 ) ^{i}}{i !}$
2. See summa on rea e⁻¹ esimesed üheksa liiget ning kõik, mis sellest välja jääb, on väiksem kui 1/9! = 2,8 × 10⁻⁶.
  
  $8! = 40320, i = 0 \sum 8 \frac{( - 1 ) ^{i}}{i !} = 0.367882$
3. Korrutage läbi ja ümardage: 14 833 loosimist, kus keegi ei hoia enda nime.
  
  $! 8 = 40320 \times 0.367882 = 14833$
4. Murdosana on see 0,36788, võrrelduna väärtusega e⁻¹ = 0,367879 — kattuvus viie komakohani kaheksa inimese korral, ning see peaaegu ei muutu suuremate rühmade puhul.
  
  $P = \frac{14 833}{40 320} = 0.36788 \approx e^{- 1} = 0.367879$
5. Nüüd teistsugune küsimus, mis on lihtsam. Iga inimene tõmbab enda nime tõenäosusega 1/n ning keskväärtused summeeruvad sõltumata sellest, kas sündmused on sõltumatud või mitte, seega on enda nime tõmbamiste oodatav arv täpselt 1 — nii kaheksa kui ka kaheksasaja inimese puhul.
  
  $E [self-draws] = i = 1 \sum n \frac{1}{n} = n \times \frac{1}{n} = 1$
Vastus

Tööriist väljastab 14 833, 5 numbrit ja log₁₀ = 4,1712. Samm 5 selgitab sammu 4. Kui enda nime tõmbamiste keskmine arv on 1 sõltumata rühma suurusest, ei saa ka tõenäosus mitte ühtegi tõmmata rühma suurusest palju sõltuda — ning harva esineva sündmuse arvu korral, mille keskväärtus on 1, on see tõenäosus e⁻¹. See konstant pole siin pelk huviväärsus. See on vastus küsimusele kui tõenäoline on null, kui keskmine on üks — küsimusele, mis kerkib pidevalt esile ka väljaspool kombinatoorikat.

$\frac{! n}{n !} \to e^{- 1}, E [self-draws] = 1 for every n$
Lühimad teekonnad 7 × 5 ruudustikus ühe blokeeritud ruuduga 5 sammu
442 lühimat teekonda läbivad 7 × 5 ruudustikku, kui üks ruut on blokeeritud. Loendage need kõik, loendage teekonnad läbi blokeeritud ruudu ja lahutage. Seejärel leidke ruut, mille kaotus kahjustaks kõige rohkem. See on Erijuhud, võrestikuteekond, 7 sammuga itta, 5 sammuga põhja ja tõkkega punktis (3, 2).
1. Iga lühim teekond on kaksteist sammu pikk, neist seitse itta ja viis põhja mingis järjestuses. Seega pole teekond midagi muud kui valik, millised sammud tehakse itta.
  
  $(7 7 + 5) = (7 12) = 792$
2. Teekond läbi blokeeritud ruudu on kaks sõltumatut teekonda, mis on kokku liimitud selles ruudus: nurgast ruuduni ja ruudust kaugeima nurgani. Korrutage, sest iga esimene pool moodustab paari iga teise poolega.
  
  $through (3, 2) : (3 5) (4 7) = 10 \times 35 = 350$
3. Lahutage, ja järele jäävad täpselt need teekonnad, mis seda ruutu ei läbi.
  
  $792 - 350 = 442$
4. See üksik ruut kandis 44% kogu liiklusest — üks tõke eemaldab peaaegu poole teekondadest.
  
  $\frac{350}{792} = 0.442$
5. Kuid see pole kõige halvem ruut, mida kaotada. Ruut, mis asub alguspunktist ühe sammu võrra idas, kannab 462 teekonda ehk 58% neist, sest iga idasuunalise sammuga algav teekond peab sellest läbi minema.
  
  $through (1, 0) : (1 1) (6 11) = 462 = 0.583 of all paths$
Vastus

Tööriist väljastab 442, 3 numbrit ja log₁₀ = 2,6454. Samm 5 on vastuolus pildiga. Blokeeritud ruut tundub kõige kahjulikum keskpaiga lähedal, kuhu teekonnad näivad koonduvat; arvutus näitab aga, et nurgalähedased ruudud kannavad rohkem, sest teekondade arv läbi ruudu on kahe binoomkoefitsiendi korrutis ja nurga lähedal katab üks neist peaaegu kogu ruudustiku. Teekondade loendamine läbi iga tipu, selle asemel et vaadata kaarti, on ühtlasi viis, kuidas mõõdetakse redundantsust reaalses võrgustikus.

$(a a + b) - (x x + y) (a - x ( a - x ) + ( b - y )) = 442$

42Mathi meeskond · Uuendatud 2026-08-17

Kontrollitud avaldatud allikate põhjal. Parandused on teretulnud. Toimetamispõhimõtted · Parandused

Kõik Statistika & rahandus õppetunnid →

Näiteülesanded

komisjoni valimine - Vali 10 inimese seast 3: järjekord ei ole oluline
5-kaardiline käsi - Pokkerikätt saab moodustada 2 598 960 viisil. Tööriist näitab selle kõrval ka arvu kuju: 7 kohta, log₁₀ 6,4148. Variantide loetlemisest see aga keeldub, tuues põhjuseks tulemuste ruumi liigse mahukuse. Selles keeldumises peitubki asja tuum. Valem annab meile koguarvu ilma hulka ennast moodustamata.
loteriivalik - Kuus numbrit neljakümne üheksast, kus järjestus pole oluline, annab 13 983 816 piletit. Ostes igal nädalal ühe pileti, kuluks nende kõigi katmiseks veerand miljonit aastat. See on kõige ausam viis selliste tõenäosuste mõistmiseks.
poodiumi järjekord - Esikolmik 10 seast: järjekord on oluline
erinevate märkidega parool - Kaheksa tähte ilma kordumisteta annab tulemuseks 62 990 928 000. See on kuuskümmend kolm miljardit pelgalt kahekümne kuuest sümbolist. Kordumiste keelamine maksab siin üllatavalt vähe, sest kaheksa on kahekümne kuue kõrval väike arv.
korralda kõik - Järjestame kõik kaheksa. Siin k võrdub n-iga ning vastus on 8! = 40 320. Üldine permutatsioonivalem taandub faktoriaalile just siis, kui ükski element ei jää kõrvale.
PIN-kood - 4-kohaline PIN-kood: kordused on lubatud
tootekood - Kuus märki kolmekümne kuuest tähest ja numbrist, kui kordumised on lubatud, annab 2 176 782 336 koodi. Kuuemärgilise sildi abil saame luua kaks miljardit varianti. Seetõttu ongi seerianumbrid nii lühikesed.
jäätisepallid - 3 kuulikest 8 maitse seast: järjekord ei loe, kordused lubatud
identsed pallid - Kaksteist identset palli viide eristatavasse lahtrisse on klassikaline tärnide ja kriipsude meetod: C(16, 4) = 1 820. Identsed elemendid muudavad koguarvu väiksemaks, mitte suuremaks. Nende omavaheline vahetamine ei muuda ju midagi.
BALLOON - Sõnas BALLOON on seitse tähte, mille hulgas kaks L-i ja kaks O-d. Seega arvutame 7! jagatuna 2!·2!-ga, saades 5 040 asemel 1 260. Iga korduv paar poolitab koguarvu.
MISSISSIPPI - Üksteist tähte, neli S-i, neli I-d, kaks P-d. Avaldis 11! jagatud 4!·4!·2!-ga annab vastuseks 34 650. Ilma kordumisteta oleks tulemus 39 916 800. Seega eemaldavad duplikaadid üle 99,9% kõikvõimalikest järjestustest.
erinevad kastidesse (mistahes) - Kuus erinevat ülesannet kolmele töötajale ilma ühegi piiranguta. Iga ülesanne teeb sõltumatu valiku, seega 3⁶ = 729. See on lihtne juhtum. Järgmine olukord, kus igaüks peab saama vähemalt ühe ülesande, kaotab aga oma lihtsuse.
erinevad kastidesse (sürjektiivne) - Jaga 6 erinevat ülesannet 3 töötaja vahel, igaüks saab vähemalt ühe
identsed kastidesse (mistahes) - Kaksteist identset eset nelja lahtrisse, kusjuures tühjad lahtrid on lubatud: C(15, 3) = 455. Võrrelge seda eelmise, eristatavate esemete variandiga. Elementide identseks muutmine on kombinatoorikas kõige drastilisem viis võimaluste arvu kahandada.
identsed kastidesse (mittetühjad) - Samad kaksteist eset nelja lahtrisse nii, et ükski ei jääks tühjaks: C(11, 3) = 165. Asetame igasse lahtrisse esmalt ühe eseme. Ülejäänud kaheksa jaotame vabalt. Just seetõttu kehtibki sama valem väiksemate arvude korral.
vähemalt üks äss - 5-kaardiline käsi, milles on vähemalt üks äss – arvutatud vastandsündmuse kaudu
kolme hulga ühend - Kolm klubi liikmete arvuga 40, 35 ja 28 annavad kattuvuste tõttu kokku 76 inimest, mitte 103. Lahutage iga paar ühe korra ja liitke kolmik uuesti juurde. Kõigisse kolme klubisse kuuluvaid inimesi eemaldati muidu ühe korra liiga palju.
ümarlaud - Istuta 7 inimest ümarlaua taha: pöörded loetakse samaväärseks
salajane jõuluvana - Kaheksa inimest, kellest keegi ei tõmba enda nime: 14 833 võimalust. See on 8! jagatud e-ga ja ümardatud. Paigaltnihete arv on alati lähim täisarv n!/e väärtusele. Siit pärinebki allpool esitatud kolmas tähelepanek.
võretee - Lühimad teed ruudustikul, kus üks ruut on blokeeritud. Esmalt loendame kõik marsruudid. Seejärel lahutame blokeeritud ruutu läbivad teed. See ongi kaasamiste-välistamiste printsiip oma kõige lihtsamal kujul.