matematikk.net

Anta at det er 200 land i verden. Fra hvert land plukkes det ut én person som skal på ferie til utlandet (relativt eget hjemland). Det er ikke mulig at to av personene reiser til samme land. På hvor mange måter kan dette gjøres?

Tenker jeg for enkelt hvis jeg sier 200! ?

Aleks855 wrote:Tenker jeg for enkelt hvis jeg sier 200! ?

Ja, en person fra Norge kan ikke reise til Norge etc.

(Problemet er nok noe vanskeligere enn det ser ut som. Hint: Finn en rekurensrelasjon for permutasjoner uten fikspunkt)

Vi skal finne antall permutasjoner i [tex]S_n[/tex] uten fikspunkter. Kaller denne størrelsen [tex]P_n[/tex]

Ønsker å finne en rekursjonsrelasjon, så vi ser på en permutasjon [tex]\rho[/tex] av [tex]\{1,2,3,\cdots,n\}[/tex]
og ser hvilke muligheter det er for det første elementet, 1. Hvis vi antar at [tex]\rho[/tex] er faktorisert i disjunkte sykler
finnes det enten en 2-sykel [tex](1,i)[/tex] eller en sykel med flere enn to elementer [tex](1,i,...)[/tex].

1) Anta først at sykelen [tex](1,i)[/tex] er med i [tex]\rho[/tex]. Da er det [tex]P_{n-2}[/tex] kombinasjoner for resten av permutasjonen.
Siden det er [tex](n-1)[/tex] valg av i har vi totalt [tex](n-1)P_{n-2}[/tex] kombinasjoner.

2) Se på en vilkårlig permutasjon uten fikspunkter i [tex]S_{n-1}[/tex] og finn sykelen som inneholder 2. Plasserer vi 1 før 2 i
denne sykelen får vi en permutasjon i [tex]S_n[/tex] uten fikspunkter. Siden det er [tex]P_{n-1}[/tex] permutasjoner i
[tex]S_{n-1}[/tex] uten fikspunkter og vi kan sende [tex]1[/tex] til [tex]2,3,\cdots,n[/tex] får vi totalt [tex](n-1)P_{n-1}[/tex] kombinasjoner.

Dermed har vi funnet at [tex]P_n=(n-1)(P_{n-1}+P_{n-2})[/tex] som også kan skrives [tex]P_n-nP_{n-1}=-(P_{n-1}-(n-1)P_{n-2})[/tex]
Setter vi opp denne ligningen for [tex]n-1,n-2,\cdots,4,3[/tex] også og multipliserer alle ligningene sammen får vi at
[tex]P_n-nP_{n-1}=(-1)^{n-2}(P_2-2P_1)=(-1)^n[/tex]
siden [tex]P_2=1[/tex] og [tex]P_1=0[/tex]

Dermed har vi at [tex]P_n=nP_{n-1}+(-1)^n[/tex] som vi heller skriver som [tex]\large\frac{P_n}{n!}=\frac{P_{n-1}}{(n-1)!}+\frac{(-1)^n}{n!}[/tex]
Setter vi opp denne for [tex]n-1,n-2,\cdots,4,3[/tex] og summerer får vi endelig at

[tex]\large P_n=n!\sum_{i=2}^n{\frac{(-1)^i}{i!}}[/tex]
Og dermed [tex]P_{200}=200!\sum_{i=2}^n{\frac{(-1)^i}{i!}}[/tex] som jeg ikke har noen planer om å regne ut.

edit: rettet slurvefeil