Combinatoria Puddu

Combinatoria
Susana Puddu

Ejemplo 1. Dados dos conjuntos A y B, donde A tiene k elementos y B tiene m elementos, queremos determinar cu´antos elementos tiene A × B. Recordemos que A × B
es el conjunto de pares ordenados cuya primera coordenada es un elemento de A y cuya
segunda coordenada es un elemento de B. Entonces, la primera coordenada puede tomar
k valores y, para cada uno de ellos, lasegunda coordenada puede tomar m valores: si
A = {a1 , a2 , . . . , ak } y B = {b1 , b2 , . . . , bm } entonces hay m pares con primera coordenada
a1 , que son (a1 , b1 ), (a1 , b2 ), . . . , (a1 , bm ), hay m pares con primera coordenada a2 , que
son (a2 , b1 ), (a2 , b2 ), . . . , (a2 , bm ), . . ., hay m pares con primera coordenada ak , que son
(ak , b1 ), (ak , b2 ), . . . , (ak , bm ). Por lotanto, A×B tiene m + m + · · · + m = k.m elementos.
k sumandos

Si A es un conjunto finito denotaremos por #A a la cantidad de elementos que tiene A.
Ejemplo 2. Dados los conjuntos A1 , A2 , . . . , An , donde #Ai = ki (1 ≤ i ≤ n), ¿cu´antos
elementos tiene A1 × A2 × . . . An ?
Como A1 tiene k1 elementos y A2 tiene k2 elementos entonces, por lo visto en el ejemplo 1.
resulta que A1 × A2 tiene k1.k2 elementos. Como A1 × A2 tiene k1 .k2 elementos y A3 tiene
k3 elementos entonces A1 × A2 × A3 tiene k1 .k2 .k3 elementos. En general, A1 × A2 × . . . An
tiene k1 .k2 . . . . .kn elementos.
Ejemplo 3. i) Si A es un conjunto de n elementos y B es un conjunto de k elementos,
¿cu´
antas funciones de A en B se pueden definir?
Si A = {a1 , a2 , . . . , an } entonces cada funci´on ϕ : A −→ B quedadeterminada por los
valores que toma en a1 , . . . , an , es decir, ϕ queda determinada por la n-upla
(ϕ(a1 ), ϕ(a2 ), . . . , ϕ(an )) ∈ B × B × . . . × B
Luego, pueden definirse tantas funciones de A en B como elementos haya en B × . . . × B .
n

Luego, la cantidad de funciones es

factores

#B × . . . × #B = k × . . . × k = k n
n

factores

n

factores

ii) ¿De cu´antas maneras se pueden ubicar nbolitas numeradas en k cajas numeradas?
Notemos que esto es lo mismo que determinar cu´antas funciones hay de A = {1, 2, . . . , n}
en B = {1, 2, . . . , k} ya que cada ubicaci´on de las bolitas en las cajas puede verse como la
funci´
on definida por f (i) = n´
umero de caja donde est´a ubicada la bolita i. Luego, hay k n
maneras de ubicar las bolitas.

1

ALGEBRA I

Combinatoria

Ejemplo 4. i) Si Aes un conjunto de n elementos y B es un conjunto de m elementos,
¿cu´
antas funciones inyectivas de A en B se pueden definir?
Es claro que si n > m entonces no se puede definir ninguna funci´on inyectiva de A en B.
Por lo tanto supondremos que n ≤ m.
Si A = {a1 , a2 , . . . , an }, las funciones inyectivas ϕ : A −→ B quedan determinadas por
las n-uplas (ϕ(a1 ), ϕ(a2 ), . . . , ϕ(an )) ∈ B × B × .. . × B que tienen todas sus coordenadas
distintas.
Como la primera coordenada puede tomar m valores, la segunda puede tomar m−1 valores,
la tercera m − 2, etc. y hay n coordenadas, entonces la cantidad de funciones inyectivas es
m(m − 1)(m − 2) . . . (m − (n − 1)) = m(m − 1)(m − 2) . . . (m − n + 1) =

m!
(m − n)!

ii) Sea n ≤ m. ¿De cu´antas maneras se pueden ubicar n bolitas numeradas en mcajas
numeradas de manera que haya a lo sumo una bolita por caja?
Esto es lo mismo que determinar cu´antas funciones inyectivas hay de A = {1, 2, . . . , n} en
B = {1, 2, . . . , k} ya que cada ubicaci´on de las bolitas en las cajas puede verse como la
funci´
on definida por f (i) = n´
umero de caja donde est´a ubicada la bolita i y que en cada
caja haya a lo sumo una bolita significa que f (i) = f(j) para todo i = j, es decir, que f
m!
sea inyectiva. Luego, hay (m−n)!
maneras de ubicar las bolitas.
Ejemplo 5. Si A y B son conjuntos finitos, #(A ∪ B) = #A + #B − #(A ∩ B). Luego,
si A y B son disjuntos entonces #(A ∪ B) = #A + #B
Ejercicio. Probar por inducci´on que si A1 , A2 , . . . An son conjuntos finitos disjuntos dos a
n

dos, es decir, tales que Ai ∩Aj = ∅ para todo i = j, entonces...