INTEGRANTES:

2º HUMANIDADES

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:

R

V

A

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

R R

R V

R A

V R

V V

V A

A R

A V

A A

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.

Cumaná

Caripe Maturín Ciudad Bolívar

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 4x3x2= 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:

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:

Primera Segunda Tercera

Selección Selección Selección

ab abc

ac ac

Primera Segunda Tercera

Selección Selección Selección

bc bca

ba bac

ca cab

cb cba

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 :

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!

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:

Grupos de 1 : A B C D V = 4

Grupos de 2: AB AC AD BC V = 12

BA CA DA BD

CB CD DB DC

Grupos de 3: ABC ABD ACD BCD V = 24

ACB ADB ADC BDC

BAC BAD CAD CBD

BCA BDA CDA CDB

CAB DAB DAC DBC

CBA DBA DCA DCB

Grupos de 4: ABCD BACD CABD DABC V = 24

ABDC BADC CADB DACB

ABCD BACD CBAD DBAC

ACBD BCAD CBDA DBCA

ACDB BCAC CDAB DCAB

ADCB BDCA CDBA DCBA

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:

C = m!

n! (m - n )!

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.

Fig. 12.1 Entre 5 puntos se pueden

dibujar C = 10 líneas distintas.