Capítulo VIII: El cardinal de un conjunto.

Una aplicación inmediata de las funciones inyectivas es la que nos permite contar los elementos de un conjunto. El hecho de decir que un determinado conjunto X tiene n elementos se debe a que si vamos asignando, comenzando por 1, 2, 3, . . . , etc., un número natural a cada elemento del conjunto X, el último número asociado es el de elementos de este posee. Este proceso recibe el nombre de enumeración del conjunto X

Si construimos para cada n N el subconjunto N_n de N definido por N_n= {1, 2, . . . , n}, el decir que X tiene n elementos equivale a decir que se puede establecer una biyección entre N_n y X.

Al número de elementos de un conjunto X se le denomina cardinal del conjunto X y se denota por | X |. Al conjunto vacío se le asigna el cardinal cero: | | = 0.

Al hablar de enumeración hemos visto la forma de contar los elementos de un conjunto asignando un número natural a cada uno de ellos. Ahora bien, si no disponemos de una lista de sus elementos, sino que el conjunto viene definido a través de unas propiedades, es necesario desarrollar técnicas, diferentes a las ya conocidas, capaces de contar sus elementos.

Dados dos conjuntos A y B, se define el conjunto unión y se denota por A B como el conjunto de todos los elementos que pertenecen, indistintamente, a A o a B.

Se define el conjunto intersección y se denota por A B como el conjunto de los elementos que pertenecen, simultáneamente, a ambos conjuntos.

Así, por ejemplo, si A ={1, 2, 3} y B ={ 2, 4, 6}, tenemos que A B = {1, 2, 3, 4, 6} y A B = {2}.

Si la intersección de dos conjuntos es vacía, diremos que dichos conjuntos son disjuntos.

Lema 3.5. Si dos conjuntos A y B son disjuntos, se verifica que | A B | = | A | + | B |.

La demostración puede realizarla el lector a modo de ejercicio.

Esta propiedad de los conjuntos disjuntos puede ser generalizada como muestra el siguiente teorema.

Teorema 3.6. [Principio de adición] Si A₁, A₂, . . . , A_n son conjuntos disjuntos dos a dos, es decir, si

se verifica que

Un resultado importante que se obtiene directamente del principio de adición es el denominado principio de las cajas que describimos a continuación.

Teorema 3.7. [Principio de las cajas] Si queremos repartir n objetos en m cajas y r es un entero tal que rm < n, al menos una caja, ha de recibir más de r objetos.

Demostración: Definamos para 1im los conjuntos A_i ={objetos de la caja i-ésima}. Evidentemente ha de verificarse que

Ahora bien:

Si fuese tendríamos que nmr contra la hipótesis de que n > rm. Por tanto , ha de ser es decir, alguna de las cajas ha de recibir más de r objetos.

Capítulo IX: Análisis Combinatorio.

 Principio Fundamental del Análisis Combinatorio

 Suponga que una persona tiene 2 formas de ir de una ciudad A a otra ciudad B; y una vez llegada a B, tiene 3 maneras de llegar a otra ciudad C, ¿De cuántas maneras podrá realizar el viaje de A a C pasando por B?

Si empezó a pie, podrá tomar luego avión, carro o trasatlántico, y si empezó en bicicleta, también podrá tomar avión, carro o trasatlántico.

La persona tuvo 6 formas diferentes de realizar el viaje que son: (iniciales) pa, pc, pt, ba, bc, bt. (2 x 3 = 6)

Se puede representar en un diagrama de árbol

PIE - AVIÓN

PIE - CARRO

PIE - TRASA.

------------------

BIC- AVIÓN

BIC - CARRO

BIC-TRASA.

Por lo que el principio fundamental del análisis combinatorio, puede expresarse así:

Si una primera decisión, operación o acción puede efectuarse de a formas diferentes, una segunda acción puede efectuarse de b formas diferentes, una tercera acción puede efectuarse de c formas diferentes y así sucesivamente hasta la enésima acción que puede efectuarse de z formas diferentes, entonces el número total de formas diferentes que pueden efectuarse estas n acciones es igual con:

a x b x c x ... x z

Este principio también se llama principio de conteo ó principio multiplicativo.

Ejemplo: ¿De cuántas maneras diferentes podrá vestirse un joven que tiene 3 camisas diferentes, 4 pantalones y 2 pares de calzado?

Solución:

3 x 4 x 2 = 24 maneras diferentes

Ejemplo: En una ciudad los números de teléfono constan de 5 dígitos, cada uno de los cuales se llama con alguno de los 10 dígitos (0 al 9). ¿Cuántos números diferentes pueden formularse?

Solución:

10 x 10 x 10 x 10 x 10 = 100,000 números diferentes

Ejemplo: La agencia de Publicidad PIPSA, ha obtenido la exclusividad respecto a una línea de polvos para preparar postres. A estos efectos la agencia ha decidido organizar un concurso nacional destinado a adivinar el nombre futuro de esa línea de productos.

Las condiciones son:

a)      Los nombres que se propongan deben ser de 4 letras.

b)      Ninguna letra debe repetirse.

c)      La primera y tercera letras deben ser consonantes.

d)      La segunda y cuarta letras deben ser vocales.

e)      Si una persona propone 2 veces el mismo nombre queda descalificada.

 ¿Cuántos nombres debe proponer una persona para estar seguro que participa en el sorteo público?

Considerar 28 letras del alfabeto

Solución:

 23 x 5 x 22 x 4 = 10,120 nombres diferentes 

¿Por qué esos números? 

Porque hay 28 letras del alfabeto, 23 consonantes y 5 vocales, pero se disminuyó de 23 a 22 en la primera y tercera cifra porque una de las condiciones es que las letras no se repitan. Así como 5 y 4 en la segunda y cuarta cifras, que son las vocales.

 Notación Factorial

 En algunos problemas de matemáticas se nos presentan multiplicaciones de números naturales sucesivos tal como: 4 x 3 x 2 x 1 = 24; 3 x 2 x 1 = 6; 2 x 1 = 2.

 Para abreviar estas expresiones, se usa una notación especial llamada notación factorial y nos denota las multiplicaciones sucesivas de n hasta l y se define como:

 4 x 3 x 2 x 1 = 4!  Se lee“cuatro factorial”

3 x 2 x 1 = 3! Se lee “tres factorial”

En términos generales:

n(n-1)(n-2)...x 2 x 1 = n! Se lee “n factorial”

Propiedades:

 a)      para n natural

n! = n(n-1)!

Ejemplo: 7! = 7 x 6! = 7 x 6 x 5 x 4!

b)      0! = 1

Ejemplos:

1)      5! = 5 x 4 x 3 x 2 x 1 = 120

2)      4! 3! = (24)(6) = 144

3)     

4)     

5)     

 Cuando n es demasiado grande se suele utilizar la fórmula de Stirling:

Ejemplo:

Determinar 50! por Stirling:

9.1. PERMUTACIONES

Permutación: Conjunto ordenado de n elementos.

Notación: Pn; Pn, n; An, n

Permutación de 5 elementos

P₅ = 5! Por lo que:

Pn = n!

P₅ = 5! = 5 x 4 x 3 x 2 x 1 = 120

Ejemplo:

Para el conjunto {a, b, c} existen las siguientes permutaciones:

Solución:

Abc, acb, bca, bac, cab, cba = 6

P₃ = 3! = 6

Ejemplo:

En una asamblea de accionistas, hay 6 personas que han solicitado hacer uso de la palabra ¿En cuántas órdenes diferentes pueden hablar, si es que no se ha establecido un orden de prioridades?

Solución:

P₆ = 6! = 720

Ejemplo:

En un proceso de manufactura hay seis operaciones distintas, que se indican con A, B, C, D, E y F. En general no existe una secuencia fija para las operaciones, con la salvedad de que A debe efectuarse al principio y F al final. ¿Cuántas secuencias diferentes pueden ocurrir?

Solución:

A B C D E F

P₄ = 4! = 24 formas diferentes

Cuando se toman parte de los elementos del conjunto se tiene:

Pn,r =

Ejemplo:

Si n = 5 y r = 3

P_5,3 =

Ejemplo:

Hay 7 candidatos para desempeñar 3 tareas, si todos los candidatos son igualmente eficientes, ¿De cuántas maneras se puede efectuar la asignación?

Solución:

P_7,3 =

Ejemplo:

De cuántas maneras 3 fresadoras, 4 tornos, 4 taladros y 2 cepillos pueden ordenarse en fila en un taller, de modo que el mismo tipo de máquina queden juntas.

3F	4T	4T	2C
P3 = 3!	P4 = 4!	P4 = 4!	P2 = 2!
P4 = 4!

3! 4! 4! 2! 4! = 165,888 maneras diferentes

10.2. COMBINACIONES

Una combinación de n elementos tomados de r en r es un subconjunto no ordenado de r elementos con .

2 combinaciones formadas por r elementos son distintas, si difieren al menos en un elemento.

Ejemplo:

Sea el conjunto {a, b, c} de cuántas maneras podemos seleccionar:

a)      un elemento

b)      dos elementos

c)      tres elementos

Solución:

a)      Existen 3 formas de seleccionar un elementos: a; b; c.

b)      Existen 3 formas de seleccionar dos elementos: ab, ac, bc

c)      Existe 1 forma de seleccionar 3 elementos: abc

Notación: _nC_r;

Para determinar el número de combinaciones de n elementos tomando de r en r:

Ejemplo:

Si n = 10 r = 7

Ejemplo:

El congreso anglo mexicano de administración pública, debe elegir el futuro comité ejecutivo que regirá a esa institución durante el próximo año.

La comisión directiva se forma con 6 integrantes y este año han sido propuestos 7 representantes mexicanos y 4 ingleses para ser electos. Se pide determinar de cuántas maneras se puede integrar la comisión en los siguientes casos:

a)      Si en la comisión debe haber 4 mexicanos y 2 ingleses.

b)      Si en la comisión debe haber como mínimo 2 ingleses y 2 mexicanos.

Solución:

a)      Los mexicanos se pueden escoger de:

Los ingleses se pueden escoger de:

Conjuntamente

b)      Se pueden presentar los casos:

1)      2 ingleses y 4 mexicanos:

2)      3 ingleses y 3 mexicanos:

3)      4 ingleses y 2 mexicanos:

210 + 140 + 21 = 371

Ejemplo:

En los laboratorios “ELKO” hay 3 plazas vacantes de un total de 33 solicitudes de empleo, sólo 14 se han considerado aceptables, en bases en las entrevistas practicadas por el departamento de personal. ¿De cuántas maneras pueden asignarse las 3 plazas?

a)      Si todos los empleos son de la misma categoría

b)      Si un empleo es de gerente de ventas, uno es de agente visitador para las ciudades de Puebla y Tlaxcala y otro de agente visitador para las ciudades de Tampico y Cd. Madero.

Solución:

a)     

b)