Combinaciones sin repetición (fórmula genérica)

Antes de iniciar nuestro viaje por el fascinante mundo de los números combinatorios, nos dedicaremos a repasar algunos conceptos básicos.

Conjunto:

Puede ser definido como una colección de componentes que tienen propiedades similares o afines. A cada componente particular se le denomina elemento del conjunto.

Como ejemplo podemos citar el conjunto de todos los países que forman las Antillas mayores. Los elementos de este conjunto serían: Cuba, Rep. Dominicana, Haití, Pto Rico y Jamaica.

Podemos notar nuestro conjunto esta formado por un número finito de elementos, y es que un conjunto puede tener cualquier cantidad de elementos desde ninguno (conjunto vacio) hasta infinitos elementos.

Un conjunto que posea una cantidad conmensurable o finita de elementos se denomina conjunto finito.

Un conjunto que posea una cantidad infinita de elementos se denomina conjunto infinito.

Un conjunto que carece de elementos se conoce como conjunto vacio.

Factorial de un número:

Sea n un número entero positivo, el producto 1 * 2 * 3 *…n, se conoce como el factorial de n y su representación matemática es: n!

0! Se define como 1.

Ejemplos:

5! = 1 * 2 * 3 * 4 * 5 = 120 3! = 1 * 2 * 3 = 6 10! = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 = 3628800

Combinatoria:

En un conjunto dado de elementos finitos, el estudio de las diferentes maneras en que se pueden arreglar dichos elementos siguiendo reglas establecidas, es lo que se conoce como combinatoria. La representación simbólica de los números combinatorios, sin repetición, es la siguiente: Donde: m y n son números enteros = 0 y m = n. Los símbolos se definen matemáticamente como: Como nota es preciso puntualizar que existen otras nomenclaturas para representar los números combinatorios, sin embargo podremos notar mas adelante que se nos hace mas conveniente usar la simbología C(m, n); por lo que en lo adelante la usaremos para nuestros fines. Algunas de las propiedades de los números combinatorios son:

• 1. 

• 2. 

• 3. 

A la expresión C (m, n) se le denomina número combinatorio y no es necesario tomar en cuenta el orden en que se disponen los elementos para la resolución de los mismos. Ejemplo: ¿De cuantas formas se pueden colocar dos letras de la palabra música? La palabra música está compuesta por seis letras diferentes de las que tomaremos dos, entonces: Esto lo podemos comprobar exhaustivamente de la siguiente manera: M-U-S-I-C-A MU US SI IC CA MS UI SC IA MI UC SA MC UA MA Recordemos que el orden en que se disponen los elementos no importa, por lo que es lo mismo MU que UM. Ahora bien, hemos hablado de orden y repetición. Sabemos que en este tipo de problemas el orden no importa y la repetición esta restringida, entonces cabe preguntarnos ¿existe alguna regla que nos prohíba hacernos el siguiente planteamiento? ¿Cuál sería el resultado del problema anterior si tomamos dos letras que no estén seguidas una de otra? M-U-S-I-C-A Por el método exhaustivo nos da: MS UI SC IA MI UC SA MC UA MA Es decir diez maneras diferentes de agrupar las letras.

Ha resultado tarea sencilla encontrar la respuesta por el método mostrado, pero resulta evidente que no es la mejor manera de resolver este tipo de problemas si tenemos números grandes, por lo que debemos buscar otro método menos mecánico.

¡Eureka!

Entonces nuestra fórmula se convierte en:

Habíamos advertido con anticipación que por conveniencia usaríamos la nomenclatura C (m, n); ahora vemos el motivo que nos llevó a tomar tal decisión.

Pero, ¿Qué significa el superíndice sobre la C?, ¿De donde ha salido tan misteriosa fórmula?

Antes de darle una respuesta a la primera pregunta, daremos la siguiente fórmula:

Que no es mas que una forma extendida de , cuando k = 0. =

Donde el superíndice (k), nos indica la cantidad de elementos consecutivos a ser discriminados.

En la segunda versión del ejemplo se nos pedía encontrar las posibles formas que se pueden combinar dos letras de la palabra MUSICA, sin que se juntasen dos letras consecutivas. En otras palabras nos piden que excluyamos o discriminemos la letra que se encuentra al lado de su antecesora, es decir que tenemos un factor discriminante k = 1.

Resolver el siguiente ejercicio:

En una fila de 10 asientos, se desean disponer tres personas de forma tal que queden por lo menos dos asientos vacios de por medio entre cada persona. ¿De cuantas maneras diferentes pueden arreglarse?

Como quedan dos asientos vacios entre cada persona, k = 2.

Solución exhaustiva del problema

Imagínense tener que calcular de manera exhaustiva, eso nos tomaría un buen tiempo, que podemos reducir aplicando la fórmula genérica.

Lo que nos acuerda que no dimos respuesta a la segunda pregunta.

La fórmula genérica puede ser demostrada de forma "sencilla", el objetivo de estas páginas es dar a conocer dicha fórmula, por lo que consideramos que no es necesario incluir tal demostración, ya que la experiencia nos dice que muchos de los potenciales lectores jamás leerían estas páginas si cometiésemos la sensatez de incluirla en este documento.

 

 

Autor:

José Acevedo