Academia Sabatina Jóvenes Talentos

Combinatoria Nivel Centro

Principio de Inyección y Biyección

Tomas A. Hernández

Suponga que un grupo de n estudiantes asisten a una conferencia en una sala de

200 asientos. Asuma que ningún estudiante ocupa mas de un asiento y que ningún par
de estudiantes comparten un asiento. Si se sabe que cada estudiante tiene una silla,
entonces tenemos n ≤ 200. Si sabemos luego que ningún asiento quedo disponible,
entonces podemos asegurar que n = 200 sin aun contar el número de estudiantes.
Este es un ejemplo que ilustra dos simples principios que vamos a establecer. Antes
de hacerlo, daremos algunas definiciones. Sean A y B dos conjuntos finitos. Una
correspondencia f : A → B de A a B es inyectiva (o una a una) si f (a1 ) 6= f (a2 ) en
B siempre que a1 6= a2 en A. f es sobreyectiva (o sobre) si para algún b ∈ B, existe
a ∈ A tal que f (a) = b. f es biyectiva si es inyectiva y sobreyectiva.
El principio de Inyección

Sean A y B conjuntos finitos. Si hay una inyección de A a B entonces |A| ≤ |B|

El principio de Biyección

Sean A y B conjuntos finitos. Si hay una biyección de A a B entonces |A| = |B|

Como el principio de la multiplicación o la suma, estos principios parecen bas-

tantes triviales. Sin embargo, a como veremos abajo, ellos son utiles y poderosas
herramientas para resolver problemas de conteo.
Ejemplo 0.0.1
Un estudiante desea caminar desde la esquina X a la esquina Y a traves de las
calles como se muestran en el mapa de carreteras de abajo. ¿Cuántos caminos
cortos hay de X a Y disponibles para el estudiante?

Solución: Sea A el conjunto de todos los caminos cortos desde X a Y . Queremos

hallar |A|.

Primero observemos que cada camino corto consiste de 7 segmentos, de los cua-
les 4 son horizontales y 3 verticales. Si usamos un ”0” para denotar un segmento
horizontal y un ”1” para designar un segmento vertical, entonces cada ruta en A
puede ser representada por una secuencia binaria de longitud 7 con 4 ceros y 3 unos.
Esta forma de representar un camino (ruta) claramente define una correspondencia

1
f de A a B de todas las secuencias binarias de longitud 7 con 4 ceros y 3 unos. Es
fácil ver que f es inyectiva y sobreyectiva y por tanto es una
 biyección de A a B.
Asi que por el Principio de Biyección, tenemos |A| = |B| = 73 .

Dado un conjunto X, el conjunto potencia de X, denotado por P (x), es el con-

junto de todos los subconjuntos de X, inclusive de X y el conjunto vacı́o ∅. Asi por
ejemplo, si X = {1, 2, 3}, entonces:

P (x) = {∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, X}

Observamos que P (x) = 8. En general, ¿Que podemos decir de |P (x)| si X consiste

de n elementos distintos?
Ejemplo 0.0.2
Muestre que si |X| = n, entonces |P (x)| = 2n para todo entero n ∈ N

Solución: Podemos asumir que X = {1, 2, · · · , n}. Ahora, sea

B = {a1 a2 · · · an |ai = 0 o 1, i = 1, 2, · · · , n}

sea el conjunto de todas las secuencias binarias de longitud n.

Define una correspondencia f : P (x) → B como sigue: Para cada S ∈ P (x),

ponemos
f (S) = b1 b2 · · · bn
donde 
1 si i ∈ S
bi =
0 si i ∈
/S
(Por ejemplo si X = {1, 2, 3, 4, 5}, S1 = {4} y S2 = {2, 3, 5}, entonces f (S1 ) =
00010 y f (S2 ) = 01101). Es fácil ver que f es una biyección de P (x) a B. Asi por el
principio de la Biyección |P (x)| = |B|. Ya que |B| = 2n , tenemos que |P (x)| = 2n
como se queria.
Ejemplo 0.0.3
Sea X = {1, 2, · · · , n}, donde n ∈ N . Muestre que el número de r− combinaciones
de X que no contienen enteros consecutivos esta dado por

n−r+1
!

donde 0 ≤ r ≤ n − r + 1

Solución: Sea A el conjunto de las r− combinaciones de X que no contienen

enteros consecutivos, y B el conjunto de las r− combinaciones de Y , donde

Y = {1, 2, · · · , n − (r − 1)}

estableceremos una biyección de A a B.

2
 Sea S = {s1 , s2 , · · · , sr } un miembro de A, asumiremos que s1 < s2 < · · · < sr .
Definimos
f (S) = {s1 , s2 − 1, s3 − 2, · · · , sr − (r − 1)}
observe que como si y si+1 no son consecutivos, todos los números en f (S) son
distintos. Por tanto, f (S) ∈ B, y asi f es una correspondencia de A a B. Es fácil
ver que f es inyectiva. Para ver que es sobreyectiva, sea T = {t1 , t2 , t3 , · · · , tr } un
miembro de B. Considere

S = {t1 , t2 + 1, t3 + 2, · · · , tr + (n − 1)}

Puede checarse que S es un miembro de A. También f (S) = T por definición.

Esto muestra que f : A → B es una biyección. Por el principio de biyección

n−r+1
!
|A| = |B| =
r

Ejemplo 0.0.4
En un campeonato de béisbol jugado por el sistema de eliminatorias se enfrentan
n equipos. En cada ronda los equipos perdedores salen del torneo. Al formar los
pares de equipos que se van a enfrentar puede eventualmente quedar un equipo
sin jugar; éste descansa y pasa a la ronda siguiente. Se desea saber cuántos juegos
se realizarán durante el campeonato.

Solución: Aparentemente una forma de resolver este problema serı́a contar el

número de juegos en cada ronda y sumar. Pero este cálculo se complica por la
posibilidad de tener un número impar de equipos en algunas rondas, y un número
par en otras. El caso más simple se da cuando el número de equipos participantes
es una potencia de 2, digamos n = 2k . Entonces evidentemente habrá k rondas, y
el número total de juegos será 2k−1 + 2k−2 + · · · + 1, o sea 2k − 1 = n − 1. Usando
el principio de correspondencia podemos demostrar que, en general, el número de
partidos será siempre n − 1. En efecto, al finalizar el campeonato tendremos un
equipo campeón y n−1 equipos eliminados. Cada uno de ellos fue eliminado en algún
partido (y sólo en uno), y en cada partido fue eliminado un equipo. Esto significa
que la correspondencia que asigna a cada partido jugado el equipo eliminado en
dicho partido, es biyectiva. Por lo tanto se jugaron tantos partidos como equipos
resultaron eliminados, esto es n − 1.
Ejemplo 0.0.5
Demostrar que el número de particiones de n en partes distintas es igual al número
de particiones de n en partes impares.

Solución:Construiremos una biyección entre el conjunto de particiones de n en

partes distintas con el conjunto de particiones de n en partes impares.

A partir de la partición de n en partes distintas, escribamos cada parte de n

como a · 2b , donde a es impar, y luego dividir la parte en 2b partes, todas iguales a a.
Esto da una partición de n en partes impares. Por ejemplo, a partir de la partición
(12, 7, 6, 4, 1) de 30, tenemos

3
 30 = 12 + 7 + 6 + 4 + 1
= 3 · 22 + 7 · 20 + 3 · 21 + 1 ·2 +1 · 20
= (3 + 3 + 3 + 3) + 7 + (3 + 3) + (1 + 1 + 1 + 1) + 1
=7+3+3+3+3+3+3+1+1+1+1+1

Entonces obtenemos la partición (7, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1) en partes distintas. Pa-

ra la dirección inversa, comenzamos con una partición de n en partes distintas. Hay
k partes iguales a a, donde a es impar, sea k = 2k1 + 2k2 + · · · + 2kn para distinto
enteros positivos k1 , k2 , · · · kn (esto es equivalente a la representación binaria de k).
Ahora se crean las partes a · 2ki para cada i. Tenga en cuenta que las partes resultan-
tes son todas distintas, ya que cada entero se puede escribir únicamente como a · 2b
donde a es impar. Por ejemplo, a partir de la partición (7, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1)
de 30, tenemos

30 = 7 + 3 + 3 + 3 + 3 + 3 + 3 + 1 + 1 + 1 + 1 + 1
=7·1+3·6+1·5
= 7 · 20 + 3 · (22 + 21 ) + 1 · (22 + 20 )
= 7 + 3 · 22 + 3 · 21 + 1 · 22 + 1 · 20
= 7 + 12 + 6 + 4 + 1

Entonces volvemos a la partición (12, 7, 6, 4, 1). Observe que los dos procedimien-
tos recién descritos son inversos entre sı́. Ası́ hemos demostrado que el número de
particiones de n en partes distintas es igual al número de particiones de n en partes
impares.
Ejemplo 0.0.6
Sea n un entero positivo. Determine el número de caminos con coordenadas enteras
desde (0, 0) a (n, n) usando solo movimientos hacia arriba y hacia la derecha y de
modo que el camino permanezca en la región x ≥ y.

Solución: Anteriormente vimos que el número total de caminos con  coordena-

das enteras desde (0, 0) a (n, n) sin la restricción x ≥ y es igual a n . Contemos
2n

el número de caminos que estan dentro de la región x < y. Llamaremos a estos

caminos caminos malos.

Supongamos que P es un camino malo. Dado que P esta en la región x < y,

debe cruzar la lı́nea y = x + 1 en algún punto. Sea X el primer punto del camino P
que se encuentra sobre la lı́nea y = x + 1. Ahora, reflejamos la porción del camino P
hasta X sobre la lı́nea y = x + 1, manteniendo la última porción de P es la misma
posición. Esto nos da un nuevo camino P 0 .

4
 Afirmamos que esto nos da una biyección entre el conjunto de caminos malos
al conjunto de caminos con coordenadas enteras desde (−1, 1) a (n, n) usando solo
movimientos hacia arriba y hacia la derecha.

Aquı́ está la construcción inversa. Para cualquier camino Q de (−1, 1) a (n, n),
sea X sea el primer punto en el camino que se encuentra en la lı́nea y = x + 1, y sea
Q0 un camino construido a partir de Q reflejando la primera porción de Q hasta X
a través de la lı́nea y = x + 1 y manteniendo el resto igual. Entonces el inverso de
la biyección dada arriba envı́a Q a Q0 .
Para completar la prueba de esta afirmación, necesitamos verificar una serie de
detalles a continuación. El lector debe pensar por qué la afirmación es verdadera.

• La construcción inversa está bien definida. Es decir, siempre podemos encon-

trar tal punto X, y también el camino resultante Q0 es siempre un camino
malo.

• Las dos construcciones son inversas entre sı́

El número de caminos malos es igual al número de caminos desde  (−1, 1) a (n, n)

usando solo movimientos hacia arriba y a la derecha, y hay n+1 de tales caminos.
2n

Por lo tanto, el número total de caminos buenos, es decir, aquellos que no entran en
la región x < y, es igual a

2n 2n 2n 2n 1 2n
! ! ! ! !
n
− = − =
n n+1 n n+1 n n+1 n+1

Este es nuestro primer ejemplo de algo que se cuenta con los Números de Catalan.
Número de Catalan

El n-ésimo número catalán es

1 2n
!
Cn =
n+1 n+1

He aqui mas ejemplos

5
Ejemplo 0.0.7
Demuestre que el n-ésimo número Catalán cuenta el número de expresiones que
contiene n pares de paréntesis que coinciden correctamente, es decir si uno abre
haya otro que cierre. Por ejemplo, para n = 3.

((())) (()()) (())() ()(()) ()()()

Solución: Podrı́amos resolver este problema usando técnicas similares al ejem-

plo anterior. Una solución mucho más rápida es encontrar una biyección entre estas
expresiones de paréntesis y los caminos contados en el problema anterior. De hecho,
tenga en cuenta que al interpretar ”(” como un movimiento a la derecha a la derecha
y ”)” como un movimiento hacia arriba, obtenemos la biyección deseada. La con-
dición de que la expresión entre paréntesis coincida corresponde exactamente a la
condición de que el camino de la red no vaya en la región x < y (¿por qué?). Esta bi-
yección muestra que el número de expresiones de n pares de paréntesis que coinciden
correctamente también es igual al n-ésimo número catalán, como se deseaba.
La biyección anterior era bastante simple. Miremos otro ejemplo mas elaborado
de los números de Catalan.

Un árbol plano es un objeto con la siguiente estructura. Empezamos con un

vértice raı́z (dibujado en la parte superior), y luego con cada nodo adjuntamos
una serie de nuevos vértices (posiblemente ninguno), donde importa el orden de los
vértices adjuntos. Por ejemplo, hay exactamente 5 arboles planos con 4 vértices:

Ejemplo 0.0.8
Demuestre que el n-ésimo número catalán cuenta el número de árboles planos con
n + 1 vértices.

Solución: Produciremos una biyección entre los arboles planos y las expresiones
entre paréntesis considerados en el ejemplo anterior. Primero describimos un algo-
ritmo para convertir un árbol plano a una expresión con paréntesis.

Dado un árbol plano, comenzando desde el vértice superior, vamos lo más abajo
posible hasta llegar a un vertice inferior, y luego retrocedemos a un punto de bifur-
cación, donde luego exploramos una nueva rama. Siempre exploraremos las ramas
de un vértice en orden de izquierda a derecha. Por ejemplo, comenzando con el
siguiente plano

6
 obtenemos el siguiente camino, donde los pasos están etiquetados en orden

Ahora registramos la secuencia de pasos que dimos, anotando un ”(” cada vez que
dimos un paso hacia abajo a lo largo de una arista, y un ”)” cada vez que caminamos
hacia arriba a lo largo de una arista. Por ejemplo, el paseo anterior corresponde a

((())(()()))(()()())

Un árbol plano con n + 1 vértices siempre produce una expresión que coincide
con una expresion de n pares de paréntesis emparejados correctamente (¿por qué
está emparejado correctamente?). Por el contrario, dado una expresión de n pares
de paréntesis correctamente emparejados, es posible invertir esta construcción para
producir un árbol plano que corresponda. Primero debe convencerse usted mismo
que este es el caso, puede escribir algunas expresiones entre paréntesis y luego dibujar
el árbol correspondiente. Luego, escribir una descripción de esta biyección.
Ejemplo 0.0.9
Una permutación x1 x2 · · · x2n del conjunto {1, 2, · · · , 2n}, donde n ∈ N , se dice
que tiene la propiedad P si |xi −xi+1 | = n para al menos un i en {1, 2, · · · , 2n−1}.
Muestre que, para cada n, hay mas permutaciones que tienen la propiedad P que
permutaciones que no la tienen.

Solución: Sea S = {1, 2, · · · , 2n}. Claramente, una permutación de S no tiene

la propiedad P si y solo si para cada k = 1, 2, · · · , n, la pareja de números k y n + k
no son adyacentes en la permutación. Para n = 2, el conjunto A de permutaciones
sin la propiedad P y el conjunto B de permutaciones que tienen la propiedad P se
muestran abajo;
A = {1234, 1432, 2143 2341, 3214, 3412, 4123, 4321}
B = {1243, 1324, 1342, 1423, 2134, 2314, 2413, 2431, 3124, 3142, 3241, 3421, 4132, 4213, 4231, 4312}

Claramente, |B| = 16 > 8 = |A|.

Prueba: El caso cuando n = 1 es trivial. Asuma que n ≥ 2. Sea A el conjunto de

permutaciones de S = {1, 2, · · · , 2n} sin la propiedad P . Para mostrar que |B| > |A|,
por P.I y P.B, es suficiente con establecer una correspondencia f : A → B el cual
sea inyectivo pero no sobreyectivo.

Por conveniencia, cada número en la pareja {n, n + k} (k = 1, 2, · · · , n) es lla-

mado, el compañero de la otra. Si k y n + k son adyacentes en una permutación, la

7
pareja es llamada Una pareja de compañeros adyacentes.

Sea α = x1 x2 · · · x2n un elemento de A. Ya que α no tiene la propiedad P , el

compañero de x1 es xr donde 3 ≤ r ≤ 2n. Ahora ponemos

f (α) = x2 x3 · · · xr−1 x1 xr xx+1 · · · x2n

quitando a x1 y colocandolo junto a su compañero xr . En f (α), es claro que {x1 xr }

es la única pareja de compañeros adyacentes. (Asi, por ejemplo, f (1234) = 2134 y
f (2143) = 1243.) Obviamente f (α) ∈ B y f define una correspondencia de A a B.
Ahora mostraremos que f es inyectiva. Sea
α = x1 x2 · · · x2n
β = y1 y2 · · · y2n
elementos de A, en la cual el compañero de x1 es xr y el compañero de y1 es ys ,
donde 3 ≤ r, s ≤ 2n. Suponga que f (α) = f (β), por ejemplo

x1 x2 · · · x1 xr · · · x2n = y1 y2 · · · y1 ys · · · y2n

ya que {x1 xr } (resp. {y1 ys }) es la única pareja de compañeros adyacentes en f {α}

(resp. f {β}), debemos tener que r = s, x1 = y1 y xr = ys . Esto implica que xi = yi
para todo i = 1, 2, · · · , 2n y asi α = β, mostrando que f es inyectiva.

Finalmente note que f (A) consiste de todas las permutaciones de S teniendo

exactamente una pareja de compañeros adyacentes, mientras que hay permutaciones
de S en B que tienen mas de una pareja de compañeros consecutivos. Asi tenemos
que f (A) ⊂ B, mostrando que f no es sobreyectiva. La prueba esta completa.

1. Propuestos
Los enunciados de cada problema deben probarse combinatoriamente, en la ma-
yorı́a de casos al exhibir una biyección explı́cita entre dos conjuntos. Trate de dar
la prueba más elegante posible. Evite la inducción, las recurrencias, las funciones
generadoras, etc., si es posible.

1 ¿De cuántas formas podemos distribuir 15 manzanas idénticas a 4 estudiantes

distintos? No todos los estudiantes tienen que comprar una manzana.

2 Determine la cantidad de formas en que podemos distribuir 20 manzanas

idénticas a 5 estudiantes diferentes, de manera que se cumplan las siguien-
tes condiciones:

a) Cada estudiante debe obtener al menos una manzana;

b) El primero, tercero y quinto estudiante deben obtener un número par de
manzanas;
c) El segundo y cuarto estudiante deben obtener un número impar de man-
zanas;
d) Todas las manzanas deben distribuirse.

8
3 Hay 5 estudiantes en una habitación y 10 manzanas idénticas en una caja.
¿De cuántas formas pueden los estudiantes tomar manzanas de tal manera
que cada estudiante tome al menos una manzana, pero no todas las manzanas
deben ser sacadas de la caja?

4 Determine la cantidad de formas en que podemos distribuir 10 manzanas

idénticas a 5 estudiantes diferentes. No todos los estudiantes tienen que com-
prar manzanas.

5 Sean r, b ∈ N con r ≤ n. Una permutación x1 x2 · · · x2n del conjunto {1, 2, · · · , 2n}

se dice que tiene la propiedad P (r) si |xi − xi+1 | = r para al menos algún i en
{1, 2, · · · , n − 1} muestre que para cada n y r, hay mas permutaciones con la
propiedad P (r) que sin ella.

6 En un partido de tiro, ocho blancos de arcilla se organizan en dos columnas

colgantes de tres blancos cada una y una columna de dos blancos. Un tirador
debe romper todos los blancos de acuerdo con las siguientes reglas:

a) El tirador elige primero una columna de la que se va a romper un objetivo.

b) El tirador debe entonces romper el objetivo restante más bajo en la co-
lumna elegida.

Si se siguen las reglas, ¿en cuántos órdenes diferentes se pueden romper los
ocho objetivos? Sol: Suppose that the columns are labeled A, B, and C.
Consider the string AAABBBCC. Since the arrangements of the strings is
bijective to the order of shooting, the answer is the number of ways to arrange
8!
the letters which is = 560.
3!3!2!
7 Sea m, n ≥ 0. ¿Cuántos caminos diferentes hay con coordenadas enteras desde
(0, 0) a (m, n), si cada paso en el camino es (1, 0) o (0, 1)? La figura muestra
un camino desde (0, 0) a (5, 4)

8 Demuestre que el número de formas de apilar monedas en el plano de manera

que la fila inferior consta de n monedas consecutivas es Cn , ejemplo para n = 3

9
 9 Muestre que el número de triangulaciones de un (n + 2)-ágono convexo en n
triángulos por n − 1 diagonales que no se cortan internamente es el n-ésimo
número catalán,Cn . Por ejemplo, para n = 3

10 Muestre que el número de árboles binarios completos con n vértices internos

es el n-ésimo número catalán, Cn . Por ejemplo, para n = 3

11 Muestre que el número de formas de teselar una forma de escalera de altura n

con n rectángulos es el n-ésimo número catalán, Cn . Por ejemplo, para n = 3

12 [IMO 2002]Sea n un entero positivo. Cada punto (x, y) en el plano, donde x

e y son números enteros no negativos con x + y < n, se colorean de rojo o azul,
sujetos a la siguiente condición: si un punto (x, y) es rojo, entonces también lo
son todos los puntos (x0 , y 0 ) con x0 ≤ x e y 0 ≤ y. Sea A el número de formas
de elegir n puntos azules con coordenadas x distintas, y sea B el número de
formas de elegir n puntos azules con coordenadas y distintas. Demostrar que
A = B.

13 [Extra OMCC 2006] El paı́s Olimpia está formado por n islas. La isla más
poblada es Panacentro y todas las islas tienen diferente número de habitan-
tes. Se desea construir puentes entre islas que puedan transitarse en ambas
direcciones de manera que cada pareja no esté unida por más de un puente.
Es necesario que se cumplan las siguientes condiciones:

a) Siempre es posible llegar desde Panacentro hasta cualquiera otra isla

usando los puentes.
b) Si se hace un recorrido desde Panacentro hasta cualquier otra isla utili-
zando cada puente no más de una vez, el número de habitantes de las
islas visitadas es cada vez menor.

Determine el número de maneras de construir los puentes

10