Jag behöver lite råd med en fråga som handlar om kombinatorik i diskret matematik kursen
Frågan är:
5.35) Vi permuterar det svenska alfabetes 29 bokstäver. I hur många av alla dessa permutationer kan man varken läsa ordet DISKRET eller RETA?
Jag tänker såhär:
Permutationen av 29 bokstäver = 29!
Permutationer som innehåller ordet DISKRET är då 29 - 7+1 = 23! (Vi drar bort 7 st bokstäver och introducerar en ny symbol)
På samma sätt är permutationer som innehåller ordet RETA 29 - 4 + 1 = 26!
Till slut räknade jag permutationer som innehåller båda orden blir då 29 - 8 + 1 = 22! (Eftersom vi har gemensamma bokstäver i båda orden dvs, DISKRETA, så drog jag bort 8 bokstäver och la till en ny symbol.)
Jag tänker att svaret borde bli 29! - 23! - 26! - 22! eftersom vi tar bort alla permutationer som innehåller dessa ord, men enligt facit ska svaret vara 29! - 23! - 26! + 22!
Jag förstår inte riktigt varför dom lägger till 22! och inte drar bort det, är väldigt tacksam om någon kunde ge en kort förklaring.
Den hela mängden består av alla permutationer och är mycket riktigt 29!.
Den mängd som innehåller DISKRET är mycket riktigt 23!. Ett exempel på en permutation kan du se nedan:
Q W DISKRET A Y U O P Å F G H J L Ö Ä Z X C V B N M
Den mängd som innehåller RETA är mycket riktigt 26!. Ett exempel på en permutation kan du se nedan:
Q W D I S K RETA Y U O P Å F G H J L Ö Ä Z X C V B N M
Observera att detta är samma permutation som den vi hade som exempel från 23!-mängden. Med andra ord, om man tar 29!-23!-26! så kommer det finnas vissa permutationer som förekommer i båda mängderna och som du subtraherat bort två gånger. Du vill dock bara subtrahera bort varje permutation en gång, så för att kompensera måste du lägga till ett ex av varje permutation som har DISKRETA i sig, vilket leder till att du måste lägga till 22!.
Ett annat sätt att se det är att tänka sig ett Venn-diagram. DISKRET-mängden och RETA-mängden består av två överlappande cirklar, med DISKRETA i snittet. Tar man bort DISKRET-mängden och RETA-mängden så kommer man att ha subtraherat snittet två gånger, så man får lägga till antalet kombinationer däri för att kompensera.
Jag förstår inte riktigt hur du fick fram 22!
Om vi tänker på venn-diagram sättet så tänker jag att de gemensamma bokstäverna RET borde vara i snittet och inte DISKRETA, tänker jag fel?
Jag kom fram till 22! på samma sätt som du trodde jag. Om jag får formulera det med egna ord:
Om vi vill ta reda på hur många permutationer som finns med en uppsättning av alla bokstäver i alfabetet så kan vi göra det genom att skriva varje bokstav på en post-it-lapp, och därmed få 29 objekt att sätta i permutation och därmed få 29! permutationer. Att ta reda på hur många det finns där slingan DISKRETA förekommer i permutationen är liktydigt med att slänga bort de post-it-lappar som det står D, I, S, K, R, E, T och A på, och istället bilda ordet DISKRETA på en post-it lapp. Vi har då blivit av med 8 objekt men fått 1 nytt så vi har 29-8+1=22 objekt att sätta i permutationer, vilket ger 22!.
Du tänker fel då det gäller Venn-diagram. DISKRET-mängden är alla de permutationer där slingan DISKRET förekommer. RETA-mängden är alla de permutationer där slingan RETA förekommer. Snittet de emellan är alla de permutationer där slingorna DISKRET och RETA förekommer, vilket givet att vi bara har ett exemplar av varje bokstav blir alla de permutationer där slingan DISKRETA förekommer.
Jag förstår, tack snälla för hjälpen !
