Kombinatorikk

[Pjolter]

Utdrag av oppgavetekst:
"Vi foretar nå en tilfeldig permutasjon av heltallene {1,2,3,4,5}. La X være antall heltall som havner i "rett" posisjon, dvs. på sin rette plass i tallrekkefølgen."

I forbindelse med en deloppgave ønsker jeg å regne ut P(X=0), dvs. sannsynligheten for at ingen av tallene havner på riktig plass. Til dette igjen behøver jeg antall permutasjoner (av de 5!) hvor ingen av tallene havner på "riktig" plass. Svaret er 44, men hvorfor? Jeg kan alltids "halvtelle" det, men det er jo ikke noe gøy.

[Pjolter]

Shiiit. Flævvt! Fant svaret gjemt i den momentgenererende funksjonen (som var oppgitt i oppgaven). 44/120 er jo nettopp konstantleddet her. Men nå har det allerede pirrett min nysgjerrighet så jeg setter fremdeles pris på om noen finner en elegant måte å regne ut at det er 44 måter å permutere tallfølgen slik at alle tallene havner på "gal" plass

[Fibonacci92]

Dersom du tar algebra til våren kan jeg vise deg en måte å finne det ut på ved å bruke sykler.

Vi var noen som diskuterte oppgaven i eksamensperioden i fjor og vi kom fram til en rekursiv formel, så prøv å løse det rekursivt;)

[Pjolter]

Yay: R(n) = (n-1)(R(n-1) + R(n-2))

[mrcreosote]

Dette var også gitt som oppgave 7 i andre runde i Abelkonkurransen i fjor, se http://abelkonkurransen.no/problems.php?lan=no for oppgaver og løsningsforslag; det siste går vel i halvtellingsboksen.

Morsom oppgave med overraskende (?) svar: Hva er P(X=0) når vi endrer {1,2,3,4,5} til {1,2,3,...,n} og lar n gå mot uendelig?

[Pjolter]

1/e

Leste meg litt opp på det i går