A maior rede de estudos do Brasil

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

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

que al cambiar x por −x en esta ecuación se obtiene
la ecuación equivalente
[x]n = L 1n [−x]1 + L 2n [−x]2 + · · ·+ Lnn [−x]n.
Entonces, del teorema de inversión, obtenemos que
∞∑
k=1
L kn L
m
k =
{
1, si n = m
0, si n 6= m.
Además cada una de las ecuaciones
an =
n∑
k=1
L kn bk , bn =
n∑
k=1
L kn ak
implica a la otra. Note además que los números (−1)nL kn son
siempre positivos.
4.4. Ejercicios 61
(a) Derive la recurrencia
L kn+1 = −(n+ k)L kn − L k−1n
y verifique con ayuda de ella la tabla siguiente:
n\k 1 2 3 4 5
1 −1
2 2 1
3 −6 −6 −1
4 24 36 12 1
5 −120 −240 −120 −20 −1
(b) Escriba Lk(t) =
∑∞
n=0 L
k
n
tn
n! . De la relación
∞∑
n=0
[−x]n
tn
n!
=
∞∑
k=0
(
x
k
)(
−t
1 + t
)k
,
muestre que
Lk(t) =
1
k!
(
−t
1 + t
)k
y en consecuencia
L kn = (−1)n
n!
k!
(
n− 1
k − 1
)
.
Verifique que este resultado satisface la relación por
recurrencia derivada en (a), con las condiciones iniciales
apropiadas.
90. Demuestre la siguiente identidad:
b∑
j=a
[j]n =
[b+ 1]n+1 − [a]n+1
n+ 1
,
válida para todo a ≤ b ∈ Z y n ∈ N.
62 Caṕıtulo 4. Particiones de un conjunto
91. Demuestre la siguiente identidad:
b∑
j=a
jn =
n∑
m=1
Smn
[b+ 1]m+1 − [a]m+1
m+ 1
,
válida para todo a ≤ b ∈ Z y n ∈ N?.
92. Una fórmula clásica, debida a James Bernoulli es
n∑
j=1
jm =
1
m+ 1
m∑
k=0
(
m+ 1
k
)
Bk n
m+1−k,
en la cual B0 = 1, B1 = 12 , B2 =
1
6 , B4 = −
1
30 , B6 =
1
42 ,
. . . , y B2k+1 = 0 para todo entero k ≥ 1. Los números Bk
son conocidos en la literatura como los números de Bernoulli.
De la fórmula anterior, escriba los números de Bernoulli en
términos de los números de Stirling de segunda especie. Util-
ice la fórmula anterior para calcular en forma cerrada la suma
de las cuartas potencias de los primeros 10 números.
Caṕıtulo 5
Principio de
inclusión y exclusión
5.1 Introducción
Supóngase que tenemos N objetos, de los cuales N(p) tienen
la propiedad p. Luego, si p′ denota la ausencia de la propiedad
p, entonces
N(p′) = N −N(p)
es la cantidad de objetos que no poseen la propiedad p. Si
dos propiedades p y q son de interés, el número de objetos
que no poseen ninguna de las dos propiedades está dado por
N(p′, q′) = N −N(p)−N(q) +N(p, q),
—donde N(p, q) denota el número de objetos que poseen
ambas propiedades— pues al sustraer N(p) y N(q) del to-
tal, N(p, q) ha sido sustráıdo dos veces y debe ser por tanto
añadido. Esto justifica la terminoloǵıa empleada de “Princi-
pio de Inclusión y Exclusión”, pues se trata de un proceso
en el que inicialmente se incluye a todos los objetos, luego
se excluyen aquellos que no se requieren, luego se incluyen
los objetos incorrectamente excluidos, etc., incluyendo y ex-
cluyendo objetos en forma alternativa.
En general tendremos la fórmula de Bernoulli1-Sylvester-
da Silva, que establece que si de N objetos, N(p) tienen la
63
64 Caṕıtulo 5. Principio de inclusión y exclusión
propiedad p, N(q) tienen la propiedad q, . . . , N(p, q) tienen
ambas propiedades p y q simultáneamente, N(p, q, r) tienen
las propiedades p, q y r simultáneamente, etc., entonces
el número N(p′, q′, r′ . . .) de objetos con ninguna de estas
propiedades está dado por
N(p′, q′, r′ . . .) = N −N(p)−N(q)−N(r)− · · ·
+N(p, q) +N(p, r) + · · ·
−N(p, q, r)− · · ·
+ · · ·
cuya demostración veremos en la siguiente sección.
Por ejemplo, suponga que en una escuela hay 100 estu-
diantes, de los cuales 40 cursan francés, 40 cursan lat́ın y
40 cursan alemán. Además, 20 estudiantes cursan cualquier
pareja de los tres idiomas y 10 estudiantes cursan los tres
1Jacob I Bernoulli (1654–1705) Matemático suizo, nacido en Basel.
Según los deseos de su padre estudió teoloǵıa, pero a la vez se dedicó al
estudio de las matemáticas. Durante un viaje por Holanda e Inglaterra
conoció a los grandes matemáticos de esos páıses. Al regresar a su
ciudad natal, dictó lecciones de f́ısica experimental. A partir de 1687 se
desempeñó como profesor de matemáticas de la universidad.
Sus mayores aportes a la matemática se ubican en el análisis infinites-
imal, la teoŕıa de series, el cálculo de variaciones y la teoŕıa de prob-
abilidades. En 1687, después de leer el libro de Leibniz sobre cálculo
diferencial (1684), Bernoulli aplica las nuevas ideas al estudio de nu-
merosas curvas: la espiral logaŕıtmica, la lemniscata (descubierta por
el mismo Bernoulli), la catenaria y otras. Definió por primera vez el
área del triángulo esférico y otras superficies esferoidales, calculando el
valor de numerosas integrales. Su libro “Aplicaciones aritméticas de las
series infinitas y sus sumas infinitas”, publicado entre 1689 y 1704, fue
el primer texto sistemático sobre la teoŕıa de series.
Junto con su hermano Iohann I, Jacob I fue uno de los fundadores del
cálculo de variaciones. Propuso y resolvió en forma parcial el problema
isoperimétrico, aśı como el problema sobre la curva de descenso más
rápido, planteado por su hermano.
En la obra “El arte de las proposiciones” publicado por su sobrino
Nicolás I en 1713, Jacob I resolvió algunos problemas de combinatoria,
5.2. Fórmula fundamental 65
idiomas. ¿Cuántos estudiantes no están cursando ningún id-
ioma?
En la solución de este problema, la población total con-
siste en N = 100, mientras que las propiedades p, q y r
representan cursar los idiomas francés, lat́ın y alemán, re-
spectivamente. Los datos del problema nos proporcionan di-
rectamente la siguiente información:
N(p) = 40, N(q) = 40, N(r) = 40,
N(p, q) = 20, N(p, r) = 20, N(q, r) = 20,
N(p, q, r) = 10.
Luego, sustituyendo en la fórmula de inclusión y exclusión
obtenemos la respuesta N(p′, q′, r′) = 30.
5.2 Fórmula fundamental
Sea S = {a1, . . . , aN} un conjunto de N elementos. Sea P
un conjunto de n propiedades,
p1, p2, . . . , pn, (5.1)
relacionadas con los elementos de S. Definimos la cantidad
N(pi1 , pi2 , . . . , pir) (5.2)
como el número de elementos de S que satisfacen cada una
de las r propiedades pi1 , pi2 , . . . , pir . Si ningún elemento
descubrió los números que hoy en d́ıa llevan su nombre, demostró el
llamado teorema de Bernoulli —caso particular de la ley de los grandes
números—, construyó un modelo matemático para la descripción de una
serie de experimentos independientes (esquema de Bernoulli). Gracias
a los trabajos de Jacob I Bernoulli, la teoŕıa de probabilidades adquirió
importancia práctica, y algunos de los términos de dicha teoŕıa llevan
desde entonces su nombre. Realizó también importantes trabajos en
f́ısica, aritmética, álgebra y geometŕıa. De sus disćıpulos cabe men-
cionar, además de su hermano Iohann I, a su sobrino Nicolás I, y a
P. Euler, padre del gran matemático L. Euler.
66 Caṕıtulo 5. Principio de inclusión y exclusión
de S satisface cada una de estas propiedades, entonces a la
expresión (5.2) le asignamos el valor 0. Finalmente, definimos
por
W (r) =
∑
N(pi1 , pi2 , . . . , pir), (5.3)
donde la suma se toma sobre todos los subconjuntos de P
con r elementos (propiedades). Extendemos la definición de
W (r) para el caso r = 0, estipulando que W (0) = N . Ten-
dremos entonces el siguiente resultado fundamental:
Teorema 40 (Fórmula fundamental) El número E(m)
de elementos de S que satisfacen exactamente m de las propiedades
(5.1) es igual a
E(m) =
n∑
k=m
(−1)k−m
(
k
m
)
W (k). (5.4)
Demostración: La expresión de la derecha en la fórmula
(5.4), en forma extendida, es igual a
W (m) −
(
m+ 1
m
)
W (m+ 1) +
(
m+ 2
m
)
W (m+ 2)− · · ·+
+ (−1)n−m
(
n
m
)
W (n),
donde n es el número de propiedades de P . Considere-
mos un elemento a ∈ S que satisface exactamente t de las
propiedades (5.1). Si t < m, entonces a contribuye en 0 a la
parte derecha de (5.4). Por otra parte, si t = m, entonces a
contribuye en 1 a la parte derecha de (5.4). Ahora, si t > m,
entonces a contribuye en(
t
m
)
−
(
m+ 1
m
) (
t
m+ 1
)
+− · · ·+ (−1)t−m
(
t
m
)(
t
t
)
a la parte derecha de (5.4). Ahora, en virtud

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