Prvky kombinatoriky. Kombinatorika - základné pojmy a vzorce. Permutácie, umiestnenia, kombinácie Príklady kombinatoriky

Kombinatorika je odvetvie matematiky. Základné pojmy a vzorce kombinatoriky ako vedy sa uplatňujú vo všetkých sférach života.

Nie je prekvapujúce, že je zaradený do programu 11. ročníka, ako aj do prijímacích skúšok na mnohých univerzitách v Ruskej federácii. Jeho základy spočívajú v úžitkovom umení mnohých oblastí ľudskej činnosti.

Jeho história siaha viac ako 6 storočí do minulosti. Prvé kombinatorické problémy sa objavili v dielach filozofov a matematikov stredoveku.

Predstavitelia tohto vedeckého sveta sa snažili nájsť metódy na riešenie takýchto problémov, ich základné pravidlá a koncepty a vytvoriť jedinečné vzorce a rovnice pre tých, ktorí sa s nimi ešte nestretli. Takéto informácie sa v našej dobe nazývajú informácie „pre figuríny“.

Pokúsme sa pochopiť aspekty tejto oblasti vedy: aké sú prvky, vlastnosti, pravidlá, metódy a jej hlavné uplatnenie v našom živote? Samozrejme, nie je možné pokryť celú oblasť v jednom článku. Preto budú všetky najzákladnejšie veci uvedené nižšie.

Čo je kombinatorika v matematike

Podstatu tohto pojmu dávajú knihy minulých rokov: toto odvetvie matematiky zaoberajúce sa operáciami s mnohými prvkami.

Na internete sú učebnice informatiky a matematiky pre deti a školákov, zbierky materiálov a úloh pre začiatočníkov, kde je prístupným spôsobom vysvetlená „zábavná“ kombinatorika. Musíme pevne prísť na to, ako takéto problémy vyriešiť.

V základných ročníkoch sa problémy na túto tému riešia v doplnkových kluboch av školách s hĺbkovým štúdiom matematiky - na hlavných hodinách. Okrem toho sú úlohy kombinatoriky zahrnuté do olympiád na všetkých úrovniach.

Základné pojmy

Je ich niekoľko:

1. Element– akýkoľvek predmet alebo jav zahrnutý v požadovanom súbore.
2. Kombinácia– podmnožiny nachádzajúce sa v ľubovoľnom poradí v pôvodnom súbore.
3. Preskupenie– prvky v súprave sú v presne definovanom poradí.
4. Ubytovanie– objednané podmnožiny v pôvodnej súprave.

Produktové pravidlo

Je to jedno zo základných pravidiel pri riešení takýchto problémov a znie takto:

Pri výbere prvku A znmetódy a výber prvku B zmV niečom platí, že je možné zvoliť si dvojicu A a B súčasnen* mspôsoby.

Pozrime sa na konkrétne príklady.

Úloha č.1.

Krabička obsahuje 2 lopty a 6 švihadiel. Koľko spôsobov je možné získať 1 loptu a 1 švihadlo?

Odpoveď je jednoduchá: 2 * 6 = 12.

Úloha č.2.

Obsahuje 1 kocku, 2 gule, 3 kvety a 4 cukríky. Koľkými spôsobmi môžete nakresliť kocku, guľu, kvet a cukrík?

Riešenie je podobné: 1 * 2 * 3 * 4 = 24.

Navyše, ľavá strana môže byť napísaná oveľa jednoduchšie: 4!

! v tomto prípade nejde o interpunkčné znamienko, ale o faktoriál. Pomocou neho môžete vypočítať zložitejšie možnosti a vyriešiť zložité problémy (existujú rôzne vzorce, ale o tom neskôr).

Úloha č.3.

Koľko dvojciferných čísel možno vytvoriť z 2 číslic?

Odpoveď: 2! = 2.

Úloha č.4.

Koľko desaťciferných čísel možno vytvoriť z 10 číslic?

Pravidlo súčtu

To je tiež základné pravidlo kombinatoriky.

Ak je možné zvoliť Ankrát a B -mkrát, potom je možné zvoliť A alebo B (n+ m) raz.

Úloha č.5.

Krabička obsahuje 5 červených, 3 žlté, 7 zelených, 9 čiernych ceruziek. Koľko spôsobov je možné vytiahnuť ktorúkoľvek 1 ceruzku?

Odpoveď: 5 + 3 + 7 + 9 = 24.

Kombinácie s opakovaním a bez opakovania

Tento výraz sa vzťahuje na kombinácie v ľubovoľnom poradí z množiny prvkov n x m.

Počet kombinácií sa rovná počtu takýchto kombinácií.

Úloha č.6.

Krabička obsahuje 4 rôzne druhy ovocia. Koľkými spôsobmi môžete získať 2 rôzne druhy ovocia súčasne?

Riešenie je jednoduché:

Kde je 4! – kombinácia 4 prvkov.

S opakovaniami trochu zložitejšie, kombinácie sa počítajú pomocou nasledujúceho vzorca:

Úloha č.7.

Zoberme si ten istý prípad, ale pod podmienkou, že jeden plod sa vráti do krabice.

V tomto prípade:

Umiestnenie s opakovaním a bez opakovania

Táto definícia znamená množinu m prvkov z množiny n prvkov.

Úloha č.8.

Z 3 číslic si musíte vybrať 2, aby ste získali rôzne dvojciferné čísla. Koľko možností?

Odpoveď je jednoduchá:

Ale čo už s opakovaniami? Tu môže byť každý prvok umiestnený niekoľkokrát! V tomto prípade bude všeobecný vzorec vyzerať takto:

Úloha č.9.

Z 12 písmen latinskej abecedy a 10 číslic prirodzenej série musíte nájsť všetky možnosti na zostavenie kódu regiónu automobilu.

Permutácie s opakovaním a bez opakovania

Tento výraz sa vzťahuje na všetky možné kombinácie množiny prvkov n.

Úloha č.10.

Koľko možných 5-ciferných čísel možno vytvoriť z 5 číslic? A čo šesť číslic zo 6 číslic? Sedem číslic zo 7?

Riešenia podľa vyššie uvedeného vzorca sú nasledovné:

Ale čo už s opakovaniami? Ak sú v takejto množine prvky rovnakej dôležitosti, potom bude menej permutácií!

Úloha č.11.

Krabička obsahuje 3 rovnaké ceruzky a jedno pero. Koľko permutácií môžete urobiť?

Odpoveď je jednoduchá: 4! / (3! * 1!) = 4.

Kombinatorické problémy s riešeniami

Príklady všetkých možných typov problémov s riešeniami boli uvedené vyššie. Tu sa pokúsime vysporiadať so zložitejšími prípadmi, s ktorými sa stretávame v našich životoch.

Typy úloh	Čo potrebujete nájsť	Metódy riešenia
Magický štvorec	Číslo, v ktorom musí byť súčet čísel v riadkoch a stĺpcoch rovnaký (jeho odrodou je latinský štvorec).	Rekurentné vzťahy. Podobný problém je vyriešený, ale s oveľa menšou množinou prvkov podľa známych pravidiel a vzorcov.
Problém s umiestnením	Štandardnou výrobnou úlohou (napríklad v technológii patchwork) je nájsť možné spôsoby, ako rozložiť množstvá produktov na bunky v určitom poradí.	Inklúzie a vylúčenia. Spravidla sa používa pri dokazovaní rôznych výrazov.
Problémy s obchodníkmi	Ide o to, nájsť všetky možné spôsoby, ako sa ľudia dostať z bodu A do bodu B.	Trajektórie. Tento typ úloh sa vyznačuje geometrickou konštrukciou možných riešení.

Záver

Stojí za to študovať túto vedu, pretože vo veku rýchlej modernizácie technológie sa budú vyžadovať špecialisti, ktorí môžu poskytnúť rôzne riešenia určitých praktických problémov.

KOMBINATORIKA

Kombinatorika je oblasť matematiky, ktorá študuje problémy výberu a usporiadania prvkov z určitého základného súboru v súlade s danými pravidlami. Vzorce a princípy kombinatoriky sa používajú v teórii pravdepodobnosti na výpočet pravdepodobnosti náhodných udalostí a podľa toho na získanie zákonov rozdelenia náhodných premenných. To nám zase umožňuje študovať vzorce hromadných náhodných javov, čo je veľmi dôležité pre správne pochopenie štatistických vzorcov, ktoré sa prejavujú v prírode a technike.

Pravidlá sčítania a násobenia v kombinatorike

Pravidlo súčtu. Ak sa dve akcie A a B vzájomne vylučujú a akciu A možno vykonať m spôsobmi a B n spôsobmi, potom jednu z týchto akcií (buď A alebo B) možno vykonať n + m spôsobmi.

Príklad 1

V triede je 16 chlapcov a 10 dievčat. Koľkými spôsobmi môžete prideliť jedného dôstojníka?

Riešenie

Do služby môže byť zaradený buď chlapec alebo dievča, t.j. dôstojníkom môže byť ktorýkoľvek zo 16 chlapcov alebo ktorékoľvek z 10 dievčat.

Pomocou pravidla súčtu zistíme, že jedného dôstojníka možno prideliť 16+10=26 spôsobmi.

Produktové pravidlo. Nech sa vyžaduje k akcií, ktoré je potrebné vykonať postupne. Ak je možné prvú akciu vykonať n 1 spôsobmi, druhú akciu n 2 spôsobmi, tretiu n 3 spôsobmi atď. až do k-tej akcie, ktorú možno vykonať n k spôsobmi, potom možno vykonať všetkých k akcií spolu. :

spôsoby.

Príklad 2

V triede je 16 chlapcov a 10 dievčat. Koľkými spôsobmi môžu byť vymenovaní dvaja dôstojníci?

Riešenie

Ako prvá osoba v službe môže byť určený chlapec alebo dievča. Pretože V triede je 16 chlapcov a 10 dievčat, prvú službukonajúcu osobu potom môžete určiť 16+10=26 spôsobmi.

Po tom, čo sme si vybrali prvého strážnika, môžeme zo zvyšných 25 ľudí vybrať druhého, t.j. 25 spôsobov.

Podľa násobiacej vety je možné vybrať dvoch účastníkov 26*25=650 spôsobmi.

Kombinácie bez opakovania. Kombinácie s opakovaním

Klasickým problémom kombinatoriky je problém počtu kombinácií bez opakovaní, ktorého obsah možno vyjadriť otázkou: koľko spôsoby Môcť vybrať m od n rôznych položiek?

Príklad 3

Musíte si vybrať 4 z 10 rôznych kníh dostupných ako darček. Koľkými spôsobmi sa to dá urobiť?

Riešenie

Musíme vybrať 4 knihy z 10, pričom na poradí výberu nezáleží. Preto musíte nájsť počet kombinácií 10 prvkov zo 4:

.

Zvážte problém počtu kombinácií s opakovaniami: existuje r identických objektov každého z n rôznych typov; koľko spôsoby Môcť vybrať m() od títo (n*r) položiek?

.

Príklad 4.

V cukrárni sa predávali 4 druhy koláčov: napoleonky, zákusky, krehké a lístkové pečivo. Koľkými spôsobmi si môžete kúpiť 7 koláčov?

Riešenie

Pretože Medzi 7 koláčmi môžu byť koláče rovnakého druhu, potom počet spôsobov, na ktoré možno kúpiť 7 koláčov, je určený počtom kombinácií s opakovaním 7 až 4.

.

Umiestnenia bez opakovania. Umiestnenia s opakovaniami

Klasickým problémom v kombinatorike je problém počtu umiestnení bez opakovaní, ktorého obsah možno vyjadriť otázkou: koľko spôsoby Môcť vybrať A príspevok Autor: m iný Miesta m od n rôzne položky?

Príklad 5.

Niektoré noviny majú 12 strán. Na stránky týchto novín je potrebné umiestniť štyri fotografie. Koľkými spôsobmi to možno urobiť, ak žiadna strana novín nesmie obsahovať viac ako jednu fotografiu?

Riešenie.

V tejto úlohe fotografie nielen nevyberáme, ale umiestňujeme ich na určité strany novín, pričom každá strana novín by nemala obsahovať viac ako jednu fotografiu. Problém sa teda redukuje na klasický problém určenia počtu umiestnení bez opakovania 12 prvkov zo 4 prvkov:

4 fotografie na 12 stranách sa teda dajú usporiadať 11 880 spôsobmi.

Klasickým problémom v kombinatorike je aj problém počtu umiestnení s opakovaním, ktorého obsah možno vyjadriť otázkou: koľko spôsoby Môcť vybarmády A príspevok Autor: m iný Miesta m od n položiek,spripravený ktoré Existuje rovnaký?

Príklad 6.

Chlapec mal ešte pečiatky s číslami 1, 3 a 7 zo svojej sady spoločenských hier. Rozhodol sa použiť tieto pečiatky na nalepenie päťciferných čísel na všetky knihy, aby vytvoril katalóg. Koľko rôznych päťciferných čísel dokáže chlapec vytvoriť?

Permutácie bez opakovania. Permutácie s opakovaniami

Klasickým problémom v kombinatorike je problém počtu permutácií bez opakovania, ktorého obsah možno vyjadriť otázkou: koľko spôsoby Môcť príspevok n rôzne položky na n rôzne Miesta?

Príklad 7.

Koľko štvorpísmenových „slov“ dokážete vytvoriť z písmen slova „manželstvo“?

Riešenie

Všeobecnú populáciu tvoria 4 písmená slova „manželstvo“ (b, p, a, k). Počet „slov“ je určený permutáciami týchto 4 písmen, t.j.

Pre prípad, že medzi vybranými n prvkami sú identické prvky (výber s návratom), problém počtu permutácií s opakovaniami možno vyjadriť otázkou: Koľkými spôsobmi možno preusporiadať n objektov umiestnených na n rôznych miestach, ak medzi n objektmi existuje k rôznych typov (k< n), т. е. есть одинаковые предметы.

Príklad 8.

Koľko rôznych kombinácií písmen možno vytvoriť z písmen slova „Mississippi“?

Riešenie

Existuje 1 písmeno "m", 4 písmená "i", 3 písmená "c" a 1 písmeno "p", spolu 9 písmen. Preto je počet permutácií s opakovaniami rovný

ZHRNUTIE ZÁKLADNÝCH PODMIENOK PRE SEKCIU "KOMBINATORIKA"

Na zostavenie zodpovedajúcich matematických modelov kombinatorických úloh použijeme matematický aparát teórie množín. Môže sa stať, že v danej množine nie je dôležité poradie prvkov, ale dôležité je len zloženie množiny. Existujú však problémy, pri ktorých je podstatné poradie prvkov.

Definícia 1: objednať v mnohých prvkov je číslovanie jeho prvkov prirodzenými číslami, t.j. nastaviť zobrazenie
pre veľa
.

Definícia 2: Súbor s daným poradím sa nazýva objednaná sada.

Je zrejmé, že sadu obsahujúcu viac ako jeden prvok možno objednať viacerými spôsobmi.

Napríklad z dvoch písmen A Usporiadanú sadu môžete zostaviť dvoma rôznymi spôsobmi:

A
.

Tri písmená ,A možno zoradiť šiestimi spôsobmi:

,
,
,
,
,
.

Pre štyri písmená získame enumeráciou 24 rôznych usporiadaných sekvencií.

Usporiadané postupnosti prvkov určitej množiny možno považovať za rozmiestnenia alebo usporiadania týchto prvkov v postupnosti.

Definícia 3: Nech je daná konečná množina
od prvkov. Akýkoľvek súbor budú volané prvky danej množiny (a prvky v množine sa môžu opakovať). -dojednania .

Prostredníctvom konceptu usporiadania sa zavádzajú základné definície kombinatoriky: kombinácie, umiestnenia a permutácie. Navyše, každý z týchto konceptov sa môže opakovať alebo bez opakovania. V tejto časti budeme uvažovať o kombinatorických vzorcoch bez opakovania.

Prestavby bez opakovania.

Definícia 4: Nechaj
- konečná množina prvkov. Permutácie od rôzne prvky súpravy
volajú sa všetky miesta prvky v určitom poradí. Označené: (z francúzskeho slova permutácia- preskupenie).

Objednané súpravy sa považujú za odlišné, ak sa líšia buď svojimi prvkami alebo poradím.

Definícia 5: Nazývajú sa rôzne usporiadané množiny, ktoré sa líšia iba poradím svojich prvkov permutácií tohto množstva.

Posledná definícia je formulovaná z pozície teórie množín.

Definícia 6: Práca po sebe idúce prirodzené čísla sa v matematike označujú a zavolajte faktoriál .

Voľba pre označenie výkričník môže byť spôsobený tým, že aj pri relatívne malých hodnotách číslo veľmi veľký. Napríklad,
,
,
,
,
,,atď.

Veta 1: Počet permutácií od rôzne prvky sa vypočítajú podľa vzorca:

Dôkaz. Zvážte ľubovoľnú množinu prvkov. Postavme si z nich najrôznejšie aranžmány prvkov. Na prvé miesto v aranžmáne môžete dať ktorýkoľvek z prvky ( metódy výberu prvého prvku). Po výbere prvého prvku a bez ohľadu na to, ako je vybratý, je možné vybrať druhý prvok
spôsobom. Zostáva vybrať tretí prvok
metóda atď. Posledný prvok sa podľa toho vyberie jedným spôsobom. Potom v dôsledku kombinatorického princípu násobenia sa počet takýchto usporiadaní bude rovnať:

Veta bola dokázaná.

Príklad 1: Koľkými spôsobmi môžu traja priatelia zaujať miesta s číslami 1, 2 a 3 v kine?

Riešenie. Počet vyhľadaných metód sa bude rovnať počtu permutácií bez opakovania troch prvkov:
spôsoby. V prípade potreby je možné tieto metódy vyriešiť.

Permutácie písmen slova sa nazývajú anagramy . Anagramy, ktoré objavil už v 3. storočí pred Kristom grécky gramatik Lycophron, stále priťahujú pozornosť lingvistov, básnikov a milovníkov literatúry. Majstri slovných hier okrem erudície a veľkej slovnej zásoby poznajú mnohé tajomstvá súvisiace s kombinačnými schopnosťami, jedným z nich sú anagramy. Často je potrebné vybrať spomedzi všetkých permutácií tie, ktoré majú určitú vlastnosť. Napríklad medzi anagramy slova "Krtko", ktorých je len
, len jeden, nerátajúc samotné slovo "Krtko", dáva zmysel v ruštine – „súd“.

Okrem lineárnych permutácií možno uvažovať o kruhových (alebo cyklických) permutáciách. V tomto prípade sa permutácie, ktoré sa navzájom transformujú počas rotácie, považujú za rovnaké a nemali by sa počítať.

Veta 2: Počet kruhových permutácií od rôzne prvky sú rovnaké

Príklad 2: Koľkými spôsobmi sa môže 7 detí zapojiť do okrúhleho tanca?

Riešenie. Počet lineárnych permutácií 7 detí sa bude rovnať
. Ak už bol okrúhly tanec vytvorený, existuje preň 7 kruhových permutácií, ktoré sa pri otáčaní navzájom premieňajú. Tieto permutácie by sa nemali počítať, takže budú kruhové permutácie 7 prvkov .

Umiestnenia bez opakovania.

Definícia 7: Nech je tam rôzne položky. Aranžmány z prvky podľa prvky (
) sa volajú umiestnenia bez opakovaní . Určenie: . Ide tu o to, že prvky v usporiadaní sa neopakujú.

V tejto definícii je podstatná nasledujúca pozícia: tieto dve usporiadania sú odlišné, ak sa líšia aspoň v jednom prvku alebo poradí prvkov.

Uveďme inú definíciu umiestnení, ekvivalentnú pôvodnej, zrozumiteľnejšej.

Definícia 8: Konečné usporiadané množiny sa nazývajú umiestnenia.

Veta 3: Počet všetkých umiestnení z prvky podľa prvky bez opakovaní sa vypočítajú podľa vzorca:

Dôkaz. Nech existuje ľubovoľná množina
, skladajúci sa z prvkov. Musíte si vybrať z tejto odrody rôzne prvky. Okrem toho je dôležité poradie výberu.

Výber prvkov sa vykonáva v etapách. Prvý prvok usporiadania je možné vybrať rôzne cesty. Potom zo zostávajúcich prvkov súpravy
vyberie sa druhý prvok usporiadania
spôsobom. Je možné vybrať tretí prvok
metóda atď. Potom si vybrať - prvok, ktorý máme
spôsobom. Preto podľa pravidla násobenia sa počet takýchto usporiadaní bude rovnať:

Podľa definície sú takéto usporiadania umiestnenia. Q.E.D.

Príklad 3: Na schôdzi 25 ľudí sa volí prezídium 3 ľudí: 1) predseda, 2) zástupca, 3) tajomník. Koľko možností je na výber prezídia?

Riešenie. Pri výbere troch ľudí z 25 si všimneme, že poradie výberu je dôležité, takže počet prezídií sa bude rovnať:

komentár: Počet umiestnení bez opakovaní možno zistiť aj pomocou vzorca:

. (3)

Ak menovateľ zlomku zo vzorca (3)
, potom je to všeobecne akceptované
.

komentár: Vzorec (3) je kompaktný, ale pri riešení úloh je vhodnejšie použiť vzorec (2). Zlomok na pravej strane vzorca (3) možno zredukovať na celé číslo. Toto číslo sa rovná číslu na pravej strane vzorca (2).

Príklad 4: Koľko dvojpísmenových slov (písmená sa neopakujú) možno vytvoriť z 33 písmen ruskej abecedy?

Riešenie. V tomto prípade nejde o slová v lingvistickom zmysle, ale o kombinácie písmen ľubovoľného zloženia.

Potom sa počet rôznych kombinácií 2 písmen vybraných z 33 písmen abecedy bude rovnať:

.

V tomto prípade je dôležité poradie písmen. Ak zmeníte 2 písmená v slove, dostanete nové slovo.

komentár: Permutácia bez opakovaní je špeciálny prípad umiestnení bez opakovaní, keď
. Môžeme povedať, že permutácia z prvkov je umiestnenie prvky podľa prvky:

V niektorých úlohách kombinatoriky nezáleží na poradí, v ktorom sú objekty usporiadané v konkrétnej množine. Dôležité je len to, ktoré prvky ho tvoria. V takýchto situáciách sa stretávame kombinácie.

Kombinácie bez opakovania.

Definícia 9: Kombinácie žiadne opakovania od prvky nejakej množiny podľa prvky (
) sú usporiadania, ktoré sa navzájom líšia zloženie, Ale nie v poriadku prvkov. Určenie: (z francúzskeho slova kombinácia- kombinácia).

V tomto prípade v aranžmánoch dôležité je zloženie, nie poradie prvkov v podmnožine. Ak sa dve usporiadania líšia iba poradím prvkov, tak z hľadiska kombinácií nie sú rozlíšiteľné. Prvky v týchto usporiadaniach sa neopakujú.

Z pohľadu teórie množín možno definíciu kombinácií formulovať rôzne.

Definícia 10: Konečné neusporiadané množiny sa nazývajú kombinácie.

Kombinácie sú teda výberom prvkov, v ktorých je ich poradie úplne nepodstatné.

Kombinácie prvky podľa prvkov by malo byť menej ako zodpovedajúcich umiestnení. Vyplýva to z toho, že nie je potrebné počítať útvary rovnakého zloženia.

Veta 4: Počet kombinácií sa nachádza podľa nasledujúceho vzorca:

. (4)

Dôkaz. Ak z ľubovoľného -vybratá súprava prvkov prvky, potom môžu byť očíslované
v mnohých smeroch rovnaké . Zostávajúce
prvky je možné očíslovať
,
, …,Celkom
spôsoby. Navyše samotný výber prvky z prvky môžu byť implementované spôsoby. Tak sme dostali
možnosti číslovania pre celú sadu prvkov, ktorých je len . Preto máme
, odkiaľ dostaneme:

.

Veta bola dokázaná.

komentár: Zlomok na pravej strane (4) možno zmenšiť na celé číslo.

Zo vzorca pre počet kombinácií vyplýva:

,
,
.

Vzorec (4) môže byť transformovaný do tvaru:
. To ukazuje, že počet umiestnení V krát počet zodpovedajúcich kombinácií . Inými slovami, spočítať všetky kombinácie , musia byť vylúčené zo všetkých umiestnení podmnožiny, ktoré sa líšia v poradí (budú kusov), t.j. deleno .

Príklad 5: Koľkými spôsobmi si môžete vybrať 3 rôzne farby z piatich dostupných?

Riešenie. Poradie výberu farieb nie je dôležité. Dôležité je len to, aké farby sú zvolené. Preto sa počet možností rovná:
.

Príklad 6: Koľkými spôsobmi je možné ušiť trojfarebné pruhované vlajky, ak je materiál v piatich rôznych farbách?

Riešenie. Poradie, v ktorom sú pruhy vybrané, je dôležité, takže počet takýchto príznakov sa rovná:
.

V mnohých kombinatorických problémoch sa priame nájdenie množstva možností, ktoré nás zaujímajú, ukazuje ako ťažké. S určitou zmenou v podmienkach problému však môžete nájsť množstvo možností, ktoré presahujú pôvodný počet známym počtom krát. Táto technika sa nazýva metóda viacnásobného počítania.

1. Koľko anagramov má slovo TRIEDA?

Ťažkosť je v tom, že v tomto slove sú dve rovnaké písmená C. Budeme ich dočasne považovať za odlišné a označíme ich C 1 a C 2. Potom sa počet anagramov bude rovnať 5! = 120. Ale tie slová, ktoré sa od seba líšia iba preskupením písmen C 1 a C 2, sú v skutočnosti rovnaké anagramy! Preto je 120 anagramov rozdelených do dvojíc rovnakých, t.j. požadovaný počet anagramov je 120/2 = 60.

2. Koľko anagramov má slovo CHARADA?

Počítaním troch písmen A ako rôznych písmen A 1, A 2, A 3 dostaneme 6! anagramy Ale slová, ktoré sú vyrobené jeden z druhého iba preskupením písmen A 1, A 2, A 3, sú vlastne jedna a tá istá anagram. Pretože sú 3! permutácií písmen A 1, A 2, A 3, pôvodne získaných 6! Anagramy sú rozdelené do skupín po 3! identické a počet rôznych anagramov je 6!/3! = 120.

3. Koľko je štvorciferných čísel, ktoré obsahujú aspoň jednu párnu číslicu?

Nájdite počet „zbytočných“ štvorciferných čísel, ktorých záznam obsahuje iba nepárne číslice. Takýchto čísel je 5 4 = 625, ale celkovo je 9000 štvorciferných čísel, takže požadovaný počet „potrebných“ čísel je 9000 – 625 = 8375.

1. Nájdite počet anagramov pre slová VERESK, BALAGAN, CITYMAN.
2. Nájdite počet anagramov pre slová BAOBAB, BALADA, TURN, ANAGRAM, MATEMATIKA, KOMBINATORIKA, OBRANA.
3. Koľkými spôsobmi môžete ubytovať 7 návštevníkov v troch hotelových izbách: jednolôžkovej, dvojlôžkovej a štvorlôžkovej?
4. V chladničke sú dve jablká, tri hrušky a štyri pomaranče. Každý deň počas deviatich dní za sebou dostane Petya jeden kus ovocia. Koľkými spôsobmi sa to dá urobiť?
5. Zo siedmich najlepších lyžiarov školy musí byť vybraný trojčlenný tím, ktorý sa zúčastní mestských súťaží. Koľkými spôsobmi sa to dá urobiť?
6. Profesor pred skúškou sľúbil, že polovici skúšaných dá zlé známky. Na skúšku prišlo 20 študentov. Koľkými spôsobmi môže splniť svoj sľub?
7. Koľko slov sa dá poskladať z piatich písmen A a najviac z troch písmen B?
8. K dispozícii je čokoládová, jahodová a mliečna zmrzlina. Koľkými spôsobmi si môžete kúpiť tri zmrzliny?
9. Pri príprave pizze sa do syra pridávajú rôzne zložky, aby sa získala osobitná chuť. Bill má k dispozícii cibuľu, šampiňóny, paradajky, papriku a ančovičky, to všetko sa podľa neho dá pridať do syra. Koľko druhov pizze môže Bill urobiť?
10. Svedok trestného stíhania si spomenul, že zločinci utiekli v Mercedese, ktorého poznávacia značka obsahovala písmená T, Z, U a číslice 3 a 7 (číslo je riadok, ktorý obsahuje najskôr tri písmená a potom tri čísla) . Koľko je takýchto čísel?
11. Koľko uhlopriečok je v konvexe n-námestie?
12. Koľko vecí je tam? n-digitálne čísla?
13. Koľko desaťciferných čísel má aspoň dve rovnaké číslice?
14. Kocka sa hádže trikrát. Medzi všetkými možnými postupnosťami výsledkov sú tie, v ktorých je aspoň raz hodená šestka. Koľkí tam sú?
15. Koľko päťciferných čísel má vo svojom zápise číslicu 1?
16. Koľkými spôsobmi možno umiestniť bieleho a čierneho kráľa na šachovnicu bez toho, aby sa navzájom udreli?
17. Koľko deliteľov má číslo 10800?

Abstrakt na tému:

Absolvoval žiak 10. ročníka „B“

stredná škola č.53

Glukhov Michail Alexandrovič

Naberezhnye Chelny

2002
Obsah

Z histórie kombinatoriky________________________________________________	3
Pravidlo súčtu__________________________________________________________	4
	-
Produktové pravidlo______________________________________________	4
Príklady úloh___________________________________________________________	-
Pretínajúce sa množiny________________________________________________	5
Príklady úloh___________________________________________________________	-
Eulerove kruhy_______________________________________________________________	-
Umiestnenia bez opakovania_______________________________________________	6
Príklady úloh___________________________________________________________	-
Permutácie bez opakovaní_________________________________________________	7
Príklady úloh___________________________________________________________	-
Kombinácie bez opakovaní________________________________________________	8
Príklady úloh___________________________________________________________	-
Umiestnenia a kombinácie bez opakovania_______________________________	9
Príklady úloh___________________________________________________________	-
Permutácie s opakovaniami________________________________________________	9
Príklady úloh___________________________________________________________	-
Problémy na nezávislé riešenie_________________________________	10
Bibliografia___________________________________	11

Z histórie kombinatoriky

Kombinatorika sa zaoberá rôznymi typmi spojení, ktoré možno vytvoriť z prvkov konečnej množiny. Niektoré prvky kombinatoriky boli v Indii známe už v 2. storočí. BC e. Nydčania vedeli, ako vypočítať čísla, ktoré sa teraz nazývajú „kombinácie“. V 12. storočí. Bhaskara vypočítal niektoré typy kombinácií a permutácií. Predpokladá sa, že indickí vedci skúmali zlúčeniny v súvislosti s ich použitím v poetike, štúdiu štruktúry veršov a poetických diel. Napríklad v súvislosti s výpočtom možných kombinácií prízvučných (dlhých) a neprízvučných (krátkych) slabík nohy z n slabík. Ako vedná disciplína sa kombinatorika sformovala v 17. storočí. V knihe „Teória a prax aritmetiky“ (1656) francúzsky autor A. tiež venuje celú kapitolu kombináciám a permutáciám.
B. Pascal vo svojom „Pojednaní o aritmetickom trojuholníku“ a „Pojednaní o číselných usporiadaniach“ (1665) načrtol doktrínu binomických koeficientov. P. Fermat vedel o súvislostiach medzi matematickými štvorcami a figurovanými číslami s teóriou zlúčenín. Termín „kombinatorika“ sa začal používať po tom, čo Leibniz v roku 1665 publikoval svoju prácu „Discourse on the Art of Combination“, ktorá po prvýkrát poskytla vedecký základ pre teóriu kombinácií a permutácií. J. Bernoulli prvýkrát študoval umiestnenia v druhej časti svojej knihy „Ars conjectandi“ (umenie predpovede) v roku 1713. Modernú symboliku kombinácií navrhli rôzni autori vzdelávacích príručiek až v 19. storočí.

Celú škálu kombinatorických vzorcov možno odvodiť z dvoch základných tvrdení týkajúcich sa konečných množín – súčtového pravidla a súčinového pravidla.

Pravidlo súčtu

Ak sa konečné množiny nepretínajú, potom sa počet prvkov množiny X U Y (alebo) rovná súčtu počtu prvkov množiny X a počtu prvkov množiny Y.

To znamená, že ak je na prvej poličke X kníh a na druhej Y, potom môžete vybrať knihu z prvej alebo druhej police X+Y spôsobmi.

Príklady problémov

Študent musí absolvovať praktickú prácu z matematiky. Dostal na výber zo 17 tém z algebry a 13 tém z geometrie. Koľkými spôsobmi si môže vybrať jednu tému na praktickú prácu?

Riešenie: X=17, Y=13

Podľa súčtového pravidla X U Y=17+13=30 tém.

Do hotovostnej lotérie je 5 tiketov, do športovej 6 tiketov a do automobilovej 10 tiketov. Koľkými spôsobmi si môžete vybrať jeden tiket zo športovej lotérie alebo autolotérie?

Riešenie: Keďže pri výbere nie je zahrnutá hotovostná a odevná lotéria, existuje len 6 + 10 = 16 možností.

Produktové pravidlo

Ak prvok X možno vybrať k spôsobmi a prvok Y m spôsobmi, potom pár (X,Y) možno vybrať k*m spôsobmi.

To znamená, že ak je na prvej poličke 5 kníh a na druhej 10, potom si môžete vybrať jednu knihu z prvej police a jednu z druhej na 5 * 10 = 50 spôsobov.

Príklady problémov

Kníhviazač musí zviazať 12 rôznych kníh v červenej, zelenej a hnedej väzbe. Koľkými spôsobmi to môže urobiť?

Riešenie: K dispozícii je 12 kníh a 3 farby, čo znamená, že podľa produktového pravidla je možných 12 * 3 = 36 možností väzby.

Koľko je päťciferných čísel, ktoré sa čítajú rovnako zľava doprava a sprava doľava?

Riešenie: V takýchto číslach bude posledná číslica rovnaká ako prvá a predposledná číslica bude rovnaká ako druhá. Tretia číslica bude čokoľvek. To môže byť znázornené vo forme XYZYX, kde Y a Z sú ľubovoľné čísla a X nie je nula. To znamená, že podľa pravidla súčinu je počet číslic, ktoré je možné čítať rovnako zľava doprava aj sprava doľava, 9*10*10=900 možností.

Pretínajúce sa množiny

Ale stane sa, že sa množiny X a Y pretnú, potom použijú vzorec

, kde X a Y sú množiny a je to oblasť priesečníka. Príklady problémov

20 ľudí vie po anglicky a 10 po nemecky, z toho 5 vie po anglicky aj po nemecky. Koľko ľudí je tam celkovo?

Odpoveď: 10+20-5=25 ľudí.

Eulerove kruhy sa tiež často používajú na vizuálne riešenie problému. Napríklad:

Zo 100 turistov, ktorí idú na zahraničný výlet, 30 ľudí hovorí po nemecky, 28 - anglicky, 42 - francúzsky 8 ľudí súčasne anglicky a nemecky, 10 - anglicky a francúzsky, 5 - nemecky a francúzsky, 3 - všetci traja. jazyky nehovoria žiadnym jazykom?

Riešenie: Vyjadrime stav tohto problému graficky. Označme kruhom tých, ktorí vedia po anglicky, ďalší kruh tých, ktorí vedia po francúzsky, a tretím kruh tých, ktorí vedia nemecky.

Traja turisti hovoria všetkými troma jazykmi, to znamená, že vo všeobecnej časti krúžkov uvádzame číslo 3. 10 ľudí hovorí po anglicky a francúzsky a 3 z nich aj po nemecky. V dôsledku toho 10-3 = 7 ľudí hovorí len anglicky a francúzsky.

Podobne zistíme, že 8-3 = 5 ľudí hovorí len anglicky a nemecky a 5-3 = 2 turisti hovoria nemecky a francúzsky. Tieto údaje zapisujeme do príslušných častí.

Poďme teraz určiť, koľko ľudí hovorí iba jedným z uvedených jazykov. 30 ľudí vie po nemecky, ale 5+3+2=10 z nich hovorí inými jazykmi, preto len 20 ľudí vie po nemecky. Podobne zistíme, že 13 ľudí hovorí len po anglicky a 30 ľudí hovorí len po francúzsky.

Podľa problému je tam len 100 turistov. 20+13+30+5+7+2+3=80 turistov ovláda aspoň jeden jazyk, teda 20 ľudí nehovorí žiadnym z týchto jazykov.

Umiestnenia bez opakovania.

Koľko telefónnych čísel možno vytvoriť zo 6 číslic, aby sa všetky číslice líšili?

Toto je príklad problému s umiestnením bez opakovania. Je tu umiestnených 10 čísel po 6 a možnosti, v ktorých sú rovnaké čísla v rôznom poradí, sa považujú za odlišné.

Ak množina X pozostávajúca z n prvkov, m≤n, potom usporiadanie bez opakovania n prvkov množiny X do m sa nazýva usporiadaná množina X obsahujúca m prvkov. Usporiadaná množina X obsahujúca m prvkov.

Počet všetkých usporiadaní n prvkov podľa m označujeme

n! - n-faktoriál (faktoriálny faktor) je súčin čísel v prirodzenom rade od 1 do ľubovoľného čísla n Úloha

Koľkými spôsobmi môžu 4 chlapci požiadať štyri zo šiestich dievčat, aby tancovali?

Riešenie: dvaja chlapci nemôžu pozvať to isté dievča súčasne. A možnosti, v ktorých tie isté dievčatá tancujú s rôznymi chlapcami, sa považujú za odlišné, preto:

360 možností.

Permutácie bez opakovania

V prípade n=m (pozri umiestnenia bez opakovania) n prvkov m sa nazýva permutácia množiny x.

Počet všetkých permutácií n prvkov označujeme P n.

Platí pre n=m:

Príklady problémov

Koľko rôznych šesťciferných čísel možno vytvoriť z číslic 0, 1, 2, 3, 4,5, ak sa číslice v čísle neopakujú?

1) Nájdite počet všetkých permutácií z týchto čísel: P 6 =6!=720

2) 0 nemôže byť pred číslom, takže počet permutácií, v ktorých je 0 pred číslom, sa musí od tohto čísla odpočítať. A toto je P 5 = 5! = 120.

P6-P5=720-120=600

Nezbedná opica

Áno, paličkovitá Mishka

Začali sme hrať kvarteto

Prestaňte, bratia, prestaňte! –

Opica kričí, - počkaj!

Ako by mala prebiehať hudba?

Koniec koncov, nesedíte tak...

A takto a že si vymenili miesta - zase hudba nejde dobre.