Contando Funciones

April 21, 2022

Resumen

1 Notación
Si A es un conjunto |A| denota el cardinal o número de elementos de A.
Siendo n un natural notamos [n] = {0, · · · , n − 1}
0 = |∅|
[m]n = {f : [n] → [m] : f es función}

Conviene ver las funciones de [m]n como palabras o sartas de longitud n sobre
el alfabeto Σ = {0, · · · , m − 1}, o lo que es lo mismo como elementos de [m]n .
Entonces [m]n señala tres cosas que identificamos:
1. El producto cartesiano de [m] consigo mismo n − veces, o las n-plas con
componentes en {0, . . . m − 1}.
2. Las palabras o sartas de n componentes cada componente un elemento de
[m]. En general, si Σ es un alfabeto (conjunto finito), se nota Σ∗ las pal-
abras o sartas con letras o componentes en Σ. El número de componentes
de una palabra w ∈ Σ∗ se nota |w|. Si x ∈ Σ y w ∈ Σ∗ el número de
apariciones de x en w lo notamos |w|x .
3. Las funciones de [n] en [m].

Utilizaremos SAGE para manipular funciones. Ası́, en el siguiente proced-

imiento, en Qu guardamos las funciones de [3]5 .

A = range(3)
Qu=cartesian_product([A,A,A,A,A])

ası́ Qu son las funciones de [5] en [3] que son como las palabras de 5 letras sobre
el alfabeto {0, 1, 2}. El comando cartesian_product() produce el producto
cartesiano y su argumento es la una lista de conjuntos. Por ejemplo si A =
{0, 1, 2} y B = {0, 1} haciendo

1
A = range(3)
B = range(2)
Qe=cartesian_product([A,B,B,A])
ahora la variable Qe contiene 36 cuádruplas.

2 Coeficientes trinómicos
Los subconjuntos de un conjunto con n elementos son palabras de n bits, es
decir elementos de [2]n y si tienen k elementos quiere decir que la suma de sus
bits es k. Por ejemplo el subconjunto {3, 2, 5} de [7] será la palabra 0011010
o la ”séptupla”: (0, 0, 1, 1, 0, 1, 0) o la función que se llama ”caracterı́atica” y
que para i ∈ {0.1, . . . 6} si i ∈ {2, 3, 5} asocia 0 y si i ∈ {0, 1, 4, 6} asocia el
0. El número
de 1’s de la palbra o sarta determina el número de elmentos.
Se tienen nk subconjuntos con k elementos, o palabras con k “ o sartas cuyos
elementos suman k ¿Cuántas sartas de [m]n suman k? A continuación se mues-
tra un procedimiento en SAGE para calcular estas sartas en [3]i con i entre 1 y 8:

TT=[]
A=range(3)
for ii in range(8):
TT.append(A)
Qu=cartesian_product(TT)
tuta=[]
for uj in range(ii*2+1):
tutu=[uu for uu in Qu if sum(uu)==uj]
tuta.append(len(tutu))
print(tuta)
La variable TT lleva la lista que harı́a los diferentes productos cartesianos, mien-
tras tutu hace la lista de los que suman uj, mientras tuta es la lista de las
longitudes para cada uj. Cuando se centran se obtiene:

1
1 1 1
1 2 3 2 1
1 3 6 7 6 3 1
1 4 10 16 19 16 10 4 1
1 5 15 30 45 51 45 30 15 5 1
1 6 21 50 90 126 141 126 90 50 21 6 1
1 7 28 77 161 266 357 393 357 266 161 77 28 7 1
1 8 36 112 266 504 784 1016 1107 1016 784 504 266 112 36 8 1

2
Comprobemos por ejemplo que hay 10 elementos de [3]4 cuyos elementos suman
2: Hay 4 que contiene un único 2 como (2, 0, 0, 0), y hay 6 que contienen dos
1’s como (1, 1, 0, 0).
La tabla que es una generalización del triángulo de Pascal, nos indica que hay
126 funciones en X
{f ∈ [3]6 : f (i) = 5}

los términos que aparecen en el triángulo los llamaremos (n+4)extitcoeficientes
trinómicos. Notaremos el número de palabras de longitud n hechas con el alfa-
beto {0, 1, 2} cuyas letras suman k ası́:
 
n
 
k 

este será el coeficiente trinómico n, k; se entiende que es interesante cuando

0 ≤ k ≤  2n, pues en otros casos cuando k < 0 o cuando k > 2n se ve fácilmente
n
que   = 0

k
   
n n
Ejercicio 1. 1. Muestre que   = 1 y   = 1 sage
 
0 2n
   
n  n 
2. Demuestre que   =  
k 2n − k 
3. Demuestre la ley recursiva para formar el árbol de los trinómicos:
       
n + 1   n   n  n
 k  k − 2 k − 1 + k 
 = +   

   
n  n 
4. Demostrar que   =  =n
1 2n − 1
   
n  n  1
5. Demostrar por inducción que   =   = n(n + 1)
2 2n − 2 2
6. Calcule:
2n  
X n
 
i
i=0

y demuestre su resutado por inducción.

7. Usando coeficientes trinómicos encuentre y demuestre una fórmula para:

(1 + x + x2 )n
   
n  n  1
8. Demostrar por inducción que   = 
    = (n − 1)n(n + 4)
3 2n − 3 6

3
Por su similitud con los coeficientes binomiales del triángulo de Pascal se usa la
notación:    
n n
 =
k  n−k 2
Los
  números
  centrales de nuestro triángulo trinómico es decir los de la forma:
n
  = n son 1, 1, 3, 7, 19, 51, 141, 393, 1107 . . . y esta sucesión se encuentra
n 0 2
en la OIES en https://oeis.org/A002426.

2.1 Principio de Inclusión-exclusión

Una herramiente muy útil para contar es este principio que empezamos viéndolo
para dos y tres conjuntos.

Proposición 1. Siendo A, B, C conjuntos

|A ∪ B| = |A| + |B| − |A ∩ B|

además

|A| ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − B ∩ C| + |A ∩ B ∩ C|

La generalización de estos resultados se expresan en el siguiente teorema, cuya

demostración aunque engorrosa no es difı́cil, una vez se interprete correctamente
la fórmula.

Theorem 2. (Principio de Inclusión-Exclusión). Dados A1 , · · · , An ⊆ S en-

tonces X
| A1 ∪ · · · ∪ An | = (−1)|J|−1 | AJ |
∅6=J⊆{1,··· ,n}
T
donde AJ = 1∈J Ai .

Prueba. Probemos que |A ∪ B| = |A| + |B| − |A ∩ B| por inducción sobre el

número de elementos de B. Si B = ∅, el resultado es obvio. Supongamos ahora
que a B le agregamos un elemento x 6∈ B (por tanto |B ∪ {x}| = |B | + 1) y hay
dos posibilidades:
Si x ∈ A entonces |A ∪ (B ∪ {x}| = |A ∪ B| = |A| + |B| − |A ∩ B| pero
|A ∩ (B ∪ {x})| = |A ∩ B| + 1 entonces

|A ∪ (B ∪ {x})| = |A| + |(B ∪ {x})| − |A ∩ (B ∪ {x})|

Si x 6∈ A entonces |A ∪ (B ∪ {x})| = |A ∪ B| + 1 = |A| + |B| − |A ∩ B| + 1 y aquı́

|A ∩ (B ∪ {x})| = |A ∩ B| entonces

|A ∪ (B ∪ {x})| = |A| + |(B ∪ {x})| − |A ∩ (B ∪ {x})|

4
quedando demostrado el resultado para A y B ∪ {x}.
Por inducción hemos probado que

|A ∪ B| = |A| + |B| − |A ∩ B|

Aplicando este resultado tenemos:

|A ∪ B ∪ C| = |A ∪ (B ∪ C)|
= |A| + |(B ∪ C)| − |A ∩ (B ∪ C)|
= |A| + |B| + |C| − |B ∩ C| − |(A ∩ B) ∪ (A ∩ C)|
= |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C|
+|(A ∩ B) ∩ (A ∩ C|
= |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C|
+|(A ∩ B ∩ C|

Ejercicio 2. 1. Encuentre el número de enteros menores que 10Cu’antas00

que son divisibles por 7 o 10.

2. ¿Cuántos enteros menores que 1000 son divisibles por 7 o 10 o 12?

3 Analizando el recorrido
Proposición 3. El número de funciones entre un conjunto con n elementos y
otro con m elementos está dado por mn
Prueba. Hay tantas de estas funciones como palabras de n letras sobre un alfa-
beto con m letras.
Ejemplo 4. ¿Cuántas funciones hay f : [n] → [2] tales que si f (i) = 0 entonces
f (i + 1) = 1 para i < n − 1? Esto es lo mismo que preguntar por el número
de palabras hay de n bits sin dos 0’s seguidos. Se sabe según OEIS que hay
F (n + 2) donde F es la famosa sucesión de Fibonacci distiguida por A000045.
Para demostrarlo Mostramos que se cumple la ley recursiba de Fibonacci: En
efecto si Ln son las palabras de n bits sin dos 0’s seguidos se puede ver que para
n ≥ 0 se tiene:
Ln+2 = Ln 10 ∪ Ln+1 1
ya que si w ∈ Ln+2 termina en 0 o en 1, pero si termina en 0 es una palabra de
longitud n que se le ha agregado 10 es decir w ∈ Ln 10 , si termina en 1 es una
palabra de longitud n + 1 a la que se le ha agregado 1 es decir w ∈ Ln+1 1. Ası́
tenemos la unión que es disjunta, como |Ln 10| = |Ln | y Ln+1 1| = |Ln+1 | por
tanto principio de inclución exclusión tenemos tenemos:

|Ln+2 | = |Ln | + |Ln+1 |

y como |L0 | = 1 y |L1 | = 2 concluı́mos que |Ln | = F (n + 2)

5
3.1 Números binomiales
Ahora nos detendremos analizando el número de funciones cuyo recorrido suma
un determinado número.
El triángulo de Pascal aparece cuando contamos el número de funciones de
[2]n cuya suma es k, en otras palabras nk indica el número de palabras con n

bits que tienen k unos. Para ello sea Lkn las palabras de n bits y k unos. Si
w ∈ Lkn+1 puede terminar en 0 o en 1. Si termina en 0 entonces w ∈ Lkn 0 pues
es una palabra de longitud n con k unos a la que se le ha agregado un 0; si
termina en 1 entonces w ∈ Lk−1
n 1 pues es una palabra de longitud n con k − 1
unos a la que se le ha agregado un 1. Tenemos que:

Lkn+1 = Lkn 0 ∪ Lk−1

n 1

como |Lkn 0| = |Lkn | y |Lk−1 k−1

n 1| = |Ln | y la unión es disyunta tenemos:

|Lkn+1 | = |Lkn | + |Lk−1

n |

Ejercicio 3. Para nosotros |Lkn | = nk y la anterior fórmula recursiva nos da la

forma de construir el muy famoso (mal llamado) y ya citado Triángulo de Pascal

ası́:      
n+1 n n
= + (1)
k k−1 k
con ésta fórmula recursiva agregando que 00 = 1 y que nk = 0 cuando k < n

y k > n, se pueden demostrar muchas porpiedades de estos coeficientes en

especial la fórmula explı́cita en términos del factorial (que también se define
recursivamente):  
n n!
=
k k!(n − k)!
está fórmula muy divulgada y explı́cita (ver ejercicio 6) no es digamos práctica,
pues n! es poco calculable, digamos por ejemplo si queremos calcular n2 que es


n(n−1)
2 pero si n es medianamente grande n! no nos sirve para aplicar la fórmula.
Por otra parte la fórmula 1 requiere guardar la fila anterior, si no se quiere
guardar la fila anterior se puede emplear la fórmula:
   
n n n−k
=
k+1 k k+1

demuestre que se cumple para k ≥ 0. ¿Cuáles son las condiciones inciales para
completar la definición recursiva?
Nótese que si a, b son elementos de un anillo no conmutativo entonces (a + b)n
es la suma de todas las expresiones de longitud n que se puedan hacer con el
alfabeto Σ = {a, b} o sea, si Ln el lenguaje de las palabras sobre Σ de longitud
n tenemos X
(a + b)n = w
w∈Ln

6
y cuando consideramos el anillo conmutativo se agrupan las palabras con igual
número de a’s (y b’s) y como |Lkn | = nk y se tendrá:

n  
n
X n
(a + b) = an−k bk
k
k=0

que es por nuestra observación el muy reconocido teorema del binomio.

3.2 Ejercicios
n n−1



1. k k =n k−1

2. (n − k) nk = n n−1



k
m
+2 m m m+2





3. n−1 n + n+1 = n+1

4. n1 + 2 n2 + 3 n3 + . . . + n nn = n2n−1

5. Supongamos que se tiene una grilla cuadrada de 5 ancho y 4 largo como

se muestra en la figura, se nos pide ir de un extremo A al otro B

solamente se permiten movimientos a la derecha y hacia arriba. Para ir

de un extremo al otro del cubo se puede representar cada camino como
una palabra sobre {a, b} donde a significa movimiento a la derecha, y b
movimiento hacia arriba. Por ejemplo, el camino señalado en la figura
corresponde a la palabra babbaabaa. Ası́, por ser esta correspondencia
biunı́voca, los caminos que nos interesan son tantos como palabras en
{a, b}∗ hay que tengan 5 a’s y 4 b’s, tantos como palabras de 9 bits con 5
unos. Entonces hay  
9
= 126
5
Generalice este resultado para grillas n×m. Plantee y resuelva el problema
cuando se trata de un paralelipı́pedo ”engrillado”.

7
3.3 Números trinomiales
Ahora extrapolamos el raciocinio para coeficientes trinomiales y aparecerá un
tetraedro de Pascal. Ya contamos el número de funciones de [3]n cuya suma es
k. Ahora en otras palabras trinom(n, i, j) indicará el número de palabras de
longitud n que tienen i ceros, j unos y n − i − j doces. Para ello sea Li,j n las
palabras de longitud n con i ceros y j unos. Si w ∈ Li,j n+1 puede terminar en
0, en 1 o en 2. Si termina en 0 entonces w ∈ Lni−1,j 0 pues es una palabra de
longitud n con i − 1 ceros j unos a la que se le ha agregado un 0; si termina en 1
entonces w ∈ Li,j−1
n 1 pues es una palabra de longitud n con k − 1 unos a la que
se le ha agregado un 1 y si termina en 2 entonces w ∈ Li,j n 2 pues es una palabra
de longitud n con i ceros, j unos y a la que se le ha agregado un 2. Tenemos
que:
Li,j
n+1 = Ln
i−1,j
0 ∪ Li,j−1
n 1 ∪ Li,j
n 2

como |Lkn 0| = |Lkn | y |Lk−1 k−1

n 1| = |Ln | y la unión es disyunta tenemos:

|Li,j i−1,j
n+1 | = |Ln | + |Li,j−1
n | + |Li,j
n |
 
n
que es la ley con que se forman los coeficientes trinomiales. Haciendo =
j, k
|Li,j
n | la ley de recurrencia de estos coeficientes serı́a:
       
n+1 n n n
= + +
j, k j − 1, k j, k − 1 j, k

y el inicio serı́a:  
n
=1
j, k
siempre que j = n o k = n o j + k = n.
Estos coeficientes, para emular el triángulo de Pascal, se colocan en una pirámide
tetrahedral, versiones parciales se muestran enseguida. En un vértice, el supe-
rior, se inicia con 1, en cada cara van los coeficientes binomiales, los vértices
de las aristas van con 1 y los puntos interiores se les asigna la suma de los tres
superiores

8
En el “Tetrahedro de Pascal” los coeficients se van poniendo por pisos. El primer
piso (de encima) es el vértce del tetrahedro que se etiqueta con 1. Luego viene
un triángulo con todos su vértices etiquetdos con 1’s.

2 2

2
1 1

Ası́ como mostramos enseguida el tercer piso 5 nodos que se llenan mirando los
nodos de encima qu se etiquetan con nos y doces :

9
 1

2 2

2
1 1

Ası́ como mostramos enseguida el cuarto piso de 10 nodos que se llenan mirando
los nodos de encima:
1

3 3

6
3 3

3 3
1 1

Finalmente mostramos el quinto piso de 15 nodos que se llenan mirando los

nodos de encima:
1

4 4

12
6 6

12 12
4 4

4 6 4
1 1

10
Nótese que si a, b, c son elementos de un anillo no conmutativo entonces (a +
b + c)n es la suma de todas las expresiones de longitud n que se puedan hacer
con el alfabeto Σ = {a, b, c} o sea, si Ln el lenguaje de las palabras sobre Σ de
longitud n tenemos X
(a + b + c)n = w
w∈Ln

y cuando consideramos el anillo conmutativo se agrupan las palabras con igual

número de a’s, b’s y c’s, y se tendrá:
n
X
(a + b + c)n = |Li,j
n |a
n−i j n−i−j
b c
i=0;j=0

que serı́a una generalización que podemos llamar teorema del trinomio:
n  
X n
(a + b + c)n = ai bj cn−i−j
i, j
i=0;j=0

Ejercicio 4. Supongamos que se tiene un cubo de 2 ancho, 2 largo y 3 altura son

enteros positivos. Para ir de un extremo al otro del cubo se puede representar
cada camino como una palabra sobre {a, b, c} en donde el número de a’s es 2,
el número de b’s es 2 el número de a’s es 2, el número de c’s es 3. Como esta
correspondencia es biunı́voca se deduce que el número de caminos es
 
7
2, 2

3.4 Contando funciones inyectivas

Proposición 5. El número de funciones inyectivas entre un conjunto con n
elementos y otro con m elementos, donde 0 < n ≤ m, está dado por

mn = m(m − 1) · · · (m − n + 1)

Prueba. Supongamos que cumple que hay mn funciones inyectivas de [n] en [m].
0
Entonces para cada función f : [n] → [m] podemos construir f : [n + 1] → [m]
0 0
haciendo f (i) = f (i) si i ∈ [n] y escogiendo f (n+1) en el conjunto [m]−f ([n]);
0
ası́ f será inyectiva y podramos escoger m − n funciones. Por otra parte, todas
las funciones inyectivas se pueden construir ası́ y de manera única. Por tanto
hay
mn+1 = m(m − 1) · · · (m − n + 1)(m − n)
funciones f : {1, · · · , n, n + 1} → {1, · · · , m} inyectivas.
Proposición 6. El número de permutaciones de un conjunto con n elementos
es
n!
Prueba. Este es un corolario de la proposición anterior.

11
A manera de ilustración veamos cómo se visualiza este hecho en SAGE. Em-
pezamos preguntando si una lista o vector representa una función inyectiva. La
estrategia consiste en construir el conjunto de imágenes de una n-pla y después
preguntar si ese conjunto tiene igual número de elementos que la longitud de la
n-pla.

def imagenes(uu): #$ devuelve el conjunto de im\’agenes de uu

rango=[]
for nu in uu:
rango.append(nu)
return Set(rango)

def inyec(uu): # decide si uu es inyectiva

if imagenes(uu).cardinality()==len(uu):
return True
else:
return False

Ahora para contar las funciones inyectivas creamos una lista

def listiny(nn,mm):
A=range(mm)
TT=[] #aqu\’i se configura el dominio
for ii in range(nn):
TT.append(A)
Qu=cartesian_product(TT)
tutu=[uu for uu in Qu if inyec(uu)] # esta es la lista
return tutu

y su longitud nos dará el número buscado:

def cuentainy(nn,mm):
return len(listiny(nn,mm))

El método utilizado es mas bien extractivo: se crea el conjunto de todas las

funciones y se recorren todas para ir escogiendo las inyectivas. Cuando los
números crecen un poquito ya no funciona, por ejemplo si queremos escoger las
funciones de [10]10 que son inyectivas la lista es de 1010 funciones y el cálculo
se demora mucho. La proposición 6 nos da un método más constructivo que
se podrı́a implementar. De todas formas el exámen del recorrido de la función
puede sernos útil para experimentar alrededor de problemas.
Ejemplo 7. El muy popular y antiguo juego de las Picas y famas trabaja
números de cuatro cifras que no se repiten. Conviene mirar nuestro universo
como funciones de [10]4 y por lo tanto tenemos 10 × 9 × 8 = 5040 opciones.

12
El juego consiste en dar candidatos buscando uno escondido; se anuncia cuańtas
picas tiene es decir aciertos pero en lugares errados y cuántas famas que son
los aciertos en los lugares correctos. Si el número a encontrar es 1952 y se da el
1234 entonces hay una fama (el 1) y una pica (el 2).
Nuestro interés es decir cuántos números hay que tengan con uno dado n picas
y m famas. Esto a veces es sencillo. Por ejemplo si damos 8354 y nos dicen
que hay 1 fama o picas. Si la fama fuera el 8, hay 6 × 5 × 4 números posibles;
entonces como la fama puede ser cualquiera de las cuatro cifras tenemos que
son 4 × (6 × 5 × 4) = 480 los número que comparten una fama con 8354. Este
resultado se puede comprobar fácilmente en Sage.
Ejercicio 5. Demuestre que con el número 5412 (podrı́a ser cualquier otro) hay:
1. hay 360 números con 0 picas y 0 famas.

2. hay 720 números con 1 picas y 1 fama.

3. hay 264 números con 3 picas y 0 famas.
4. hay 24 números con 0 picas 3 famas.

5. hay 6 números con 2 picas y 2 famas.

6. hay 180 números con 0 picas y 2 famas.
7. hay 72 números con 1 pica y 2 famas.
Compruebe en cada caso con un programa que sı́ es correcto y argumente con
métodos combinatorios que sı́ se tiene el resultado.
Ejemplo 8. ¿Cuántas funciones hay de de {0, 1, 2, 3} en {0, 1, 2, 3} que contengan
en su imagen a 0 o 1 y a 2 o 3? Es decir nos preguntamos por las f ∈ [4][4] tales
que {0, 1} ∩ f ([4]) 6= ∅ y {2, 3} ∩ f ([4]) 6= ∅. Las anteriores rutinas nos pueden
ayudar:

13
A=range(4)
TT=[A,A,A,A]
Qu=cartesian_product(TT)
Yo=Set([0,1])
Tu=Set([2,3])
tuti=[]
for uu in Qu:
ro=imagenes(uu)
suy=ro.intersection(Yo).cardinality()
if not suy==0:
tuy=ro.intersection(Tu).cardinality()
if not tuy==0:
tuti.append(uu)
print(len(tuti))
La respuesta que indica SAGE es 224. Ahora calculemos el número con argu-
mentos combinatorios. Hay 44 = 256 funciones, ¿cuáles debemos descartar?
pues aquellas que todas sus imágenes caen en {0, 1}, de éstas hay 24 ; nos faltan
las que todas sus imágenes caen en {2, 3} también hay 24 en total tenemos que
hay 44 − 24 − 24 = 224.
Ejemplo 9. ¿Cuántas funciones inyectivas hay en [10]4 que no tengan ningún
punto fijo? Haciendo un programa en SAGE se obtiene que son 3333. La
sucesión A094793 de OEIS da razón del número de funciones inyectivas de [4]
en [n + 4] sin puntos fijos. Para encontrar cuántas funciones hay sin punto fijo
contamos las que si tienen punto fijo. Sea A0 las funciones que tiene punto fijo
el 0, es decir,
A0 = {f ∈ [10]4 | f es 1 − 1 ∧ f (0) = 0}
tenemos que |A0 |= 9 × 8 × 7 pues tenemos que escojer f (1) ∈ {1, · · · , 9}, f (2) ∈
{1, · · · , 9}\{f (1)} y f (3) ∈ {1, · · · , 9}\{f (1), f (2)}, total 9×8×7 posibilidades.
Ahora nos interesa A0 ∪ A1 ∪ A2 ∪ A3 y por el principio de inclusón-exclusión:
S S S
|A0 A1 A2 A3 |= |A0 | + |A1 | + |A2 | + |A3 | − |A0 ∩ A1 | − ,· · · , −
|A2 ∩ A3 | + |A0 ∩ A1 ∩ A2 | + ,· · · , + |A1 ∩ A2 ∩ A3 | −
|A0 ∩ A1 ∩ A2 ∩ A3 |
como hay 4 intersectiones de 1 conjunto, 6 de a dos conjuntos, 4 de a tres
conjuntos y solo 1 de 4 conjuntos tenemos
S S S
|A0 A1 A2 A3 |= 4 |A0 | − 6 |A0 ∩ A1 | + 4 |A0 ∩ A1 ∩ A2 | −
|A0 ∩ A1 ∩ A2 ∩ A3 |
aquı́ se tiene en cuenta que por ejemplo |A0 ∩ A1 |= |A2 ∩ A3 | etc . . . Ahora por
un raciocinio similar se tiene aquı́ se tiene en cuenta que por ejemplo |A0 ∩ A1 |=
8 ∗ 7, |A0 ∩ A1 ∩ A2 |= 7 y |A0 ∩ A1 ∩ A2 ∩ A3 |= 1 entonces tenemos
S S S
|A0 A1 A2 A3 |= 4 ∗ 9 ∗ 8 ∗ 7 − 6 ∗ 8 ∗ 7 + 4 ∗ 7 − 1 = 1707

14
estas son las que tienen al menos 1 punto fijo, para hallar las que NO tienen
puntos fijos restamos este número del total de funciones inyectivas :

10 ∗ 9 ∗ 8 ∗ 7 − 1707 = 5040 − 1707 = 3333

Ejercicio 6. 1. El factorial de un número entero positivo n se pordrı́a enten-

der como n! = nn . ¿Cuál es la función recursiva de n!?
2. Es fácil (y útil) ver que
m!
mn =
(m − n)!
3. Demuestre recursivamente la muy popular fórmula:
 
n n!
=
m m!(n − m)!

4. ¿Cuántas funciones inyectivas en [10]4 hay que contienen 1 en su imagen

pero no como punto fijo?

5. Determine el cardinal del conjunto

{f ∈ [m]n | f es 1 − 1 j ∈ f ([n])}

6. Determine el cardinal del conjunto

{f ∈ [m]n | f es 1 − 1 j ∈ f ([n]) ∧ f (j) 6= j}

7. Sea
FA = {f : [k] → A : f es 1-1}
(a) Es claro (¿por qué?) que si k = |A| se tiene |FA | = k!
(b) Sea ρk el número de subconjuntos de D que tienen k elementos.
Demuestre que:

|{f : [k] → D : f es 1-1}| = ρk k!

es decir ρk k! = k m donde m = |D|

(c) De lo anterior se deduce que ρk = k m \ k! es decir el número de
subconjuntos con k elementos de un conjunto con m elementos es
m!
(m − k)!k!

8. Encuentre y demuestre una fórmula basada en factorial que exprese los

coeficientes trinomiales  
m
i, j

15
3.5 Funciones sobreyectivas
Para la demostración de la siguiente proposición se usa el principio de inclusión-
exclusión y el cardinal del conjunto de funciones entre dos conjuntos (proposición
1). Antes veamos un ejemplo.

Ejemplo 10. Calcularemos el cardinal del conjunto de funciones sobreyectivas

de {0, 1, 2, 3} en {0, 1, 2}. De las 34 funciones que hay de {0, 1, 2, 3} en {0, 1, 2},
debemos quitar las que no son sobreyectivas. Entonces sea
Ai = {f : {0, 1, 2, 3} → {0, 1, 2} | i 6∈ f ({0, 1, 2, 3})}
es decir, aquellas cuya imagen está contenida en {1, 2, 3} − {i} (hay 24 ) y ası́
las funciones no sobreyectivas son exactamente las del conjunto A0 ∪ A1 ∪ A2 y
por el principio de inclusión exclusión (descontando las tres constantes) hay

 
3
24 − 3 (2)
2
funciones no sobreyectivas, es decir tenemos

 
4 3
3 − 24 + 3 = 81 − 3 × 16 + 3 = 36 (3)
2
funciones sobreyectivas.

Es bueno contar las funciones sobreyectivas de otra manera. Para cada función
sobreyectiva existen necesariamente dos elementos en el dominio y únicamente
dos, que tiene igual imagen. Si esta imagen es 1 hay 2 42 = 12 funciones

sobreyectivas que llevan dos elementos a 1. Como lo mismo sucede con 2 y con
3 tendremos 3 × 2 42 = 36 funciones sobreyectivas.

Apoyándonos en el pricipio de inclusión exclusión podemos hallar una fórmula

general para las funciones sobreyectivas.

Proposición 11. El número de funciones sobreyectivas entre un conjunto con

n elementos y otro con m elementos está dado por

m  
X m
(−1)i (m − i)n
i=0
i

Prueba. Nos preocupamos por las funciones sobreyectivas entre [n] = {0, 1, · · · , n−
1} y [m] = {0, 1, · · · , m − 1}. Sabemos que el cardinal de M el conjunto de las
funciones entre [n] y [m] es mn . Por cada j ∈ [m] sea

16
 Mj = {f ∈ M | j 6∈ f ([n])}
S
es evidente que N = j ∈[n] Mj es el conjunto de todas las funciones de M que
NO son sobreyectivas. Por el principio de inclusión exclusión se tiene

X
| N |= (−1)|J|−1 | AJ | donde AJ = ∩j∈J Mj .
∅6=J⊆[n]

Pero AJ = {f ∈ M | f ([n]) ⊆ [m] − J} entonces |AJ |= (m− | J |)n . Si hacemos

m


la suma sobre i = |J | como hay un i conjuntos J ⊆ [n] con esta condición
entonces
n  
X m
| N |= (−1)i−1 (m − i)n
i=1
i
como nos interesa son las funciones sobreyectivas tenemos

n   n  
n
X
i−1 m n
X
i m
| M − N |= m − (−1) (m − i) = (−1) (m − i)n
i=1
i i=0
i

4 Contando particiones
El número de particiones
  de un conjunto con n elementos que pueden hacerse
n
en k partes se nota y son los números de Stirling de segundo tipo.
k  
3
Es fácil ver que por ejemplo = 3 pues por ejemplo el conjunto de las
2
particiones del conjunto {1, 2, 3} con dos partes es:
{{{1}, {2, 3}}, {{1, 2}, {3}}, {{1, 3}, {2}}}
     
n n n
Es claro que = 1 y por convención se acepta que = 0 y que =0
n 0 k
si k > n

De los números de Stirling de segundo tipo podemos decir:

 
n
Proposición 5. 1. Para n > 0 se tiene = 2n−1 − 1
2
2. Cumplen una ecuación recursiva muy parecida a la de los números binomi-
ales:
     
n n−1 n−1
= +k
k k−1 k

17
Prueba. Demostración. 1. Cada conjunto no vacı́o y su complemento forman
una partición en dos partes, como hay 2n − 2 de estos conjuntos (debemos de-
n
scontar el todo y el vacı́o) 2 2−2 = 2n−1 − 1 tenemos particiones.
0
2. Consideremos X = {x1 , · · · , xn−1 } y X = {x1 , · · · , xn−1 , xn } y supongamos
0
que queremos particionar X en k partes. Estas particiones se pueden clasificar
en dos clases disjuntas: Las que contienen a {xn } como un  conjunto,
 de éstas
n−1
hay tantas como particiones de X con k − 1 partes es decir . Nos faltan
k−1
las que no contienen {xn } como un conjunto, en éstas xn se incluye en alguno
de los conjuntos que forman una partición de X en k partes y naturalmente  xn
n−1
se puede incluir en cualquiera de estas k partes, es decir hay k de estas
k
particiones; en total:
   
n−1 n−1
+k
k−1 k
0
particiones de X en k conjuntos.
El siguiente código es una implementación en SAGE del algoritmo para crear el
triángulo de los números de Stirling de segundo tipo

def stirl2(nn): #N\’umeros de Stirlings de 2 tipo

AA=[[1],[0,1]]
for ii in range(2,nn):
NOTA=[0,1]
for jj in range(2,ii):
re=AA[ii-1][jj-1]+jj*AA[ii-1][jj]
NOTA.append(re)
NOTA.append(0)
AA.append(NOTA)
return(AA)

La lista de listas AA lleva todas las filas, cada una sedesarrolla en la variable
NOTA que se inicia con [0, 1]. En cada fila se incluyen 0’s en los extremos para
poder aplicar la fórmula de recurrencia plenamente en la siquiente fila. Ası́
aparece stirl2(9):
[[1],
[0, 1],
[0, 1, 0],
[0, 1, 1, 0],
[0, 1, 3, 1, 0],
[0, 1, 7, 6, 1, 0],
[0, 1, 15, 25, 10, 1, 0],

18
[0, 1, 31, 90, 65, 15, 1, 0],
[0, 1, 63, 301, 350, 140, 21, 1, 0]]
Proposición 12. Si X tiene n elementos y Y tiene m elementos, hay
  
n m
k!
k k

funciones de X en Y tales que la imagen tenga k elementos.

Prueba. Una vez escogidos k números de la imagen hay que asociar a cada y los
que le corresponden f −1 (y) y estos conjuntos forman una partición del dominio.
Fija la partición ylosk números hay k! funciones. Para escoger los
 k números
m n
de la imagen hay formas y para escoger la partición hay maneras en
k k
total:
  
m n
k!
k k
De aquı́ deducimos dos resultados; apoyándonos en el conteo de las funciones
sobreyectivas encontramos otra fórmula los números de Stirling de segundo tipo
y además vemos cómo éstos nos sirven para expresar el total de funciones :
Proposición 13. Se tienen
  m  
n 1 X i m
= (−1) (m − i)n
m m! i=0 i

Proposición 14.
m   
n
X n m
m = k!
k k!
k=1

Prueba. mn es el total de funciones y éstas se pueden clasificar según la cantidad

de elementos que tengan en su imagen, para cada k el número de funciones con
k imágenes está dado por la proposición anterior, ası́ solo falta sumar cuando
hacemos variar k.

5 Funciones que ordenan

Definición 15. Un desarreglo es una permutación que no deja fijo ningún
elemento.
Los desarreglos de 3 serı́an (2, 0, 1) y (1, 2, 0). En SAGE se trabaja Permu-
tations para crear el la lista de las permutaciones de {1, · · · , n}. El siguiente
procedimiento devuelve la lista de los desarreglos de orden n :

19
def desarr(n): #lista los desarreglos de n
tona=[]
P=Permutations(n)
for uu in P:
tutis=[]
for ii in range(n):
if uu[ii]==ii+1:
break
else:
tutis.append(ii)
if len(tutis)==n:
tona.append(uu)
return tona
Para sacar una lista del número de desarreglos aplicamos:

for ij in range(1,10):
print( ij,’---’, len(desarr(ij)))

y obtenemos:
1 0
2 1
3 2
4 9
5 44
6 265
7 1854
8 14833
9 133496
Ejemplo 16. Cuando queremos asociar a un número aquellos que tiene 4 picas
y 0 famas , estamos buscando los desarreglos de 4 y por tanto hay 9 de tales
números.
Notaremos Dn los desarreglos de n. A Dn , que es la sucesión A000166 de OEIS,
también se le denomina el subfactorial de n y sirve para contar otros muchos
objetos, por ejemplo es también el número de permutaciones de [n] con un único
paso, es decir aquellas que existe un único i con f (i + 1) = f (i) + 1.

Es fácil ver que Dn es el cardinal de las biyecciones entre dos conjuntos que no
coinciden con una fija en ningún punto. Más exactamente, si |A| = |B| = n y
g : A → B es una biyección entonces:

{f : A → B : (∀i)f (i) 6= g(i)} |= Dn

20
También, particionando el conjuto de permutaciones, es fácil ver que
X n
n! = Di
i

aquı́ convenimos en que D0 = 1. No hay problema en considerar la única

permutación del vacı́o como un desarreglo. A partir de D0 = 1, D1 = 0 podemos
calcular los demás usando una fórmula recursiva debida a Euler que afirma

Dn = (n − 1)(Dn−1 + Dn−2 )

¿Cómo demostrarla?
Sean En el número de desarreglos de n que intercambia a n con algún elemento
y Fn los que no intercambian a n. Tenemos entonces que
Dn = En + Fn
Ahora fijemos un i con 0 < i < n − 1 y supongamos que nuestra nueva per-
mutación intercambia n con i, es decir f (i) = n y f (n) = i. De cuántas maneras
podemos darle valor a los restantes n − 2 valores? Tantos como desarreglos
podamos hacer en un conjunto con n − 2 elementos. Tenemos entonces que
En = (n − 1)Dn−2
Ahora pensemos en Fn . Supongamos que f es una de estas permutaciones,
que no intercambia n y que envı́a a n en i con 0 < i < n − 1 y que por
tanto f (i) 6= n. ¿Cómo escoger los restantes valores? De tantas maneras como
funciones biyectivas hay entre {1, 2, · · · , n − 1} en {1, 2, · · · , i − 1, i + 1, · · · , n}
que sean diferentes a
g : {1, 2, · · · , n − 1} → {1, 2, · · · , i − 1, i + 1, · · · , n}
y que está definida por g(j) = j si j 6= i y g(i) = n. De tales funciones, diferentes
de g, hay Dn−1 y tenemos que
Fn = (n − 1)Dn−1
Ası́ conluı́mos que con esta fórmula recursiva se puede demostrar la fórmula
explı́cita:

n
X (−1)i
Dn = n!
i=0
i!

Nótese que según ésta tenemos por ejemplo:

1 −1 1
D4 = 4!(1 − 1 + 2 − 3! + 4! = 4 ∗ 3 − 4 + 1)
también:
D6 = 6 ∗ 5 ∗ 4 ∗ 3 − 6 ∗ 5 ∗ 4 + 6 ∗ 5 − 6 + 1

21
y
D7 = 7 ∗ 6 ∗ 5 ∗ 4 ∗ 3 − 7 ∗ 6 ∗ 5 ∗ 4 + 7 ∗ 6 ∗ 5 − 7 ∗ 6 + 7 − 1
esto nos induce una fórmula cuando n ≥ 3 equivalente a la anterior:

n+1
X n
Y
j+1
Dn = (−1) i
j=3 i=j

se tendrı́a
n+1
X n
Y n
X n−1
Y
Dn + Dn−1 = (−1)j+1 i+ (−1)j+1
j=3 i=j j=3 i=j
y  
n
X n−1
Y
Dn + Dn−1 =  (−1)j+1 (n + 1) i
j=3 i=j

entonces multiplicando por n:

 
Xn n−1
Y n+2
X n+1
Y
j+1 j+1
n(Dn + Dn−1 ) =  (−1) (n + 1) i =
 (−1) i
j=3 i=j j=3 i=j

y tenemos:

n(Dn + Dn−1 ) = Dn+1

5.1 Funciones Crecientes

Definición 2. Una función f : [n] → [m] es creciente si f (i + 1) ≥ f (i) y es
estrictamente creciente si f (i+1) > f (i) para cada 0 ≤ i < n−1. El conjunto de
funciones f : [n] → [m] crecientes se notarı́a m(≤,n) y el conjunto de funciones
f : [n] → [m] estrictamente crecientes se notarı́a m(<,n) .

Es fácil ver lo siguiente:

 
m
Proposición 17. Hay funciones f : [n] → [m] estrictamente crecientes.
n
Prueba. Es claro que para cada subconjunto de n elementos del recorrido (que
tiene m elementos) hay una única
 función
 estrictamente creciente cuya imagen
n
es ese conjunto. Por tanto hay exactamente funciones de éstas.
m
Enseguida se proporciona una rutina que decide si nuestra palabra es estricta-
mente creciente:

22
def creci(uu):
nn=len(uu)
mi=0
for ii in range(1,nn):
if uu[ii]>uu[ii-1]:
mi=1
else:
mi=0
break
if mi==0:
return False
else:
return True

que aprovechamos para listar las funciones estrictamente crecientes de mm en

mn , que son los mismos subconjuntos de mm elementos escogidos de uno con
mn elementos.

def crechen(mn,mm):
AA=range(mn)
LU=[]
for nini in range(mm):
LU.append(AA)
meta=cartesian_product(LU)
son=[ki for ki in meta if creci(ki)]
return son
Ejercicio 7. Formule una rutina en SAGE para listar las funciones crecientes de
[n]m
 
m+n−1
Proposición 18. Hay funciones f : [n] → [m] crecientes.
n

Prueba. Estableceremos la función F : m(≤,n) → (m + n − 1)(<,n) que será

biyectiva. Definimos para cada f : [n] → [m] creciente, se tendrı́a F (f ) = g sı́ y
sólo sı́ g(i) = f (i) + i para cada i ∈ [n]. Es fácil ver que si f ∈ m(≤, n) entonces
F (f ) es estrictamente creciente pues

g(i + 1) = f (i + 1) + (i + 1) ≥ f (i) + i + 1 > f (i) + 1 = g(i)

y F (f ) ∈ (m + n − 1)(<,n) . Por otra parte si para g ∈ m(<,n) se define 4(g) = f

sı́ y sólo sı́ para i ∈ [m + n − 1] se tiene f (i) = g(i) − i tenemos que 4 es la
inversa de f y por lo tanto m(≤,n) y (m + n − 1)(<,n) tienen igual número de
elementos es decir  
m+n−1
| m(≤,n) | =
n

23
Nótese que este resultado también se deduce del hecho que los grafos de estas
funciones corresponden a ciertos caminos en una grilla n × m (ver ejercicio 5)
Ahora variamos las funciones que nos interesan, en algunas partes totalmente
crecientes y en otras solamente crecientes.

Definición 3. Sea J ⊆ [n − 1]. Una función f : [n] → [m] es J−creciente

si para cada i ∈ J se tiene que f (i + 1) > f (i) y si i ∈ [n − 1] − J entonces
f (i + 1) ≥ f (i). El conjunto de funciones f : [n] → [m] que son J−crecientes se
notará m(≤,n,J) .

Proposición 19. Si J tiene k elementos entonces

 
(≤,n,J) m+n−k−1
|m |=
n

Prueba. Sin pérdida de generalidad podemos pensar que J = [k] entonces para
cada función f ∈ m(≤,n,J) definimos F (f ) = g sı́ y sólo sı́ g(i) = f (i) cuando
i ∈ J y g(i) = f (i) + i − k para cada i ∈ [n] − J ası́ la función g es estrictamente
creciente, si i ∈ J sabemos que g(i + 1) > g(i), ahora si i 6∈ J :

g(i + 1) = f (i + 1) + (i + 1 − k) ≥ f (i) + i + 1 − k > f (i) + i − k = g(i)

y su recorrido es [m + n − k − 1]; es decir, g ∈ [m + n − k − 1](<,n) , como F es

biyección se tiene  
(≤,n,J) m+n−k
|m |=
n

6 Permutación asociada a cualquier función

Definición 4. Dada función f : [n] → [m] le asociamos la permutación σf ∈ Sn
de tal manera que f ◦ σf es creciente y si σf (i) > σf (i + 1) implica que
f (σf (i)) < f (σf (i + 1)).

La permutación σf reordena los ı́ndices para que lo compuesta quede creciente,

la garantı́a de su existencia la da el algoritmo para su cálculo, presentamos una
versión para SAGE

def asocc(uu):
orr=[]
for ii in range(3):
for jj in range(5):
if not (jj in orr):
if uu[jj]==ii:
orr.append(jj)
return orr

24
El algoritmo ha sido hecho para aplicarlos en funciones de [3][5] . La función va
en la variable uu. La lista orr que inicia vacı́a, se va llenando con los ı́ndices
de acuerdo a su valor, empieza por 0 y busca qué indices tiene ese valor y los
va guardando en orden ncon la instrucción orr.append(jj). Ası́ con 1 y con 2.

Ejemplo 20. No hay ninguna función en [3]6 que le corresponda la permutación

[5, 4, 3, 2, 1, 0] tampoco la permutación [5, 4, 3, 0, 1, 2].
A todas las funciones crecientes de [3]6 le corresponde la permutación idéntica
[0, 1, 2, 3, 4, 5].
A la función [1, 1, 0, 2] que está en [3]4 le corresponde la permutación [2, 0, 1, 3].
También a la función [1, 2, 0, 2] le corresponde la permutación [2, 0, 1, 3].
A la función [1, 1, 0, 2, 1, 1] que está en [3]6 le corresponde la permutación [2, 0, 1, 4, 5, 3].
Esta es la única función [1, 1, 0, 2, 1, 1] que tiene asociada la permutación [2, 0, 1, 4, 5, 3].

Definición 21. Un salto de una permutación α ∈ Sn es un ı́ndice i tal que

α(i) > α(i + 1) o bien i = n − 1.

Proposición 22. Dada una permutación α ∈ Sn hay

 
m+n−k
n

funciones f ∈ [m]n tales que α = σf donde k es el número de saltos de la

permutación.
Prueba. Fijo α, se trata de poner en correspondencia m(≤,n,J) con la funciones
f tales que α = σf donde J es el conjunto de ı́ndices en donde α tiene saltos.
Si α tiene un salto en i se tiene que α(i) > α(i + 1) y si g(α(i)) = g(α(i + 1))
se tendrı́a α(i) < α(i + 1); por tanto se debe tener g(α(i)) < g(α(i + 1)).
Esto nos garantiza que cualquier salto (no extremo) de α la función resultante
g ◦ σf es J−crecientes. Ahora siendo J los lugares de salto de α y una función
f ∈ m(≤,n,J) debemos encontrar una g ∈ [m]n tal que f = g ◦ α. Como α es
biyección hacemos g = f ◦ α−1 .

7 Trabajos
En cada caso se deben elaborar programas en SAGE para enumerar y contar los
conjuntos de funciones. Comprobar en casos con números pequeños para estar
seguros que su procedimiento funciona. Luego se deben buscar argumentos com-
binatorios que corrabore y amplie los resultados obtenidos computacionalmente.
Se recomienda tratar en primera instacia, casos particulares que puedan resutar
mas sencillos. No se necesita resolver totalmente el problema, en algunos casos
es suficiente dar razón exhaustiva de sus dificultades.

1. F (n, m, k) = {f ∈ [m]n : (∀i) | f (i) − f (i + 1) |> k}

25
 2. F (n, m, k) = {f ∈ [m]n : (∀i) | f (i) − f (i + 1) |< k}
3. F (n, m, k) = {f ∈ [m]n : (∀i) | f (i) = f (i + k)}
4. F (n, m, k) = {f ∈ [m]n : f (i) = f (j) ⇒| i − j |< k}

5. F (n, m, k) = {f ∈ [m]n : f (i) 6= f (i + k)∀i}

6. F (n, m, k) = {f ∈ [m]n : f (i) 6= f (i + k)∃i}
7. F (n, m, k) = {f ∈ [m]n : f ({0, · · · , k − 1}) ∩ f ({k, · · · , n − 1}) = ∅}
8. F (n, m, k) = {f ∈ [m]n : f ({0, · · · , k − 1}) = f ({k, · · · , n − 1})}

9. F (n, m, k) = {f ∈ [m]n : f (i) = k}

P

10. F (n, m, k) = {f ∈ [m]n : f (2i) = i f (2i + 1)}

P P

11. F (n, m, k) = {f ∈ [m]n : {0, · · · , k} ⊆ f ([n])}

12. F (n, m, k) = {f ∈ [m]n : {0, · · · , k} ∩ f ([n]) 6= ∅}

13. F (n, m, k) = {f ∈ [m]n : (∀j) | f −1 (j) |≤ k}
14. F (n, m, k) = {f ∈ [m]n :| {j : f (j) ≤ k} |≡ 0 (mod 3)}
15. F (n, m, k) = {f ∈ [m]n : (∀j)(f (j) < k ⇒ f (j + 1) ≥ k)}

8 Bibliografı́a
1. D. Knuth The Art of Computer Programming, Volume 3
2. I. Anderson, A First Course in Discrete Mathematics.

3. E. Andrews, Euler’s exemplum memorabile inductionis fallacis’ and q-

trinomial coefficients, J. Amer. Math. Soc. 3 (1990) 653-669.
4. Weisstein, Eric W. Trinomial Triangle. mathworld.wolfram.com

26