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:^[1]

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:^[2]

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:^[3]

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\,$ .

Referencias

↑ Grimaldi, Ralph P. (1997). «Principios fundamentales de conteo». Matemáticas Discreta y Combinatoria: Una introducción con aplicaciones (3a edición). México: Addison Wesley. ISBN 9684443242. |fechaacceso= requiere |url= (ayuda)
↑ Aigner, Martin (2007). «Elementary Counting Principles». A Course in Enumeration (en inglés). Graduate Texts in Mathematics, vol. 238. Springer. ISBN 3540390324.
↑ Bóna, Miklós (2007). Introduction to Enumerative Combinatorics (en inglés) (1a edición). McGraw-Hill. ISBN 9780073125619.

Datos: Q557624

[1] Grimaldi, Ralph P. (1997). «Principios fundamentales de conteo». Matemáticas Discreta y Combinatoria: Una introducción con aplicaciones (3a edición). México: Addison Wesley. ISBN 9684443242. |fechaacceso= requiere |url= (ayuda)

[2] Aigner, Martin (2007). «Elementary Counting Principles». A Course in Enumeration (en inglés). Graduate Texts in Mathematics, vol. 238. Springer. ISBN 3540390324.

[3] Bóna, Miklós (2007). Introduction to Enumerative Combinatorics (en inglés) (1a edición). McGraw-Hill. ISBN 9780073125619.

[1]

[2]