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

...