Multiplikasjonsprinsippet

Multiplikasjonsprinsippet, også kalt produktregelen, er et grunnleggende prinsipp i kombinatorikken. Det sier at hvis en oppgave kan utføres på m måter, og etter denne oppgaven kan en annen oppgave utføres på n måter, så kan hele oppgaven utføres på m×n måter. Dette utvides til flere trinn: hvis en prosess består av k trinn, og trinn i har ni forskjellige måter å gjennomføre på (for alle i), blir det totale antallet måter å fullføre prosessen n1×n2×…×nk.

Vilkår og generaliseringer: Produktregelen gjelder når antall valgmuligheter i hvert trinn er fast og ikke avhenger av hvilket alternativ som ble valgt i tidligere trinn, eller mer generelt når antallet mulige utfall for hvert trinn er spesifisert slik at det gir et produkt over trinnene. Prinsippet brukes også når man teller sekvenser av valg eller funksjoner som består av uavhengige deler.

Eksempler: Et passord med tre bokstaver hvor første bokstav har 3 alternativer, andre har 4 alternativer, og tredje har 2 alternativer gir 3×4×2 = 24 mulige passord. En meny med 3 typer hovedrett og 5 drikker gir 3×5 = 15 kombinasjoner. Antall funksjoner fra en mengde med m elementer til en mengde med n elementer er n^m, hvilket følger av produktregelen ved å velge en bilde for hvert av de m elementene.

Forhold til addisjonsprinsippet: Mens addisjonsprinsippet teller alternative valg, gir multiplikasjonsprinsippet antall kombinasjoner når valgene skjer i sekvensielle trinn. Det er et av de mest brukte verktøyene i kombinatorikk og sannsynlighet.