Principi del producte (combinatòria)

El principi del producte, regla del producte o principi d'elecció és un dels principis fonamentals de la combinatòria. En la seua versió més simple establix:

Principi del producte (informal). Si una tasca es realisa en dos etapes, a on la primera es pot realisar de m formes possibles i, si para cada una d'ells la segona etapa es pot realisar de n distintes formes, llavors la tasca completa es pot tirar mn formes possibles.

Eixemple

Si es desija triar una darreria i una beguda, tenint 5 opcions per a la darreria i 6 opcions per a la beguda, llavors l'elecció completa es pot realisar de 5·6 = 30 maneres diferents.

Versió formal

El principi del producte pot expressar-se de manera formal i precisa:

La relació en la versió informal del principi s'obté prenent A com el conjunt de possibles resultats o seleccions de la primera etapa, B el conjunt de resultats o seleccions de la segona, mentres que s'identifica cada parella (a, b) en un parell d'eleccions i per tant $A\times B$ en el conjunt total d'eleccions completes.

Existix una generalisació del principi del producte per a varis conjunts:

Aplicacions

El principi del producte es troba subjacent en tota prova o enumeració a on es realisen eleccions successives.

Eixemple: Paraules binarias

Es desija determinar el número de paraules binarias de llongitut n. És dir, séries de llongitut n formades per sifres 0 o 1. Per eixemple, les paraules binarias de llongitut 4 són:

0000	0001	0010	0011	0100	0101	0110	0111
1000	1001	1010	1011	1100	1101	1110	1111

Es deu fer l'observació que estrictament parlant, una paraula binaria no és lo mateix que un número binario. Una paraula binaria és únicament una llista formal de símbols, i per tant les paraules 0010, 010, 10 són diferents encara que puguen interpretar-se totes elles com l'número binario 10.

Per a poder elegir una paraula, és necessari fer n eleccions, una per a cada posició de la paraula. Per eixemple: la primera posició pot ser 0 o 1 (dos opcions), la segona posició és independent de la primera i per tant pot ser 0 o 1 (dos opcions), i aixina successivament.

Cada série de n eleccions correspon a una paraula i cada paraula correspon a n eleccions, per lo que el número de paraules binarias és igual al número de formes de realisar n eleccions cada una de les quals té 2 possibilitats. El principi del producte establix llavors que el resultat ha de ser $2\times 2\times 2\times \cdots \times 2=2^n$.

Un argument similar permet concloure que si es desija enumerar paraules de llongitut n, en a on cada posició pot ser qualsevol de r possibles símbols, el número de formes de fer-ho serà $r^n$.

Eixemple: Permutació

Es desija determinar el número de formes en que n objectes es poden ordenar de forma seqüencial.

Com a ilustració, considerem el conjunt de les 4 lletres {A, B, C, D}. En ordenar-se de forma seqüencial obtenim totes les següents permutació

ABCD	ABDC	ACBD	ACDB	ADBC	ADCB
BACD	BADC	BCAD	BCDA	BDAC	BDCA
CABD	CADB	CBAD	CBDA	CDAB	CDBA
DABC	DACB	DBAC	DBCA	DCAB	DCBA

Per a obtindre una permutació, és necessari realisar n eleccions corresponents a cada una de les posicions de la mateixa.

• La primera posició pot ser qualsevol dels n elements, de modo que la primera elecció pot realisar-se de n formes.
• La segona posició pot ser qualsevol dels elements llevat l'element seleccionat per a la primera posició, tenint llavors n'-1 opcions diferents.

En l'eixemple, si la primera opció va ser B, la segona posició solament pot ser A, C o D, quedant en 4-1=3 possibilitats.

• La tercera posició pot ser qualsevol element llevat els dos ya seleccionats, tenint aixina n-2 formes de triar la tercera posició.

En l'eixemple, si la primera opció va ser B i després es va seleccionar D, la tercera posició pot ser únicament A o C, és dir, hi ha 4-2 = 2 possibilitats.

Continuant el procés, s'observa que per a la posició k hi ha únicament n-(k-1) = n-k+1 opcions (ya que les k-l selecciones realisades en anterioritat no poden ya repetir-se), mateix procés que continua fins a realisar la n-ésima selecció, la qual solament pot fer-se d'1 forma.

Aplicant el principi del producte, es conclou que el número de formes en que pot realisar-se el procés complet de selecció és

$n(n-1)(n-2)\cdots 3\cdot 2\cdot 1$,

és dir, el factorial de n.

Concloem: el número de formes d'ordenar secuencialmente $n$ objectes, és dir, permutació de n objectes és igual al factorial de $n$.