Szállás

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2022. április 17-én felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .

A kombinatorikában az allokáció ( n -től k -ig ) k különböző elemből álló rendezett halmaz , amely különböző n elemű halmazokból áll.

1. példa: egy 4 elemű kiosztás egy 6 elemű halmazból . $\langle 1,3,2,5\rangle$ $\{1,2,3,4,5,6\}$

2. példa: egy halmaz elemeinek néhány elrendezése 2-vel: … … … $\{1,2,3,4,5,6\}$ $\langle 1,2\rangle$ $\angle 1,3\range$ $\langle 1,4\rangle$ $\langle 1,5\rangle$ $\langle 2,1\rangle$ $\szög 2,3\szög$ $\szög 2,4\szög$ $\angle 2,6\angle$

A kombinációkkal ellentétben az elhelyezések figyelembe veszik az elemek sorrendjét. Így például a halmazok és különböző elrendezések, bár ugyanazokból az elemekből állnak (vagyis kombinációként egybeesnek). $\langle 2, 1, 3$ $\langle 3, 2, 1$ $\{1, 2, 3\}$

A sor kitöltése azt jelenti, hogy az adott halmazból egy objektumot elhelyezünk ennek a sornak valamely helyére (sőt, minden objektum csak egyszer használható). Egy adott halmaz tárgyaival kitöltött sort elhelyezésnek nevezzük, vagyis ezekre a helyekre helyeztünk el tárgyakat. [egy]

Elhelyezések száma

Az n -től k -ig terjedő elhelyezések száma , amelyet jelöl , egyenlő a csökkenő faktoriálissal : $A_{n}^{k}$

A_{n}^{k}=n^{\aláhúzás {k))=(n)_{k}=n(n-1)\cdot \ldots \cdot (n-k+1)= {\frac {n!}{(nk)!}}

Alapvetően a Pochhammer szimbólumon keresztül kifejezve :

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

Az utolsó kifejezésnek természetes kombinatorikus értelmezése van: minden n-től k-ig tartó elhelyezés egyedileg megfelel n-től k-ig valamilyen kombinációnak és e kombináció elemeinek valamilyen permutációjának ; az n -től k -ig terjedő kombinációk száma megegyezik a binomiális együtthatóval , miközben pontosan k permutáció van k elemen ! dolgokat. $\tbinom{n}{k}$

Ha k = n , az elhelyezések száma megegyezik az n sorrendű permutációk számával : [2] [3] [4]

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

A következő állítás igaz: . A bizonyíték triviális: ${\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}

Elhelyezés ismétlésekkel

Az ismétlődő egymásba ágyazás vagy visszatérési lekérés [5] az "elemek" egymásba ágyazását jelenti, azzal a feltételezéssel, hogy minden "elem" többször is részt vehet a beágyazásban.

Elhelyezések száma ismétlődésekkel

A szorzási szabály szerint az n -től k -ig ismétlődő elhelyezések száma , amelyet jelöl : [6] [2] [5] $\bar{A}_n^k$

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

Például egy 3 számjegyű kód opcióinak száma, amelyben minden karakter egy 0 és 9 közötti számjegy, és megismételhető, a következő:

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

Egy másik példa: a 4 elemből álló a , b , c , d 2-vel ismétlődő elhelyezések 4 2 = 16, ezek az elhelyezések a következők:

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

Lásd még

Linkek

↑ ISBN 978-5-406-05433-8 Matematika tankönyv az SPO számára, szerkesztette: Bashmakov M.I. Archiválva : 2019. december 9. a Wayback Machine -nél
↑ 1 2 Vilenkin N. Ya . fejezet III. Sorok és halmazok kombinatorikája. Kiosztások ismétlődésekkel // Népszerű kombinatorika . - M. : Nauka, 1975. - S. 80. - 208 p.
↑ Konfigurációelmélet és felsoroláselmélet . Hozzáférés dátuma: 2009. december 30. Az eredetiből archiválva : 2010. január 23. (határozatlan)
↑ 3. fejezet. A kombinatorika elemei archiválva : 2010. január 4. a Wayback Machine -nél . // Előadások a valószínűségelméletről.
↑ 1 2 Korn G., Korn T. Tab. 18.7-2(2.b), 18.7-3(2.b) // Matematikai kézikönyv tudósok és mérnökök számára . - M. : Nauka, 1973. - S. 568. - 832 p.
↑ Kombinatorikus elemzés // Matematikai enciklopédia / Szerk. I. M. Vinogradova. - M. , 1977. - T. 2. - S. 974. - (Sov. Encyclopedia).