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

Vista previa | Página 16 de 30

de la justificación de la validez del intercambio
de la sumatoria infinita con la integral no los veremos.
6.3 Funciones generadoras
de combinaciones
Algunas maniobras combinatorias muy útiles pueden reali-
zarse con las funciones generadoras ordinarias, empleando
tan sólo procesos algebraicos elementales. Ilustremos lo an-
terior con un ejemplo: sean x1, x2 y x3 tres objetos distintos.
Formemos el producto algebraico
F (t) = (1 + x1 t)(1 + x2 t)(1 + x3 t). (6.2)
6.3. Funciones generadoras de combinaciones 81
Multiplicando todos los términos y agrupando en potencias
de t, obtenemos el polinomio
F (t) = 1+(x1+x2+x3) t+(x1x2+x1x3+x2x3) t2+x1x2x3 t3.
Los coeficientes de este polinomio coinciden precisamente con
las enumeraciones de las combinaciones sin repetición de los
3 objetos x1, x2, x3, tomando k de ellos a la vez (k = 0, 1, 2 y
3, respectivamente). Si deseamos contar estas combinaciones
(en vez de enumerarlas), hacemos la sustitución x1 = x2 =
x3 = 1, para obtener entonces
F (t) = 1 + 3t+ 3t2 + t3 = (1 + t)3.
Ahora los coeficientes del polinomio F (t) coinciden precisa-
mente con la cantidad de combinaciones sin reemplazo de 3
objetos distintos, tomando k de ellos a la vez; esto es, co-
incide con los coeficientes combinatorios ( 3k ), con k = 0, 1,
2 y 3, respectivamente. Esto tiene un sentido adicional, en
virtud de la entrada f) de tabla anterior.
En la expresión F (t) = (1 + x1 t)(1 + x2 t)(1 + x3 t) cada
factor es “binomial” en el sentido que tiene 2 términos: el
término 1 indica que el objeto xi puede no aparecer del todo
en la combinación, mientras que el término xi t indica que el
objeto xi puede aparecer una sola vez.
Podemos generalizar nuestro experimento, considerando
expresiones que incluyan los términos cuadráticos x2i t
2, como
por ejemplo
G(t) = (1+x1 t+x21 t
2)(1+x2 t+x22 t
2)(1+x3 t+x23 t
2). (6.3)
Realizando las multiplicaciones y agrupando en potencias de
t, obtenemos
G(t) = 1 + (x1 + x2 + x3) t+
(x21 + x1x2 + x1x3 + x
2
2 + x2x3 + x
2
3) t
2 +
(x21x2 + x
2
1x3 + x1x
2
2 + x1x
2
3 + x1x2x3 + x2x
2
3 + x
2
2x3) t
3 +
(x21x
2
2 + x
2
1x
2
3 + x
2
1x2x3 + x1x
2
2x3 + x1x2x
2
3 + x
2
2x
2
3) t
4 +
(x21x
2
2x3 + x
2
1x2x
2
3 + x1x
2
2x
2
3) t
5 + (x21x
2
2x
2
3) t
6.
82 Caṕıtulo 6. Funciones generadoras
Los coeficientes de este polinomio G(t) coinciden ahora pre-
cisamente con las enumeraciones de las combinaciones de
los tres objetos x1, x2, x3, tomando k de ellos a la vez,
permitiendo que cada uno de los objetos repita una sola
vez. Para contar estas combinaciones hacemos la sustitución
x1 = x2 = x3 = 1, obteniendo entonces
G(t) = 1 + 3t+ 6t2 + 7t3 + 6t4 + 3t5 + t6 = (1 + t+ t2)3,
donde ahora los coeficientes de G(t) son el número de com-
binaciones de 3 objetos distintos, tomando k de ellos a la
vez (k = 0, 1, 2 y 3, respectivamente), permitiendo a lo
sumo una repetición de cada objeto. En la expresión original
G(t) = (1+x1 t+x21 t
2)(1+x2 t+x22 t
2)(1+x3 t+x23 t
2) cada
factor tiene 3 términos, 1, xi t y x2i t
2, coincidiendo con el he-
cho que las combinaciones que se producen pueden contener
0, 1 o 2 veces al objeto xi.
Podemos generalizar estas ideas, considerando funciones
generadoras ordinarias tales como por ejemplo
F1(t) = (1 + t+ t2 + · · ·+ tm)n, con m ∈ N∗,
F2(t) = (1 + t+ t2 + t3 + · · ·)n,
F3(t) = (1 + t2 + t4 + t6 + · · ·)n.
Tendremos que F1(t) es la función generadora ordinaria del
número de combinaciones de n objetos distintos, tomando k
de ellos a la vez, con a lo sumo m repeticiones de cada objeto.
Por otra parte, siguiendo las ideas anteriores, F2(t) deberá
ser, al menos formalmente, la función generadora ordinaria
del número de combinaciones de n objetos, tomando k de
ellos a la vez, permitiendo cualquier número de repeticiones
de los objetos. En efecto,
F2(t) := (1 + t+ t2 + t3 + · · ·)n =
1
(1− t)n
,
coincidiendo con la entrada h) de la tabla de funciones gen-
eradoras presentada anteriormente. Finalmente, la función
6.4. Funciones generadoras de permutaciones 83
F3(t) será la función generadora ordinaria del número de
combinaciones de n objetos, tomando k de ellos a la vez,
para las cuales cada objeto aparece un número par de veces
(o ninguna vez).
Estos razonamientos permiten resolver rápidamente al-
gunos problemas. Por ejemplo, ¿cuál es el número de combi-
naciones de n objetos distintos, tomando k de ellos a la vez
con reemplazo, con la restricción de que cada objeto debe
aparecer al menos una vez? La función generadora ordinaria
será entonces Fϕ(t) = (t+ t2 + t3 + · · ·)n, de donde
Fϕ(t) = (t+ t2 + t3 + · · ·)n = tn (1 + t+ t2 + · · ·)n
= tn (1− t)−n = tn
∞∑
i=0
(
n+ i− 1
i
)
ti
=
∞∑
i=0
(
n+ i− 1
i
)
tn+i =
∞∑
k=n
(
k − 1
k − n
)
tk
Luego, el número de combinaciones buscado será igual a 0,
si k < n, e igual a ( k−1k−n), si k ≥ n. Por ejemplo, para los
n = 3 objetos a, b, c, habrá (5−15−3) = 6 combinaciones con
repetición de estos objetos, tomando k = 5 de ellos a la vez,
con la restricción de que cada objeto aparezca al menos una
vez. Estas 6 combinaciones son: aaabc, aabbc, aabcc, abbbc,
abbcc, abccc.
6.4 Funciones generadoras
de permutaciones
Resultados completamente análogos a los de las combina-
ciones se obtienen también para las permutaciones, pero esta
vez utilizando funciones generadoras exponenciales, en vez
de funciones generadoras ordinarias. Las manipulaciones al-
gebraicas que condujeron a estos resultados deben ahora re-
alizarse dentro del contexto del álgebra no-conmutativa, pues
84 Caṕıtulo 6. Funciones generadoras
recordemos que con las permutaciones śı debe tomarse en
consideración el orden de los objetos.
En general tendremos que funciones generadoras expo-
nenciales tales como
E(t) =
(
1 + t+
t2
2!
+
t3
3!
+ · · · t
m
m!
)n
corresponden al número de permutaciones de n objetos dis-
tintos, tomando k de ellos a la vez, con la restricción de que
cada objeto puede aparecer a lo sumo m veces. Dejaremos
los detalles al lector.
Igualmente puede demostrarse las funciones generadoras
exponenciales tales como
E1(t) =
(
1 + t+
t2
2!
+
t3
3!
+ · · ·
)n
= ent
E2(t) =
(
t+
t3
3!
+
t5
5!
+ · · ·
)n
,
corresponden a: E1(t) es la función generadora exponencial
del número de permutaciones con reemplazo de n objetos,
tomando k de ellos a la vez (esto es, ϕ(k) = nk, para todo
k ∈ N; E2(t) es la función generadora exponencial del número
de permutaciones con reemplazo de n objetos, tomando k de
ellos a la vez, con la restricción de que cada objeto aparece
un número impar de veces.
Por ejemplo, ¿cuál es el número de permutaciones con
reemplazo de n objetos distintos, tomando k de ellos a la
vez, con la restricción de que cada objeto debe aparecer al
menos una vez? La función generadora exponencial, en este
caso, es
Eϕ(t) =
(
t+
t2
2!
+
t3
3!
+ · · ·
)n
= (et − 1)n
=
n∑
i=0
(
n
i
)
(−1)i e(n−i)t
6.5. Ejercicios 85
=
n∑
i=0
(
n
i
)
(−1)i
∞∑
k=0
(n− i)k tk
k!
=
∞∑
k=0
{ n∑
i=0
(
n
i
)
(−1)i (n− i)k
}
tk
k!
,
de donde el número de permutaciones buscado es
ϕ(k) =
n∑
i=0
(
n
i
)
(−1)i (n− i)k =
n∑
j=0
(−1)n−j
(
n
j
)
jk.
En virtud de las proposiciones 30 y 38 se deduce entonces
que el anterior número de permutaciones coincide con n!S nk
y es igual al número de funciones sobreyectivas que pueden
definirse entre un conjunto A de k elementos y un conjunto
X de n elementos.
6.5 Ejercicios
104. Encuentre la función generadora ordinaria para Ak, el
número de distribuciones de k objetos idénticos en:
(a) Cinco cajas diferentes, con a lo sumo cuatro objetos en
cada caja.
(b) Cuatro cajas diferentes, con de tres a seis objetos en
cada caja.
(c) Siete cajas diferentes, con al menos un objeto en cada
caja.
(d) Tres cajas diferentes, con a lo sumo cinco objetos en la
primera caja.
105. Encuentre la función generadora ordinaria para Ak,
el número de maneras de seleccionar k bolas de una urna
que contiene tres bolas verdes, tres bolas blancas, tres bolas

Crea tu cuenta gratis ahora para ver el material sin restricciones.