Principio del producto (combinatoria)

El principio del producto, regla del producto o principio de elección es uno de los principios fundamentales de la combinatoria. En su versión más simple establece:

 Ejemplo Si se desea escoger un postre y una bebida, teniendo 5 opciones para el postre y 6 opciones para la bebida, entonces la elección completa se puede realizar de 5·6 = 30 maneras diferentes.

Versión formal 
El principio del producto puede expresarse de manera formal y precisa:

La relación con la versión informal del principio se obtiene tomando A como el conjunto de posibles resultados o selecciones de la primera etapa, B el conjunto de resultados o selecciones de la segunda, mientras que se identifica cada pareja (a, b) con un par de elecciones y por tanto  con el conjunto total de elecciones completas.

Existe una generalización del principio del producto para varios conjuntos:

Aplicaciones 
El principio del producto se encuentra subyacente en toda prueba o enumeración donde se realicen elecciones sucesivas.

Ejemplo: Palabras binarias 

Se desea determinar el número de palabras binarias de longitud n. Es decir, series de longitud n formadas por cifras 0 o 1.  Por ejemplo, las palabras binarias de longitud 4 son:

Se debe hacer la observación que estrictamente hablando, una palabra binaria no es lo mismo que un número binario. Una palabra binaria es únicamente una lista formal de símbolos, y por tanto las palabras 0010, 010, 10 son diferentes aunque puedan interpretarse todas ellas como el número binario 10.

Para poder elegir una palabra, es necesario hacer n elecciones, una para cada posición de la palabra. Por ejemplo: la primera posición puede ser 0 o 1 (dos opciones), la segunda posición es independiente de la primera y por tanto puede ser 0 o 1 (dos opciones), y así sucesivamente.

Cada serie de n elecciones corresponde a una palabra y cada palabra corresponde a n elecciones, por lo que el número de palabras binarias es igual al número de formas de realizar n elecciones cada una de las cuales tiene 2 posibilidades. El principio del producto establece entonces que el resultado ha de ser .

Un argumento similar permite concluir que si se desea enumerar palabras de longitud n, en donde cada posición puede ser cualquiera de r posibles símbolos, el número de formas de hacerlo será .

Ejemplo: Permutaciones 
Se desea determinar el número de formas en que n objetos se pueden ordenar de forma secuencial.

Como ilustración, consideremos el conjunto de las 4 letras {A, B, C, D}. Al ordenarse de forma secuencial obtenemos todas las siguientes permutaciones

Para obtener una permutación, es necesario realizar n elecciones correspondientes a cada una de las posiciones de la misma.

 La primera posición puede ser cualquiera de los n elementos, de modo que la primera elección puede realizarse de n formas.
 La segunda posición puede ser cualquiera de los elementos excepto el elemento seleccionado para la primera posición, teniendo entonces n'-1 opciones diferentes.
 En el ejemplo, si la primera opción fue B, la segunda posición solo puede ser A, C o D, quedando en 4-1=3 posibilidades.
 La tercera posición puede ser cualquier elemento excepto los dos ya seleccionados, teniendo así n-2 formas de escoger la tercera posición.
 En el ejemplo, si la primera opción fue B y luego se seleccionó D, la tercera posición puede ser únicamente A o C, es decir, hay 4-2 = 2 posibilidades.

Continuando el proceso, se observa que para la posición k hay únicamente n-(k-1) = n-k+1 opciones (ya que las k-l selecciones realizadas con anterioridad no pueden ya repetirse), mismo proceso que continúa hasta realizar la n-ésima selección, la cual solo puede hacerse de 1 forma.

Aplicando el principio del producto, se concluye que el número de formas en que puede realizarse el proceso completo de selección es

es decir, el factorial de n.

Concluimos: el número de formas de ordenar secuencialmente  objetos, es decir, permutaciones de n objetos es igual al factorial de .

Referencias 

Combinatoria

fi:Todennäköisyysteoria#Tuloperiaate ja summaperiaate