Ubytování

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 17. dubna 2022; ověření vyžaduje 1 úpravu .

V kombinatorice je alokace (od n do k ) uspořádaná množina k různých prvků z nějaké množiny různých n prvků .

Příklad 1: je alokace 4 prvků ze sady 6 prvků . $\langle 1,3,2,5\rangle$ $\{1,2,3,4,5,6\}$

Příklad 2: některá uspořádání prvků množiny o 2: … … … $\{1,2,3,4,5,6\}$ $\langle 1,2\rangle$ $\úhel 1,3\úhel$ $\langle 1,4\rangle$ $\langle 1,5\rangle$ $\langle 2,1\rangle$ $\úhel 2,3\úhelník$ $\úhel 2,4\úhelník$ $\úhel 2,6\úhelník$

Na rozdíl od kombinací berou umístění v úvahu pořadí položek. Takže například množiny a jsou různá uspořádání, ačkoli se skládají ze stejných prvků (to znamená, že se shodují jako kombinace). $\langle 2, 1, 3$ $\langle 3, 2, 1$ $\{1, 2, 3\}$

Vyplnit řádek znamená umístit nějaký objekt z dané množiny na nějaké místo tohoto řádku (navíc každý objekt lze použít pouze jednou). Řádek vyplněný objekty dané množiny se nazývá umístění, tj. na tato místa jsme umístili objekty. [jeden]

Počet umístění

Počet umístění od n do k , označený , se rovná klesajícímu faktoriálu : $A_{n}^{k}$

A_{n}^{k}=n^{\podtržítko {k))=(n)_{k}=n(n-1)\cdot \ldots \cdot (n-k+1)= {\frac {n!}{(nk)!}}

Vyjádřeno elementárním způsobem prostřednictvím symbolu Pochhammer :

{\displaystyle A_{n}^{k}=(n-k+1)_{k))

Poslední výraz má přirozenou kombinatorickou interpretaci: každé umístění od n do k jednoznačně odpovídá nějaké kombinaci n až k a nějaké permutaci prvků této kombinace; počet kombinací od n do k se rovná binomickému koeficientu , přičemž na k prvcích je přesně k permutací ! věci. $\tbinom{n}{k}$

Pro k = n je počet umístění roven počtu permutací řádu n : [2] [3] [4]

A_{n}^{n}=P_{n}=n!

Následující tvrzení je pravdivé: . Důkaz je triviální: ${\displaystyle A_{n}^{n-1}=A_{n}^{n))$

A_{n}^{n-1}={\frac {n!}{(n-(n-1))!}}={\frac {n!}{(n-n+1) !}}=n!=A_{n}^{n}

Umístění s opakováním

Opakované vnořování nebo zpětné načítání [5] je vnořování „položky“ za předpokladu, že každá „položka“ se může vnořování zúčastnit vícekrát.

Počet umístění s opakováním

Podle pravidla násobení je počet umístění s opakováním od n do k , označený jako: [6] [2] [5] $\bar{A}_n^k$

{\bar {A}}_{n}^{k}=n^{k}

Například počet možností pro 3místný kód, ve kterém je každý znak číslicí od 0 do 9 a může se opakovat, je:

{\bar {A}}_{10}^{3}=10^{3}=1000

Jiný příklad: umístění s opakováním 4 prvků a , b , c , d x 2 je 4 2 = 16, tato umístění jsou následující:

aa , ab , ac , ad , ba , bb , bc , bd , ca , cb , cc , cd , da , db , dc , dd .

Viz také

Odkazy

↑ ISBN 978-5-406-05433-8 Učebnice matematiky pro SPO vydal Bašmakov M.I. Archivováno 9. prosince 2019 na Wayback Machine
↑ 1 2 Vilenkin N. Ya . Kapitola III. Kombinatorika n-tic a množin. Alokace s opakováním // Populární kombinatorika . - M. : Nauka, 1975. - S. 80. - 208 s.
↑ Teorie konfigurace a teorie výčtu . Datum přístupu: 30. prosince 2009. Archivováno z originálu 23. ledna 2010. (neurčitý)
↑ Kapitola 3. Elements of Combinatorics Archivováno 4. ledna 2010 na Wayback Machine . // Přednášky z teorie pravděpodobnosti.
↑ 1 2 Korn G., Korn T. Tab. 18.7-2(2.b), 18.7-3(2.b) // Příručka matematiky pro vědce a inženýry . - M. : Nauka, 1973. - S. 568. - 832 s.
↑ Kombinatorická analýza // Matematická encyklopedie / Ed. I. M. Vinogradová. - M. , 1977. - T. 2. - S. 974. - (Sov. Encyklopedie).