Metodos Combinatorios

Métodos combinatorios
En muchos problemas es necesario citar todas las alternativas posibles de una situación dada o por lo menos determinar cuántas posibilidades diferentes existen. Para estoscasos frecuentemente se utiliza la “regla de multiplicación” que se define según el siguiente teorema:
Teorema 1.1Si una operación consta de dos pasos, de los cuales el primero puede efectuarse en n1formas y para cada una de éstas el segundo puede realizarse en n2 formas, entonces la operación se lleva a cabo de maneras. |
La “regla de multiplicación” puede ampliarse para comprender situacionesdonde una operación consta de un número fijo de pasos. El caso general se enuncia en el siguiente teorema:
Teorema 1.2Si una operación consta de k pasos, de los cuales el primero puede efectuarse enn1 formas, para cada una de éstas el segundo puede realizarse en n2 maneras, para cada un de éstas el tercero puede realizare en n3 formas, etc., entonces toda la operación puede llevarse a cabo enformas. |
Con frecuencia, estamos interesados en situaciones donde los productos o resultados son los órdenes o arreglos diferentes de un grupo de objetos. Los diversos arreglos se denominanpermutaciones.
Teorema 1.3El número de permutaciones de n objetos distintos es n!. |

Teorema 1.4El número de permutaciones de n objetos diferentes tomados r a la vez es:nPr = |
En aplicaciones dondeintervienen permutaciones, suele ser más sencillo proceder mediante el uso del teorema 1.2, pero la formula del factorial del teorema 1.4 es más fácil de recordar.
Las permutaciones que ocurren cuandose ordenan objetos en un círculo se denominan permutaciones circulares. Dos permutaciones circulares no se consideran distintas si objetos correspondientes de los dos arreglos van precedidos y seguidosde los mismos objetos a medida que avanzamos en el sentido que giran las agujas del reloj.
Teorema 1.5El número de permutaciones de n objetos distintos ordenados en un círculo es (n-1)!. |
En...