Combinatoria – OME

1. Números factoriales, combinatorios y aplicaciones básicas

 Número factorial
Dado un número entero no negativo n , se define la factorial de n y se denota por n ! a:
n !=n ( n−1 ) … 1
 Número combinatorio
Dados dos números n , r enteros no negativos tal que n ≥ r , se define el numero combinatorio de n sobre k , y se

escribe (nr), como el cociente:

()
n= n!
r r ! ( n−r ) !
 Propiedades básicas de los números combinatorios

- (nr)=(n−rn )
- ( )=( )
n n
0 n
- ( )+ (
r r +1 ) ( r +1 )
n n = n+1

DEMOSTRACIÓN. Las primeras dos propiedades se prueban inmediatamente con la definición ya que:

()
n! n!
n= =
( )
= n
r r ! ( n−r ) ! ( n−r ) ! r ! n−r

()
n = n ! =1=
()
n!
Y = n . Para probar la tercera propiedad operamos algebraicamente:
0 0!n! n! ( n−n ) ! n

()( )
n + n = n! n! n! n!
+ = + =¿
r r +1 r ! ( n−r ) ! ( r +1 ) ! ( n−r −1 ) ! r ! ( n−r ) ( n−r−1 ) ! ( r + 1 ) r ! ( n−r−1 ) !
n ! ( r +1 ) +n !(n−r ) n ! ( r +1+n−r ) ( n+ 1 ) n ! ( n+1 ) !
¿ = = =
( )
= n+1
r ! ( r+ 1 )( n−r ) ( n−r−1 ) ! (r +1)! ( n−r ) ! (r +1)! ( n−r ) ! (r +1)! ( n−r ) ! r +1
∎
 Número de subconjuntos de cierta cantidad de elementos de un conjunto

El número de subconjuntos de r elementos que tiene un conjunto de n elementos es (nr).

 Número de subconjuntos de un conjunto
Un conjunto de n elementos tiene 2n subconjuntos, contando el vacío y el conjunto total.
 Triángulo de Tartaglia
El triángulo de Tartaglia se representa por:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
… … … … … …
Y cumple que:
- En cada fila los extremos son iguales a 1.
- Cada elemento del interior es la suma de los dos que tiene encima.

- Los elementos de la fila enésima son (n0) ,(n1) , … ,(nn) en ese mismo orden.
 Binomio de Newton
El desarrollo de ( a+ b )n es:
n
n

k=0 k
() 0 () ()1 n−1 ( )
( a+ b ) =∑ n a k b n−k = n an + n a n−1 b+ …+ n a bn−1 + n b n
n ()
Y el caso de ( a−b )n es idéntico pero los signos se alternan:
n
n

k=0 k
() 0 1 () ()
( a−b ) =∑ n ak (−b)n −k = n a n− n a n−1 b+ …+ (−1 )
n−1

n−1 ( )
n a b n−1+ (−1 )n n bn
n ()
 Propiedades avanzadas de los números combinatorios

- (n0)+(n1)+…+(nn)=2 n

- ( )−( ) +…+ (−1 ) ( )=0

n n n n
0 1 n
- ( ) +(
r ) ( r ) ( r +1)
r r +1 + …+ n = n+1
r
- ( )( ) +( )(
1 r−1 ) ( r )( 0 ) ( r )
n m n m +…+ n m = m+ n
0 r
2 2 2
-
(n0) +( n1) + …+( nn) =(2nn)
DEMOSTRACIÓN. Para demostrar la primera propiedad desarrollamos por binomio de Newton 2n= (1+1 )n:
n n
n

r =0 r
()
2n= (1+1 ) =∑ n 1r 1n−r =∑ n = n + n +…+ n
r=0 r 0 1 n () ()() ()
n n
Análogamente desarrollando 0=0 = (1−1 ) se demuestra la segunda propiedad:
n n
0=0 = (1−1 ) =∑
n n

r=0
()
n 1 r (−1 )n−r=
r
∑
r=0 r
() 0 () ()
1 ()
n (−1 )n−r= n − n +…+ (−1 )n n
n
∎
2. Técnicas de conteo
 Variaciones sin repetición
Dado un conjunto de n elementos se denomina variaciones sin repetición de n elementos tomados de k en k como
el número de subconjuntos ordenados que se pueden formar con k elementos distintos del conjunto. Es decir,
consideramos que dos subconjuntos son distintos si tienen algún elemento distinto o lo tienen en distinto orden. Se
k
denota por V n y se calcula como:
k
V n=n ( n−1 ) …(n−k +1)
 Variaciones con repetición

Dado un conjunto de n elementos se denomina variaciones con repetición de n elementos tomados de k en k como
el número de subconjuntos ordenados que se pueden formar con k elementos distintos o no del conjunto. Es decir,
consideramos dos subconjuntos distintos si tienen algún elemento distinto o lo tienen en distinto orden. Se denota
k
por VRn y se calcula como:
k k
VRn=n
 Permutaciones sin repetición
Dado un conjunto de n elementos se denomina permutaciones sin repetición de n elementos como el número de
subconjuntos ordenados que se pueden formar con los n elementos del conjunto sin que haya ninguno repetido. Es
decir, consideramos dos subconjuntos distintos si tienen algún elemento en distinto orden. Se denota por Pn y se
calcula como:
Pn=n!
 Permutaciones cíclicas o circulares
Dado un conjunto de n elementos se denomina permutaciones cíclicas o circulares de n elementos a un caso
particular de las permutaciones sin repetición en el que los elementos se han de ordenar “en circulo”, es decir donde
“se situé” el primer elemento en la muestra determina el principio y el fin de esta. Se denota por PC n y se calcula
como:
PC n =P n−1=( n−1 ) !
 Permutaciones con repetición
Dado un conjunto de n elementos con r elementos distintos (1 , … , r ), de modo que el elemento i-ésimo está
repetido k i veces (es decir, k 1+ k 2+ …+k r=n ), se define las permutaciones con repetición como el número de
formas distintas de ordenar nuestros n elementos, considerando dos subconjuntos distintos si tienen algún elemento
k , k ,… ,k
en distinto orden (los elementos repetidos son indistinguibles unos de otros). Se denota por Pn 1 2 r
y se calcula
como:
k 1 , k 2 ,… ,k r n!
Pn =
k1! … kr !
 Combinaciones sin repetición
Dado un conjunto de n elementos se denomina combinaciones sin repetición de n elementos tomados de k en k al
número de subconjuntos no ordenados que se pueden formar con k elementos distintos del conjunto. Es decir,
consideramos dos subconjuntos distintos si tienen algún elemento distinto, sin importar el orden en que se
k
encuentren. Se denota por C n y se calcula como:
V kn n
C kn=
Pk k
= ()
 Combinaciones con repetición
Dado un conjunto de n elementos distintos se denomina combinaciones con repetición de n elementos tomados de
k en k al número de subconjuntos que se pueden formar con k elementos distintos o no del conjunto. Considerando
dos subconjuntos distintos si tienen algún elemento distinto, sin importar el orden en que se encuentren. Se denota
k
por CR n y se calcula como:

CR n= n+ k−1
k

k ( )
3. Principios de la combinatoria
 Principio de la multiplicación
Si un evento A se puede realizar de m formas diferentes y luego se puede realizar otro evento B de n formas
diferentes, el número total de formas en que pueden ocurrir A y B es igual a m ×n. Es decir, ambos eventos se
realizan, primero uno y luego el otro. El “y” indica multiplicación.
 Principio de la suma
Si un evento A se puede realizar de m maneras diferentes, y otro evento B se puede realizar de n maneras
diferentes, además, si ocurre uno no puede ocurrir el otro, entonces, el evento A o el evento B, se realizarán de
m+n formas. Es decir, aquí ocurre A o B. El “o” indica suma.
 Principio del Palomar o Teorema de Dirichlet
Si tenemos más palomas que palomares al menos un palomar tiene más de una paloma. Generalizando, si tenemos n
elementos a repartir en m grupos tal que:
n=cm+r
Siendo c el cociente de la división entera y r el resto, si r ≠ 0, entonces cada uno de los grupos habrá al menos c +1
elementos.
4. Invariantes y teoría de juegos
 Invariantes
Una invariante es una magnitud que permanece constante en un problema, puede ser una suma, un producto, etc.
Son útiles para resolver muchos problemas, pero no hay una forma específica de encontrarlas.
 Demostración de invariantes
Para demostrar que una propiedad f (n) es invariante basta con demostrar que f ( n )=f (n+1).
 Teoría de juegos
La teoría de juegos es un área de la matemática aplicada que utiliza modelos para estudiar interacciones en
estructuras formalizadas de incentivos.
 Conceptos básicos de la teoría de juegos
- Jugadores: son las partes que toman decisiones estratégicas.
- Estrategias: son las opciones que cada jugador puede elegir.
- Pagos o recompensas: son los resultados asociados a cada combinación de estrategias.
 Estrategia ganadora
Que un jugador tenga estrategia ganadora quiere decir que si aplica dicha estrategia gana el juego sin importar la
estrategia del otro u otros jugadores.
5. Lógica proposicional
 Condición necesaria y suficiente
Se dice que una condición es necesaria para que se cumple cierta afirmación cuando si no se cumple diche condición
a afirmación no se puede cumplir, pero puede darse el caso de que se cumple la condición y la afirmación no. Por
otro lado, se dice que una condición es suficiente para que se cumple cierta afirmación si al cumplirse dicha
condición se cumple inmediatamente la afirmación, es decir, la condición implica la afirmación.
 Símbolos lógicos básicos
- Entonces (o implica que) se representa por ⇒ o →.
- Si y solo si (afirmación en ambas direcciones) se representa por ⇔.
- El negado de una afirmación p, es decir, la afirmación contraria se representa por ¬ p .
 Recíproco de una afirmación
Si una afirmación p implica una afirmación q , entonces se dice que q es el recíproco de p.
 Teorema del contrarrecíproco
Si p implica q , entonces el negado de q implica el negado de p, es decir, la afirmación contraria.
6. Teoría de conjuntos
 Conjuntos
Un conjunto es una agrupación de elementos similares. Los conjuntos que contiene números se conocen como
+¿, Z ,Q , I , R , C ¿
conjuntos numéricos, algunos son N , N 0 , Z , Z ≥0
que son los naturales, los naturales con el cero, los
enteros, los enteros positivos, los enteros no negativos, los racionales, los irracionales, los reales y los complejos
respectivamente.
 Pertenencia de un elemento a un conjunto
Si un elemento a pertenece a un conjunto A se denota por a ∈ A . Si no pertenece se denota por a ∉ A .
 Inclusión e igualdad de conjuntos
Un conjunto A esta incluido o contenido (lo que es lo mismo a que sea un subconjunto) en otro conjunto B si todos
los elementos de A pertenecen también a B. Se representa por A ⊂ B. Por otra parte, dos conjuntos A y B son
iguales si están formados por los mismos elementos. Se representa por A=B . Si el conjunto pertenece o es igual se
denota por A ⊆ B.
 Unión de conjuntos
Si tenemos dos conjuntos A y B, llamamos conjunto unión de A y B al conjunto que tiene todos los elementos que
están en A o B. Se representa por A ∪ B.
 Intersección de conjuntos
Si tenemos dos conjuntos A y B, llamamos conjunto intersección de A y B al conjunto que tiene todos los
elementos que están en A y B. Se representa por A ∩ B.
 Conjuntos contrarios
Para un conjunto cualquiera A contenido en otro conjunto E , llamamos conjunto contrario de A al conjunto que
tiene los elementos que no están en A pero si en E , y recíprocamente. Se representa por A . Cumplen las siguientes
propiedades:
- A ∪ A=E
- A ∩ A=∅
- E=∅
- ∅ =E
 Diferencia de conjuntos
Dados dos conjuntos A y B contenidos en otro conjunto E , llamamos diferencia de A y B, se escribe A−B , al
conjunto que tiene los elementos que pertenecen a A y no a B. Se calcula como:
A−B= A ∩ B
 Algebra de Boole de conjuntos
Las operaciones unión, intersección y complementación (contrario) verifican las propiedades:
- Conmutativa: A ∪ B , B ∪ A
- Asociativa: A ∪ ( B∪ C )= ( A ∪ B ) ∪ C , A ∩ ( B∩C )= ( A ∩ B ) ∩C
- Idempotente: A ∪ A=A , A ∩ A= A
- Simplificación: A ∪ ( B∩ C )= A , A ∩ ( B ∪ C )=A
- Distributiva: A ∪ ( B∩ C )= ( A ∪ B ) ∩ ( A ∪ C ) , A ∩ ( B ∪C )=( A ∩ B)∪ (A ∩C)
- Elementos neutros: A ∪ ∅ = A , A ∩ E= A
- Absorción: A ∪ E=E , A ∩∅ = A
Las familias de conjuntos que verifican las propiedades anteriores se denominan algebras de Boole.
 Cardinal de un conjunto
El cardinal de un conjunto A se denota por | A| y se define como la cantidad de elementos del conjunto A .
 Principio de inclusión-exclusión
Si tenemos dos conjuntos A y B, el número de elementos en su unión es:
| A ∪ B|=|A|+|B|−| A ∩ B|
Y en general para n conjuntos A1 , A 2 ,… , A n, el numero de elementos en la unión se calcula como:
n

|¿ i=1 ¿ n A i|=∑ (−1 ) ∑ |A i ∩ Ai ∩… ∩ Ai |

k +1
1 2 k
k=1 1 ≤i 1 <…<i k ≤n
Lo que podemos interpretar como que se suman los tamaños individuales, se restan las intersecciones de pares, se
suman las intersecciones de tríos y se continúa alternado de signos hasta la intersección de todos los conjuntos.
 Máximo de un conjunto
Sea un conjunto A , su máximo es el mayor elemento del conjunto, y lo escribimos como máx
❑
A . Muchas veces se
representa el conjunto directamente por la lista de elementos.
 Mínimo de un conjunto
Sea un conjunto A , su mínimo es el menor elemento del conjunto, y lo escribimos como mín
❑
A . Muchas veces se
representa el conjunto directamente por la lista de elementos.
 Aplicaciones entre conjuntos
Una aplicación f entre dos conjuntos A y B es una correspondencia que relaciona los elementos de ambos
conjuntos, se denota por f : A → B . Si una aplicación relaciona a cada elemento de A con un único elemento de B se
dice que la aplicación es una función, y se llama a A dominio y a B recorrido o imagen. Existen tres tipos de
funciones según como relacionan los elementos:
- Inyectiva: una función f : A → B es inyectiva si cada elemento de B no está relacionado con más de un elemento
en A , se cumple que si f ( a )=f (b), entonces a=b .
- Sobreyectiva: una función f : A → B es sobreyectiva si cada elemento de B proviene de algún elemento de A .
- Biyectiva: una función f : A → B es biyectiva si es inyectiva y sobreyectiva a la vez, se cumple que existe otra
función f −1 : B → A , llamada función inversa tal que f ( f −1 ( x ) )=f −1 ( f ( x ) )=x .
- Multiplicativa: una función f : A → B es multiplicativa si f ( ab )=f ( a ) f (b).
7. Teoría de grafos
 Grafos
Un grafo es un conjunto de vértices (también llamados nodos), que representan objetos, conectados por aristas, que
representan una relación entre los objetos. Como se representen no importa, solo importa las conexiones entre ellos.
 Grado o valencia de un vértice
El grado o valencia de un vértice de un grafo es el número de vértices con los que está conectado, la valencia de un
vértice v se representa por δ ( v ).
 Grado de un grafo
El grado de un grafo es mayor grado de los nodos que contiene.
 Camino en un grafo
Un camino en un grafo es una sucesión de aristas adyacentes que va de un vértice a otro o a el mismo, en este
segundo caso al camino se le conoce como camino cerrado o ciclo.
 Caminos Eulerianos
Dado un grafo, un camino que recorre todas las aristas del grafo sin repetirlas se conoce como camino Euleriano.
Para que exista un camino Euleriano en un grafo como máximo puede haber dos vértices con grado impar, si solo hay
dos vértices con grado impar por estos se inicia y acaba el camino, y en caso de que todos los vértices tengan grado
par entonces el camino empieza y acaba en el mismo vértice.
 Caminos Hamiltonianos
Dado un grafo, un camino que recorre todos los vértices sin repetir ninguno se conoce como camino Hamiltoniano. Si
un grafo tiene un vértice con grado uno entonces no existe un camino Hamiltoniano que lo recorra.
 Distancia y diámetro de un grafo
En un grafo, la distancia entre dos vértices es el menor número de aristas de un recorrido entre ellos. El diámetro, en
una figura como un grafo, es la mayor distancia entre todos los pares de puntos de la misma.
 Tipos de grafos básicos
- Grafos camino: cada vértice se conecta con el siguiente formando un camino.
- Grafos ciclo: cada vértice se conecta con otros dos formando un ciclo.
- Grafos rueda: todos los vértices menos 1 forman un ciclo, y estos se conecta al restante.
- Grafos completos: todos los vértices están conectados entre sí.
- Grafos bipartitos: están formados por dos grupos de vértices que no se conectan entre ellos, si los grupos están
totalmente conectados se les denomina bipartitos completos.
- Grafo conexo: no hay ningún vértice sin conectar.
- Grafo no conexo: hay algún vértice sin conectar.
 Forma formal de definir un grafo
Un grafo G cualquiera se puede definir con dos conjuntos V y A , donde V es el conjunto de todos los vértices del
grafo enumerados y A es el conjunto que tiene todas las aristas del grafo, que se representan con el conjunto que
contiene los dos vértices que la definen, esto se denota como G=(V , A) .
 Forma formal de definir una arista
Una arista de un grafo se puede definir con los dos vértices que al unirse forman la arista, para una arista e formada
por la unión de unos vértices v y w , la arista e se define como e= {u , v }.
 Lema del apretón de manos
La cantidad de aristas de un grafo, | A| , se puede calcular como:
∑ δ(v)
v ∈V
| A|=
2
Donde δ (v) representa la valencia del vertice y es el conjunto de todos los vértices.
v V
 Grafos dirigidos
Si las aristas de un grafo tienen un sentido se dice que el grafo es dirigido, de este modo a un grafo G se le puede
¿
asociar un grafo G que tiene el mismo número de vértices y aristas que G solo que sus aristas tienen sentido.
 Grado de salidas y entradas de un vértice
A la cantidad de aristas que “salen” de un vértice v se les conoce como grado de salidas (outdegree) de v y se denota
por outdeg v , de manera análoga se el grado de entradas (indegree) de un vértice v que se denotan por indeg v .
 Subgrafo de un grafo
Sea G=(V , A) , se dice que T =( V ' , A ' ) es un subgrafo de G si V ' ⊆ V y A' ⊆ A , es decir, si T esta “contenido” en
G.
 Árbol
Un grafo que no tiene ciclos y que conecta a todos los puntos, se llama un árbol. En un grafo con n vértices, los
subgrafos que sean árboles tienen exactamente n−1 aristas, y hay n n−2 árboles posibles. Su importancia radica en
que los árboles son grafos que conectan todos los vértices utilizando el menor número posible de aristas. En un árbol
solo existe un nodo sin anterior, que se dice que no tiene padre, el resto de nodos tienen un único padre. Se pueden
distinguir los nodos hoja, que no son más que nodos que no tienen hijos, es decir, son terminales, además, todos los
arcos son dirigidos, ya que siempre implican una relación “es padre de”.
 Spanning tree
Un spanning tree (árbol abarcador o árbol recubridor) de un grafo conexo no dirigido es un subgrafo que cumple las
siguientes características:
- Es un árbol, es decir, es un grafo sin ciclos.
- Contiene todos los vértices del grafo original.
- Tiene exactamente n−1 aristas, donde n es el número de vértices del grafo.
Básicamente, un spanning tree es una forma de conectar todos los vértices del grafo con el menor número posible de
aristas y sin formar ciclos.
 Grafo plano
Un grafo plano es un grafo que puede ser dibujado en el plano sin que ninguna arista se cruce.
 Caras de un grafo
Las caras de un grafo plano son las regiones del plano que están acotadas por aristas y ya no se pueden dividir en
más subregiones.
  Teorema de Euler para los grafos planos
En todo grafo conexo y plano que esté apropiadamente representado se verifica que:
C+ V − A=2
Donde C es el número de caras del grafo, V el número de vértices y A el de aristas. Además, esta relación también
se cumple en todos los poliedros convexos.
 Teorema de los cuatro colores
Cualquier mapa plano puede colorearse con un máximo de cuatro colores de manera que no haya dos regiones
adyacentes con el mismo color. Un "mapa plano" se puede modelar como un grafo planar, donde cada región es un
vértice y las fronteras entre regiones son aristas, además que dos regiones sean adyacentes significa que comparten
un borde, no solo un punto.