Lectura Tecnicas de Conteo

Unidad 1: MODELOS PARA EL AZAR I (DISCRETOS) Taller 1: MODELO BINOMIAL Lectura 2: TECNICAS DE CONTEO

1

LECTURA N 2

TCNICAS DE CONTEO

Principio Multiplicativo y Principio Aditivo: Motivamos estos principios a partir de un par de

ejemplos.

Ejemplo 1: Para viajar en transporte pblico entre Santiago y Antofagasta existen 2 lneas areas y

5 de buses. De cuntas maneras se puede escoger una lnea de transporte para viajar entre

Santiago y Antofagasta?.

Si viaja va area tiene 2 alternativas, mientras si viaja va terrestre tiene 5. En consecuencia, se

dispone de 2 + 5 = 7 lneas de transporte para viajar entre Santiago y Antofagasta.

El ejemplo anterior ilustra el llamado Principio Aditivo, el cual dice:

Si una decisin d1 puede ser tomada de m maneras y una decisin d2 de n maneras, entonces el

nmero de maneras en que pueden tomarse las decisiones d1 o d2 es m + n

En el ejemplo, para viajar en transporte pblico entre Santiago y Antofagasta pueden tomarse las

decisiones:

d1: viajar en una lnea area

d2: viajar en una lnea de buses,

Como la decisin d1 puede ser tomada de dos maneras y d2 de 5 maneras, entonces el nmero de

lneas de transporte pblico para viajar (es decir, tomar las decisiones d1 o d2) es 2 + 5 = 7.

Ejemplo 2: En un grupo de 5 alumnos hay 3 mujeres y 2 hombres. Cuntas parejas ( diferente

sexo) pueden formarse en este grupo?

Llamaremos m1, m2, m3 a las mujeres y h1, h2 a los hombres. Una posible pareja que puede

formarse es hombre h2 y mujer m3. Este resultado lo anotamos {h2 , m3}. Siguiendo esta notacin,

mostramos el total de parejas que pueden formarse:

{h1 , m1} , {h1 , m2} , {h1 , m3} , {h2 , m1} , {h2 , m2} , {h2 , m3}

Notemos que hay 3 casos en los cuales el hombre es h1 y otros 3 casos en los cuales el hombre es

h2. O sea, el nmero de parejas que pueden formarse es 3+3 = 2 x 3 = 6.

Este ltimo ejemplo ilustra el llamado principio multiplicativo, el cual dice:


2

Si una decisin d1 puede ser tomada de p maneras y si, una vez tomada la decisin d1, una decisin

d2 puede ser tomada de q maneras, entonces el nmero de maneras en que se pueden tomar las

decisiones d1 y d2 es p x q.

En el ejemplo anterior, para formar las parejas se deben tomar las decisiones:

d1: escoger un hombre,

d2: escoger una mujer.

Como la decisin d1 puede ser tomada de 2 maneras y, despus de esto, d2 puede ser tomada de 3

maneras, entonces el nmero de maneras en que pueden formarse las parejas ( es decir, tomar las

decisiones d1 y d2 ) es 2 x 3 = 6.

Cabe sealar que el Principio Multiplicativo permite obtener el nmero de elementos del conjunto

constituido por todas las parejas posibles, sin que sea necesario mostrar explcitamente sus

elementos. En todo caso, dicho conjunto es

{h1 , m1} , {h1 , m2} , {h1 , m3} , {h2 , m1} , {h2 , m2} , {h2 , m3}

Los Principios Aditivo y Multiplicativo fueron enunciados para dos decisiones, pero tambin

pueden ser aplicados (inductivamente) con r decisiones.

Ejemplo 3: 5 estacionamientos en lnea desocupados, numerados del 1 al 5. Slo 2 autos digamos

A y B, escogen al azar donde estacionar. Calcular la probabilidad de que:

i) A elija el nmero 1,

ii) Uno de los dos elija el nmero 1,

iii) Los dos autos elijan estacionamientos contiguos.

Ejemplo 4: Cuntos nmeros naturales de 4 dgitos ( en base 10) pueden formarse usando

solamente los dgitos 2, 3, 4, 5 y de modo que sean menores que 4000 y divisibles por 5?

Usamos el Principio Multiplicativo con las 4 decisiones siguientes.

d1: escoger el ltimo dgito,

d2: escoger el primer dgito,


3

d3: escoger el segundo dgito,

d4: escoger el tercer dgito.

La decisin d1 puede ser tomada de 1 sola forma (tiene que ser el 5, pues el nmero debe ser

divisible por 5).

La decisin d2 puede ser tomada de 2 maneras (puede ser el nmero 2 o el 3 ya que el nmero que

se forme debe ser menor que 4000).

La decisin d3 puede ser tomada de 4 maneras (hay 4 nmeros disponibles y no se tiene ninguna

restriccin). Similarmente, la decisin d4 puede ser tomada de 4 maneras.

En consecuencia, el Principio Multiplicativo implica que hay 1 x 2 x 4 x 4 = 32 nmeros de cuatro

dgitos con las restricciones antes mencionadas.

El conjunto con los 32 nmeros en cuestin es:

{2225, 2235, 2245, 2255, 2325, 2335, 2345, 2355,

2425, 2435, 2445, 2455, 2525, 2535, 2545, 2555,

3225, 3235, 3245, 3255, 3325, 3335, 3345, 3355,

3425, 3435, 3445, 3455, 3525, 3535, 3545, 3555}.

Reiteramos que no es necesario mostrar explcitamente los 32 elementos.

NMEROS FACTORIALES

Se define 0! = 1 y para cada n entero positivo, n! se define recursivamente como el nmero

natural

n! = ( n 1 )! n

As por ejemplo,

1!0!1 2212!1!2 6323!2!3 24464!3!4

!2!3!23 2!4

!8 2730151413

!12

151413!12

!12

!15


4

99

991

10099

991!98

10099!98

99!98!98

10099!98

!99!98

!100

Ejemplo 5: Si disponemos de los objetos , , , De cuntas maneras es posible ordenar estos objetos?.

A continuacin mostramos las 6 posibles ordenaciones:

, , , , , .

Consideremos las siguientes decisiones.

d1: escoger primer objeto ( 3 formas posibles, pues se puede escoger cualquiera de los 3 objetos),

d2: escoger segundo objeto (2 formas posibles, pues se dispone de 2 objetos, ya que uno fue

utilizado en la primera decisin),

d3: escoger tercer objeto ( 1 forma posible, pues se dispone de un objeto ya que dos fueron

utilizados en la primera y segunda decisin).

Entonces, el nmero de posibles ordenamientos de los tres objetos corresponde al nmero de

maneras en que pueden tomarse las decisiones d1, d2 y d3. As, Principio Multiplicativo implica que

hay 3 x 2 x 1 = 6 ordenamientos posibles.

Consideremos ahora n objetos distintos, y para cada ni ,...,1 , la decisin i

d : escoger el i-

simo objeto.

La decisin 1

d , es decir, escoger el primer objeto, puede ser tomada de n maneras (se puede

escoger cualquiera de los n objetos).

La decisin 2

d , es decir escoger el segundo objeto, puede ser tomada de n 1 maneras ( hay n-1

objetos disponibles ya que uno fue utilizado en la primera decisin).

En general, la decisin i

d , es decir, escoger el i-simo objeto, puede ser tomada de

1 in maneras (quedan 1 in objetos, pues se han usado 1i objetos en las 1i

decisiones anteriores).

En consecuencia, Principio Multiplicativo implica que el nmero de maneras en que es posible

ordenar n objetos distintos es .11 nn


5

Recordemos que por definicin, 0! = 1 y para cada n entero positivo n ! = n 21 , por lo que el

nmero de maneras en que es posible ordenar n objetos distintos es n !. Es comn llamar a cada

una de estas ordenaciones de n objetos, permutacin de n objetos distintos.

Ejemplo 6: Cuntos anagramas es posible formar con las letras del nombre KENO?

Cada anagrama que formamos con el nombre KENO no es ms que una ordenacin de las letras K,

E, N, O. As, el nmero de palabras es 4! = 24.

Las siguientes son los 24 anagramas que se pueden formar:

KENO, KEON, KNEO, KNOE, KOEN, KONE,

EKNO, EKON, ENKO, ENOK, EOKN, EONK,

NKEO, NKOE, NOKE, NOEK, NEKO, NEOK,

OKEN, OKNE, OEKN, OENK, ONKE, ONEK.

Ejemplo 7: Cuntos anagramas es posible formar con las letras del nombre KENO de modo que

las vocales estn juntas?.

Cada anagrama que formemos no es ms que una ordenacin de tres objetos: K, N y el bloque

EO. As, el nmero de anagramas sera 3! = 6. Pero tambin se puede considerar como bloque a

OE. Por lo tanto el nmero de anagramas es 12.

Ejemplo 8: Tres lpices y tres nios. Calcule la probabilidad de que:

i) Todos los nios reciban su respectivo lpiz

ii) Todos los nios reciban su lpiz cambiado

iii) Slo un nio recibe su propio lpiz

Ejemplo 9: Repita i) y iii) del ejemplo 3, pero con tres autos, digamos A, B y C.


6

COMBINATORIA

Calcular el valor de las siguientes expresiones.

!01!0

!1

!11!1

!1

!02!0

!2

!12!1

!2

!22!2

!2

!03!0

!3

!13!1

!3

!23!2

!3

!33!3

!3

!04!0

!4

!14!1

!4

!24!2

!4

!34!3

!4

!44!4

!4

!05!0

!5

!15!1

!5

!25!2

!5

!35!3

!5

!45!5

!5

!55!5

!5

Los valores obtenidos ordenarlos en el tringulo de Pascal. Deducir una forma general.

Para r natural y 0kr, definir el nmero natural !!

!

krk

r

k

r

De la definicin observar que, para todo r natural,

10

r, 1

r

r, r

r

1, r

r

r

1,

kr

r

k

r

Adems, la relacin en la construccin del Tringulo de Pascal se traduce en

k

r

k

r

k

r

1

1

Extensiones:

Conectar con el nmero de maneras de escoger k objetos desde un total de n (sin

reposicin y sin importar orden).


7

Ver el caso anterior, pero con orden. Conectar con decisiones

Conectar con permutaciones con repeticiones.

Documents

Lectura Tecnicas de Conteo