A maior rede de estudos do Brasil

Grátis
179 pág.
Análise combinatória matemática

Pré-visualização | Página 14 de 30

de la identidad(
k
m
)(
t
k
)
=
(
t
m
)(
t−m
t− k
)
, (m ≤ k ≤ t),
5.3. Algunas aplicaciones 67
tendremos que la última expresión se reduce a(
t
m
) [(
t−m
t−m
)
−
(
t−m
t− (m+ 1)
)
+− · · ·+ (−1)t−m
(
t−m
t− t
)]
.
La expresión entre corchetes “[ ]” es igual al desarrollo bino-
mial (1−1)t−m = 0, de acuerdo al corolario 21 (ver el caṕıtulo
3). Luego, cuando t > m, la contribución del elemento a en
la parte derecha de la ecuación (5.4) es igual a 0. Esto im-
plica que la parte derecha de la ecuación (5.4) coincide con
el número de elementos de S que satisfacen exactamente m
de las propiedades de P .
Una consecuencia inmediata del teorema anterior es pre-
cisamente la fórmula de inclusión y exclusión de Bernoulli-
Sylvester-da Silva, llamada también criba de inclusión-exclu-
sión, mencionada en la sección anterior. En efecto:
Teorema 41 (Criba de inclusión-exclusión) El número
de elementos de S que no satisface ninguna de las propiedades
(5.1) es igual a
E(0) = W (0)−W (1) +− · · ·+ (−1)nW (n)
= N −N(p1)−N(p2)−N(p3)− · · ·
+N(p1, p2) +N(p1, p3) +N(p1, p4) + · · ·
−N(p1, p2, p3)−N(p1, p2, p4)− · · ·
+ · · ·
Demostración: Claramente se trata del caso m = 0 del
teorema precedente.
5.3 Algunas aplicaciones
5.3.1 Coloreando una casa
En la Figura 5.1 se presenta el plano esquemático de una casa
con 4 habitaciones H1, H2, H3 y H4, intercomunicadas por 5
68 Caṕıtulo 5. Principio de inclusión y exclusión
puertas p1, p2, p3, p4 y p5. Supongamos que disponemos dem
colores para colorear las habitaciones. ¿De cuántas maneras
distintas podemos colorearlas, si respetamos la restricción
que las habitaciones contiguas (aquellas comunicadas por al-
guna puerta) deben tener colores diferentes?
p1
p2
p3
p4
p5
H1
H2
H3
H4 •
•
•
•
p1
p2
p4
p5
p3H1 H4
H2
H3
Figura 5.1: Casa con 4 habitaciones H1, . . . , H4 y y 5 puertas
p1, . . . , p5. A la derecha se representa la situación con un grafo.
Definimos las propiedades q1, q2, q3, q4 y q5, donde qi
se cumple si las habitaciones a ambos lados de la puerta
pi tienen el mismo color. Luego, andamos buscando todas
aquellas coloraciones de las habitaciones en las cuales no se
cumplan ninguna de las propiedades q1, . . . , q5, esto es,
N(q′1, q
′
2, q
′
3, q
′
4, q
′
5) = W (0)−W (1)+W (2)−W (3)+W (4)−W (5).
Analicemos cada uno de los términos W (i) por aparte:
(a) W (0) = m4, pues en ausencia de restricciones cada una
de las 4 habitaciones puede ser pintada de m maneras
diferentes.
(b) W (1) =
∑
iN(qi) = 5m
3, pues si se cumple la condición
qi entonces las habitaciones contiguas a la puerta pi
tendrán el mismo color (m posibilidades), mientras que
las restantes 2 habitaciones tendrán m2 posibilidades
de coloración.
(c) W (2) =
∑
i<j N(qi, qj) = (
5
2)m
2, pues si se cumplen
las condiciones qi y qj simultáneamente, entonces las
tres habitaciones que colindan con las puertas pi y pj
5.3. Algunas aplicaciones 69
tendrán el mismo color (m posibilidades) y la habitación
restante tendrá m posibilidades de coloración.
(d) W (3) =
∑
i<j<k N(qi, qj , qk) = 2m
2+[(53)−2)]m, pues
las puertas p1, p2, p3 interconectan tres (y no cua-
tro) habitaciones, al igual que las puertas p3, p4, p5.
Las otras tripletas de puertas interconectan todas las 4
habitaciones.
(e) W (4) =
∑
i<j<k<lN(qi, qj , qk, ql) = (
5
4)m, pues siem-
pre cuatro puertas interconectan a las cuatro habita-
ciones.
(f) W (5) = N(q1, q2, q3, q4, q5) = m.
Luego, simplificando, obtenemos
N(q′1, q
′
2, q
′
3, q
′
4, q
′
5) = m
4 − 5m3 + 8m2 − 4m.
5.3.2 Desarreglos y problema de los reencuentros
Sea (a1, a2, . . . , an) una permutación de n elementos numer-
ados por 1, 2, . . . , n. Decimos que esta permutación es un
desarreglo si ai 6= i, para todo i ∈ {1, 2, . . . , n}. Luego, un
desarreglo es una permutación en la cual ningún elemento
queda en su posición original.
El famoso Problema de los Reencuentros (planteado por
Montmort) plantea calcular el número de tales desarreglos.
Sea D(n) este número. Podemos evaluar D(n) empleando la
criba de inclusión-exclusión. Para ello, consideremos S como
el conjunto de las n! permutaciones (a1, a2, . . . , an), y para
cada i ∈ {1, 2, . . . , n} sea pi la propiedad “la permutación
(a1, a2, . . . , an) satisface ai = i”. Entonces:
N(pi1 , pi2 , . . . , pir) = (n− r)!,
mientras que
W (r) =
(
n
r
)
(n− r)! = n!
r!
.
70 Caṕıtulo 5. Principio de inclusión y exclusión
Luego, obtenemos la siguiente fórmula para Dn:
Dn = n!
(
1− 1
1!
+
1
2!
− · · ·+ (−1)n 1
n!
)
. (5.5)
Teniendo en cuenta el desarrollo asintótico de e−1,
e−1 = 1− 1
1!
+
1
2!
− 1
3!
+− · · · ,
obtenemos entonces que
Dn
n!
− e−1 = (−1)n 1
(n+ 1)!
± · · · ,
de dondeDn/n! difiere de e−1 en menos que 1/(n+1)!. Luego,
n!/e es una buena aproximación para Dn. Algunas aplica-
ciones sencillas del problema de los reencuentros se mencio-
nan a continuación.
1. El problema de las torres en el tablero de ajedrez : el
número de distintas maneras en que se puede colocar
8 torres en un tablero de ajedrez, de manera tal que
ninguna torre ataque a otra y que la diagonal principal
blanca se encuentre libre de torres, es igual a D8 =
14, 833 maneras.
2. El problema de los abrigos: n personas que asisten al
teatro dejan sus abrigos en el guardarropa. Los abrigos
son mezclados y al final de la función son devueltos al
azar. ¿Cuál es la probabilidad de que ninguna persona
reciba su propio abrigo? La respuesta es, naturalmente,
Dn/n!. Sorprende al principio que dicha cantidad sea
aproximadamente igual a e−1, tanto para n = 10 como
para n = 10, 000 personas.
5.3. Algunas aplicaciones 71
5.3.3 El problema de los matrimonios
Otro problema famoso que se resuelve con las fórmulas de
inclusión y exclusión de Bernoulli-Sylvester-da Silva y sus
generalizaciones es el “Problema de los Matrimonios”, que
consiste en calcular el número Tn de maneras de sentar n
esposos y sus respectivas esposas en una mesa circular, de
forma tal que los hombres y las mujeres queden alternados y
además ningún hombre quede sentado a la par de su esposa,
ya sea a su derecha o a su izquierda.
Empezamos sentando a las esposas, lo cual puede hacerse
de 2n! maneras distintas, dejando en cada distribución los
asientos pares (o los impares) disponibles para sentar en ellos
a los esposos. En cada una de estas distribuciones, pasamos
a renumerar las esposas del 1 al n, renumerando también los
asientos vaćıos con los mismos ı́ndices del 1 al n. Luego,
procedemos a sentar a los n esposos de Un maneras distintas,
de forma tal que el esposo i no ocupe el asiento i ni el asiento
i + 1, para i ∈ {1, 2, . . . , n − 1}, y el esposo n no ocupe el
asiento n ni el asiento 1. Los números Un se llaman “números
de ménage”. La solución de nuestro problema es, entonces,
Tn = 2n! Un.
Falta calcular los números de ménage Un. Observamos
que Un coincide con la cantidad de permutaciones de n obje-
tos numerados 1, 2, . . . , n, en las cuales el objeto i no queda
en las posiciones {i, i+ 1}, para cada i ∈ {1, . . . , n− 1} y el
objeto n no queda en las posiciones {1, n}. Consideremos las
2n propiedades
p1, q1, p2, q2, . . . , pn, qn, (5.6)
donde pi se satisface si el objeto i queda en la posición i,
mientras que qi se satisface si el objeto i queda en la posición
i + 1 (posición 1, cuando i = n). Seleccionamos k de esas
propiedades y preguntamos por el número de permutaciones
72 Caṕıtulo 5. Principio de inclusión y exclusión
que satisfacen cada una de esas k propiedades. La respuesta
es (n − k)! si las k propiedades son compatibles entre ellas,
y 0 si no son compatibles entre ellas. Sea vk el número de
maneras de seleccionar k propiedades compatibles de las 2n
propiedades (5.6). Entonces, por la fórmula de inclusión y
exclusión de Bernoulli-Sylvester-da Silva, tendremos
Un = v0 n!− v1 (n− 1)! +− · · ·+ (−1)nvn 0!.
Finalmente, para calcular vk observamos que si las 2n propiedades
(5.6) son dispuestas en un ćırculo,

Crie agora seu perfil grátis para visualizar sem restrições.