Bachicher

Combinatoria
Original de Carlos Domingo. Editado por Carmen Rodríguez y Jacinto Dávila. Universidad de Los Andes, Venezuela. 1. Considere un objeto elemento △ que puede tomarse en 3 formas: △ ▷ ▽ y un elemento □ que puede tomarse en cuatro formas: __, __, __, ___. ¿En cuántas formas diferentes puede tomarse uno cualquiera de estos elementos es decir un elemento del conjunto: { △, □ } ?__________ 2. Esta solución es un caso particular de la regla de la suma: “Si un objeto A puede tomarse en m formas y el objeto B en n formas entonces uno entre A ó B puede tomarse de _____________ formas”. 3. Considere el mismo ejemplo 1 pero ahora hay que tomar 2 objetos, el △ y el □. ¿En cuántas formas puedo tomarlos? (no interesa el orden, es decir △ □ es igual a □ △). Sugerencia: observar el "árbol":El número de formas es: _________________ 4. Esta solución es un caso particular de la regla del producto: “Si un elemento A puede tomarse de m formas y el B de n formas entonces el par A y B puede tomarse en ___________ formas”. 5. Sean los conjuntos C1={A, B, C, D} C2={X, Y, Z} ¿Cuántas y cuáles son las duplas o pares que pueden construirse teniendo cada dupla un primer elemento de C1 y unsegundo elemento de C2? Considerar que el primer elemento puede tomarse en ____ formas y el segundo en _____ formas. Construir el árbol:

Duplas: AX,___________________________________________________________________ Cantidad: ____________ 7. Sean r conjuntos con n1, n2, ..., nr objetos respectivamente. El número de conjuntos diferentes con r elementos cada uno, conteniendo un elemento de cadaconjunto será: M = n1* _________________________________ Demostrarlo por inducción:

8. Si tenemos k conjuntos iguales de n elementos cada uno el número de k-tuplas distintas que pueden formarse extrayendo un elemento de cada uno es:________ 9. Demostrar, usando esta fórmula que hay 1000 números de tres cifras o menos. 10. a) Calcular, basándose en la fórmula dada en 8, ¿cuántos subconjuntosdiferentes pueden formarse en un conjunto C de n elementos?. Nota: Los subconjuntos podrían formarse considerando el C={a1, a2, ... , an} y luego los subconjuntos {a1} ... {a1, a2}, {a2, a3}, ... , {an-1, an}, .. {a1,..,an} b) Demostrar la misma fórmula por inducción.

11. ¿Cuántos números binarios de n cifras hay? (Número binario es el que se escribe con sólo dos cifras 0 y 1 así: 0, 1, ..10,...11, ....100, .....101, ......110, etc) 12. ¿Cómo resolvería el problema 10 con el resultado del problema 11? 13. ¿Cuántas funciones diferentes f: A -> B pueden formarse si el dominio A tiene k valores y el rango B n valores? __________________________________ Sigamos la respuesta que propone J. Rodríguez en el “Arte de Contar”: Digamos primero que f es una función de A en B y representemoslo así f∈B A . Esta es una exageración notacional, porque A y B son conjuntos, pero veremos que conviene para los resultados que siguen. Digamos ahora que A= { t 1, t 2, ..,t k } y B= { c1, c 2, ... ,c n } . “Una de las” f es puede representar como sigue:

f=



t1
i

t2
j

cf t  c f  t 

... t k ... cf t 
l



pareando la k-tupla de elementos de A con una selección particular (quedetermina la f) de elementos de B. Decimos ahora que: f es una k-permutación o permutación(n,k) de los n elementos de B. Proposición para probar: ∣B A∣=∣B∣∣A∣=n k Demostración: Sea B k =B×B×B×...×B 
k veces

(noten que esta no es ninguna de las anteriores, sino

una nueva construcción, de nuevo exagerada, para referirnos al producto cartesiano múltiple del conjunto B consigo mismo), talque: B k ={ cf ,c f , cf ,... , cf /c f ∈B∧1≤i≤k }
1 2 3 k i

La función auxiliar φ:

B A  B k definida así:

φ f =f t 1 ,... , f t k  es biyectiva y, por tanto, en virtud del principio de igualda, conseguir a ∣B k∣
i j l

∣B A∣ es igual que conseguir

Para encontrar todas esas k-tuplas (o k-uplas)  c f  t  c f  t  ... c f t  formadas por elementos de B, basta con...