1 Funciones

2 1 a 1 muchos a muchos 1 a muchos

3 Capítulo 4 Funciones 4.1 FuncionesDefinición Dados los conjuntos no vacíos A, B, una función, o transformación f de A a B, definida por f : A  B, es una relación de A a B donde cada elemento de A aparece exactamente una vez como primera componente de un par ordenado de la relación.

4 Capítulo 4 Funciones 4.1 FuncionesSuele escribirse f(a) = b cuando (a, b) es un par ordenado de la función f. Para (a, b)f, b se denomina imagen de a en f, mientras que a es un antecedente de b. Además la definición sugiere que f es un método para asociar a cada a  A una única b  B; este proceso se denota mediante f(a) = b. Por tanto, (a, b) , (a, c)  f implica que b = c.

5 Capítulo 4 Funciones 4.1 FuncionesEJEMPLO Para A = {1, 2, 3}, B = {w, x, y, z}, f = {(1, w), (2, x), (3, x)} es una función y, por tanto una relación de A a B. R1 = {(1, w), (1, x), (2, x)}, R2 = {(1, w), (2, w), (2, x), (3, z)} son relaciones, pero no funciones, de A a B. (¿Por qué no lo son?).

6 Capítulo 4 Funciones 4.1 FuncionesDefinición Para la función f : A  B, A y B se denominan dominio y codominio de f, respectivamente. El subconjunto de B formado por aquellos elementos que aparecen como segundas componentes en los pares ordenados de f, se llama imagen de f y también se define por f(A).

7 Capítulo 4 Funciones 4.1 FuncionesPara A = {1, 2, 3}, B = {w, x, y, z}, f = {(1, w), (2, x), (3, x)} el dominio de f ={1, 2, 3}, el codominio de f = {w, x, y, z}, y la imagen de f= f(A) ={w, x}.

8 Capítulo 4 Funciones 4.1 FuncionesEstas ideas se pueden representar mediante un diagrama de Venn, como en la figura siguiente. Este diagrama muestra que a puede considerarse como una entrada que es transformada mediante f en la correspondiente salida f(a).

9 Capítulo 4 Funciones 4.1 FuncionesEJEMPLO En el lenguaje de programación BASIC, la función del mayor entero, denotada por INT, es una función definida para el dominio de todos los números reales, es decir, INT: RZ, donde INT(X)=X, si X es un entero; si X no lo es, INT(X)= al entero situado inmediatamente a la izquierda de X. Por ejemplo, INT(5.1) = 5 e INT(-7.8) = -8. Aquí el codominio y la imagen son el conjunto Z.

10 Capítulo 4 Funciones 4.1 FuncionesEn Pascal se presenta la función trunc (por truncamiento), que es una función con valores enteros definida en R. La función elimina la parte fraccionaria de un número real. Por ejemplo, trunc(3.78) = 3, trunc(5) = 5, trunc(-7.22) = -7.

11 Capítulo 4 Funciones 4.1 FuncionesAl almacenar una matriz en una disposición unidimensional muchos lenguajes de programación lo hacen por filas. Aquí si A = (aij)nn es una matriz de n  n, la primera fila de A se almacena en las posiciones 1, 2, 3,..., n de la disposición si se comienza con a11 en la posición 1. Entonces, el registro a21 se halla en la posición n + 1, mientras que el a34 ocupa la posición 2n + 4 de la disposición. Para determinar la posición de cualquier registro aij, 1 i, j n, a partir de A, se define la función de acceso f de los registros de A a las posiciones 1,2,3, ..., n2 de la disposición. Aquí una fórmula para la función de acceso es f(aij) = (i – 1)n + j.

12 Capítulo 4 Funciones 4.1 FuncionesDada una relación de A a B. Ya se ha analizado una función entre estas relaciones, y ahora se desea contar el número total de funciones de A a B.

13 Capítulo 4 Funciones 4.1 FuncionesPara el caso general, sean A, B conjuntos con = m, = n. En consecuencia, si A = {a1, a2, ..., am}, B = {b1, b2, ... ,bn}, una función típica f : A  B se puede describir por medio de {(a1, x1), (a2, x2), ..., (am, xm)}. Se puede seleccionar cualquier elemento entre los n de B para x1 y a continuación hacer lo mismo para x2. (Se puede elegir cualquier elemento de B para x2 de modo que se puede elegir un mismo elemento de B para x1 y para x2). Este proceso de selección continúa hasta que uno de los n elementos de B sea finalmente seleccionado para xm. Así, por la regla del producto, hay nm = funciones de A a B.

14 Capítulo 4 Funciones 4.1 FuncionesPor tanto, si = 3 y = 4 entonces hay 43 = = 64 funciones de A a B y 34 = = 81 funciones de B a A.

15 Funciones Uno a Uno

16 Capítulo 4 Funciones 4.2 Funciones uno a unoDefinición Una función f : AB se llama uno a uno o inyectiva si cada elemento de B aparece a lo sumo una vez como la segunda componente de un par ordenado de f. Si f : A  B es uno a uno, con A, B finitos, entonces  Para conjuntos generales A, B, si f: AB es uno a uno, entonces para a1,a2 A, f(a1)=f(a2)  a1=a2. Entonces, una función de este tipo se puede caracterizar como aquella donde cada elemento de la imagen es imagen de exactamente un elemento del dominio.

17 Capítulo 4 Funciones 4.2 Funciones uno a unoEJEMPLO Sea A={1,2,3}, B={1,2,3,4,5}. La función f={(1,1),(2,3),(3,4)} es una función inyectiva de A a B. Mientras que g={(1,1),(2,3),(3,3)}es una función de A a B, aunque no es inyectiva, pues g(2)=g(3), pero 23. Para A, B del ejemplo hay 215 relaciones de A a B, y 53 de ellas son funciones. Lógicamente, la siguiente cuestión que se quiere resolver es ¿Cuántas funciones f : A  B son uno a uno?.

18 Capítulo 4 Funciones 4.2 Funciones uno a unoCon A={a1,a2,...,am}, B ={b1,b2,...,bn}, mn, una función uno a uno f: AB tiene la forma {(a1,x1),(a2,x2),...,(am,xm)}, donde hay n selecciones posibles para x1 (cualquier elemento de B), n–1 selecciones posibles para x2 (cualquier elemento posible de B, excepto el seleccionado para x1), n–2 selecciones posibles para x3, etc., y se concluye con n–(m–1)= n–m+1 selecciones posibles para xm. Por la regla del producto, el número de funciones uno a uno de A a B es n(n–1)(n–2)...(n–m+1) = = P(n,m) = P( , )

19 Capítulo 4 Funciones 4.2 Funciones uno a unoDefinición Si f : A  B y A1  A, entonces f(A1)= EJEMPLO Sea f: R  R dada por f(x) = x2. Entonces, f(R) = la imagen de f = [0, +]. La imagen de Z en f es f(Z) = {0,1,4,9,16,...}.

20 Capítulo 4 Funciones 4.2 Funciones uno a unoTeorema Sea f: A  B con A1, A2  A. Entonces, f(A1  A2) = f(A1)  f(A2) f(A1  A2)  f(A1)  f(A2) f(A1  A2) = f(A1)  f(A2) cuando f es inyectiva.

21 Capítulo 4 Funciones 4.2 Funciones uno a unoDemostración Se prueba el apartado b) y se deja el resto como ejercicio. Para cualquier bB, b f(A1  A2)  b = f(a), para algún a  A1  A2  (b = f(a), a  A1) y (b = f(a), a  A2)  b  f(A1) y b  f(A2)  b  f(A1)  f(A2), de modo que f(A1  A2)  f(A1)  f(A2).

22 Capítulo 4 Funciones 4.2 Funciones uno a unoDefinición Si f: A  B y A1  A, : A1  B se denomina restricción de f a A1 si = f(a) para toda a A1. Definición Sea A1  A y f: A1  B. Si g: A  B y g(a) = f(a) para toda a A1, g se denomina extensión de f a A.

23 EJEMPLO Sea A = {w, x, y, z}, B = {1, 2, 3, 4, 5}, A1={w, y, z}EJEMPLO Sea A = {w, x, y, z}, B = {1, 2, 3, 4, 5}, A1={w, y, z}. Sean f: AB, g: A1B. Entonces, g = y f es una extensión de g de A1 a A. Obsérvese que para la función dada g: A1  B hay cinco formas de extender g de A1 a A.

24 Funciones Suprayectivas: Números de Stirling de 2do Tipo

25 Capítulo 4 Funciones 4.3 Funciones suprayectivasDefinición Si f: A  B, f se llama sobre o suprayectiva si f(A)=B (es decir, si para toda b  B existe al menos un a A tal que f(a) = b). EJEMPLO La función f: R  R definida por f(x) = x3 es una función suprayectiva pero g: R  R dada por x2 no lo es, ya que g(R) =[0, +)  R.

26 Capítulo 4 Funciones 4.3 Funciones suprayectivasEJEMPLO Con A = {1, 2, 3, 4}, B = {x, y, z}, f1 = {(1, z), (2, y), (3, x), (4, y)} y f2={(1,x), (2, x), (3, y), (4, z)} son funciones de A sobre B. La función g = {(1, x), (2,x), (3,y), (4,y)} no es suprayectiva, pues g(A) = {x, y} B.

27 Capítulo 4 Funciones 4.3 Funciones suprayectivasEJEMPLO Si A = {x, y, z} y B = {1, 2}, entonces todas las funciones f: A  B son suprayectivas, excepto f1={(x, 1), (y, 1), (z, 1)} y f2={(x, 2), (y, 2), (z, 2)}, funciones constantes; de modo que hay –2 = 23–2 = 6 funciones suprayectivas de A a B. En general, si = m  2 y = 2, hay 2m – 2 funciones suprayectivas de A a B.

28 EJEMPLO Para A = {w, x, y, z} y B = {1, 2, 3} hay 34 funciones de A a B. Si se consideran los subconjuntos de B de tamaño 2, hay 24 funciones de A a {1, 2}, 24 de A a {2, 3}, y 24, de A a {1, 3}; así se obtienen 3(24) = funciones de A a B que no son suprayectivas. Sin embargo, antes de aceptar 34 – como respuesta, ha de tenerse en cuenta que no todas las funciones son diferentes, pues, cuando se tienen en cuenta todas las funciones de A a {1,2}, se elimina entre otras, la función {(w,2), (x,2), (y,2), (z,2)}. Al considerar las funciones de A a {2,3}, se suprime la misma función: {(w,2), (x,2), (y,2), (z,2)}. Por tanto, en el resultado se eliminaron dos veces las funciones constantes. Al adaptar el resultado a esto, se halla que hay 34 – = funciones suprayectivas de A a B.

29 Capítulo 4 Funciones 4.3 Funciones suprayectivasSi se mantiene B = {1, 2, 3}, para cualquier conjunto A, con = m  3, hay funciones suprayectivas de A a B.

30 Capítulo 4 Funciones 4.3 Funciones suprayectivasLos ejemplos anteriores sugieren como fórmula general: para conjuntos finitos A, B con = m  n= hay funciones suprayectivas de A a B.

31 Capítulo 4 Funciones 4.3 Funciones suprayectivasEJEMPLO Sea A = {1, 2, 3, 4, 5, 6, 7} y B ={w, x, y, z}. Si se aplica la fórmula general con m = 7, n = 4, hay funciones de A sobre B. El resultado es también la respuesta al siguiente problema: se desea distribuir, 7 objetos diferentes en 4 recipientes distintos sin dejar ningún recipiente vacío. Esto puede resolverse por funciones suprayectivas.

32 Capítulo 4 Funciones 4.3 Funciones suprayectivasEJEMPLO En la compañía CH, Juana la directora, tiene una secretaría, Teresa, y otras tres auxiliares. Si hay que procesar 7 cuentas, ¿de cuantas formas las puede distribuir Juana para que cada auxiliar trabaje al menos en una cuenta y el trabajo de Teresa incluya, aunque sólo haga eso, la cuenta más elevada?.

33 Capítulo 4 Funciones 4.3 Funciones suprayectivasSi Teresa trabaja sólo en la cuenta más elevada, entonces las otras seis cuentas se pueden distribuir entre las tres auxiliares administrativas de = 540 formas. (540 = el número de funciones suprayectivas f: A  B con = 6, = 3). Si Teresa trabaja en otra cosa, además de en la cuenta más elevada, las asignaciones se pueden hacer de = 1560 formas (1560 = el número de funciones suprayectivas g: C  D con =6, =4). Por lo tanto, las asignaciones se pueden hacer de = 2100 formas en las condiciones anteriores.

34 Ahora se prosigue al análisis de la distribución de objetos distintos en recipientes sin dejar ninguno vacío, pero en este caso los recipientes son idénticos. EJEMPLO Si A ={a, b, c, d}, B = {1, 2, 3} hay 36 funciones suprayectivas de A a B, o 36 formas de distribuir 4 objetos diferentes en tres recipientes distintos, sin dejar ninguno vacío (y sin tener en cuenta la posición de los objetos en un recipiente dado). Entre estas 36 distribuciones se halla la siguiente colección de seis (una de las seis posibles): 1) {a, b}1 {c}2 {d}3 2) {a, b}1 {d}2 {c}3 3) {c}1 {a, b}2 {d}3 4) {c}1 {d}2 {a, b}3 5) {d}1 {a, b}2 {c}3 6) {d}1 {c}2 {a, b}3, Nota: {c}2 significa que c está en el segundo recipiente.

35 Ahora, si no hay diferencia entre los recipientes, estas 6 = 3Ahora, si no hay diferencia entre los recipientes, estas 6 = 3! distribuciones se hacen idénticas, de modo que hay 36/(3!) = 6 formas de distribuir los distintos objetos a, b, c, d en tres recipientes idénticos sin dejar ninguno vacío. En general, para m  n hay formas de distribuir m objetos distintos entre n recipientes numerados (y por lo tanto, no idénticos) sin dejar ninguno vacío. Al suprimir los números de los recipientes para que sean idénticos, se halla que hay una distribución de estos n (no vacíos) recipientes idénticos que se corresponde con n! de tales distribuciones de los recipientes numerados. Así, el número de formas para distribuir los m objetos distintos en n recipientes idénticos, sin dejar ninguno vacío, es

36 Capítulo 4 Funciones 4.3 Funciones suprayectivasn m 1 2 3 4 5 6 7 8 15 25 10 31 90 65 63 301 350 140 21 127 966 1701 1050 266 28 n m 1 2 3 4 5 6 7 8 15 25 10 31 90 65 63 301 350 140 21 127 966 1701 1050 266 28 m 1 2 3 4 5 6 7 8 15 25 10 31 90 65 63 301 350 140 21 127 966 1701 1050 266 28 n n m 1 2 3 4 5 6 7 8 15 25 10 31 90 65 63 301 350 140 21 127 966 1701 1050 266 28 m 1 2 3 4 5 6 7 8 15 25 10 31 90 65 63 301 350 140 21 127 966 1701 1050 266 28 n Capítulo 4 Funciones 4.3 Funciones suprayectivas Esto se denota por S(m, n), y se denomina número de Stirling de segundo tipo. Se observa que para = m  n = , hay n!  S(m, n) funciones suprayectivas de A a B. 1 1 1 1 1

37 Capítulo 4 Funciones 4.3 Funciones suprayectivasEn la siguiente tabla se relacionan algunos números de Stirling de segundo tipo.

38 Capítulo 4 Funciones 4.3 Funciones suprayectivasEJEMPLO Para m  n, es el número de formas de distribuir m objetos distintos en n recipientes idénticos, admitiendo la posibilidad de recipientes vacíos. En la cuarta fila de la tabla anterior se observa que hay = 14 formas de distribuir los objetos a, b, c, d en tres recipientes idénticos con la posibilidad de recipientes vacíos.

39 Capítulo 4 Funciones 4.3 Funciones suprayectivasTeorema Sea n un número positivo con 1  n  m. entonces, S(m + 1, n) = S(m, n – 1) + nS(m, n).

40 Capítulo 4 Funciones 4.3 Funciones suprayectivasn recipientes idénticos S(m+1,n) am+1 está sola en un recipiente am+1 no está sola en un recipiente S(m,n-1) 1.-Distribuir n objetos en n recipientes. 2.- am+1 puede colocarse en uno de estos nS(m,n)

41 Capítulo 4 Funciones 4.3 Funciones suprayectivasDemostración Sea A = {a1, a2, ... , am, am+1}. Entonces, S(m + 1, n) cuenta el numero de formas en que los objetos de A pueden distribuirse en n recipientes idénticos, sin dejar ningún vacío.

42 Demostración ...(continuación)Hay S(m, n – 1) formas de distribuir a1, a2, ... , am, en n – 1 recipientes idénticos sin dejar ninguno vacío. Así al colocar am+1 en el recipiente vacío restante se obtienen S(m, n – 1) distribuciones contadas de S(m + 1, n), es decir, aquellas distribuciones donde am+1 está sola en un recipiente. Otra opción es distribuir a1, a2, ... , am, en los n recipientes idénticos sin que ninguno quede vacío, se obtienen S(m, n) distribuciones. Sin embargo, para cada una de estas S(m, n) distribuciones, los n recipientes se pueden distinguir ahora por su contenido. Al seleccionar uno de los n recipientes distintos para am+1 se tienen nS(m, n) distribuciones del total de S(m + 1, n) , esto es, aquellas donde am+1 está en el mismo recipiente que otro objeto de A. El resultado se obtiene mediante la regla de la suma.