Kombinatorické modelování - Combinatorial modelling - Wikipedia
![]() | Tento článek obsahuje seznam obecných Reference, ale zůstává z velké části neověřený, protože postrádá dostatečné odpovídající vložené citace.Červen 2019) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) ( |
Kombinatorické modelování je proces, který nám umožňuje identifikovat vhodný matematický model pro přeformulování problému. Tyto kombinatorické modely budou prostřednictvím kombinatorika teorie, operace potřebné k vyřešení problému.
Implicitní kombinatorické modely
Jednoduché kombinatorické problémy jsou ty, které lze vyřešit použitím pouze jedné kombinatorické operace (variace, permutace, kombinace, ...). Tyto problémy lze rozdělit do tří různých modelů, které se nazývají implicitní kombinatorické modely.
Výběr
Problém s výběrem vyžaduje vybrat vzorek k prvků ze sady n elementy. Je třeba vědět, zda záleží na pořadí, ve kterém jsou objekty vybrány, a zda lze objekt vybrat vícekrát nebo ne. Tato tabulka ukazuje operace, které model poskytuje, aby získal počet různých vzorků pro každý z výběrů:
Opakování nepovoleno | Opakování povoleno | |
---|---|---|
Objednané vzorek | ||
Není objednáno vzorek |
Příklady
1.- Na večírku je 50 lidí. Každý jednou potřese každému ruku. Jak často se celkem potřásají rukama?Musíme vypočítat počet všech možných párů hostů večírku, což znamená vzorek 2 lidí z 50 hostů, takže a . Dvojice bude stejná bez ohledu na pořadí těchto dvou lidí. Potřesení rukou musí být provedeno dvěma různými lidmi (bez opakování). Je tedy nutné vybrat uspořádaný vzorek 2 prvků ze sady 50 prvků, ve kterých není dovoleno opakování. To je vše, co potřebujeme vědět, abychom vybrali správnou operaci, a výsledek je:
2.- Bohužel si nepamatujete kód svého čtyřmístného zámku. Pouze víte, že jste žádnou číslici nepoužili vícekrát. Kolik různých způsobů musíte vyzkoušet?Musíme vybrat vzorek 4 číslic ze sady 10 číslic (základ 10), takže a . Číslice je nutné určit určitým způsobem, abychom získali správné číslo, proto chceme vybrat objednaný vzorek. Jak říká prohlášení, žádná číslice nebyla vybrána vícekrát, takže náš vzorek nebude mít opakované číslice. Je tedy nutné vybrat uspořádaný vzorek 4 prvků ze sady 10 prvků, ve kterých není opakování povoleno. To je vše, co potřebujeme vědět, abychom vybrali správnou operaci, a výsledek je:
3.- Chlapec chce koupit 20 pozvánek, které dá svým přátelům na oslavu narozenin. V obchodě jsou 3 typy karet a všechny se mu líbí. Kolik způsobů si může koupit 20 karet? Ze sady 3 typů karet je nutné vybrat vzorek 20 pozvánek a . Na pořadí, ve kterém si vyberete různé typy pozvánek, nezáleží. Vzhledem k tomu, že typ karty musí být vybrán vícekrát, budou se naše pozvánky opakovat. Takže chceme vybrat neobjednaný vzorek 20 prvků () ze sady 3 prvků (), ve kterém je povoleno opakování. To je vše, co potřebujeme vědět, abychom vybrali správnou operaci, a výsledek je:
Rozdělení
V problému s distribucí je nutné umístit k předměty do n pole nebo příjemci. Aby bylo možné vybrat správnou operaci z těch, které model poskytuje, je nutné znát:
- Zda jsou objekty rozlišitelné nebo ne.
- Zda jsou krabice rozlišitelné nebo ne.
- Pokud záleží na pořadí, ve kterém jsou objekty umístěny do rámečku.
- Podmínky, které musí distribuce splňovat. V závislosti na tom může být distribuce:
- Injekční distribuce: každá krabice musí mít maximálně 1 objekt ()
- Distribuce surjektiv: každá krabice musí mít alespoň 1 objekt ()
- Bijective distribution: every box must exactly 1 object ()
- Distribuce bez omezení
Injekční distribuce
Suraktivní distribuce
Bijektivní distribuce
Distribuce bez omezení
V následující tabulce jsou uvedeny operace, které model poskytuje k získání počtu různých způsobů distribuce objektů pro každou z distribucí:
Neregistrovaná distribuce | Objednaná distribuce | |||||
---|---|---|---|---|---|---|
Rozlišitelné objekty | Nerozeznatelné předměty | Rozlišitelné objekty | ||||
Rozlišitelné krabice | K nerozeznání | Rozlišitelné krabice | K nerozeznání | Rozlišitelné krabice | K nerozeznání | |
Žádný rozdělení | ||||||
Injekční rozdělení | ||||||
Surjective rozdělení | ||||||
Bijective rozdělení |
- Počet oddílů celého čísla k do n části
Příklady
1.- Učitel matematiky musí udělit 3 studentství mezi svými studenty. Sedm z nich získalo „vynikající“ známku, takže jsou kandidáty na jejich získání. Kolik způsobů může rozdělit granty?Uvažujme, že 3 studentství jsou objekty, které je třeba rozdělit do 7 polí, což jsou studenti. Vzhledem k tomu, že tyto objekty jsou identické, jsou k nerozeznání. Krabice jsou rozlišitelné, protože se jedná o různé studenty. Každé stipendium musí být uděleno jinému studentovi, takže každé políčko musí mít maximálně 1 předmět. Kromě toho nezáleží na pořadí, ve kterém jsou objekty umístěny do rámečků, protože na každém rámečku nemůže být více než jeden. Jde tedy o neobjednané injektivní rozdělení 3 nerozlišitelných objektů () do 7 rozlišitelných polí (). To je vše, co potřebujeme vědět, abychom vybrali správnou operaci, a výsledek je:
2.- Skupina 8 přátel si pronajímá 5pokojovou chalupu, kde stráví dovolenou. Pokud jsou pokoje totožné a nikdo nemůže být prázdný, kolika způsoby je lze v chatě rozdělit?Uvažujme, že přátelé jsou objekty, které je třeba rozdělit do 5 polí, což jsou místnosti. Protože objekty jsou různí lidé, lze je rozlišit. Krabice jsou k nerozeznání, protože se jedná o identické místnosti. Můžeme to považovat za neobjednanou distribuci, protože na pořadí, ve kterém jsou všichni umístěni v místnostech, nezáleží. Žádná místnost nemůže být prázdná, takže každá krabice musí mít alespoň 1 objekt. Jedná se o neobjednané surjektivní rozdělení 8 rozlišitelných objektů () do 5 nerozeznatelných krabic (). To je vše, co potřebujeme vědět, abychom vybrali správnou operaci, a výsledek je:
3.- 12 lidí nakupuje v supermarketu, kde v současné době pracují 4 pokladníci. Kolik různých způsobů je možné je rozdělit do pokladen?Uvažujme, že lidé jsou objekty, které je třeba rozdělit do krabic, což jsou pokladny. Jelikož se lidé a pokladny liší, objekty a pole jsou rozlišitelné. Na pořadí, ve kterém jsou objekty umístěny do polí, záleží, protože jde o lidi, kteří se dostávají do front. Prohlášení nezmiňuje žádné omezení. Jedná se o uspořádanou distribuci bez omezení 12 rozlišitelných objektů () do 4 rozlišitelných polí (). To je vše, co potřebujeme vědět, abychom vybrali správnou operaci, a výsledek je:
Rozdělit
Problém s oddílem vyžaduje rozdělení sady k prvky do n podmnožiny. Tento model souvisí s distribučním, protože objekty uvnitř každého pole můžeme považovat za podmnožiny sady objektů k distribuci. Každá z výše popsaných 24 distribucí má tedy odpovídající druh oddílu do podmnožin. Problém oddílu lze tedy vyřešit jeho transformací na distribuční a použitím odpovídající operace poskytované distribučním modelem (předchozí tabulka). Podle této metody získáme počet možných způsobů rozdělení sady. Vztah mezi těmito dvěma modely je popsán v následující tabulce:
Rozdělení | Rozdělit |
---|---|
Objednané | Podmnožiny seřazených prvků |
Není objednáno | Podmnožiny neobjednaných prvků |
Rozlišitelné objekty | Rozlišitelné prvky |
Nerozeznatelné předměty | Nerozlišitelné prvky |
Rozlišitelné krabice | Objednané oddíly |
K nerozeznání | Neobjednané oddíly |
Injekční distribuce | Podmnožiny 1 prvku nebo prázdné |
Surjective distribuce | Žádné prázdné podmnožiny |
Bijektivní distribuce | Podmnožiny přesně 1 prvku |
Bez omezení | Podmnožiny 1 nebo více prvků nebo prázdné |
Tento vztah nám umožní transformovat tabulku poskytnutou distribučním modelem na novou, kterou lze použít k poznání různých způsobů rozdělení sady k prvky do n podmnožiny:
Neobjednané prvky | , | |||||
---|---|---|---|---|---|---|
Rozlišitelné prvky | Nerozlišitelné prvky | Rozlišitelné prvky | ||||
Objednané podmnožiny | Neobjednané podmnožiny | Objednané podmnožiny | Neobjednané podmnožiny | Objednané podmnožiny | Neobjednané podmnožiny | |
Jakékoli podmnožiny | ||||||
Prázdné podmnožiny nebo podmnožiny s 1 prvkem | ||||||
Žádné prázdné podmnožiny | ||||||
Podmnožiny 1 prvku |
Příklady
1.- Skupina 3 spolužáků musí vypracovat diplomovou práci o 8 různých matematických tématech. Kolik způsobů mohou rozdělit práci?Soubor 8 témat musíme rozdělit do 3 podmnožin. Tyto podmnožiny budou tématy, na kterých bude každý ze studentů pracovat. Prvky v sadě (témata) jsou rozlišitelné. Tyto oddíly musí být objednány, protože každý bude odpovídat jinému studentovi, ale témata uvnitř každé podmnožiny se nemusí objednávat, protože každý student se může při práci na diplomové práci rozhodnout, jaké pořadí bude následovat. Prohlášení nezmiňuje žádné omezení podmnožin. Je tedy nutné rozdělit sadu 8 prvků () do 3 objednaných podmnožin () neobjednaných prvků. To je vše, co potřebujeme vědět, abychom vybrali správnou operaci, a výsledek je:
Viz také
Zdroje
- Dubois, Jean-Guy. Unikátní systémová konfigurace jednoduchých kombinací. Pedagogická studia z matematiky 15, 37–57 (1984) doi: 10,1007 / BF00380438
- V. Navarro-Pelayo; Carmen Batanero; Juan D. Godino (1996). Razonamiento Combinatorio en Alumnos de Secundaria.
- Rafael Roa (2000). Razonamiento Combinatorio en Estudiantes con Preparación Matemática Avanzada.
- Tan Mingshu (2011). Některé kombinatorické identity a vysvětlení podle modelu obsazenosti.