Monografías
Publicar | Monografías por Categorías | Directorio de Sitios | Software Educativo | Juegos Educativos | Cursos On-Line Gratis

 

Combinatoria - Monografía



 
DESCARGA ESTA MONOGRAFÍA EN TU PC
Esta monografía en formato html para que puedas guardarla en tu pc e imprimirla.



Vínculo Patrocinado




Aquí te dejamos la descarga gratuita
Nota: para poder abrir archivos html solo necesitas tener instalado internet explorer u otro navegador web.




Matemáticas. Álgebra. Probabilidad. Permutaciones. Variaciones



TEORÍA COMBINATORIA



Principio de Conteo



A menudo se presenta la necesidad de calcular el número de maneras distintas en que un suceso se presenta o puede ser realizado. Otras veces es importante determinar la probabilidad de ocurrencia de un evento específico. En ambos casos se apela al sentido común, o se establecen métodos que permitan sistematizar tales cálculos. Con frecuencia el sentido común ayuda a entender por qué se eligió un procedimiento dado, mientras que la formalización del cálculo las vías para encontrar las soluciones apropiadas.

Iniciaremos nuestro estudio de teoría combinatoria enunciando los principios aditivo y multiplicativo de conteo.

Principio aditivo de conteo: Sean A y B dos sucesos que no pueden ocurrir simultáneamente. Si A ocurre de a maneras distintas y B ocurre de b maneras distintas, el número de maneras en el cual puede ocurrir A o B es A +B

Ejemplo: 12.1



Se tienen 6 banderas de señalización, dos rojas, dos verdes y dos azules. ¿Cuántas señales distintas pueden hacerse con una o dos banderas a la vez?

-  Solución:

Si denotamos las banderas rojas, verdes y azules por R, V y A, respectivamente, vemos que con una bandera a la vez se pueden hacer 3 señales distintas:
100666.gif

Con dos banderas a la vez se puede hacer las siguientes señales (sacando, por ejemplo, una primera y después la otra):

100667.gif

PRIMERA                           SEGUNDA
BANDERA                           BANDERA

Entonces, si se utilizan dos banderas, se pueden hacer 9 señales distintas. Luego, con una o dos banderas se podrán realizar 3+9= 12 señales diferentes. Observa que, como se establece en la definición, se trata de dos sucesos A y B descritos como:

A: Se hacen señales con una sola bandera
B: Se hacen señales con dos banderas.

Y que ambos no pueden ocurrir simultáneamente, ya que si se decide hacer señales con una bandera se descarta la segunda alternativa y viceversa.

Principio multiplicativo de conteo: Si un suceso puede ocurrir en a maneras e, independientemente, un segundo suceso puede ocurrir en b maneras, entonces el número de maneras en que ambos, A y B, pueden ocurrir ab.

A este principio también se le denomina principio fundamental de conteo.

Ejemplo 12.2



En la fig. 12.1 se demuestra distintas rutas para ir desde Cumaná hasta Caripe, desde Caripe hasta Maturín y desde Maturín hasta Ciudad Bolívar. ¿De cuántas maneras distintas puede irse desde Cumaná hasta Ciudad Bolívar?
La letra Rj ( j = 1,8) indica las distintas rutas.
100668.gif

Fig. 12.1 ¿De cuántas maneras distintas se puede ir desde Cumaná hasta Ciudad Bolívar?

* Solución:



Analicemos el problema a partir del principio fundamental del conteo:

Suceso A: Ir  desde Cumaná hasta Caripe. Hay 4 rutas distintas.
Suceso B: Ir  desde Caripe hasta Maturín. Hay 2 rutas distintas.
Suceso C: Ir desde Maturín hasta Ciudad Bolívar. Hay 2 rutas distintas.

Los distintos sucesos, A,B,C, son independientes, ya que la selección de una ruta determinada de una ciudad a otra no depende de la anterior.

Luego, para ir desde Cumaná hasta Ciudad Bolívar pueden seleccionarse 4. 2.2 =16 rutas diferentes. Estas posibles rutas son:

R   R   R       R   R   R      R   R   R     R   R   R

R   R   R       R   R   R      R   R   R     R   R   R

R   R   R       R   R   R      R   R   R     R   R   R

R   R   R       R   R   R      R   R   R     R   R   R

Ejemplo: 12.3



Un agente gubernamental tiene que inspeccionar los ferrys que hacen la travesía entre la isla de Margarita y tierra firme. Para ello se embarca en Punta de Piedras, en dicha isla, y debe abordar cualquier de las 9 unidades disponibles y luego regresarse en un ferry distinto. ¿De cuántas maneras puede el inspector ir desde Margarita a tierra firme y luego regresar?

* Solución



Si llamamos U , U , U , U , U , U , U , U , y U  a las unidades, el inspector tiene 9 maneras de venirse desde Margarita a tierra firme seleccionando uno de los nueve ferrys. Una vez en tierra firme, como no puede devolverse para Margarita en el mismo ferry en que se vino, tiene 8 posibilidades distintas. Entonces hay 9 x 8 =72 maneras distintas de que el agente puede cumplir su función. Estas distintas posibilidades son:

U  U      U  U      U  U      U  U      U  U      U  U      U  U    U  U

U  U      U  U      U  U      U  U      U  U      U  U      U  U    U  U

U  U      U  U       U  U     U  U      U  U      U  U      U  U    U  U

U  U      U  U       U  U     U  U      U  U      U  U      U  U    U  U

U  U     U  U        U  U     U  U      U  U      U  U     U  U    U   U

U  U     U  U        U  U     U  U      U  U      U  U      U  U    U  U

U  U     U  U        U  U      U  U      U  U      U  U      U  U    U  U

U  U      U  U       U  U      U  U      U  U      U  U      U  U    U  U

U  U      U  U       U   U      U  U      U   U    U  U      U  U    U  U

Ejemplo:  12.4



Tres profesores de Matemática del liceo Andrés Bello de Caracas van a ser asignados a cuatro secciones distintas. ¿ De cuántas maneras distintas pueden asignarse los profesores si cada uno puede tomar sólo una sección?

* Solución:



Designemos a tres profesores por P , P , y P  y  a las distintas secciones por S , S , S, y S . El primer profesor seleccionado puede ser asignado a cualquiera de los 4 cursos. Quedan así 3 cursos que puede ser asignado el primer y segundo profesor.

Por tanto, los tres profesores pueden ser asignados de 4×3x2= 24 maneras distintas a los cuatro cursos. Si designamos Pj  Sj  ( i = 1,2,3,j =1,2.,3,4) a las distintas combinaciones profesor- curso, las posibilidades se muestran a continuación:
100669.gif

Permutaciones



Estudiaremos a continuación una aplicación directa del principio fundamental del conteo. Supongamos que tenemos los objetos distintos, a, b y c, y que queremos saber de cuantas maneras distintas se pueden agrupar tomados tres a la vez. El primer elemento seleccionado puede ser a, b, o c y, por tanto, tenemos 3 maneras distintas de seleccionar el primer elemento.

Una vez seleccionado el primer elemento, tenemos dos elementos para escoger, es decir, dos maneras distintas de seleccionar el segundo elemento, sólo queda uno y, por tanto, una sola manera de seleccionar el tercer elemento. En definitiva, hay:

3.2.1=6 maneras distintas de agrupar los 3 elementos.

Veamos cuáles son esas agrupaciones distintas:
100670.gif

Observamos que las agrupaciones mostradas no incluyen elementos repetidos y descartan, por lo tanto, selecciones de la forma aab, acc, etc. En este libro consideraremos sólo agrupaciones sin repetición. Si el número de elementos es 4, las agrupaciones que puedan formarse son:

4.3.2.1= 24

En general, si hay n elementos, el número de agrupaciones distintas, designado por P y denominado permutaciones de n elementos, es:

P  = n ( n-1 ) (n-2)… 3.2.1 =n!

Ejemplo: 12.5



a)  En una elección hay 8 candidatos. ¿Cuántos resultados distintos pueden tener lugar una vez efectuada la votación?

b)  ¿ De cuántas maneras distintas pueden colocarse 5 libros en una biblioteca? Escribe 4 de esas agrupaciones.

*  Solución



a)  Es posible obtener:

P  = 8! = 8.7.6.5.4.3.2.1 = 40.320 resultados.

b)  Los libros pueden colocarse de:

P = 5! = 5.4.3.2.1= 120 maneras distintas.

Si llamamos L  , L  , L   ,L   ,y  L  a los libros, 4 agrupaciones distintas son:

L    L   L   L   L                 L   L   L   L   L                     L   L   L   L   L                  L   L   L   L   L

Observemos que las permutaciones se cumple lo siguiente:

a.  En las agrupaciones intervienen todos los elementos.
b.  Dos agrupaciones son distintas si el orden en que aparecen los elementos difieren.

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 :

100671.gif

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)

100672.gif

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

100673.gif

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:

100674.gif

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!

Combinaciones



Consideremos cuatro elementos, A, B, C, y D, y veamos nuevamente las distintas agrupaciones que se pueden formar si se forman grupos de 1, 2, 3 y 4 elementos:

100675.gif

En las agrupaciones estudiadas, permutaciones y variaciones, los grupos que contenían los mismos elementos eran distintos cuando el orden no era el mismo.

Cuando hablamos de combinaciones, las agrupaciones que tengan el mismo número de elementos son iguales, independientemente del orden que ocupan dichos elementos. A las combinaciones de m elementos tomados de n en n se les denota como C    .Así, en el caso anterior, se obtienen las siguientes combinaciones distintas :

Corresponde a:

Grupos de 1 :         A         B        C        D                                                         V   =  4

Grupos de 2 :         AB       AC      AD                                                                 V    = 6
BC       BD      CD

Grupos de 3 :         ABC    ABD     ACD    BCD                                                 V     = 4

Grupos de 4 :        ABCD                                                                                   V    = 1

Si hacemos una comparación para amos casos, variaciones y combinaciones, obtenemos para las agrupaciones de los elementos A, B, C y D la siguiente tabla:

Número de elementos (n)         Variaciones ( v    )          Combinaciones  ( C   )

1                                         4                                         4
2                                       12                                         6
3                                       24                                         4
4                                       24                                         1

Si analizamos la tabla anterior, nos damos cuenta que el número de variaciones se obtiene multiplicando el número de combinaciones por n!, por lo que podemos obtener la tabla:

n         n!          C          V

1         1           4           4
2         2          6          12
3         6          4          24
4       24           1         24

En general, el número de variaciones de m elementos, tomando de n en n, está dado por:

V    = n!  . C

Como P  =  n!:

V     = P .    C

Despejando C    :                  C           V
P

Finalmente, se obtiene:

100676.gif

Ejemplo 12. 11



Se tienen 12 jugadores de béisbol y se van a seleccionar 9 para formar un equipo. ¿ Cuántos equipos distintos pueden formarse?

*  Solución



Este es un problema de combinaciones, ya que un equipo es distinto a otro se difiere al menos en un jugador. Por tanto, el número de equipo es :

C     =   12!             9!  10 . 11 . 12    =   220
9! ( 12 - 9 )!                    9! 2. 3

Ejemplo 12.12



Se tienen 5 puntos en un plano ubicados de forma tal que no hay tres de ellos en línea recta. ¿ Cuántas líneas pueden dibujarse entre dichos puntos? Dibuja las tres distintas líneas.

* Solución



Se trata, en este caso, de seleccionar 2 puntos de los 5 posibles. Cada dos puntos dan origen a una línea distinta. El número de líneas es:

C  =    12!           9! 10. 11 . 12  = 220
9! (12 -9)               9! 2 . 3

En la figura 12.1 se muestra las diferentes alternativas.

100677.gif

Fig. 12.1 Entre 5 puntos se pueden
dibujar C    = 10 líneas distintas.





Creative Commons License
Estos contenidos son Copyleft bajo una Licencia de Creative Commons.
Pueden ser distribuidos o reproducidos, mencionando su autor.
Siempre que no sea para un uso económico o comercial.
No se pueden alterar o transformar, para generar unos nuevos.

 
TodoMonografías.com © 2006 - Términos y Condiciones - Esta obra está bajo una licencia de Creative Commons. Creative Commons License