Majoitus

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 17. huhtikuuta 2022 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

Kombinatoriikassa allokaatio ( n : sta k :aan ) on k eri elementin järjestynyt joukko jostakin eri n elementin joukosta .

Esimerkki 1: on 4 elementin allokaatio 6 elementin joukosta . $\langle 1,3,2,5\rangle$ $\{1,2,3,4,5,6\}$

Esimerkki 2: jotkut joukon elementtien järjestelyt luvulla 2: … … … $\{1,2,3,4,5,6\}$ $\langle 1,2\rangle$ $\kulma 1,3\kulma$ $\langle 1,4\rangle$ $\langle 1,5\rangle$ $\langle 2,1\rangle$ $\kulma 2,3\kulma$ $\kulma 2,4\kulma$ $\kulma 2,6\kulma$

Toisin kuin yhdistelmät , sijoittelut ottavat huomioon kohteiden järjestyksen. Joten esimerkiksi joukot ja ovat erilaisia järjestelyjä, vaikka ne koostuvat samoista elementeistä (eli ne ovat yhteneväisiä yhdistelminä). $\langle 2, 1, 3$ $\langle 3, 2, 1$ $\{1, 2, 3\}$

Rivin täyttäminen tarkoittaa jonkin kohteen sijoittamista annetusta joukosta johonkin tämän rivin paikkaan (lisäksi kutakin objektia voidaan käyttää vain kerran). Tietyn joukon kohteilla täytettyä riviä kutsutaan sijoitukseksi, eli sijoitimme esineitä näihin paikkoihin. [yksi]

Sijoittelujen määrä

Sijoittelujen lukumäärä n :stä k :aan merkittynä on yhtä suuri kuin laskeva tekijä : $A_{n}^{k}$

A_{n}^{k}=n^{\alleviivaus {k))=(n)_{k}=n(n-1)\cdot \ldots \cdot (n-k+1)= {\frac {n!}{(nk)!}}

Ilmaistu alkeellisella tavalla Pochhammer-symbolin kautta :

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

Viimeisellä lausekkeella on luonnollinen kombinatorinen tulkinta: jokainen sijoittelu n :stä k : hen vastaa yksiselitteisesti jotakin n: n ja k :n yhdistelmää ja jotakin tämän yhdistelmän elementtien permutaatiota ; yhdistelmien lukumäärä n - k on yhtä suuri kuin binomikerroin , kun taas k alkiolla on tasan k permutaatiota ! asioita. $\tbinom{n}{k}$

Kun k = n , sijoittelujen määrä on yhtä suuri kuin permutaatioiden määrä kertaluvulla n : [2] [3] [4]

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

Seuraava väite pitää paikkansa: . Todistus on triviaali: ${\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}

Sijoittelu toistoilla

Toistuva sisäkkäis- tai palautushaku [ 5 ] on "kohteiden" sisäkkäisyyttä sillä oletuksella, että jokainen "tuote" voi osallistua sisäkkäisyyteen useita kertoja.

Toistojen sijoittelujen määrä

Kertoussäännön mukaan sijoittelujen määrä toistojen välillä n - k , merkitty symbolilla , on: [6] [2] [5] $\bar{A}_n^k$

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

Esimerkiksi 3-numeroisen koodin vaihtoehtojen määrä, jossa jokainen merkki on numero 0-9 ja voidaan toistaa, on:

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

Toinen esimerkki: sijoittelut, joissa toistetaan 4 elementtiä a , b , c , d 2:lla on 4 2 = 16, nämä sijoittelut ovat seuraavat:

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

Katso myös

Linkit

↑ ISBN 978-5-406-05433-8 SPO:n matematiikan oppikirja, toimittanut Bashmakov M.I. Arkistoitu 9. joulukuuta 2019 Wayback Machinessa
↑ 1 2 Vilenkin N. Ya . III luku. Tuplejen ja joukkojen kombinatoriikka. Allokaatiot toistoilla // Suosittu kombinatoriikka . - M .: Nauka, 1975. - S. 80. - 208 s.
↑ Konfiguraatioteoria ja laskentateoria . Käyttöpäivä: 30. joulukuuta 2009. Arkistoitu alkuperäisestä 23. tammikuuta 2010. (määrätön)
↑ Luku 3. Kombinatoriikan elementit Arkistoitu 4. tammikuuta 2010 Wayback Machinessa . // Todennäköisyysteorian luentoja.
↑ 1 2 Korn G., Korn T. Tab. 18.7-2(2.b), 18.7-3(2.b) // Matematiikan käsikirja tutkijoille ja insinööreille . - M .: Nauka, 1973. - S. 568. - 832 s.
↑ Kombinatorinen analyysi // Mathematical Encyclopedia / Toim. I. M. Vinogradova. - M. , 1977. - T. 2. - S. 974. - (Sov. Encyclopedia).