Multiplikationsprincipen

Multiplikationsprincipen, ofta kallad multiplikationsregelen, är en grundläggande sats inom kombinatorik som används för att räkna antalet möjliga utfall när ett problem består av flera steg i följd. Om ett första steg kan genomföras på m sätt och ett andra steg på n sätt oberoende av vilket val som gjordes i det första steget, finns det totalt m·n möjliga sekvenser av val.

Mer generellt gäller: om en process består av r r tillståndsbad som ska genomföras i följd, och varje steg i kan göras på n_i sätt, så är det totala antalet möjliga utfall produkten n_1·n_2·...·n_r. Villkoret är att antalet alternativ vid varje steg är fast och inte beror på vilket val som gjordes i tidigare steg; om något steg har noll alternativ leder det totala antalet utfall till noll.

Exempel: att välja en t-shirt där färg (3 val) och storlek (4 val) ger 3×4=12 olika kombinationer. Ett lösenord med fyra tecken där varje tecken kan vara en av 10 siffror ger 10^4 möjliga lösenord eftersom varje tecken val är oberoende och har 10 alternativ.

Multiplikationsprincipen används ofta inom kombinatorik och sannolikhet för att beräkna antalet gynnsamma utfall eller totala utfall i situationer där valen görs i flera steg. Den är också närbesläktad med kartesiska produkten och utgör en viktig byggsten i många räkneläten.