Ir al contenido

Principio del producto (combinatoria)

De Wikipedia, la enciclopedia libre

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

[editar]

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:

.

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]

Principio del producto: Si son conjuntos finitos entonces

.

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]
  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. 
  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.