Rod (permutation)

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 20. december 2021; verifikation kræver 1 redigering .

I kombinatorik er en lidelse en permutation uden fikspunkter .

Eksempler

Kontrol af arbejde

Lad os sige, at en professor gav fire elever (lad os kalde dem A, B, C og D) en test og derefter bad dem om at tjekke det med hinanden. Naturligvis bør ingen studerende tjekke sin egen prøve. Hvor mange muligheder har professoren for at distribuere kontroltest, hvor ingen studerende får deres eget arbejde? Ud af alle 24 permutationer (4!) til tilbagevenden af arbejde er kun 9 lidelser egnede for os:

BADC, BCDA, BDAC, CADB, CDAB, CDBA, DABC, DCAB, DCBA.

I enhver anden permutation af disse 4 elementer får mindst én elev deres test til at blive tjekket.

Bogstavproblem

Beregning af mængden af lidelse er et populært problem i Olympiade-matematik , som forekommer i forskellige formuleringer såsom lidelsesproblemet , bogstavproblemet , mødeproblemet og så videre.

Hvis breve er tilfældigt placeret i forskellige konvolutter, hvad er sandsynligheden for, at nogen af bogstaverne ender i sin egen konvolut?

n

n

Svaret er givet af udtrykket

1-{\frac {!n}{n!}}\ca. 1-{\frac {1}{e}}.

Svaret afhænger således svagt af antallet af bogstaver og kuverter og er omtrent lig med konstanten . $1-{\frac {1}{e}}\approx 0{,}63212$

Antal optøjer

Antallet af alle ordensforstyrrelser n kan beregnes ved hjælp af inklusions-udelukkelsesprincippet og er givet af

!n=n!-{\frac {n!}{1!}}+{\frac {n!}{2!}}-{\frac {n!}{3!}}+\prikker +(-1)^{n}{\frac {n!}{n!}}=\sum _{k=0}^{n}(-1)^{k}{\frac {n!}{ k!}},

som kaldes delfaktoren af n .

Antallet af lidelser tilfredsstiller de rekursive relationer $!n=d(n)$

d(n)=(n-1)[d(n-1)+d(n-2)]

d(n)=nd(n-1)+(-1)^{n},

hvor og . $d(1)=0$ $d(2)=1$

I lyset af det faktum , at værdien opfører sig som . Desuden, når det kan repræsenteres som resultatet af afrunding af tallet . $\sum _{k=0}^{\infty }(-1)^{k}{\frac {1}{k!}}={\frac {1}{e}}$ $!n$ $n$ ${\frac {n!}{e))$ $n>0$ ${\frac {n!}{e))$

Se også

Fødselsdagsparadokset