Principio del producto (combinatoria)
# 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:

* Principio del producto (informal). Si una tarea se realiza en dos etapas, donde la primera se puede realizar de m formas posibles y, si para cada una de ellos la segunda etapa se puede realizar de n distintas formas, entonces la tarea completa se puede arrojar mn formas posibles.

## 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:

* Principio del producto. Si A, es igual o menor que B son conjuntos finitos entonces la cardinalidad del producto cartesiano es:
* $|A\times B|=|A|\cdot |B|$.

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 $A\times B$ con el conjunto total de elecciones completas.

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

* Principio del producto: Si $A_{1},A_{2},\ldots A_{r}$ son conjuntos finitos entonces
* $\left|\prod _{i=1}^{r}A_{i}\right|=|A_{1}\times A_{2}\times \cdots \times A_{r}|=|A_{1}|\cdot |A_{2}|\cdots |A_{r}|=\prod _{i=1}^{r}|A_{i}|$.

## 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:

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

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 $2\times 2\times 2\times \cdots \times 2=2^{n}$.

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á $r^{n}$.

### 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

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

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

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

es decir, el factorial de n.

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

