Tecnicas_Combinatorias

Probabilidad y sus aplicaciones
en ingenier´ inform´tica
ıa
a

V´ctor Hern´ ndez
ı
a
Eduardo Ramos
Ildefonso Y´ nez
a˜

c V´ctor Hern´ ndez, Eduardo Ramos, Ildefonso Y´ nez
ı
a
a

´
EDICIONES ACADEMICAS

Probabilidad y sus aplicaciones en Ingenier´ Inform´tica
ıa
a
Otro ejemplo, si B = “el primer resultado es el doble del segundo”, se tiene P(B) =
3/36, ya que hay 36casos posibles y s´ lo tres casos favorables a que el primer
o
q
q q q qq q q
resultado sea el doble del segundo, B = { q q , q q q , q q q q }.
q
En el C´ lculo de probabilidades, es costumbre reservar la expresi´ n “al azar” para refea
o
rirse a un experimento aleatorio uniforme. Si decimos “se escoge al azar un elemento entre los
elementos de Ω”, debe entenderse que cada elemento puede serescogido con igual probabilidad. Nosotros emplearemos el adjetivo “equilibrado ” para designar a un dado, una moneda o
cualquier otro ingenio cuyos resultados posibles sean intercambiables. As´, la expresi´ n “lanı
o
zamos un dado equilibrado ” nos informa que cada uno de los seis resultados posibles tiene la
misma probabilidad de ocurrir. Naturalmente, tambi´ n consideraremos modelos nouniformes;
e
por ejemplo, el dado del ejemplo 1.5.3 est´ desequilibrado.
a

1.8. Tres t´cnicas combinatorias
e
Contar es hallar el n´ mero de elementos de un conjunto. La Combinatoria es el arte de
u
contar. Es un arte en cuanto que resolver problemas combinatorios no es autom´ tico, sino que
a
depende de nuestra experiencia y entrenamiento. En este apartado presentamos tres t´ cnicas
ecombinatorias elementales que bastan para resolver casi cualquier problema de nivel elemental y medio que se nos pueda plantear. Los problemas de combinatoria elemental, con ser
sencillos, no son banales. Creemos que una de las principales dificultades que los estudiantes encuentran al intentar resolverlos es la pretensi´ n de reducirlos a los conocidos modelos:
o
combinaciones, permutaciones yvariaciones, idem con repetici´ n. Estos seis modelos son deo
masiado r´gidos y s´ lo cubren una peque˜ a parte de los problemas que necesitamos resolver.
ı
o
n
Por el contrario, los tres m´ todos que mostraremos se adaptan con facilidad y son suficientes
e
para los problemas que se nos plantean en este nivel.
1.8.1.

Contar con los dedos

Las primeras veces que contamos lo hacemos conlos dedos. De esa forma establecemos
una correspondencia biyectiva entre el conjunto problema y un subconjunto de los primeros
n´ meros naturales. Nuestros dedos sirven de patr´ n para contar cualquier conjunto peque˜ o.
u
o
n
La Matem´ tica nos proporciona otros dedos y el primer m´ todo general para contar es estaa
e
blecer una correspondencia biyectiva entre un conjunto problema A y otroconjunto patr´ n de
o
la forma {1, 2, . . . , n}.

EJEMPLO 1.5
Para contar cu´ ntos n´ meros enteros hay entre 3 y 25, ambos
a
u
incluidos, establecemos la correspondencia biyectiva:
3

4

5

......

24

25

1

2

3

......

22

23

y concluimos que hay 23 n´ meros. Esta observaci´ n se puede hacer general sin
u
o
mucho esfuerzo. Si m ≤ n, la correspondenciabiyectiva:
m

m+1

m+2

......

n = m+n−m

1

2

3

......

n−m+1

nos demuestra que entre m y n, ambos incluidos, hay n − m + 1 n´ meros. Otro
u
ejemplo, si queremos contar cu´ ntos n´ meros pares son mayores que 1 y menores
a
u

13

14

Experimentos aleatorios
que 123, y establecemos la correspondencia biyectiva
2 = 2·1

4 = 2·2

6 = 2·3

......

122 = 2 ·61

1

2

3

......

61

concluiremos que hay 61 n´ meros.
u
1.8.2.

Contar palabras

Frecuentemente, los elementos del conjunto cuyo cardinal queremos hallar pueden ser
interpretados como secuencias o palabras formadas por s´mbolos que pertenecen a un alfabeı
u
to dado y que cumplen ciertas restricciones. Cuando esto ocurre, podemos contar el n´ mero
de palabras mediante...