Cap´ıtulo III Combinatoria B´ asica: Conteo En este cap´ıtulo continuamos determinando la cardinalidad de varios conjuntos interesantes, en particular, permutaciones y combinaciones. Como parte de esto encontramos el teorema binomial.

III.1.

Conjunto de Partes

El conjunto de partes o´ conjunto potencia de un conjunto X, denotado P(X), es el conjunto de todos los subconjuntos de X: P(X) = {A : A ⊆ X} Por ejemplo P({1, 2, 3}) = {∅, {1}, {2}, {3}, {1, 2}, {2, 3}, {1, 3}, {1, 2, 3}}. Estamos interesados en el tama˜ no de P(X): Teorema 1 Si X es n conjunto finito, entonces |P(X)| = 2|X| . ? Este resultado se puede verificar usando la regla del producto: un subconjunto A de X se puede formar tomando la decisi´on para cada elemento a de X de si a ∈ A o´ a 6∈ A. Estas decisiones son independientes. Por lo tanto el n´ umero de |X| subconjuntos posibles es 2 . ? Para cada A ∈ P(X), la decisi´on para cada elemento de X se puede registrar como una cadena de bits (0’s y 1’s) de longitud n en la cual el i-´esimo bit es 1 si el i-´esimo elemento de X pertenece a A o´ 0 si no pertenece. Por ejemplo para P({1, 2, 3}) en el orden dado arriba, se tienen las cadenas correspondientes: 000, 100, 010, 001, 110, 011, 101, 111. 1

´ CAP´ITULO III. COMBINATORIA BASICA: CONTEO

2

Se tiene una correspondencia (funci´on biyectiva) entre P(X) y tales cadenas. El n´ umero de tales cadenas es 2|X| por la regla del producto. ? Otra correspondencia importante es la de un subconjunto A de X con su funci´on caracter´ıstica1 χA : X → {0, 1}, definida como

χA (x) =

1 si x ∈ A 0 si x 6∈ A

Por ejemplo, con X = {1, 2, 3} y A = {2}, se tiene χA = {(1, 0), (2, 1), (3, 0)}. De nuevo, el n´ umero de tales funciones es 2|X| . ? Una forma alternativa es por inducci´on. El caso base con n = 0 es obvio: P(∅) = {∅}. Para el paso de inducci´on, sea X con |X| = n + 1. Tomemos un a ∈ X y sea Y = X − {a}. Por hip´otesis de inducci´on, puesto que |Y| = n, se tiene que P(Y) = 2|Y| . Adem´as, podemos dividir los subconjuntos de Y entre los que no contienen a, que es igual a P(Y) y los que contienen a, que es igual a la uni´on de cada conjunto en P(Y) con {a}: P(X) = {A : A ∈ P(Y)} ∪ {A ∪ {a} : A ∈ P(Y)} (Como ejemplo P({1, 2, 3}) = {∅, {1}, {2}, {1, 2}} ∪ {{3}, {1, 3}, {2, 3}, {1, 2, 3}}. ) Esta es una uni´on disyunta. Adem´as, el segundo conjunto tiene una correspondencia uno a uno con el conjunto P(Y): P(Y) → {A ∪ {a} : A ∈ P(Y)} A 7→ A ∪ {a} es una biyecci´on. Por lo tanto |P(X)| = = = = 1

|P(Y)| + |P(Y)| 2|Y| + 2|Y| 2|Y|+1 2|X| .

χ es la letra griega chi que desafortunadamente ac´a es dif´ıcil de diferenciar de la letra equis

´ ´ III.2. PRINCIPIO DE INCLUSION/EXCLUSI ON

III.2.

3

Principio de Inclusi´ on/Exclusi´ on

El principio de inclusi´on/exclusi´on extiende la computaci´on de la uni´on de conjuntos al caso en que estos no sean disyuntos. Teorema 2 Si A y B son conjuntos finitos, entonces |A ∪ B| = |A| + |B| − |A ∩ B| Prueba. Podemos escribir A ∪ B como la uni´on disyunta A ∪ B = (A − (A ∩ B)) ∪ B, lo cual se verifica f´acilmente. De aqu´ı que, usando (i), |A ∪ B| = |A − (A ∩ B)| + |B|.

(∗)

Similarmente, tenemos la uni´on disyunta A = (A − (A ∩ B)) ∪ (A ∩ B) y la correspondiente igualdad |A| = |A − (A ∩ B)| + |A ∩ B| de donde |A − (A ∩ B)| = |A| − |A ∩ B|.

(∗∗)

De (∗) y (∗∗) se obtiene que |A ∪ B| = |A − (A ∩ B)| + |B| = (|A| − |A ∩ B|) + |B| = |A| + |B| − |A ∩ B|. Alternativamente, se puede verificar que cada elemento en A ∪ B contribuye 1 a la suma en la derecha, y que un elemento que no est´a en A ∪ B contribuye 0 (en clase, en lugar de la tabla, se uso un diagrama de Venn):

A∩B A∩B A∩B A∩B

|A| 1 0 1 0

|B| 1 1 0 0

|A ∩ B| total −1 1 0 1 0 1 0 0

´ CAP´ITULO III. COMBINATORIA BASICA: CONTEO

4

La generalizaci´on a tres conjuntos (la cual se puede derivar del caso para dos conjuntos) es |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |B ∩ C| − |A ∩ C| + |A ∩ B ∩ C|. y en este caso podemos ver las contribuciones A∩B∩C A∩B∩C A∩B∩C A∩B∩C A∩B∩C A∩B∩C A∩B∩C A∩B∩C

|A| 1 0 1 0 1 0 1 0

|B| |C| 1 1 1 1 0 1 0 1 1 0 1 0 0 0 0 0

|A ∩ B| −1 0 0 0 −1 0 0 0

|B ∩ C| −1 −1 0 0 0 0 0 0

|A ∩ C| −1 0 −1 0 0 0 0 0

|A ∩ B ∩ C| 1 0 0 0 0 0 0 0

total 1 1 1 1 1 1 1 0

Ejemplo. Determine el n´ umero de enteros entre 1 y 1000 divisibles por 3 o´ 5 Soluci´ on. Los enteros divisibles por 3 y divisibles por 5 son exactamente los enteros divisibles por 15. Por lo tanto enteros entre 1 enteros entre 1 enteros entre 1 enteros entre 1 y 1000 divisibles = y 1000 divisibles + y 1000 divisibles − y 1000 divisibles por 3 y 5 por 5 por 3 por 3 ´ o5       1000 1000 1000 = + − 3 5 15 = 333 + 200 − 66 = 467

El principio de inclusi´on/exclusi´on se generaliza a la uni´on de n conjuntos A1 , A2 , . . . , An de la manera natural: La cardinalidad de la uni´on es igual a la suma de las cardinalidades de las intersecciones de subcolecciones, con signo positivo ´o negativo dependiendo de si el tama˜ no de la subcolecci´on es impar o´ par: n [ X X X Ak = |Ai | − |Ai ∩ Aj | + |Ai ∩ Aj ∩ Ak | k∈In

i=1

1≤i 0 y n > k arbitrario. Fijando un a ∈ A, sea A 0 = A − {a} y para cada b ∈ B sea Bb = B − {b}. Entonces I(A, B) =

[

Ib (A, B)

b∈B

donde Ib (A, B) = {f ∈ I(A, B) | f(a) = b}. Note que la uni´on es disyunta y por lo tanto X |I(A, B)| = |Ib (A, B)|. b∈B

III.3. CONTEO DE FUNCIONES

7

Ahora, para cada b ∈ B la funci´on gb : Ib (A, B) → I(A 0 , Bb ) f 7→ f|A 0 es una biyecci´on. Por lo tanto, usando la hip´otesis de inducci´on, |Ib (A, B)| = I(A 0 , Bb )| (n − 1)! = ((n − 1) − (k − 1))! (n − 1)! . = (n − k)! As´ı que reemplazando en la ecuaci´on anterior para |I(A, B)|, tenemos que |I(A, B)| =

X (n − 1)! b∈B

(n − k)!

(n − 1)! (n − k)! n! = (n − k)! = n·

(iii) Sabemos que en una biyecci´on es posible s´olo si |A| = |B| = n. El resultado deseado |B(A, B)| = n! se obtiene de (ii) con k = n. Usamos Pk (A) para denotar la colecci´on de subconjuntos de A con cardinalidad k: Pk (A) = {B ⊆ A : |B| = k}.
Para n ∈ N y k ∈ Z, el coeficiente binomial de “n en k”, denotado nk es   n n! = , k! (n − k)! k si 0 ≤ k ≤ n, y es 0 en otro caso.   n Proposici´ on 5 Para B con |B| = n y 0 ≤ k ≤ n, |Pk (B)| = . k Prueba. Sea A = Ik = {1, 2, . . . , k} y consideremos I(A, B). Para f ∈ I(A, B), |f(A)| = k. Definimos una relaci´on de equivalencia para f, g ∈ I(A, B): f ∼ g sii f(A) = g(A).

´ CAP´ITULO III. COMBINATORIA BASICA: CONTEO

8

Sea [f] la clase de f. Para cualquier f, |[f]| = k! porque u : B(A, A) → [f] σ 7→ f ◦ σ es una biyecci´on. Ahora I(A, B) =

[

{f ∈ I(A, B) : f(A) = X}

X∈Pk (B)

y por lo tanto |I(A, B)| = |Pk (B)| · k! y

III.4.

|I(A, B)| n! |Pk (B)| = = = k! k!(n − k)!

  n . k

Permutaciones

Una k-permutaci´on de un conjunto X de n elementos es una sucesi´on de k elementos diferentes de X. Formalmente es una funci´on inyectiva (los elementos no se pueden repetir) f : {1, 2, 3, . . . , k} → X. Por ejemplo, si X = {a, b, c, d, e} entones bda, deb son 3-permutaciones de X (los escribimos aqu´ı unidos porque no hay ambiguedad; en otros casos puede ser conveniente separar los elementos por comas). En el primer ejemplo, la funci´on f es f(1) = b, f(2) = d y f(3) = a, pero usualmente es suficiente con la lista ordenada. Estamos interesados en contar el n´ umero de k-permutaciones posibles de un conjunto de n elementos. Denotamos este n´ umero por P(n, k) y para obtenerlo usamos la regla del producto: una k-permutaci´on se puede obtener eligiendo sucesivamente el primer elemento, el segundo elemento, etc, hasta el k-´esimo elemento. Para el primer elemento se tienen n opciones, pare el segundo se tienen n − 1 opciones (porque debe ser diferente del primero), y en general para el i-´esimo elemento se tienen n − (i − 1) = n − i + 1 opciones. As´ı que por la regla del producto, el n´ umero total de posibles k-permutaciones es P(n, k) = n · (n − 1) · · · · · (n − k + 1).

III.5. COMBINACIONES

9

Este n´ umero se puede escribir en forma m´as compacta en t´erminos de factoriales multiplicando y dividiendo por (n − k)!: n · (n − 1) · · · · · (n − k + 1) · (n − k)! (n − k)! n! = . (n − k)!

P(n, k) =

III.5.

Combinaciones

Una k-combinaci´on o´ k-subconjunto (´o k-conjunto) de un conjunto X es un subconjunto de X de tama˜ no k. A diferencia de una k-permutaci´on, como conjunto, el ordenamiento no importa. Si |X| = n entonces el n´ umero de k-combinaciones se denota por C(n, k). Por ejemplo, si X = {a, b, c, d, e} entonces las posibles 2-combinaciones son: {a, b}, {a, c}, {a, d}, {a, e}, {b, c}, {b, d}, {b, e}, {c, d}, {c, e}, {d, e} El valor de C(n, k) se puede derivar de la siguiente manera: una k-permutaci´on se puede obtener eligiendo primero una k-combinaci´on y luego una permutaci´on de esta. En el primer paso el n´ umero de opciones es C(n, k) y en el segundo es k!. En el ejemplo anterior, las 2-permutaciones se obtienen pemutando las 2-combinaciones, se obtienen 10 · 2! = 20: {a, b} → ab; ba {a, e} → ae; ea {b, e} → be; eb {d, e} → de; eb

{a, c} → ac; ca {b, c} → bc; cb {c, d} → cd; de

{a, d} → ad; da {b, d} → bd; db {c, e} → ce; ec

En general, usando la regla del producto se obtiene P(n, k) = C(n, k) · k! y de aqu´ı que C(n, k) =

n! P(n, k) = k! (n − k)! k!

Este valor tambi´en recibe el nombre de coeficiente binomial (por su papel en el teorema binomial que se presenta m´as adelante) y se denota   n n! = k (n − k)! k!

´ CAP´ITULO III. COMBINATORIA BASICA: CONTEO

10

III.6.

Interpretaci´ on Combinatorial

Con frecuencia igualdades entre coeficientes binomiales se pueden verificar interpret´andolas como diferentes formas de contar la misma colecci´on de objetos. Sea In = {1, 2, 3, . . . , n}. Damos un par de ejemplos:

    n n−1 ? k =n k k−1 Contamos subconjuntos de In con un elemento “especial”, o´ m´as formalmente pares (a, X) con a ∈ X y X ⊆ In . Para obtener el conteo de la izquierda de la igualdad, seleccionamos primero el subconjunto de k elementos, y luego el elemento especial del subconjunto entre sus k elementos. Para obtener el conteo de la derecha, seleccionamos primero el elemento especial y luego los k − 1 elementos restantes para X entre los n − 1 elementos restantes de X.       n s n n−k ? = s k k s−k Contamos pares (X, Y) con X ⊆ Y ⊆ In , |Y| = s y |X| = k. Para obtener el conteo de la izquierda, seleccionamos primero Y como subconjunto de In , y luego seleccionamos X como subconjunto de Y. Para obtener el conteo de la derecha, seleccionamos X como subconjunto de In , y luego seleccionamos Y − X como subconjunto de In − X.

III.7.

Teorema Binomial

El teorema binomial generaliza las expresiones bien conocidas para el cuadrado y el cubo de una suma X + Y donde X y Y son variables: (X + Y)2 = X2 + 2XY + Y 2 (X + Y)3 = X3 + 3X2 Y + 3XY 2 + Y 3 . (Para ser precisos, estamos asumiendo que X y Y conmutan, es decir XY = YX, y las leyes usuales de exponentes Xi Xj = Xi+j .) Los coeficientes de la expresi´on

III.7. TEOREMA BINOMIAL

11

general (X + Y)n son los enteros en la n-´esima fila del tri´angulo de Pascal: k=0

1

n=0

1

n=1

1

n=2

1

n=3

1

n=4

1

n=5

1

n=6 n=7

1

7

2 3

4 5

6

10

1

k=3

1 4

10 20

35

k=2

3 6

15 21

k=1

1

k=4

1 5

15 35

k=5

1 6

21

k=6

1 7

k=7

1

En cada fila el primer y u ´ltimo elementos son 1 y los dem´as se obtienen sumando los dos enteros en la fila anterior inmediatamente antes y despu´es. Mientras que n indexa las filas como se muestra, k indexa las diagonales que corren de arriba a la derecha hacia abajo a la izquierda, como tambi´en se muestra en la figura. El coeficiente con ´ındices n y k es el k-´esimo coeficiente de (X + Y)n . Este coeficiente, para n ≥ 0 y 0 ≤ k ≤ n, lo denotamos con cn,k y de acuerdo con la construcci´on satisface la ecuaci´on de recurrencia para n ≥ 0 y 1 ≤ k ≤ n: cn+1,k = cn,k−1 + cn,k con casos base cn,0 = cn,n = 1 para n ≥ 0. Veamos primero que cn,k

  n = k




Para esto es suficiente ver que n0 = nn = 1 (el caso base) y probar que nk satisface la misma recurrencia que cn,k . Esta es la llamada relaci´on de Pascal: Lema 6 Para n ≥ 0 y 1 ≤ k ≤ n, se tiene que       n+1 n n = + . k k−1 k Esto se puede verificar algebraicamente, o usando un argumento combinatorial. Este u ´ltimo es esencialmente que para un (k+1)-subconjunto X de {1, 2, . . . , n+ 1} existen dos posibilidades: X contiene n + 1 y contiene otros k − 1 elementos de {1, 2, . . . , n}, ´o X no contiene n + 1 y contiene k elementos de {1, 2, . . . , n}.

12

´ CAP´ITULO III. COMBINATORIA BASICA: CONTEO

Prueba. (Alternativa 1) Tenemos la derivaci´on algebraica:     n n n! n! + = + k−1 k (n − k + 1)! (k − 1)! (n − k)! k!   n! 1 1 = · + (n − k)! (k − 1)! n−k+1 k n! k+n−k+1 = · (n − k)! (k − 1)! (n − k + 1)k n+1 n! · = (n − k)! (k − 1)! (n − k + 1)k (n + 1)! = (n − k + 1)! k!   n+1 = . k Prueba. (Alternativa 2) Ahora vamos a dar una prueba biyectiva. Sean A = {X ⊆ {1, 2, 3, . . . , n + 1} : |X| = k} B = {X ⊆ {1, 2, 3, . . . , n} : |X| = k − 1} C = {X ⊆ {1, 2, 3, . . . , n} : |X| = k} Sabemos que   n+1 |A| = , k

|B| =



 n , k−1

  n |C| = k

Definimos la funci´on f : A → B ∪ C como X − {n + 1} si n + 1 ∈ X f(X) = X si n + 1 6∈ X En el primer caso la imagen est´a en B y en el segundo en C. Es “f´acil de ver” que f es biyectiva: Uno a uno: Sean X1 , X2 ∈ A con f(X1 ) = f(X2 ). Si f(X1 ) = f(X2 ) est´a en B entonces X1 = f(X1 ) ∪ {n + 1} y X2 = f(X2 ) ∪ {n + 1} y por lo tanto X1 = X2 . Si f(X1 ) = f(X2 ) est´a en C entonces X1 = f(X1 ) y X2 = f(X2 ) y por lo tanto X1 = X2 . En ambos casos X1 = X2 y por lo tanto f es uno a uno. Sobre: Sea Y ∈ B ∪ C. Si Y ∈ B entonces para X = Y ∪ {n + 1}, se tiene X ∈ A y f(X) = Y. Si Y ∈ C entonces para X = Y, se tiene X ∈ A y f(X) = Y. Por lo tanto f es sobre.

III.7. TEOREMA BINOMIAL

13

Puesto que B y C son disyuntos, se obtiene que |A| = |B| + |C| y de aqu´ı que       n+1 n n = + . k k−1 k En la prueba anterior, la verificaci´on de que f es una biyecci´on es m´as f´acil mostrando la inversa: Y ∪ {n + 1} si Y ∈ B g(Y) = Y si Y ∈ C Se verifica f´acilmente que f(g(Y)) = Y y g(f(X) = X.
Puesto que cn,k y nk satisfacen la misma ecuaci´on de recurrencia, entonces deben ser iguales:   n cn,k = k (formalmente se verifica por inducci´on). Ahora podemos establecer el teorema binomial. La expresi´on para la n-´esima potencia de (X + Y) se llama con frecuencia la f´ormula del binomio de Newton. Teorema 7 (Teorema Binomial) Para n ∈ N0 , se tiene n   X n k n−k (X + Y) = X Y . k k=0 n

En este enunciado, X y Y son variables que conmutan (pueden tomar valores por ejemplo enteros, racionales ´o reales). As´ı que (X + Y)n es un polinomio en las dos variables X y Y. Prueba. El resultado de (X + Y)n es una suma de t´erminos Xk Y n−k y es sufi
ciente identificar el coeficiente ck de cada uno de estos. Afirmamos que ck = nk . Esto es cierto porque en el producto (con n t´erminos) (X + Y) · (X + Y) · (X + Y) · · · · · (X + Y) · (X + Y) despu´es de aplicar distributividad, cada t´ermino equivalente a Xk Y n−k resulta de “escoger” X en k factores y Y en los n − k factores restantes. As´ı que el coeficiente de Xk Y n−k es igual al n´ umero de
formas de escoger k elementos de un total de n elementos. Este n´ umero es nk .

´ CAP´ITULO III. COMBINATORIA BASICA: CONTEO

14

Como ejemplo, si n = 5 y k = 2, entonces los en X2 Y 3 son:

5 2




= 10 productos que resultan

XXYYY XYXYY XYYXY XYYYX YXXYY YXYXY YXYYX YYXXY YYXYX YYYXX Alternativamente, se puede dar una prueba por inducci´on que usa la relaci´on de Pascal. Prueba alternativa. Por inducci´on sobre n. Para n = 0, (X + Y)0 = 1 y por
0 0 0 otra parte 0 = 1 y X Y = 1. Para el paso inductivo, consideramos, (X + Y)n+1 = (X + Y)n · (X + Y) n   X n k n−k = X Y · (X + Y) k k=0 n   n   X n k+1 n−k X n k n−k+1 = X Y + X Y k k k=0 k=0 n   n   X n k+1 n+1−(k+1) X n k (n+1)−k = X Y + X Y k k k=0 k=0   n+1 n   X X n n k (n+1)−k k (n+1)−k = X Y + X Y k−1 k k=1 k=0    n  X n n n+1 = X + + Xk Y (n+1)−k + Y n+1 k − 1 k k=1  n  X n + 1 k (n+1)−k n+1 = X + X Y + Y n+1 k k=1  n+1 X n + 1 = Xk Y (n+1)−k k k=0 donde se ha usado el lema anterior.

III.7.1.

Aplicaciones

Del teorema binomial se puden derivar otras igualdades que aparte de ser interesantes por s´ı mismas, tienen interpretaciones combinatoriales (de conteo) tambi´en interesantes. Sea In = {1, 2, 3, . . . , n}. n   X n n ? 2 = k k=0

III.7. TEOREMA BINOMIAL

15

Derivaci´on: Se obtiene del teorema binomial con X = 1 y Y = 1 Interpretaci´on combinatorial: Se cuentan todos los subconjuntos de In , es decir P(In ). A la izquierda est´a el conteo ya conocido 2n y a la derecha est´a la suma sobre k del n´ umero de subconjuntos de tama˜ no k.   n X k n ? 0= (−1) k k=0 Derivaci´on: Se obtiene del teorema binomial con X = −1 y Y = 1: n   X n (−1 + 1) = (−1)k . k i=0 n

Interpretaci´on combinatorial: Pasando todos los t´erminos negativos al otro lado, la identidad se puede reescribir como X n X n = . k k k par

k impar

Esta identidad se puede verificar por medio de una biyecci´on (funci´on biyectiva) entre los subconjuntos de {1, 2, . . . , n} de tama˜ no par y los subconjuntos de {1, 2, . . . , n} de tama˜ no impar, de la siguiente manera. Sea [ Ppar (In ) = {A ⊆ In : |A| = k} k par

[

Pimpar (In ) =

{A ⊆ In : |A| = k}

k impar

Definimos la funci´on f : Ppar (In ) → Pimpar (In ) como

f(A) =

A ∪ {n} si n 6∈ A A − {n} si n ∈ A

Claramente, si A ∈ Ppar (In ) entonces f(A) ∈ Pimpar (In ). Verificamos que f es una biyecci´on mostrando su inversa: g : Pimpar (In ) → Ppar (In )

´ CAP´ITULO III. COMBINATORIA BASICA: CONTEO

16 dada por

g(B) =

B ∪ {n} si n 6∈ B B − {n} si n ∈ B

(f y g son restricciones de la misma funci´on definida en P(In ) a sus dominios.) Es claro que f(g(B)) = B y g(f(A)) = A.   n X n n−1 ? n·2 = k k k=1 Derivaci´on: Con Y = 1 en el teorema binomial se obtiene n   X n k n (X + 1) = X . k k=1 Derivando ambos lados con respecto a X se obtiene n   X n n−1 n(X + 1) = kXk−1 k k=1 Reemplazando X = 1 se obtiene n2

n−1

  n X n = k . k k=1

Interpretaci´on combinatorial: Esta igualdad se puede interpretar como dos formas diferentes de contar pares (a, A) donde A ⊆ In y a ∈ A. Para obtener el t´ermino a la izquierda se escoge primero a ∈ In y luego A − {a} de In − {a}. Para obtener el t´ermino a la derecha, primero se escoge k y un subconjunto A de tama˜ no k y luego a ∈ A.   n X n k n ? 3 = 2 k k=0 Derivaci´on: En el teorema binomial reemplace X = 2 y Y = 1. Interpretaci´on combinatorial: Taller.   X  k    m+n m n ? = · k j k−j j=0 Derivaci´on: Taller. Interpretaci´on combinatorial: Taller.

´ ´ III.8. PRINCIPIO DE INCLUSION-EXCLUSI ON

III.8.

17

Principio de Inclusi´ on-Exclusi´ on

Ahora regresamos a la generalizaci´on de la relaci´on |A ∪ B| = |A| + |B| − |A ∩ B| al caso de m´as de 2 conjuntos. Teorema 8 Sea In = {1, 2, 3, . . . , n} y Ai con i ∈ In una familia de conjuntos finitos. Entonces T [ X Ai = (−1)|J|−1 j∈J Aj i∈In

∅6=J⊆In

En la prueba χA denota la funci´on caracter´ıstica de A ⊆ U. Recuerde que χA : U → {0, 1} dada por 0 si x 6∈ A χA (x) = 1 si x ∈ A Prueba. Una alternativa es inducci´on sobre n, la cual se puede encontrar en el texto de Bloch. Aqu´ı presentamos una prueba basada en funciones caracter´ısticas. Por conveniencia, abreviamos las intersecciones en el enunciado como \ AJ = Aj . j∈J

Sea A = ∪i∈In Ai . Si x 6∈ A entonces χA (x) = 0 y χAJ (x) = 0 para todo J ⊆ In , y por lo tanto la contribuci´on de x en ambos lados es cero. Si x ∈ A, entonces sea Ix = {i ∈ In : x ∈ Ai } y k = |Ix |. Para ∅ = 6 J ⊆ Ix , se tiene χAJ (x) = 1. Entonces mientras que la funci´on caracter´ıstica evaluada en el lado izquierdo es obviamente 1, χA (x) = 1, en el lado derecho se tiene que la contribuci´on que no se anula directamente es X

(−1)

|J|−1

=

∅6=J⊆Ix

=

k X

X

i=1

|J|=i;J⊆Ix

k  X i=1

(−1)i−1 sumando sobre los tama˜ nos posibles i de J

   k k i−1 (−1) porque es el n´ umero de k-subconjuntos. i i

Esta suma es exactamente 1 si (cambiando de lado la suma y entrando el 1 a la suma) k   X k (−1)i = 0 i i=0

18

´ CAP´ITULO III. COMBINATORIA BASICA: CONTEO

lo cual es cierto por el siguiente lema (que es realmente una de las aplicaciones presentadas arriba del teorema binomial). Es decir cada x contribuye 0 o´ 1 en la izquierda y correspondientemente 0 o´ 1 en la derecha. Por lo tanto la igualdad es v´alida. Lema 9 Sea k ≥ 0, entonces k   X k (−1)i = 0. i i=0

Prueba. El resultado se puede deducir aplicando el teorema binomial a (X + Y)k con X = −1 y Y = 1 porque entonces k   X k (−1 + 1) = 0 = (−1)i . i i=0 k

Ejercicio. Pruebe el principio de inclusi´on-exclusi´on usando inducci´on sobre n.

Aplicaci´ on: N´ umero de Desarreglos Un desarreglo de In = {1, . . . , n} es una permutaci´on σ ∈ Sn tal que para todo i ∈ In , σ(i) 6= i. Sea Dn el conjunto de desarreglos. Para i ∈ In , sea Ai ⊆ Sn el conjunto de permutaciones con σ(i) = i. Entonces Dn =

\

Ai ,

i∈In

donde Ai denota el complemento de Ai . Tenemos entonces que Dn =

\ i∈In

Ai =

[

Ai .

i∈In

As´ı que podemos determinar la cardinalidad de esta uni´on usando el principio de inclusi´on-exclusi´on y luego substraer esa cardinalidad de n! Para esto usamos que dado ∅ = 6 J ⊆ I con |J| = k, \ Ai = (n − k)! i∈J

´ ´ III.8. PRINCIPIO DE INCLUSION-EXCLUSI ON porque si σ ∈ I − J. As´ı que

T

J

19

Ai entonces σ(j) = j para j ∈ J y σ|J es una permutaci´on de

[ Ai = i∈In

X

\ (−1)|J|−1 Ai i∈J ∅6=J⊆I   n X k−1 n (n − k)! = (−1) k k=1 =

n X

(−1)k−1

k=1

= n! ·

n X (−1)k−1 k=1

Entonces |Dn | = n! − n! ·

n! (n − k)! k! (n − k)!

k!

n X (−1)k−1 k=1

k!

= n! ·

n X (−1)k k=0

k!

Note que la suma es la parte inicial de la serie de la funci´on ex evaluada en P x = −1. Esto significa que Pncuando n → ∞, |Dn |/n! → 1/e. (Note que k∈In (·) significa lo mismo que k=1 (·)) En el siguiente cap´ıtulo usamos este principio para determinar la funci´on φ de Euler.