Teoria Combinatoria

TEORIA COMBINATORIA:

La Combinatoria es una rama de las matemáticas cuyo objeto es estudiar las posibles agrupaciones de objetos que podemos llevar a cabo de un modo rápido teniendo en cuenta las relaciones que deben existir entre ellas.

La Teoría Combinatoria es la parte de Matemáticas que se encarga de crear grupos de datos, objetos, etc., y además de llevar a cabo los cálculos necesarios.

Entre las diferentes formas que hay para llevar a cabo estos agrupamientos tenemos las: Variaciones, Permutaciones y Combinaciones.

VARIACIONES SIN REPETICIÓN

Llamamos variaciones a los distintos grupos de elementos que podemos formar tomados de n en n de un total de m elementos.

Ejemplo:

¿Cuántos grupos de 2 cifras (n) podemos formar con las tres primeras cifras (m)?

Sirviendo de un diagrama de árbol podemos hacer:

Los grupos de 2 elementos son: 12, 13, 21, 23, 31 y 32

Variaciones

Consideremos cuatro elementos, A,B,C y D, y veamos cuántas agrupaciones pueden formarse si se toman dichos elementos uno, dos, tres y cuatro a la vez. Al número de elementos, en este caso 4, lo denotamos por la letra m ( m= 4).

a. Si se toma un elemento a la vez, el número de agrupaciones que se puede formar es 4:

A B C D

Se dice que se han formado las variaciones de 4 elementos tomados de uno en uno, lo cual se representa como V Observa que:

V = 4

b. Si se toman dos elementos a la vez, se tienen las siguientes agrupaciones:

AB BA CA DA

AC BC CB DB

AD BD CD DC

Se han formado así las variaciones de 4 elementos tomando de dos en dos, entonces:

V = 12

Observa que:

V = V . ( 4 - 1)

V = 4. (4 -1) = 4.3 = 12

c.Si se toman 3 elementos de los 4, obtenemos las siguientes agrupaciones:

ABC BAC CAB DAB

ABD BAD CAD DAC

ACB BCA CBA DBA

ACB BCD CBD DBC

ABD BDA CDA DCA

ADC BDC CDB DCB

El número de agrupaciones es:

V = V . ( 4 - 2)

V = 4. ( 4 - 2) . ( 4 - 2 ) = 24

d. Si se toman 4 elementos de los 4, obtenemos las siguientes agrupaciones:

ABCD BACD CABD DABC

ABDC BADC CADB DACB

ACBD BCAD CBAD DBAC

ACDB BCDA CBDA DBCA

ADBC BDAC CDAB DCAB

ADCB BDCA CDBA DCBA

El total de agrupaciones resulta en este caso igual a:

V = 4. ( 4 -1 ) . ( 4 - 2) . ( 4 - 3) = 4.3.2.1 = 24

El ejemplo estudiado indica que :

V = 4

V = 4.3 V = V . 3

V = 4.3.2 V = V . 2

V = 4.3.2.1 V = V . 1

En general, para m elementos podemos escribir:

V = m

V = m ( m -1 ) V = V . (m -1 )

V = m ( m -1 ) (m - 2 ) V = V. ( m -2)

.

.

.

V = m (m -1 ) ( m - 2 ) ... (m - n + 1 ) V =V . ( m - n + 1 )

De acuerdo a lo anterior, la relación :

V = m ( m - 1 ) ( m - 2 ) ... ( m - n + 1 )

Permite determinar las variaciones de m elementos tomados de n en n . Si en la relación (12.2) multiplicación y dividimos el numerador y denominador por ( m- n)!, obtenemos :

m ( m - 1 ) ( m - 2 ) ... ( m - n + 1 ) (m - n ) !

V =

( m - n ) !

Ahora bien, de acuerdo a ( 11.4 ) , ( m - n ) ! puede escribirse como:

( m - n ) ! = ( m - n ) ( m- n - 1 ) ( m- n - 2 ) ... 3.2.1

Sustituyendo en ( 12. 3)

m (m - 1 ) ( m -2 )... ( m - n + 1 ) (m - n) ( m- n -1 ) ( m - n - 2 ) ... 3.2.1

V=

(m - n ) !

El numerador de (12.5) es m ! y, por tanto,

V = m!

(m -n )

Es importante notar lo siguiente, que en el caso de variaciones de m elementos tomados de n en n :

a. De los m elementos, sólo n intervienen en las agrupaciones.

b. Las agrupaciones de n elementos son distintas si distintas si difieren en el orden de colocación.

Ejemplo 12.6

Determina:

a) V b) V c) V

* Solución

a) V 7! = 4! 5. 6. 7 = 210

( 7 - 3 ) ! 4!

b) V ( x + 1 ) ! x! ( x + 1 )

( x + 1 - 1 ) ! x !

c) V ( m - n ) ! ( m - n + 2 ) ! ( m - n )! ( m - n + 1 ) ( m - n + 2 )

V m! (m- n ) ( m- n )!

(m - n + 2 )!

= (m - n + 1) ( m - n +2 )

Ejemplo 12. 7

¿ De cuántas maneras se pueden agrupar 5 bolas de distintas colores?

* Solución

Si las bolas colores distintos, digamos amarillo (A), rojo , negro (N), verde (V) y marrón (M), se trata de permutarlas para obtener agrupaciones diferentes. Así serían distintas las agrupaciones.

ARNVM MVARN NRAMV RAVNM

El número total de maneras distintas es:

P = 5 ! = 1 . 2 . 3 . 4 . 5 = 120

Ejemplo 12. 8

10 personas se van sentar en 4 sillas. ¿ De cuántas maneras pueden hacerlo?

* Solución

De las 10 personas se van a seleccionar 4 y estas 4 personas pueden cambiarse entre si de asientos. Se trata entonces de . Observa que agrupaciones como P P P P y P P P P son distintas. Luego, el número de agrupaciones son:

10! = 6! 7. 8 . 9. 10 = 5.040

6! 6!

Ejemplo 12.9

¿ Cuántos números de 4 dígitos pueden formarse con los números 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 si ninguno de ellos puede repetirse?

* Solución

Los números no pueden comenzar por cero, ya que se formarían números tales como 0358, que correspondería al número de tres cifras 358. por tanto, el primer dígito puede ser seleccionado sólo de 9 maneras distintas ( se excluye al cero ). Una vez seleccionado el primer dígito, los tres pueden ser seleccionados en V maneras diferentes. Por tanto, se pueden formar:

9. V = 9. 9! = 9 . 6! 7 . 8 . 9 = 7 . 8 . 9 . 9 = 4.536 números de cifras

6! 6!

Ejemplo 12.10

¿Cuántos números de 4 dígitos pueden formarse con los números 0, 1, 2, 3 , 4, 5, 6, 7, 8, y 9 si el último debe ser cero y ninguno puede repetirse?

* Solución

En este caso, el cero se fija al final del número y quedan tres posiciones que llenar y 9 números para escoger. Luego se puede formar:

V = 9! = 6! 7 . 8 . 9 = 504 números de 4 cifras.

6! 6

Permutaciones

Estudiaremos a continuación una aplicación

...