Kombinatorikk
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
Tenker jeg for enkelt hvis jeg sier 200! ?
-
Brahmagupta
- Guru
- Innlegg: 628
- Registrert: 06/08-2011 01:56
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
Ø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