Matemática discreta

Christian Torres

12 de marzo de 2026
ii
Índice general

1. Números reales 1

2. Números complejos 3

3. Conjuntos, aplicaciones y relaciones 5

4. Números naturales y enteros 7

5. Combinatoria elemental 9
5.1. Técnicas básicas de conteo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
5.2. Coeficientes binomiales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
5.3. Problemas de distribución . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
5.4. Principio de inclusión-exclusión . . . . . . . . . . . . . . . . . . . . . . . . . 15
5.5. Recurrencias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

6. Funciones generatrices 21
6.1. Funciones generatrices y series de potencias formales . . . . . . . . . . . . . 21
6.2. Teorema binomial generalizado . . . . . . . . . . . . . . . . . . . . . . . . . 23
6.3. Funciones generatrices racionales . . . . . . . . . . . . . . . . . . . . . . . . 24

7. Introducción a la teoría de grafos 27

8. Grafos con costos 29

9. Flujo en redes y aplicaciones 31

iii
iv ÍNDICE GENERAL
Capítulo 1

Números reales

1
2 CAPÍTULO 1. NÚMEROS REALES
Capítulo 2

Números complejos

3
4 CAPÍTULO 2. NÚMEROS COMPLEJOS
Capítulo 3

Conjuntos, aplicaciones y
relaciones

5
6 CAPÍTULO 3. CONJUNTOS, APLICACIONES Y RELACIONES
Capítulo 4

Números naturales y enteros

7
8 CAPÍTULO 4. NÚMEROS NATURALES Y ENTEROS
Capítulo 5

Combinatoria elemental

5.1. Técnicas básicas de conteo

Principio 5.1.1 (Principio del palomar). Si n + 1 objetos se colocan en n cajas, entonces
al menos alguna de las cajas contendrá dos objetos o más.

Teorema 5.1.2 (Versión fuerte del principio del palomar). Sean m1 , m2 , . . . , mn enteros
positivos. Si m1 +m2 +· · ·+mn −n+1 objetos se colocan en n cajas, entonces o la primera
caja contiene al menos m1 objetos, o la segunda caja contiene al menos m2 objetos, ..., o
la n-ésima caja contiene al menos mn objetos.

Demostración. Supongamos que, para i = 1, ..., n, la caja i contiene menos de mi objetos.

Entonces, el total de objetos en las cajas sería a lo más (m1 − 1) + · · · + (mn − 1) =
m1 +· · ·+mn −n, lo que contradice que el número de objetos es m1 +m2 +· · ·+mn −n+1.
Por tanto, en alguna caja i hay al menos mi elementos.

Principio 5.1.3 (Principio de adición). Supongamos que un conjunto S se puede par-

ticionar en m subconjuntos S1 , ..., Sm , disjuntos dos a dos. El número de elementos en
S se puede determinar a través de la suma del número de elementos en cada uno de los
subconjuntos, es decir, |S| = |S1 | + · · · + |Sm |.

Teorema 5.1.4 (Principio de la resta). Sea A un conjunto contenido en otro conjunto

U . Sea Ā el complemento de A, es decir, Ā = {x ∈ U |x ∈
/ A}. Entonces el número de
elementos en A viene dado por |A| = |U | − |Ā|.

Principio 5.1.5 (Principio del producto). Si un proceso de recuento puede describirse

como una sucesión de m pasos independientes entre sí, con n1 posibles resultados en el paso
1, n2 resultados en el paso 2 y así sucesivamente, entonces el número total de resultados
posibles en el proceso es n1 n2 · · · nm .

Teorema 5.1.6. Sea S un conjunto de n elementos distintos.

1. Las formas diferentes de seleccionar 0 ≤ r ≤ n objetos de S (variaciones de n

elementos tomados de r en r) es

V (n, r) = n(n − 1) · · · (n − r + 1).

Si r = n (permutaciones de n elementos), entonces V (n, n) = n!.

9
10 CAPÍTULO 5. COMBINATORIA ELEMENTAL

2. El número de selecciones distitnas de 0 ≤ r ≤ n objetos de S (combinaciones de n

elementos tomados de r en r) es
!
n n(n − 1) · · · (n − r + 1)
C(n, r) = =
r r!

Demostración. Demostremos la primera parte. Hay n posibles elecciones para el primer

elemento de la secuencia, n − 1 para el segundo, n − 2 para el tercero, y así sucesivamente.
Por tanto,
V (n, r) = n(n − 1) · · · (n − r + 1).
Para demostrar 2, si generamos los C(n, r) subconjuntos no ordenados de S y ordenamos
los elementos de cada subconjunto en las r! formas posibles, entonces obtendremos los
V (n, r) subconjuntos ordenados de S. Por lo tanto, C(n, r)r! = V (n, r), es decir,
V (n, r) n(n − 1) · · · (n − r + 1)
C(n, r) = = .
r! r!

n

Nota. A los números r se les suele llamar coeficientes binomiales.
Nota. Si S contiene n elementos y r es un entero 1 ≤ r ≤ n, el primer apartado del
teorema anterior nos dice que el número de subconjuntos ordenados es
V (n, r) = n(n − 1) · · · (n − r + 1)
. Notar que si r es un entero mayor que n, la fórmula anterior nos da el valor 0, lo cual
también coincide con el número de subconjuntos ordenados que tenemos de ese tamaño,
pues no hay ninguno. Igualmente, si r > n, entonces C(n, r) = V (n,r)
r! vale 0, que coincide
con el número de subconjuntos de ese tamaño, que no hay. Por otra parte, el conjunto ∅
siempre es un subconjunto de S, y aunque no tiene sentido ordenar sus elementos, se suele
definir por convenio que V (n, 0) = 1. De esta forma, C(n, 0) = 0 = V (n,0)
n

0! = 1, y por
tanto C(n, 0) nos da también el número de subconjuntos de tamaño 0 de S
(el conjunto
∅). Por convenio, también se define V (0, 0) = 0! = 1, con lo que C(0, 0) = 00 = 1
Definición 5.1.7. Si los elementos de un conjunto S no son distintos, y se tienen elementos
repetidos, se dice que S es un multiset.
Teorema 5.1.8. Sea S un multiset que consta de k elementos distintos a1 , a2 , . . . , ak ,
cada uno de ellos repetido n1 , n2 , . . . , nk veces. Si ni > 0, para todo i, y r = n = ki=1 ni ,
P

entonces el número de secuencias ordenadas de S (permutaciones con repetición) es

n!
.
n1 ! · · · nk !
Demostración. Queremos calcular el número de formas distintas de ordenar estos n ele-
mentos, o dicho de otra forma, el número de secuencias e1 e2 . . . en , donde cada ei es un
elemento de S y cada elemento ai aparece exactamente ni veces en esa secuencia. Ob-
servar que a1 aparecerá en n1 posiciones, y por tanto hay C(n, n1 ) formas de posicionar
los elementos a1 . Una vez colocados los elementos a1 en la secuencia, podemos colocar
los elementos a2 en las n − n1 posiciones que quedan de C(n − n1 , n2 ) formas distin-
tas. Igualmente, después de colocados los a1 y a2 , los elementos a3 pueden colocarse de
C(n − n1 − n2 , n3 ) formas distintas y así sucesivamente. Por tanto el número buscado es
n!
C(n, n1 )C(n − n1 , n2 ) · · · C(n − n1 − n2 − · · · − nk−1 , nk ) = .
n1 ! · · · nk !
5.2. COEFICIENTES BINOMIALES 11

Teorema 5.1.9. Sea S con conjunto con n elementos distintos.

1. El número de secuencias ordenadas de longitud r > 0 que se pueden formar con los
elementos de S, permitiendo repeticiones (variaciones con repetición de n elementos
tomados de r en r), es V ∞ (n, r) = nr .

2. El número de secuencias no ordenadas (selecciones) de longitud r > 0 que se pue-

den formar con los elementos de S, permitiendo repeticiones (combinaciones con
repetición de n elementos tomados de r en r), es
!
∞ n+r−1
C (n, r) = .
n−1

Demostración. Demostremos la primera parte. Hay n posibles elecciones para el primer

elemento de la secuencia, n para el segundo, n para el tercero, y así sucesivamente. Por
tanto, V ∞ (n, r) = nr . Para demostrar la segunda parte, supongamos que a1 , . . . , an son
los n elementos distintos de S. Consideremos un multiset S ′ formado por r símbolos ◦ y
n − 1 símbolos |. Veamos que hay una correspondencia biyectiva entre las secuencias de
r símbolos ◦ y n − 1 símbolos |, y las selecciones con repetición de tamaño r obtenidas
de S. A cada secuencia s de S ′ le asignaremos una selección con repetición t en S de la
siguiente forma: si s1 , . . . , sn−1 son las posiciones donde aparece el símbolo | en la secuencia
s, construiremos la selección t de S de forma que el elemento ai (i = 1, . . . , n) aparece
repetido en t exactamente ri = si − si−1 − 1 veces (número de círculos entre 2 barras
consecutivas), tomando s0 = 0 y sn = n + r. Claramente esta aplicación es inyectiva (a
secuencias s distintas les corresponden selecciones con repetición t distintas) y suprayectiva
(la selección con repetición {r1 · a1 , r2 · a2 , . . . , rk · ak } se obtiene de la secuencia s formada
por r1 símbolos ◦, seguidos de un |, después r2 símbolos ◦ y un |,..., y finalmente rk símbolos
◦). Por tanto, hay tantas selecciones con repetición de tamaño r en S, como secuencias s
(permutaciones con repetición) en S ′ . Por el teorema anterior, este número es
!
(n + r − 1)! n+r−1
= .
(n − 1)!r! n−1

5.2. Coeficientes binomiales

!
n n!
Proposición 5.2.1. 1. Para r y n enteros tales que r ≥ 0 y n ≥ r, = .
r r!(n − r)!
! !
n n
2. Para r y n enteros tales que r > 0 y n ≥ r, = .
r n−r
! !
n n n−1
3. Para r > 0 entero, = .
r r r−1
! ! !
n n−1 n−1
4. Para r > 0 entero, = + .
r r r−1
! ! ! !
n n+1 n+r n+r+1
5. Para r ≥ 0 entero, + + ··· + = .
0 1 r r
12 CAPÍTULO 5. COMBINATORIA ELEMENTAL
! ! ! !
r r+1 n n+1
6. Para r ≥ 0 entero, + + ··· + = .
r r r r+1

Demostración. Demostraremos 4, 5 y 6.

• Supongamos que n es entero y que S = {1, ..., n}. La parte izquierda cuenta el
número de subconjuntos de tamaño r de S. La parte derecha cuenta también esos
subconjuntos de una
forma distinta. Cuenta subconjuntos de tamaño r que no con-
tienen a n (hay n−1
r puesto que hay que elegir r elementos de los n − 1 restantes),
subconjuntos de tamaño r que contienen a n (hay n−1


r−1 puesto que hay que elegir
r − 1 elementos de los n − 1 restantes).

• Supongamos que n es entero y que S = {1, 2, ..., n + r + 1}. La parte derecha de la

identidad cuenta subconjuntos de tamaño r de S. La parte izquierda cuenta también
los subconjuntos de tamaño r de S de una manera distinta. Cuenta subconjuntos
de
tamaño r cuando el elemento n + r + 1 no está y se eligen r del resto (de n+r r ),
subconjuntos de tamaño r cuando el elemento n + r + 1 está, el elemento n + r no
está y se eligen r −1 del resto (de n+r−1


r−1 formas), subconjuntos de tamaño r cuando
los elementos n + r + 1 y n + r están, el elemento n + r − 1 no está y se eligen r − 2
del resto (de n+r−2


r−2 formas), y así sucesivamente.

• Supongamos que n es un entero y que S = {1, 2, . . . , n + 1}. La parte derecha

cuenta subconjuntos de tamaño r + 1 de S. La parte izquierda cuenta también esos
subconjuntos de una forma distinta.
Cuenta subconjuntos de tamaño r + 1 cuando
el mayor elemento es r + 1 (hay rr subconjuntos), subconjuntos de tamaño r + 1
cuando el mayor elemento es r + 2 (hay r+1


r subconjuntos), y así sucesivamente.

Teorema 5.2.2 (Identidad de Vandermonde). Dados a, b y r números enteros tales que

a > 0, b > 0 y 0 ≤ r ≤ a + b, se tiene que
r
! ! !
X a b a+b
= .
i=0
i r−i r

Demostración. Supongamos que tenemos a + b bolas numeradas 1, ..., a, a + 1, ..., a + b.

a+b

Podemos seleccionar r subconjuntos de r bolas. Cada subconjunto constará de i bolas
de las a primeras (para un cierto valor de i), que pueden seleccionarse de ai formas


b

distintas, y r − i de las últimas b bolas, que pueden seleccionarse de r−i formas distintas.
Notar que i ha de satisfacer que máx(0, r − b) ≤ i ≤ mı́n(a, r). Sumando entre los posibles
b
a

valores de i, y aplicando que r−i = 0 cuando i < r − b, y que i = 0 cuando i > a, se
obtiene la identidad buscada.
!2 !2 !2 !
r r r 2r
Corolario 5.2.3. Dado r ≥ 0 entero, + + ··· + = .
0 1 r r

Teorema 5.2.4 (Teorema binomial). Para cualquier entero n ≥ 0 y números arbitrarios

(reales o complejos) x e y se tiene que
n
!
n
X n
(x + y) = xr y n−r .
r=0
r
5.3. PROBLEMAS DE DISTRIBUCIÓN 13

Demostración. Al realizar el producto (x + y)(x + y) · · · (x + y), hay que elegir el término

x o el término y de cada uno de los n factores y multiplicar dichos términos. Por tanto,
el resultado del producto tiene que ser una suma de términos del tipo xr y n−r , donde r
puede variar de 0 a n. Por ejemplo, si tomamos el término x del primer factor y el término
y en el resto de los factores, el resultado de multiplicar esos términos es xy n−1 . Se tiene
entonces que
n
X
(x + y)n = cr xr y n−r
r=0

donde para r = 0, . . . , n, la constante cr es el número de veces que se repite el término

xr y n−r al realizar el producto. Veamos cuánto vale cr , para r = 0, . . . , n. Fijado un r
cualquiera, el sumando xr y n−r se obtiene eligiendo x en r de los n factores (x + y) e y
n

en los (n − r) factores restantes. Como hay r formas de elegir x en r de los n factores,
necesariamente cr debe ser nr .

n
!
X n
Corolario 5.2.5. 1. Para n ≥ 0 entero, = 2n .
r=0
r

n
!
X
r n
2. Para n ≥ 0 entero, (−1) = 0.
r=0
r

n
!
X n
3. Para n ≥ 0 entero y número arbitrario x, (x + 1)n = xr .
r=0
r

∞
!
X n
4. Para n ≥ 0 entero y número arbitrarios x e y, (x + y)n = xr y n−r .
r=0
r

5.3. Problemas de distribución

Corolario 5.3.1. Para n y r números enteros tales que n > 0 y r ≥ 0,
el número de
formas de repartir r bolas iguales en n cajas distintas es C ∞ (n, r) = n+r−1
n−1 .

Demostración. Sea S = {a1 , ..., an } un conjunto de n elementos distintos. Definimos f que

a cada submultiset {r1 · a1 , . . . , rn · an } de S que cumpla que r1 + · · · + rn = r le asigna la
forma de meter las r bolas iguales en las n cajas distintas que consiste en meter ri bolas
en la caja i para todo i = 1, ..., n. Como esta aplicación es biyectiva ambos problemas son
equivalentes, y el número buscado es C ∞ (n, r).

Corolario 5.3.2. Para n y r números enteros tales que r ≥ n > 0, el número de formas
de repartir r bolas
iguales en n cajas distintas, de forma que en cada caja haya al menos
r−1
una bola, es n−1 .

Demostración. Dejamos una bola en cada cada caja y repartimos r−n bolas restantes.

Corolario 5.3.3. El número de soluciones enteras y ordenadas de la ecuación

x1 + x2 + · · · + xn = r,
n+r−1

con xi ≥ 0 para todo i, es C ∞ (n, r) = n−1 .
14 CAPÍTULO 5. COMBINATORIA ELEMENTAL

Corolario 5.3.4. El número de soluciones enteras y ordenadas de la ecuación

x1 + x2 + · · · + xn = r,
r−1

con xi > 0 para todo i, es n−1 .

Definición 5.3.5. Dado un conjunto S de r elementos distintos, una partición de S es una

colección de bloques no vacíos, de forma que cada elemento de S pertenezca exactamente
a uno de los bloques.

Definición 5.3.6. Dado un conjunto S de r elementos distintos, al número de particiones

de S en i bloques se le denota por S2 (r, i). A estos números S2 (r, i) se les conoce con el
nombre de números de Stirling de segunda clase (o de segunda especie). Además, S2 (0, 0) =
1 por convenio.

Corolario 5.3.7. Para cualesquiera enteros r ≥ n ≥ 1, el número de formas de distribuir

r bolas distintas en n cajas iguales, sin que ninguna caja esté vacía, es S2 (r, n).

Proposición 5.3.8. 1. S2 (r, 1) = 1 para r > 0.

2. S2 (r, r) = 1 para r > 0.

3. S2 (r, i) = 0 si i > r.

4. S2 (r, 0) = 0 si r > 0.

Teorema 5.3.9. Para r > 1 y 1 ≤ i ≤ r − 1, se tiene

S2 (r, i) = S2 (r − 1, i − 1) + iS2 (r − 1, i).

Demostración. Vamos a realizar una demostración combinatoria de este resultado. Por

conveniencia, supondremos que el conjunto S que queremos particionar es S = {1, 2, . . . , r}.
La parte izquierda de la igualdad cuenta las formas de particionar S en i bloques. Vea-
mos que la parte de la derecha también cuenta esa cantidad. En una partición de S en i
bloques, o el elemento r va sólo en un bloque o no. Si r va sólo en un bloque, los r − 1
elementos restantes se tienen que particionar en i − 1 bloques, de S2 (r − 1, i − 1) formas
distintas. En otro caso, el elemento r irá en uno de los bloques (i posibilidades) en los que
se pueden particionar los r − 1 elementos restantes en i bloques (S2 (r − 1, i) formas).

Nota. Hay que notar que, como S2 (r, i) = 0 si i > r, entonces la identidad del teorema
sigue siendo cierta para i ≥ r. Además, definiendo S2 (0, i) = 0 para i > 0, entonces la
identidad anterior también es válida cuando r = 1 e i ≥ 1. En definitiva, la identidad del
teorema es cierta para r > 0 y 1 ≤ i.

Corolario 5.3.10. Para cualesquiera enteros r ≥ n ≥ 1, el número de formas de distribuir

r bolas distintas en n cajas iguales, si se permiten cajas vacías, es ni=1 S2 (r, i).
P

Demostración. Basta tener en cuenta que podemos optar por meter todas las bolas en
una caja, o en dos, o en tres, ...

Teorema 5.3.11. Para cualesquiera enteros r ≥ n ≥ 1, el número de formas de distribuir

r bolas distintas en n cajas distintas, sin que ninguna caja esté vacía, es S2 (r, n)n!.
5.4. PRINCIPIO DE INCLUSIÓN-EXCLUSIÓN 15

Demostración. Si S = {1, 2, . . . , r}, podemos particionar S en n bloques de S2 (r, n) formas.

Dada una de esas particiones, etiquetamos sus bloques de 1 a n. Cualquier permutación
de esas etiquetas, origina una forma distinta de colocar las bolas en las distintas cajas; si
la etiqueta i está en la posición j de la permutación, entonces asignamos los elementos del
bloque i a la caja j. Por tanto, el número de formas de distribuir r bolas distintas en n
cajas distintas, sin que ninguna caja esté vacía, es S2 (r, n)n!.

Corolario 5.3.12. Para cualesquiera enteros r ≥ n ≥ 1, el número de formas de distribuir

r bolas distintas en n cajas distintas, si se permiten cajas vacías, es nr .

Definición 5.3.13. Sean a1 ≥ a2 ≥ · · · ≥ an ≥ 1 enteros positivos tales que

a1 + a2 + · · · + an = r.

Entonces a la secuencia (a1 , ..., an ) se la denomina una partición del entero r. Al núme-
ro total de particiones de r se le denota por p(r), y al número de particiones de r en
exactamente n sumandos se le denota por pn (r), con lo que p(r) = rn=1 pn (r).
P

Corolario 5.3.14. Para cualesquiera enteros r ≥ n ≥ 1, el número de formas de colocar

r bolas iguales en n cajas iguales, sin que ninguna caja este vacía, es pn (r).

Corolario 5.3.15. Para cualesquiera enteros r ≥ n ≥ 1, el número de formas de colocar

r bolas iguales en n cajas iguales, si se permiten cajas vacías, es ni=1 pi (r).
P

Demostración. Basta tener en cuenta que podemos optar por meter todas las bolas en
una caja, o en dos, o en tres, ...

5.4. Principio de inclusión-exclusión

Teorema 5.4.1 (Principio de inclusión-exclusión). Sea S un conjunto con n elementos
y E1 , ..., Er subconjuntos de S (no necesariamente distintos). Entonces el número de ele-
mentos de S que no están en ninguno de los subconjuntos Ei es
r
[ r
X X X r
\
r
S\ Ei = |S| − |Ei | + |Ei ∩ Ej | − |Ei ∩ Ej ∩ Ek | + · · · + (−1) Ei .
i=1 i=1 i<j i<j<k i=1

Demostración. Observar que si tenemos varios subconjuntos S1 , S2 , S3 de S, una forma

de calcular una expresión como |S1 | − |S2 | + |S3 | es contar, para cada elemento x ∈ S,
cuanto contribuye ese elemento a esa expresión. Por ejemplo, si un elemento x está en los
tres subconjuntos S1 , S2 y S3 , entonces contribuye como 1 − 1 + 1 = 1, y si pertenece a S1
y S3 , pero no a S2 , entonces contribuye con 1 − 0 + 1 = 2. La suma de las contribuciones
de cada elemento de S nos ha de dar |S1 | − |S2 | + |S3 |. Vamos a demostrar la validez de la
fórmula dada en el teorema, viendo la contribución de cualquier elemento x ∈ S. Tenemos
que n = |S|, n1 = ki=1 |Ei |, n2 = i<j |Ei ∩ Ej |, . . . representan sumas de cardinales
P P

de subconjuntos de S. Tomemos un elemento x ∈ S. Supongamos que x no pertenece

a ninguno de los Ei . Su contribución en la parte izquierda de la igualdad es entonces 1
y su contribución neta en la suma de la derecha también es 1, pues sólo aparece en n
(pertenece a S). Supongamos ahora que x está en exactamente k > 0 subconjuntos Ei . Su
contribución en la izquierda es claramente 0. En la derecha, la contribución de x en n es
k
k
k

1 = 0 (pertenece a S), su contribución en n1 es 1 (pues pertenece a 1 subconjuntos
16 CAPÍTULO 5. COMBINATORIA ELEMENTAL

Ei ), su contribución a n2 es k2 (pues está en k2 conjuntos Ei ∩ Ej ), y así sucesivamente.

Por tanto, su contribución neta en la derecha es

! ! ! !
k k k k
− + − · · · + (−1)k = 0,
0 1 2 k

como en la izquierda.

Definición 5.4.2. Dada una permutación π de los números {1, 2, ..., n}, se dice que π es
un derangement si ninguno de los números {1, 2, ..., n} aparece en su posición natural en
π, es decir π(i) ̸= i.

Ejemplo 5.4.3. Si dn es el total de derangements de R = {1, 2, ..., n}, ¿cuánto vale

dn ?¿cuál es el número de permutaciones conteniendo k puntos fijos?

Solución. Veamos cómo calcular dn mediante el principio de inclusión-exclusión. Definamos

los siguientes conjuntos:

• S: permutaciones de los elementos de R.

• Para i = 1, ..., n, Ei es el conjuntos de permutaciones π de R tales que π(i) = i (el

número i aparece en su posición natural en π).

Por el
principio de inclusión-exclusión, dn = |S \ (∪ni=1 )|. Claramente, |S| = n!. Dado i (y

hay n1 formas de elegir i), es claro también que |Ei | = (n − 1)!, pues una vez fijado el
i en su posición natural, el resto de los números se pueden permutar de (n − 1)! formas
distintas. Dado i y k (y hay n2 formas de elegir i y k), se tiene que |Ei ∩ Ek | = (n − 2)!,

pues fijados el i y el k en sus posiciones natural, el resto de los números se pueden permutar
de (n − 2)! formas distintas. En general, elegidos j números {i1 , ..., ij } (y hay nj formas

de hacerlo), se tiene que |Ei1 ∩ · · · ∩ Eij | = (n − j)!. En consecuencia,

n n n
!
X
j n X n! X (−1)j
dn = (−1) (n − j)! = (−1)j (n − j)! = n! .
j=0
j j=0
j!(n − j)! j=0
j!

Utilizando el desarrollo en serie de potencia de la función ex , se puede dar una aproximación

j
xj −1 es P∞ (−1) . Para n
de dn . El desarrollo en serie de ex es ∞
P
j=0 j! , por lo que e j=0 j!
suficientemente grande, se tiene entonces

dn ≈ n!e−1 .

Por otra parte, el número de permutaciones conteniendo exactamente k puntos fijos es

!
n
dn−k .
k

Ejemplo 5.4.4. Calcular el número de submultisets de tamaño 6 del multiset

R = {a, a, a, a, b, b, b, c, d, d}.

Solución. Para aplicar inclusión-exclusión, definimos los siguientes conjuntos:

• S: submultisets de tamaño 6, usando un número ilimitado de copias de los elementos

{a, b, c, d}.
5.4. PRINCIPIO DE INCLUSIÓN-EXCLUSIÓN 17

• E1 : submultisets de tamaño 6, usando un número limitado de copias de los elementos

{a, b, c, d}, de forma que contengan más de 4 a’s.

• E2 : submultisets de tamaño 6, usando un número limitado de copias de los elementos

{a, b, c, d}, de forma que contengan más de 3 b’s.

• E3 : submultisets de tamaño 6, usando un número limitado de copias de los elementos

{a, b, c, d}, de forma que contengan más de una c.

• E4 : submultisets de tamaño 6, usando un número limitado de copias de los elementos

{a, b, c, d}, de forma que contengan más de 2 d’s.

Observar que la definición de los conjuntos Ei se hace en función del número de copias de
cada uno de los elementos distintos del multiset de partida R. Así, como R sólo contiene 4
copias de a, no podemos permitir que nuestros submultisets tengan más de 4 a’s. Con estas
definiciones, la solución a nuestro problema vendrá dada por |S \ (E1 ∪ E2 ∪ E3 ∪ E4 )|, que
podremos calcular a través del principio de inclusión-exclusión. En primer lugar, claramen-
te |S| = 6+4−1


4−1 = 84, puesto que S no es más que el conjunto de las combinaciones con
repetición de tamaño 6 del conjunto {a, b, c, d}. Para el cálculo de |E1 |, como necesitamos
submultisets con más de 4 a’s, elegimos 5 a’s para nuestro submultiset y el resto de los
elementos son las combinaciones con repetición de tamaño 1 del conjunto {a, b, c, d}. Por
1+4−1

tanto, |E1 | = 4−1 = 4. Para el cálculo de |E2 |, elegimos 4 b’s para nuestro submultiset
y el resto de los elementos son las combinaciones con repetición de tamaño 2 del conjun-
to {a, b, c, d}. Por tanto, |E2 | = 2+4−1


4−1 = 10. Usando el mismo tipo de razonamiento,
4+4+−1
3+4−1

se obtiene que |E3 | = 4−1 = 35 y que |E4 | = 4−1 = 20. Vamos con las dobles
intersecciones. Para contar los elementos en E1 ∩ E2 , tenemos que construir submultisets
con al menos 5 a’s y al menos 4 b’s. Pero eso es imposible ya que el tamaño de nues-
tros submultisets es 6. Por tanto, E1 ∩ E2 = ∅ y |E1 ∩ E2 | = 0. Por el mismo motivo,
|E1 ∩ E3 | = |E1 ∩ E4 | = |E2 ∩ E4 | = 0. Con respecto a E2 ∩ E3 , tenemos que |E2 ∩ E3 | = 1,
pues con al menos 4
b’s y al menos 2 c’s solo está el submultiset (b, b, b, b, c, c). Por último,
|E3 ∩ E4 | = 1+4−14−1 = 4, ya que elegidas 2 c’s y 3 d’s, el resto son combinaciones con
repetición de tamaño 1 del conjunto {a, b, c, d}. Usando argumentos similares, no es díficil
ver que las intersecciones triples y la cuádruple son vacías. En definitiva,

|S \ (E1 ∩ E2 ∩ E3 ∩ E4 )| = 84 − 4 − 10 − 35 − 20 + 1 + 4 = 20.

Nota. El principio de inclusión-exclusión también permite resolver el problema de contar

cuántos submultisets ordenados de tamaño r se pueden obtener a partir de un submultiset,
pero los cálculos en general son más complicados. Por ejemplo, calculemos el número de
submultisets ordenados de tamaño 6 del multiset R = {a, a, a, a, b, b, b, c, d, d}. Para resol-
ver el problema aplicando el principio de inclusión-exclusión, habría que definir S como el
conjunto de submultisets ordenados de tamaño 6, usando un número ilimitado de copias
de los elementos {a, b, c, d}. El conjunto E1 sería el conjunto de submultisets ordenados
de tamaño 6, usando un número ilimitado de copias de los elementos {a, b, c, d}, de forma
que contengan más de 4 a’s. Los conjuntos E2 , E3 y E4 se definirían de forma análoga
a E1 , de forma que contengan más de 3 b’s, más de una c y más de 2 d’s, respectiva-
mente. El el caso de S, el total de submultisets ordenados de tamaño 6 con repeticiones
liminadas no es más que |S| = 46 = 4096. Sin embargo, para calcular |E1 |, la solución
6
1 6
0
sería |E1 | = 5 3 + 6 3 = 19 (distinguimos si tenemos 5 a’s ó 6 a’s). Para E2 , E3 y E4 ,
tendríamos |E2 | = 64 32 + 65 31 + 66 30 = 154, |E3 | = 1909 y |E4 | = 694. En cuanto a las

intersecciones, sólo E2 ∩ E3 y E3 ∩ E4 son no vacías. En el caso de E2 ∩ E3 , tenemos que

18 CAPÍTULO 5. COMBINATORIA ELEMENTAL

6!
|E2 ∩ E3 | = 4!2! = 15, pues hay que permutar 4 b’s y 2 c’s. En el caso de E3 ∩ E4 , hay que
distinguir los casos en lo que se tengan exactamente 2 c’s y 3 d’s, 2 c’s y 4 d’s, y 3 c’s y 3
d’s. Así, |E3 ∩ E4 | = 65 2!3!

5! 6! 6!
+ 2!4! + 3!3! = 155. En definitiva,

|S \ (E1 ∩ E2 ∩ E3 ∩ E4 )| = 4096 − 19 − 154 − 1909 − 69 + 15 + 155 = 1490.

5.5. Recurrencias
Definición 5.5.1. Una fórmula de recurrencia para una secuencia de números f0 , f1 , ..., fn , ...
es una identidad que permite calcular un valor de la secuencia fn en función de valores fi
calculador previamente.

Ejemplo 5.5.2. Dado el conjunto S = {1, ..., n}, calcular el número de subconjuntos de
S que no contengan números consecutivos.

Solución. Llamemos fn a ese número, para n ≥ 1. Claramente, f1 = 2, f2 = 3 e incluso

se podría definir f0 = 1. Vamos a calcular fn . De los subconjuntos que buscamos, algunos
contendrán a el número n y otros no. Los que no contienen a n han de ser subconjuntos
de {1, 2, . . . , n − 1} y sin contener números seguidos. Luego hay exactamente fn−1 de ellos.
Por otra parte, los subconjuntos que sí contienen a n no pueden contener al número n − 1,
puesto que no puede haber números seguidos. Luego al n le acompañan subconjuntos de
{1, 2, . . . , n − 2} sin números consecutivos, que hay fn−2 de ellos. Por tanto, fn verifica la
fórmula de recurrencia

fn = fn−1 + fn−2

válida para cualquier n ≥ 2.

Definición 5.5.3. Una sucesión de Fibonacci es una sucesión f0 , f1 , f2 , . . . , fn , . . . que

responde a la recurrencia fn = fn−1 + fn−2 .

Teorema 5.5.4. Supongamos que S es un multiset con elementos a1 , . . . , ak , repetidos

n1 , . . . , nk veces, respectivamente. Definamos n = ki=1 ni . El número de submultisets
P

ordenados de S de tamaño 0 ≤ r ≤ n que se pueden obtener utilizando los primeros h

elementos ai es
mı́n(r,nh ) !
′ r
V ′ (r − j, h − 1).
X
V (r, h) =
j=0
j

En particular, el número de submultisets ordenados de S es V ′ (r, k).

Demostración. Fijados h > 1 y 1 ≤ r ≤ hi=1 ni , en uno de los submultisets ordenados de

P

V ′ (r, h) el elementos ah puede aparecer j veces, donde j puede ir desde 0 hasta mı́n(r, nh ).
r

Si aparece j veces, podemos colocar en el submultiset los j elementos de ah de j formas
distintas. Una vez colocados los elementos ah , lo que queda es un problema de calcular
submultisets ordenados de tamaño r − j, usando a1 , . . . , ah−1 , repetidos n1 , ..., nh−1 veces.
Por tanto, para h = 2, . . . , k y 1 ≤ r ≤ hi=1 ni , se tiene la siguientes recurrencia
P

mı́n(r,nh ) !
′ r
V ′ (r − j, h − 1).
X
V (r, h) =
j=0
j
5.5. RECURRENCIAS 19

Nota. 1. Si r = 0, entonces V ′ (0, h) = 1 para cualquier h. Como los submultisets

ordenados son de tamaño r = 0, lo único que podemos elegir es el submultiset vacío.

2. Si r > hi=1 ni , entonces V ′ (r, h) = 0. Como el número de elementos en el multiset

P

es hi=1 ni , no podemos formar submultisets ordenados de tamaño mayor.

P

3. Si h = 1, entonces tenemos un multiset en el que sólo está el elementos a1 repetido

n1 veces. Claramente, V ′ (r, 1) = 1, siempre que 0 ≤ r ≤ n1 , y V ′ (r, 1) = 0, si r > n1 .

4. Notar que la recurrencia anterior también es vália si r > hi=1 ni (en cuyo caso
P

V ′ (r, h) = 0), puesto que para cualquiera de los términos V ′ (r − j, h − 1) que aparece
en el sumatorio, se tiene que r − j > h−1 ′
i=1 ni , con lo que V (r − j, h − 1) = 0. Por
P

tanto, usando 1 y 3 como condiciones iniciales, se pueden calcular todos los valores
de V ′ (r, h) de forma recurrente, para h = 2, . . . , k y r > 0.
Teorema 5.5.5. Supongamos que S es un multiset con elementos a1 , . . . , ak , repetidos
n1 , . . . , nk veces, respectivamente. Definamos n = ki=1 ni . El número de submultisets de
P

S de tamaño 0 ≤ r ≤ n que se pueden obtener utilizando los primeros h elementos ai es

mı́n(r,nh )
C ′ (r − j, h − 1).
X
C ′ (r, h) =
j=0

En particular, el número de submultisets de S es C ′ (r, k).

Demostración. Tenemos que en un multiset de tamaño r el elemento ah puede aparecer j
veces, donde j puede variar desde 0 hasta mı́n(r, nh ). Una vez elegidas las j copias de ah , lo
que queda es un problema de calcular submultisets de tamaño r − j, usando los elementos
a1 , . . . , ah−1 , repetidos n1 , . . . , nh−1 veces. Por tanto, para h = 2, . . . , k y 1 ≤ r ≤ hi=1 ni ,
P

se tiene la siguiente recurrencia

mı́n(r,nh )
C ′ (r, h) = C ′ (r − j, h − 1).
X

j=0

Nota. 1. Si r = 0, entonces C ′ (0, h) = 1 para cualquier h. Como lo submultisets son

de tamaño r = 0, lo único que podemos elegir es el submultiset vacío.

2. Si r > hi=1 ni , entonces C ′ (r, h) = 0. Como el número de elementos en el multiset

P

es hi=1 ni , no podemos formar submultisets de tamaño mayor.

P

3. Si h = 1, entonces tenemos un multiset en el que sólo está el elemento a1 repetido

n1 veces. Claramente, C ′ (r, 1) = 1, siempre que 0 ≤ r ≤ n1 , y C ′ (r, 1) = 0, si r > n1 .

4. La recurrencia anterior también es válida si r > hi=1 ni , puesto que en ese caso
P

C ′ (r, h) = 0 y todos los términos C ′ (r − j, h − 1) del sumatorio son también cero.

Teorema 5.5.6. Para cualesquiera enteros 1 < n < r, pn (r) cumple la relación

pn (r) = pn−1 (r − 1) + pn (n − r).

Demostración. O bien el último sumando es 1, y el resto es una partición de r − 1 en n − 1

sumandos, o todos los sumandos son mayores o iguales a 2, y restando 1 a cada uno de
los n sumandos obtenemos una partición de r − n en n sumandos.
20 CAPÍTULO 5. COMBINATORIA ELEMENTAL
Capítulo 6

Funciones generatrices

6.1. Funciones generatrices y series de potencias formales

Definición 6.1.1. Dada una secuencia infinita de números f0 , f1 , . . . , fn , . . . (que incluso
pueden ser complejos), su función generatriz F (z), se define como la serie infinita

f0 + f1 z + f2 z 2 + · · · + fn z n + · · · .
P∞ n.
En forma compacta, F (z) = n=0 fn z

Una de las ventajas que tiene el uso de las funciones generatrices es que una función
generatriz puede interpretarse de dos formas distintas. Por una parte, se puede interpretar
como una expresión algebraica, cuya manipulación formal nos puede permitir descubrir
identidades o encontrar fórmulas explícitas para las secuencias de números. Por otra parte,
puede interpretarse como una suma infinita (una serie) para cada valor de z. En este último
caso, si D es el conjunto de valores de z para los que esa serie converge, la función generatriz
puede mirarse como una función F (z) de D en C, que a cada z ∈ D le asigna el valor de
esa suma infinita.
Definición 6.1.2. Una serie de potencias formal es una expresión de la forma

f0 + f1 z + f2 z 2 + · · · + fn z n + · · ·

donde los números fn se denominan los coeficientes de las serie y f0 , f1 , . . . , fn , . . . es la

secuencia de coeficientes. Dos series son iguales si tienen la misma secuencia de coeficientes.
Definición 6.1.3. Sean F (z) = ∞ n ∞ n
P P
n=0 fn z y G(z) = n=0 gn z las series formales de las
secuencias f0 , f1 , . . . , fn , . . . y g0 , g1 , . . . , gn , . . . , respectivamente.
• La suma de dos series formales, F (z) + G(z), es la serie formal
∞
X
F (z) = (fn + gn )z n .
n=0

• Dados a y b números cualesquiera, con aF (z) + bG(z) indicamos la serie formal

∞
X
F (z) = (afn + bgn )z n .
n=0

• El elemento neutro de la operación suma, que denotaremos por 0, es la serie con

todos los coeficientes nulos 0, 0, . . . . Por tanto, F (z) + 0 = F (z).

21
22 CAPÍTULO 6. FUNCIONES GENERATRICES

P∞ n.
• La serie opuesta de F (z) es −F (z) = n=0 (−fn )z

• El producto de dos series formales, F (z)G(z), es la serie formal

∞
X
H(z) = hn z n ,
n=0
Pn
donde hn = k=0 fk gn−k .

• El elemento neutro de la operación producto, que denotaremos por 1, es la serie con

coeficientes 1, 0, 0, . . . .
• G(z) es la recíproca de F (z) si el producto de ambas es la serie 1, es decir, si
F (z)G(z) = 1. En ese caso, escribiremos G(z) = F ′1(z) .

• La derivada F ′ (z) de una serie formal F (z) es la serie formal con término n-ésimo
(n + 1)fn+1 , es decir, F ′ (z) = ∞ n
P
n=0 (n + 1)fn+1 z .

• La integral 0z F (t)dt de una serie formal F (z) es la serie formal con término n-ésimo
R
fn−1
n , si n > 0, y 0, si n = 0.
P∞ n 1
Teorema 6.1.4. La serie formal F (z) = n=0 fn z tiene recíproca, F (z) , si y sólo si,
f0 ̸= 0.
Demostración. Al multiplicar la serie F (z) por una serie arbitraria G(z) = ∞ n P
n=0 gn z , el
coeficiente que acompaña a z n en ese producto es nk=0 fk gn−k . En particular, f0 g0 es el
P

coeficiente que acompaña a z 0 . Si f0 = 0, entonces f0 g0 = 0 y no podemos obtener la serie

1. Luego f0 ̸= 0 es una condición necesaria para que exista recíproca. Veamos ahora que
si f0 ̸= 0, entonces existe G(z) = ∞ n
P
Pn n=0 gn z , tal que F (z)G(z) = 1. Si F (z)G(z) fuese 1,
entonces el coeficiente k=0 fk gn−k que acompaña a zn en ese producto debe ser siempre
0, excepto si n = 0. En este último caso, ha de ser f0 g0 = 1. Como f0 ̸= 0, para que se
cumpla que f0 g0 = 1 podemos definir g0 como
1
g0 = .
f0
Una vez elegido g0 , para que f0 g1 + f1 g0 sea 0 (el coeficiente que acompaña a z en el
producto), hay que definir g1 como
−f1 g0
g1 = .
f0
En general, una vez definidos g0 , g1 , . . . , gn−1 , para que nk=0 fk gn−k = 0, hay que definir
P

gn como
− nk=1 fk gn−k
P
gn = .
f0
Con esta elección de g0 , g1 , . . . , gn , . . . , estamos definiendo una serie G(z) tal que F (z)G(z) =
1, como queríamos demostrar.

Nota. Si la secuencia de números es finita f0 , f1 , . . . , fn , la secuencia se puede considerar

infinita sin más que añadir infinitos ceros f0 , f1 , . . . , fn , 0, 0, . . . . En este caso, la función
generatriz de una secuencia finita f0 , f1 , . . . , fn es
F (z) = f0 + f1 z + · · · + fn z n + 0z n+1 + 0z n+2 + · · · .
Normalmente, una serie formal con un número finito de coeficientes no nulos se identifica
con un polinomio.
6.2. TEOREMA BINOMIAL GENERALIZADO 23

6.2. Teorema binomial generalizado

α

Definición 6.2.1. Sean n ∈ N y α ∈ R, n se define como
!
α α(α − 1) · · · (α − n + 1)
C(α, n) = = ,
n n!
α

excepto si n = 0, que en ese caso se define como 0 = 1.

Teorema 6.2.2 (Binomial generalizado). Para cualquier número real α y números arbi-
trarios x e y, se tiene que
∞
!
α
X α n α−n
(x + y) = x y .
n=0
n
x
Demostración. Haciendo el cambio z = y lo que queremos demostrar se transforma en

∞
!
α
X α n
(1 + z) = z .
n=0
n

Luego demostrar el teorema es equivalente a
demostrar esto último. Fijado α, sea F (z) la
función generatriz asociada a la secuencia α0 , α1 , . . . , αn , . . . . Nos bastará



con demostrar
α α

que la fórmula explícita de F (z) es precisamente (1 + z) . Sea fn = n . Por la definición
de αn = α(α−1)···(α−n+1)


n! , es fácil ver que fn satisface la siguiente recurrencia

α − (n − 1)
fn = fn−1
n
para todo n > 0, o equivalentemente

nfn = αfn−1 − (n − 1)fn−1 .

Por definición, F (z) = ∞

P ′ P∞ n−1 .
n=0 fn zn , con lo que se tiene que F (z) = n=1 nfn z Multi-
plicando la recurrencia anterior por z n−1 , obtenemos que

nfn z n−1 = αfn−1 z n−1 − (n − 1)fn−1 z n−1 .

Sumando para todo los valores de n mayores que 0, obtenemos

∞
X ∞
X ∞
X
nfn z n−1 = αfn−1 z n−1 − (n − 1)fn−1 z n−1
n=1 n=1 n=1

con lo que F ′ (z) = αF (z) − zF ′ (z). En consecuencia,

F ′ (z) α
= .
F (z) 1+z
F ′ (z) α
Como la derivada de ln(F (z)) es F (z) , y la de α ln(1 + z) es 1+z , necesariamente

ln(F (z)) = α ln(1 + z) + c = ln((1 + z)α ec ).

Por tanto, F (z) = (1 + z)α ec . La condición f0 = 1 = F (0) implica que la constante c de

la ecuación anterior deber ser cero, por lo que F (z) = (1 + z)α .
24 CAPÍTULO 6. FUNCIONES GENERATRICES

m+n−1

Corolario 6.2.3. 1. La función generatriz de la secuencia fn = (−1)n m−1 , para
un m natural fijado, es
1
F (z) = .
(1 + z)m
m+n−1

2. La función generatriz de la secuencia fn = m−1 , para un m natural fijado, es
1
F (z) = .
(1 − z)m
m+n−1
n
3. La función generatriz de la secuencia fn = m−1 γ , para un m natural fijado y
un valor γ fijado, es
1
F (z) = .
(1 − γz)m
Demostración. 1. Aplicando el teorema binomial generalizado para α = −m. Tenemos
que
∞
!
1 X −m n
= z .
(1 + z)m n=0 n
−m

Desarrollando n ,
!
−m −m(−m − 1) · · · (−m − n + 1)
=
n n!
m(m + 1) · · · (m + n − 1)
= (−1)n
n!
!
m+n−1
= (−1)n
n
!
n m+n−1
= (−1) .
m−1
1
Por tanto, (1+z)m es la función generatriz buscada.
1
2. Evaluando la función (1+z)m en −z obtenemos lo buscado.
1
3. Evaluando la función (1−z)m en γz obtenemos lo buscado.

6.3. Funciones generatrices racionales

Definición 6.3.1. Una función generatriz F (z) es racional si es de la forma
P (z)
F (z) =
Q(z)
donde P (z) y Q(z) son polinomios en z con deg(P ) < deg(Q).
Definición 6.3.2. Una secuencia f0 , f1 , . . . , fn , . . . se dice que satisface una recurrencia
lineal de orden k si existen cantidades a1 , . . . , ak , con ak ̸= 0, y en tales que
fn = a1 fn−1 + · · · + ak fn−k
con n ≥ k. Una recurrencia lineal se dice homogénea si en = 0, y se dice que tiene
coeficientes constantes si a1 , . . . , ak son constantes.
6.3. FUNCIONES GENERATRICES RACIONALES 25

Teorema 6.3.3. Sea a1 , . . . , ad una secuencia de números complejos, con d ≥ 1 y ad ̸= 0,

y sea Q(z) = 1 + a1 z + a2 z 2 + · · · + ad z d . Supongamos que las raíces de Q(z) = 0 son
1 1 Pk
γ1 , . . . , γk , con multiplicidades d1 , . . . , dk , respectivamente (por tanto i=1 di = d). Las
siguientes condiciones sobre la secuencia fn (de números complejos) son equivalentes:

1. Para todo n ≥ 0, fn+d + a1 fn+d−1 + a2 fn+d−2 + · · · + ad fn = 0.

Pk n
2. Para todo n ≥ 0, fn = i=1 pi (n)γi donde pi (n) es un polinomio en n de grado
menor que di .

3. La función generatriz asociada a la secuencia fn es

∞
X P (z)
fn z n =
n=0
Q(z)

donde P (z) es un polinomio de grado menor que d.

Definición 6.3.4. Dada una secuencia f0 , f1 , . . . , fn , . . . , satisfaciendo la recurrencia

fn+d + a1 fn+d−1 + a2 fn+d−2 + · · · + ad fn = 0

para n ≥ 0, al polinomio R(z) definido como

R(z) = z d + a1 z d−1 + a2 z d−2 + · · · + ad−1 z + ad

se le denomina polinomio característico o ecuación característica.

P (z)
Nota. La función generatriz F (z) asociada a la secuencia tendrá la forma Q(z) , con

Q(z) = 1 + a1 z + a2 z 2 + · · · + ad z d .

Por definición, R(z) coincide con z d Q( z1 ), lo que implica que si 1 1

γ1 , . . . , γk son las raíces de
Q(z), entonces γ1 , . . . , γk son las raíces de R(z).

Nota. Un método para resolver una recurrencia lineal homogénea con coeficientes cons-
tantes
fn+d + a1 fn+d−1 + a2 fn+d−2 + · · · + ad fn = 0
y condiciones iniciales f0 , f1 , . . . , fd−1 es el siguiente:

1. Buscar las raíces γ1 , . . . , γk , junto con sus multiplicidades d1 , . . . , dk , del polinomio

característico R(z) = z d + a1 z d−1 + · · · + ad−1 z + ad .

2. Plantear la solución genérica de la recurrencia

fn = (c10 + c11 n + · · · + c1d1 −1 nd1 −1 )γ1n + · · · + (ck0 + ck1 n + · · · + ckd1 −1 ndk −1 )γkn .

Como la suma de las multiplicidades es d, es decir ki=1 di = d, el número de cons-

P

tantes cji que aparecen en la solución genérica es precisamente d.

3. Encontrar las d constantes cji utilizando las condiciones iniciales f0 , f1 , . . . , fd−1 ,

resolviendo un sistema de d ecuaciones con d incógnitas.
26 CAPÍTULO 6. FUNCIONES GENERATRICES

Teorema 6.3.5. Sea F0 la familia de secuencia {fn } que satisfacen la recurrencia

fn+d + a1 fn+d−1 + a2 fn+d−2 + · · · + ad fn = 0,

sea F1 la familia de secuencia {gn } que satisfacen la recurrencia no homogénea

fn+d + a1 fn+d−1 + a2 fn+d−2 + · · · + ad fn = en ,

y sea {gn1 } una secuencia de F1 . Entonces

F1 = {gn1 } + F0

es decir, cualquier secuencia de la forma {gn1 +fn0 }, con {fn0 } una solución de la recurrencia
homogénea, es solución de la ecuación no homogénea, y no hay otras soluciones que no
sean de esa forma.
Teorema 6.3.6. Sea fn una secuencia que satisface la relación de recurrencia no homo-
génea
fn+d + a1 fn+d−1 + a2 fn+d−2 + · · · + ad fn = en .
Supongamos que en = q(n)γ0n , donde q(n) es un polinomio en n de grado h0 y γ0 es una
constante. Supongamos además que el polinomio Q(z) = 1+a1 z +a2 z 2 +· · ·+ad z d se puede
factorizar de la forma Q(z) = ki=0 (1 − γi z)di , siendo d0 + d1 + · · · + dk = d, pero donde
Q

puede ser que d0 sea cero (es decir, γ10 no sería raíz de Q(z)). Entonces, la recurrencia no
homogénea tiene una solución particular de la forma

nd0 (b0 + b1 n + · · · + bh0 nh0 )γ0n

donde b0 , b1 , . . . , bh0 son constantes.

Nota. El teorema anterior da un método para resolver una recurrencia lineal no homogé-
nea con coeficientes constantes, cuando la parte no homogénea es de una forma particular.
Dada la recurrencia

fn+d + a1 fn+d−1 + a2 fn+d−2 + · · · + ad fn = q(n)γ0n

con las condiciones iniciales f0 , f1 , . . . , fd−1 , donde q(n) es un polinomio en n de grado h0 ,

el método para resolverla sería el siguiente:
1. Buscar las raíces γ0 , . . . , γk , junto con sus multiplicidades d0 , . . . , dk , del polinomio
característico R(z) = z d + a1 z d−1 + · · · + ad−1 z + ad .

2. Usando la propia recurrencia, buscar una solución particular de la forma

gn1 = nd0 (b0 + b1 n + · · · + bh0 nh0 )γ0n ,

donde d0 será cero si γ0 no es raíz del polinomio característico.

3. Plantear la solución general como la suma de la solución genérica de la recurrencia

homogénea y la solución particular anterior

fn = (c00 + c01 n + · · · + c0d0 −1 nd0 −1 )γ0n + · · · + (ck0 + ck1 n + · · · + ckdk −1 ndk −1 )γkn + gn1 .

4. Encontrar las d constantes cji utilizando las condiciones iniciales f0 , f1 , . . . , fd−1 ,

resolviendo un sistema de d ecuaciones con d incógnitas.
Capítulo 7

Introducción a la teoría de grafos

27
28 CAPÍTULO 7. INTRODUCCIÓN A LA TEORÍA DE GRAFOS
Capítulo 8

Grafos con costos

29
30 CAPÍTULO 8. GRAFOS CON COSTOS
Capítulo 9

Flujo en redes y aplicaciones

31