A maior rede de estudos do Brasil

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

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

entonces solamente aque-
llas no-consecutivas son compatibles. Aplicando el teorema
18 del caṕıtulo 2, obtenemos entonces
vk =
2n
2n− k
(
2n− k
k
)
.
Luego, concluimos que
Tn = 2n!
n∑
k=0
(−1)k 2n
2n− k
(
2n− k
k
)
(n− k)!
5.4 Ejercicios
93. ¿Cuántos enteros entre 1 y 6300 inclusive no son divisi-
bles por 3, ni por 5, no por 7? Respuesta: 2880.
94. En un instituto de investigación cient́ıfica trabajan varias
personas, y cada una de ellas conoce por lo menos una lengua
extranjera. Seis saben inglés; seis, alemán; siete, francés.
Cuatro saben inglés y alemán; tres, alemán y francés; dos,
francés e inglés. Una persona sabe los tres idiomas. ¿Cuántas
personas trabajan en el instituto? ¿Cuántas de ellas saben
solamente inglés? ¿Y solamente francés?
5.4. Ejercicios 73
95. A un paseo a las afueras de la ciudad fueron 92 personas.
47 de ellas llevaron sándwich de carne; 38, de queso; 42,
de jamón; 28, de queso y carne; 31 de carne y jamón; 26,
de queso y jamón. 25 personas llevaron los tres tipos de
sándwich y varias llevaron empanadas en lugar de sándwich.
¿Cuántas personas llevaron empanadas?
96. En una escuela hay 100 estudiantes, de los cuales 40
están cursando francés, 40 lat́ın y 40 alemán. Suponga ade-
más que 20 estudiantes están cursando solamente francés, 20
solamente lat́ın y 15 solamente alemán. Adicionalmente, 10
estudiantes están cursando francés y lat́ın. ¿Cuántos estudi-
antes están cursando los tres idiomas? ¿Cuántos estudiantes
no están cursando ningún idioma? Respuesta: 5 y 15, re-
spectivamente.
97. Suponga que al 45% de todos los lectores de periódicos
les gusta el vino, al 60% les gusta el jugo de naranja y al
55% les gusta el té. Suponga además que al 35% les gusta
cualquier par de las anteriores bebidas y al 25% les gusta
todas las tres bebidas.
(a) ¿Qué porcentaje les gusta solamente el vino?
(b) ¿Qué porcentaje les gusta exactamente dos de las tres
bebidas?
98. En la Figura 5.2 se presenta el plano esquemático
de una casa con 5 habitaciones H1, . . . , H5, intercomuni-
cadas por 6 puertas p1, . . . , p6. Si disponemos de m col-
ores para colorear las habitaciones, ¿de cuántas maneras dis-
tintas podemos colorearlas, si respetamos la restricción que
las habitaciones contiguas (aquellas comunicadas por alguna
puerta) deben tener colores diferentes?
99. Repita el ejercicio anterior, ahora para las casas rep-
resentadas a través de los grafos de la Figura 5.3. En cada
74 Caṕıtulo 5. Principio de inclusión y exclusión
p1
p2
p3
p4
p5
p6
H1
H2
H3
H4
H5
Figura 5.2: Habitaciones en el problema 98.
caso, numere las habitaciones y las puertas que intercomuni-
can estas habitaciones.
•
•
•
•
�
�H
H
Casa 1
• • • •
• • • •
@
@
@
Casa 2
Figura 5.3: Distribución de habitaciones en el ejercicio 99.
100. ¿Cuántas secuencias de n d́ıgitos ternarios (0, 1, 2) hay
con al menos un 0, un 1 y un 2? Respuesta: 3n − 3 · 2n + 3.
101. Sea N ≥ 1. Muestre que el número de enteros positivos
menores e iguales a N que no son divisibles por los primos 2,
3, 5 y 7 es igual a
N −
∑
bN/ic+
∑
bN/ijc −
∑
bN/ijkc+
∑
bN/ijklc,
donde las suma
∑
bN/ic se toma sobre todos los cuatro pri-
mos dados,
∑
bN/ijc se toma sobre todos los pares (i, j) dis-
tintos de los cuatro primos dados, etc. Si N = 210n, muestre
que este número es 48n.
102. Sean p1, p2, . . . , pr los primos no mayores que
√
N .
Muestre que el número de primos mayores que pr y no may-
ores que N es
N − 1− S1 + S2 − · · ·+ (−1)rSr,
5.4. Ejercicios 75
donde Sk =
∑
bN/pa11 p
a2
2 · · · parr c, sumando sobre todas las
( rk ) maneras de poner k de los exponentes a1, a2, . . . , ar
iguales a 1 y el resto igual a 0.
103. Demuestre que el número de enteros positivos, φ(n),
menores que n y primos relativos con n, es igual a
φ(n) = n
(
1− 1
p1
)(
1− 1
p2
)
· · ·
donde p1, p2, . . . son los diferentes factores primos de n. Ver-
ifique la siguiente tabla (φ(1) = 1, por convención):
n 1 2 3 4 5 6 7 8 9 10
φ(n) 1 1 2 2 4 2 6 4 6 4
Caṕıtulo 6
Funciones generadoras
6.1 Introducción y definiciones
Las funciones generadoras juegan un papel muy importante
en la teoŕıa de la combinatoria. En este trabajo tan sólo
presentaremos una breve introducción a las mismas.
Definición 42 Sea ϕ: N 7→ R una función cualquiera. Aso-
ciamos a ϕ las dos funciones reales Fϕ y Eϕ, definidas me-
diante
Fϕ(t) :=
∞∑
k=0
ϕ(k) tk , Eϕ(t) :=
∞∑
k=0
ϕ(k)
tk
k!
. (6.1)
La función Fϕ se llama función generadora ordinaria de
ϕ, mientras que Eϕ se llama función generadora expo-
nencial de ϕ.
Obviamente las series anteriores Fϕ(t) y Eϕ(t) en (6.1)
siempre convergen para t = 0. Por otra parte, bajo ciertas
hipótesis adicionales concernientes al crecimiento de ϕ(k),
k ∈ N, estas series son convergentes en algún vecindario del
origen del tipo V = (−r, r), con r > 0. No obstante, nos
interesa tan solo el desarrollo formal de estas funciones gen-
eradoras, sin importarnos los aspectos relativos a la conver-
gencia de las series de potencias involucradas.
77
78 Caṕıtulo 6. Funciones generadoras
El nombre de función generadora (ordinaria y exponen-
cial) de las funciones Fϕ y Eϕ proviene del siguiente hecho,
el cual puede ser establecido fácilmente por el lector:
ϕ(k) =
1
k!
[
dk Fϕ
dxk
]
t=0
=
[
dk Eϕ
dxk
]
t=0
.
Esta propiedad pone de manifiesto que cualquiera de estas
funciones, Fϕ o Eϕ, efectivamente “genera” o define comple-
tamente a la función original ϕ, al menos cuando tienen un
radio de convergencia positivo.
6.2 Algunas funciones generadoras
En la Figura 6.1 se presentan algunas funciones generado-
ras clásicas de funciones simples. Varias de estas funciones
generadoras ya fueron establecidas a lo largo de este trabajo.
Tales son los casos f) y g) de las funciones generadoras de
los coeficientes binomiales (nk ) y de las permutaciones [n]k,
aśı como los casos j) y k), relativos a los números de Stirling
de primera especie s kn y los números de Bell, Bk, respectiva-
mente. Queda al lector la demostración, como ejercicio, de
los casos a), b), c), d), e) e i), haciendo uso de la definición de
las funciones generadoras ordinarias y exponenciales. Una in-
spección a la tabla anterior justifica los adjetivos “ordinario”
y “exponencial” asignado a las funciones generadoras Fϕ y
Eϕ respectivamente.
De la tabla 6.1 queda aún por demostrar el caso h) cor-
respondiente a los coeficientes (n+k−1k ) de combinaciones de
n objetos con reemplazo, tomando k de ellos a la vez. Uti-
lizamos el desarrollo binomial de (1−t)−n, visto en la fórmula
(3.2): para |t| < 1 tenemos
(1− t)−n =
∞∑
k=0
(
−n
k
)
(−1)k tk
6.2. Algunas funciones generadoras 79
=
∞∑
k=0
(−n)(−n− 1) · · · (−n− k + 1)
k!
(−1)k tk
=
∞∑
k=0
(−1)k n(n+ 1) · · · (n+ k − 1)
k!
(−1)k tk
=
∞∑
k=0
(
n+ k − 1
k
)
tk
= Fϕ(t).
De los resultados elementales de la extensa teoŕıa de las
funciones generadoras mencionamos el siguiente, que establece
la relación exacta entre las funciones generadoras ordinaria
Fϕ(t) y exponencial Eϕ(t).
ϕ(k) Fϕ(t) Eϕ(t)
a) ak (1− at)−1 eat
b) k t(1− t)−2 tet
c) k(k − 1) 2t2(1− t)−3 t2et
d) k2 t(t+ 1)(1− t)−3 t(t+ 1)et
e) k! no simplifica (1− t)−1
f)
(
n
k
)
(1 + t)n no simplifica
g) [n]k no simplifica (1 + t)n
h)
(
n+ k − 1
k
)
(1− t)−n no simplifica
i) nk (1− nt)−1 ent
j) s kn (Stirling) [t]n no simplifica
k) Bk (Bell) no simplifica e(e
t−1)
Figura 6.1: Algunas funciones generadoras.
80 Caṕıtulo 6. Funciones generadoras
Proposición 43 Cuando son convergentes en un intervalo
t ∈ (−r, r) del origen, las funciones generadoras ordinaria
Fϕ(t) y exponencial Eϕ(t) satisfacen la siguiente relación:
Fϕ(t) =
∫ ∞
0
e−sEϕ(ts) ds.
En efecto, haciendo uso de la conocida fórmula relacionada
con la definición de la función Gamma: k! = Γ(k + 1) =∫∞
0 e
−s sk ds, obtenemos
Fϕ(t) =
∞∑
k=0
ϕ(k) tk
=
∞∑
k=0
ϕ(k)
tk
k!
∫ ∞
0
e−s sk ds
=
∫ ∞
0
e−s
( ∞∑
k=0
ϕ(k)
(st)k
k!
)
ds
=
∫ ∞
0
e−sEϕ(ts) ds.
Los detalles

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