Kombinatorické modelování - Combinatorial modelling - Wikipedia

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:
    1. Injekční distribuce: každá krabice musí mít maximálně 1 objekt ()
    2. Distribuce surjektiv: každá krabice musí mít alespoň 1 objekt ()
    3. Bijective distribution: every box must exactly 1 object ()
    4. 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í:

Distribuce k předměty do n krabice
Neregistrovaná distribuceObjednaná distribuce
Rozlišitelné objektyNerozeznatelné předmětyRozlišitelné objekty
Rozlišitelné krabiceK nerozeznáníRozlišitelné krabiceK nerozeznáníRozlišitelné krabiceK nerozeznání
Žádný

rozdělení

Injekční

rozdělení

Surjective

rozdělení

Bijective

rozdělení

Stirlingova čísla druhého druhu
Počet oddílů celého čísla k do n části
Lah čísla (Stirlingova čísla třetího druhu)

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ánoPodmnožiny neobjednaných prvků
Rozlišitelné objektyRozlišitelné prvky
Nerozeznatelné předmětyNerozlišitelné prvky
Rozlišitelné krabiceObjednané oddíly
K nerozeznáníNeobjednané oddíly
Injekční distribucePodmnožiny 1 prvku nebo prázdné
Surjective distribuceŽádné prázdné podmnožiny
Bijektivní distribucePodmnož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:

Rozdělení sady k prvky do n podmnožiny
Neobjednané prvky,
Rozlišitelné prvkyNerozlišitelné prvkyRozlišitelné prvky
Objednané podmnožinyNeobjednané podmnožinyObjednané podmnožinyNeobjednané podmnožinyObjednané podmnožinyNeobjednané 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