Boende

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 17 april 2022; verifiering kräver 1 redigering .

I kombinatorik är en allokering (från n till k ) en ordnad uppsättning av k olika element från någon uppsättning av olika n element.

Exempel 1: är en 4-elementsallokering från en 6-elementsuppsättning . $\langle 1,3,2,5\rangle$ $\{1,2,3,4,5,6\}$

Exempel 2: några arrangemang av element i en mängd med 2: … … … $\{1,2,3,4,5,6\}$ $\langle 1,2\rangle$ $\vinkel 1,3\vinkel$ $\langle 1,4\rangle$ $\langle 1,5\rangle$ $\langle 2,1\rangle$ $\vinkel 2,3\vinkel$ $\vinkel 2,4\vinkel$ $\vinkel 2,6\vinkel$

Till skillnad från kombinationer tar placeringar hänsyn till ordningen på objekten. Så, till exempel, sätter och är olika arrangemang, även om de består av samma element (det vill säga de sammanfaller som kombinationer). $\langle 2, 1, 3$ $\langle 3, 2, 1$ $\{1, 2, 3\}$

Att fylla i en rad innebär att placera ett objekt från den givna uppsättningen på någon plats i denna rad (desutom kan varje objekt endast användas en gång). En rad fylld med objekt av en given uppsättning kallas placering, det vill säga vi placerade objekt på dessa platser. [ett]

Antal placeringar

Antalet placeringar från n till k , betecknat med , är lika med den minskande faktorn : $A_{n}^{k}$

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

Uttryckt på ett elementärt sätt genom Pochhammer-symbolen :

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

Det sista uttrycket har en naturlig kombinatorisk tolkning: varje placering från n till k motsvarar unikt någon kombination av n till k och någon permutation av elementen i denna kombination; antalet kombinationer från n till k är lika med binomialkoefficienten , medan det finns exakt k permutationer på k element ! saker. $\tbinom{n}{k}$

För k = n är antalet placeringar lika med antalet permutationer av ordning n : [2] [3] [4]

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

Följande påstående är sant: . Beviset är trivialt: ${\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}

Placering med upprepningar

Upprepad häckning eller returhämtning [5] är kapsling av "föremål" under antagandet att varje "föremål" kan delta i kapslingen flera gånger.

Antal placeringar med upprepningar

Enligt multiplikationsregeln är antalet placeringar med repetitioner från n till k , betecknade med ,: [6] [2] [5] $\bar{A}_n^k$

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

Till exempel är antalet alternativ för en 3-siffrig kod, där varje tecken är en siffra från 0 till 9 och kan upprepas:

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

Ett annat exempel: placeringar med upprepningar av 4 element a , b , c , d med 2 är 4 2 = 16, dessa placeringar är som följer:

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

Se även

Länkar

↑ ISBN 978-5-406-05433-8 Matematiklärobok för SPO redigerad av Bashmakov M.I. Arkiverad 9 december 2019 på Wayback Machine
↑ 1 2 Vilenkin N. Ya . Kapitel III. Kombinatorik av tupler och set. Tilldelningar med upprepningar // Populär kombinatorik . - M. : Nauka, 1975. - S. 80. - 208 sid.
↑ Konfigurationsteori och uppräkningsteori . Datum för åtkomst: 30 december 2009. Arkiverad från originalet den 23 januari 2010. (obestämd)
↑ Kapitel 3. Elements of Combinatorics Arkiverad 4 januari 2010 på Wayback Machine . // Föreläsningar om sannolikhetsteori.
↑ 1 2 Korn G., Korn T. Tab. 18.7-2(2.b), 18.7-3(2.b) // Handbok i matematik för vetenskapsmän och ingenjörer . - M. : Nauka, 1973. - S. 568. - 832 sid.
↑ Kombinatorisk analys // Mathematical Encyclopedia / Ed. I. M. Vinogradova. - M. , 1977. - T. 2. - S. 974. - (Sov. Encyclopedia).