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. Prosím pomozte zlepšit tento článek představuji přesnější 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	${ displaystyle V_ {n, k}}$	${ displaystyle VR_ {n, k}}$
Není objednáno vzorek	${ displaystyle C_ {n, k}}$	${ displaystyle CR_ {n, k}}$

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 ${ displaystyle k = 2}$ a ${ displaystyle n = 50}$. 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:

${ displaystyle C_ {50,2} = { frac {50!} {2! cdot (50-2)!}} = 1225}$

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 ${ displaystyle k = 4}$ a ${ displaystyle n = 10}$. Čí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:

${ displaystyle V_ {10,4} = { frac {10!} {(10-4)!}} = 5040}$

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 ${ displaystyle k = 20}$ a ${ displaystyle n = 3}$. 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ů (${ displaystyle k = 20}$) ze sady 3 prvků (${ displaystyle n = 3}$), 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:

${ displaystyle CR_ {3,20} = C_ {22,20} = { frac {22!} {20! cdot (22-20)!}} = 231}$

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 (${ displaystyle k leq n}$)
  2. Distribuce surjektiv: každá krabice musí mít alespoň 1 objekt (${ displaystyle k geq n}$)
  3. Bijective distribution: every box must exactly 1 object (${ displaystyle k = n}$)
  4. 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í:

Distribuce k předměty do n krabice

	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í	${ displaystyle VR_ {n, k}}$	${ displaystyle sum _ {i = 1} ^ {n} S (k, i)}$	${ displaystyle CR_ {n, k}}$	${ displaystyle sum _ {i = 1} ^ {n} P (k, i)}$	${ displaystyle k! cdot CR_ {n, k}}$	${ displaystyle sum _ {i = 1} ^ {n} L (k, i)}$
Injekční rozdělení	${ displaystyle V_ {n, k}}$	${ displaystyle 1}$	${ displaystyle C_ {n, k}}$	${ displaystyle 1}$	${ displaystyle V_ {n, k}}$	${ displaystyle 1}$
Surjective rozdělení	${ displaystyle n! cdot S (k, n)}$	${ displaystyle S (k, n)}$	${ displaystyle CR_ {n, k-n}}$	${ displaystyle P (k, n)}$	${ displaystyle k! cdot CR_ {n, k-n}}$	${ displaystyle L (k, n) = { frac {k!} {n!}} cdot {k-1 zvolit n-1}}$
Bijective rozdělení	${ displaystyle n!}$	${ displaystyle 1}$	${ displaystyle 1}$	${ displaystyle 1}$	${ displaystyle n!}$	${ displaystyle 1}$

${ displaystyle S (k, n) = vlevo {{k nahoře n} vpravo }:}$ Stirlingova čísla druhého druhu

${ displaystyle P (k, n):}$ Počet oddílů celého čísla k do n části

${ displaystyle L (k, n):}$ 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ů (${ displaystyle k = 3}$) do 7 rozlišitelných polí (${ displaystyle n = 7}$). To je vše, co potřebujeme vědět, abychom vybrali správnou operaci, a výsledek je:

${ displaystyle C_ {7,3} = { frac {7!} {3! cdot (7-3)!}} = 35}$

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ů (${ displaystyle k = 8}$) do 5 nerozeznatelných krabic (${ displaystyle n = 5}$). To je vše, co potřebujeme vědět, abychom vybrali správnou operaci, a výsledek je:

${ displaystyle S (8,5) = vlevo {{8 na vrcholu 5} vpravo } = { frac {1} {5!}} součet _ {i = 0} ^ {5} (- 1) ^ {i} { binom {5} {i}} (5-i) ^ {8} = 1050}$

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ů (${ displaystyle k = 12}$) do 4 rozlišitelných polí (${ displaystyle n = 4}$). To je vše, co potřebujeme vědět, abychom vybrali správnou operaci, a výsledek je:

${ displaystyle 12! cdot CR_ {4,12} = 12! cdot C_ {15,12} = 12! cdot { frac {15!} {12! cdot (15-12)!}} = 217945728000}$

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:

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é 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	${ displaystyle VR_ {n, k}}$	${ displaystyle sum _ {i = 1} ^ {n} S (k, i)}$	${ displaystyle CR_ {n, k}}$	${ displaystyle sum _ {i = 1} ^ {n} P (k, i)}$	${ displaystyle k! cdot CR_ {n, k}}$	${ displaystyle sum _ {i = 1} ^ {n} L (k, i)}$
Prázdné podmnožiny nebo podmnožiny s 1 prvkem	${ displaystyle V_ {n, k}}$	${ displaystyle 1}$	${ displaystyle C_ {n, k}}$	${ displaystyle 1}$	${ displaystyle V_ {n, k}}$	${ displaystyle 1}$
Žádné prázdné podmnožiny	${ displaystyle n! cdot S (k, n)}$	${ displaystyle S (k, n)}$	${ displaystyle CR_ {n, k-n}}$	${ displaystyle P (k, n)}$	${ displaystyle k! cdot CR_ {n, k-n}}$	${ displaystyle L (k, n) = { frac {k!} {n!}} cdot CR_ {n, k-n}}$
Podmnožiny 1 prvku	${ displaystyle n!}$	${ displaystyle 1}$	${ displaystyle 1}$	${ displaystyle 1}$	${ displaystyle n!}$	${ displaystyle 1}$

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ů (${ displaystyle k = 8}$) do 3 objednaných podmnožin (${ displaystyle n = 3}$) neobjednaných prvků. To je vše, co potřebujeme vědět, abychom vybrali správnou operaci, a výsledek je:

${ displaystyle VR_ {3,8} = 3 ^ {8} = 6561}$

Viz také

• Dvanáctkrát

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.