Sannolikhetsteori (?)

Skulle vilja lära mig följande:

Säg att jag har 5 böcker, numrerade 1-5. Dom sätts in i en bokhylla på slumpmässig plats.

Om jag inte är helt ute och cyklar så kan böckerna sättas in på 5! (120) olika sätt i hyllan.

Men säg att jag t.ex. vill att bok nummer 2 måste hamna på position 2, och att bok nummer 3 INTE kan hamna på position 3, på hur många sätt kan böckerna sättas in nu?

Sen antar jag att sannolikheten för att böckerna hamnar på detta sätt är <antal kombinationer>/5! om dom sätts in slumpmässigt.

Jag vill alltså inte främst veta svaret på mitt exempel, utan hur man räknar ut det, och gärna en allmän formel.

EDIT:

Om en speciell bok måste vara på en speciell position så blir det ju samma sak som om boken inte fanns, dvs i mitt exempel (5-1)!

Det är mer när en bok inte får vara på ett specifikt ställe som bekymrar mig, eller ännu värre, när flera böcker inte får vara på specifika ställen.

Det blir väl 4! - 3! = 18 möjliga kombinationer.
Sedan en av böckerna är låst, har du fyra böcker att placera på fyra positioner minus en bok som bara tillåts vara placerad på tre positioner.

Jo, men hur får man det till en allmän formel? T.ex. om det skulle handla om 50 böcker och 15 som inte får vara på samma position som sin siffra.

Om vi har n böcker och k av dessa inte får vara på sin plats så går det att göra en allmän formel som säger hur många sätt det går att göra detta på (vill man ha sannolikheten är det bara att dela med n!). Det är dock möjligt att det går att göra en snyggare än den jag kom på nu:

C(n, k) = n! / (k! * (n - k)!) är antalet kombinationer (dvs. att man inte tar hänsyn till ordningen) bestående av k objekt valda av n möjliga objekt.

!n kallas på engelska för subfactorial och är antalet sätt att permutera n objekt så att inget element hamnar på sin ursprungliga plats. Man kan t.ex. beräkna !n rekursivt med denna formel (men det finns ett gäng andra sätt):
!0 = 1
!n = !(n - 1) * n + (-1)^n då n ≥ 1

Tanken bakom summan är att varje del i summan är antalet sätt man kan välja i stycken element av de som får vara på rätt plats och sedan multiplicerar man det med antalet sätt det går att permutera de övriga elementen så att inte något av dessa är på rätt plats.

det är viktigt att vi räknar precis samma typ av objekt här:
för som jag tolkade det så ska vi räkna antalet permutationer av {1,2,3,...,n} sådana att 1,2,...,k ej fixeras, dvs alla sätt att placera ut de n böckerna på sådana att de k första böckerna ej hamnar på sin egen plats. (eller k st från början valda böcker, kan anta utan inskränkning att de är de k första)
Men man kan istället fråga sig "Antalet permutationer där minst k st element ej fixeras", "Antalet permutationer där exakt k st element ej fixeras" eller "Antalet permutationer där endast de k första elementen fixeras" och få olika svar, jag vet inte vad den bästa tolkningen här är.

Men jag skriver mitt resultat iaf, som bygger på principen om inklusion exklusion, jag hoppar över nästan alla steg nu, för jag orkar inte lära mig hur man skriver summor och sånt på snyggt sätt:
Sätt A_i={alla permutationer där element i fixeras} Då får vi
(antal)#permutationer=n!-|Union(i=1..k;A_i)|=Sum(j=0..k;ch(k,j)*(n-j)!*(-1)^j)

speciellt n=4, k=1 => #perm=ch(1,0)*(4-0)!-ch(1,1)(4-1)!=18
När k närmar sig n och när n blir stort så kommer sannolikheten att välja en sådan permutation gå mot 1/e~37%

kortsyntax kommentar:
sum(j=1..k;(...)) innebär att j är summationsvariablen o går från 1 till k.
pss betyder |Union(i=1..k;A_i)| antalet element i unionen mellan alla k st A_i
ch() är choose function definerad av yoda.

yoda, vilken tolkning av problemet gjorde du? och om du hade samma tolkning som jag, har du testat knacka in n=4, k=1 som bör ge 18?

Min tolkning av problemet var att om vi har mängden {1,2,3,...,n} så väljer vi ut k av dessa tal (t.ex. de k första) och inget av dessa tal får hamna på sin ursprungliga plats. Sätter vi in n = 4 och k = 1 så får vi
C(3, 0) * !4 + C(3, 1) * !3 + C(3, 2) * !2 + C(3, 3) * !1 = !4 + 3 * !3 + 3 * !2 + !1 = 9 + 6 + 3 + 0 = 18.

okej, intressant, jag har aldrig stött på subfactorials förut, däremot har jag läst lite om "dearrangements" som de uppkommer ifrån. Men jag ser varför din formel fungerar nu, och det e rätt snyggt.
Tydligen är !n lätt att beräkna också. eftersom !n är det närmaste heltal till n!/e ie !n*e~n!
din formel är användbar för stora k, medan min e enklare för små k.

Det var precis vad jag sökte efter, tack så mycket!

Var alltså mitt antagande om att en bok som måste vara på sin egen plats bara är att ta bort från uträkningen korrekt?

Jo, för att ställa ut dom böckerna som skall vara på sina givna platser kan ju bara göras på ett sätt.

Jag märkte att man kan få fram !n genom att ta:

int((n!/e)+0.5)

Stämmer det för alla tal, eller är det bara en slump att det stämmer på vissa?

EDIT: Hittade precis på wikipedia att det stämmer.

En annan intressant sak. Säg att jag har 10 böcker, men bara 2 olika sorter (t.ex. 5 röda och 5 gröna). På hur många sätt kan man sätta in böckerna i hyllan?

På låga tal är det ju lätt att räkna ut i huvudet, en röd och en grön bok kan sättas in på 2 sätt, 3 gröna och 3 röda på 6 sätt. Jag antar att det finns en formel för detta också?

Detta är inget svar på din fråga men en kanske lite rolig kalkylator, i vilken man kan testa lite olika parametrar finns på...
http://www.mathsisfun.com/combinator...alculator.html