Principio del producto (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.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 tantocon el conjunto total de elecciones completas.El principio del producto se encuentra subyacente en toda prueba o enumeración donde se realicen elecciones sucesivas.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 serUn 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á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.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