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]
|
- 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
[editar]El principio del producto puede expresarse de manera formal y precisa:[2]
|
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:[3]
|
Aplicaciones
[editar]El principio del producto se encuentra subyacente en toda prueba o enumeración donde se realicen elecciones sucesivas.
Ejemplo: Palabras binarias
[editar]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 .
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
[editar]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
,
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
[editar]- ↑ 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.
- ↑ 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.