Análisis combinatorio
Introducción
Podemos considerar el análisis combinatorio como el conjunto de procedimientos y técnicas que nos permite determinar el número de subconjuntos que pueden formarse a partir de un conjunto dado, de acuerdo a ciertas instrucciones.
Estas deben indicar claramente como se diferencian dos subconjuntos entre sí, de acuerdo a:
- la naturaleza de los elementos
- el orden de los elementos.
Realizaremos el análisis combinatorio sin repetición, es decir, cada elemento debe aparecer una única vez en cada subconjunto.
Reglas de Conteo
Al asignar probabilidades es necesario saber identificar y contar los resultados experimentales, si el numero de posibles resultados de un experimento es pequeño, es relativamente fácil listar y contar todos los posibles resultados. Por ejemplo, al tirar un dado se obtiene solo 6 posibles resultados s = {1,2,3,4,5,6}, como se ha visto anteriormente, aún tirando dos datos se pueden obtener estos resultados: S = {(1,1), (1,2), (1,3), (1,4), (1,5), (1,6), (2,1), (2,2), (2,3), (2,4), (2,5), (2,6), (3,1), (3,2), (3,3), (3,4), (3,5), (3,6), (4,1), (4,2), (4,3), (4,4), (4,5), (4,6), (5,1), (5,2), (5,3), (5,4), (5,5), (5,6), (6,1), (6,2), (6,3), (6,4), (6,5), (6,6) }
Sin embargo, hay un gran número de posibles resultados tales como el número de niños y niñas por familias con cinco hijos, sería tedioso listar y contar todas las posibilidades. Que serían, 5 niños, 4 niños y una niña, 3 niños y 2 niñas, etc. Para facilitar el conteo veamos tres técnicas de conteo, la de multiplicación, la técnica de permutación y la de la combinación.
Producto Cartesiano.
3.3.1 Definición. Sean A y B conjuntos. Al conjunto formado por todos los pares ordenados de primera componente en A y segunda componente en B, se le denota A x B y se le llama producto cartesiano de A y B. Simbólicamente:
A x B = {(x, y) / x Î A Ù y Î B}.
En consecuencia:
(x, y) Î A x B Û x Î A Ù y Î B
(x, y) Ï A x B Û x Ï A Ú y Ï B
En particular, siendo R el conjunto de los números reales, se tiene:
Rx R = {(x, y) / x ÎRÙ y ÎR }.
Rx R es el conjunto de todas las parejas de números reales. La representación geométrica de Rx R es el plano cartesiano llamado también plano numérico.
Se establece una relación biunívocaentreR x Ry el conjunto de los puntos del plano geométrico, asociándose de esta forma el par ordenado (x, y) con el punto P(x,y).
Ejemplo 1:
Sean A = {1, 2} y B = {3, 4, 5} el producto cartesiano A x B será:
A x B = {(1, 3),(1, 4),(1, 5),(2, 3),(2, 4),(2, 5)}.
Ejemplo 2:
Sean A = {x / x ÎR Ù1 < x £3 },
B = {x / x ÎR Ù-2 £ x < 2 }.
Su representación geométrica es:
A x B es el conjunto de los puntos interiores al rectángulo PQRS y los puntos que pertenecen a los segmentos PQ y QR.
Ejemplo 3:
Sean A = {x / x ÎNÙ1 £ x < 4}, B = {x / x ÎRÙ1 £ x £ 3}.
Representar A x B en el plano cartesiano.
Nota: La definición de producto cartesiano puede generalizarse al producto entre n conjuntos A1, A2,..., An. En este caso, al conjunto formado por todas las n-adas ordenadas (a1, a2,..., an) tales que aiÎAi con i = 1, 2,..., n, se llama producto cartesiano de A1, A2,..., An y se denota A1x A2x ...xAn.
Propiedades del producto cartesiano.
3.3.2.1 A Ì X Ù B Ì Y Û A x B Ì X x Y.
3.3.2.2 A x B = 0 Û A = 0 Ú B = 0.
3.3.2.3 A ¹ B Ù A x B ¹ 0 Þ A x B ¹Bx A.
3.3.2.4 A x (B · C) = (A x B)( A x C).
3.3.2.5 A x( B+ C) = (A x B) + ( A x C ).
Demostración de 3.3.2.2:
Suponga que A x B = 0. Razonando por reducción al absurdo, sí A ¹ 0 y B ¹ 0; entonces existen elementos a y b tales que a ÎA y b ÎB. Luego la pareja (a,b) Î A x B, en contradicción con la hipótesis de que A x B = 0.
Recíprocamente si A = 0, debe ser A x B = 0 pues si se llega a dar que Ax B ¹ 0, existirá (a, b) Î A x B entonces a ÎA en contradicción con la suposición de que A = 0.
Análogamente se razona en el caso de que B = 0.
Demostración de 3.3.2.4: (x, y) Î A x (B · C) Û x Î A Ù y Î B · C. Û x Î A Ù( yÎ B Ù y Î C). Û( xÎA Ù y Î B) Ù (x Î A Ù y Î C). Û (x, y) Î A x B Ù (x, y) Î A x C. Û (x, y) Î (A x B) · (A x C).
3.3.3 Número de elementos del producto cartesiano. (Técnicas de conteo). Para conjuntos finitos A y B se tiene:
½ A x B ½ = ½ A½½ B½ .
puesto que:
A x B = {(a, b): a ÎAÙ b Î B}.
y para cada una de las ½ A ½ elecciones de a en A hay ½ B½ elecciones de b en B para formar el par ordenado (a, b).
Ejemplo 4. Sea A = {1, 2, 3, 4} y B = {a, b, c}. Entonces A x B consta de 12 elementos, los cuales se pueden representar por medio de una tabla organizada en la siguiente forma:
Para el producto de más de dos conjuntos, se cumple una identidad semejante.
3.3.3.1 Reglas del producto.
- Para conjuntos finitos A1, A2,..., Ak, se tiene:
k
½ A1x A2x ... xAn½= P½ Aj½
j =1
- De manera más general, suponga que un conjunto puede considerarse como un conjunto de k-adas ordenadas de la forma (a1, a2,..., ak) con la siguiente estructura. Hay n1 elecciones posibles de a1. Dado a1, hay n2 elecciones posibles de a2. Dados a1 y a2 hay n3 elecciones posibles de a3.
- En general dados a1, a2,..., aj-1 hay nj elecciones posibles de aj. Entonces el conjunto tiene n1, n2,..., nk elementos.
Ejemplo 5: Calcular el número de maneras de seleccionar cinco cartas con reemplazo de una baraja de 52 cartas.
Solución: En este problema deben considerarse quintillas ordenadas de cartas de baraja. Con reemplazo significa que cada carta se regresa a la baraja antes de sacar la nueva carta. El conjunto de formas de seleccionar 5 cartas con reemplazo está en correspondencia uno a uno con:
D x D x D x D x D = D5.
Donde D es el conjunto de cartas con 52 elementos. Por la tanto el conjunto de cartas tiene 525 elementos.
Ejemplo 6: Calcular el número de maneras de seleccionar cinco cartas sin reemplazo de una baraja de 52 cartas.
Solución: Esta vez la regla del producto no puede aplicarse puesto que no se permiten todas las quintillas ordenadas en D5. Específicamente están prohibidas las quintillas donde se repita una carta. Sin embargo es posible razonar de la forma siguiente: La primera carta puede seleccionarse de 52 maneras. Una vez seleccionada, la segunda carta puede elegirse de 51 maneras. La tercera carta puede escogerse de 50 formas, la cuarta de 49 y la quinta de 48. De esta forma, pueden elegirse 5 cartas sin reemplazo de 52 · 51· 50 · 49 · 48 maneras diferentes.
PERMUTACIÓN
Es un arreglo de todos o parte de un conjunto de objetos considerando el orden en su ubicación; cuando en el arreglo solo entran parte de los elementos del conjunto se llama variación . Es importante resaltar que el orden es una característica importante en la permutación, cuando variamos el orden de los elementos se dice que permutamos dichos elementos.
Ejemplo :
Determinar los diferentes arreglos o permutaciones que se pueden hacer con las letras a, b y c tomadas de dos en dos
Solución :
Método 1:
- Sea el conjunto : {a, b, c} , entonces los arreglos pueden ser: ab, ba. ac, ca, bc, cb
- Número de arreglos = 6
Método 2: (principio de multiplicación)
Para ver el gráfico seleccione la opción "Descargar"
# arreglos = 3 x 2 = 6
Teorema 1: (Permutación lineal con elementos diferentes)
"El número de permutaciones de "n" objetos diferentes, tomados en grupos de k elementos (siendo k £ n) y denotado por , estará dado por:
Para ver el gráfico seleccione la opción "Descargar" del menú superior
; donde: n, k e N y 0 £ k £ n
Estas permutaciones son llamados lineales , porque los objetos son ordenados en una línea recta de referencia
Ejemplo:
En una carrera de 400metros participan 12 atletas. ¿De cuantas formas distintas podrán ser premiados los tres primeros lugares con medalla de oro , plata y bronce?
Solución :
Método 1 : Empleando el principio de multiplicación
Oro Plata Bronce
Para ver el gráfico seleccione la opción "Descargar" del menú superior
10 x 9 x 8
# maneras = 720
Método 2: (usando la fórmula de permutación lineal)
- Se busca las diferentes ternas (k = 3) que se pueden formar con los 10 atletas (n = 10)
Para ver el gráfico seleccione la opción "Descargar"
Teorema 2: (Permutación lineal con elementos repetidos)
El número de permutaciones (P) distintas de "n" elementos tomados de "n" en "n" en donde hay un primer grupo de n1 objetos iguales entre si; n2 objetos iguales entre si de un segundo tipo y así sucesivamente hasta nk objetos iguales entre si de un último tipo, entonces:
Ejemplo :
¿De cuántas maneras distintas se podrán ordenar las siguientes figuras?
Para ver el gráfico seleccione la opción "Descargar"
Solución:
- Como entran todos los elementos del conjunto y estos se repiten, se trata de una permutación con repetición, donde n1 = 3 (tres círculos), n2 = 2 (dos cuadrados) , n3 = 1 (un triángulo), n4 = 1( un rombo), luego:
=
Combinaciones
Una combinación es un arreglo donde el orden NO es importante. La notación para las combinaciones es C(n,r) que es la cantidad de combinaciones de “n” elementos seleccionados, “r” a la vez. Es igual a la cantidad de permutaciones de “n” elementos tomados “r” a la vez dividido por “r” factorial. Esto sería P(n,r)/r! en notación matemática.
Ejemplo: Si se seleccionan cinco cartas de un grupo de nueve, ¿cuantas combinaciones de cinco cartas habría?
La cantidad de combinaciones posibles sería: P(9,5)/5! = (9*8*7*6*5)/(5*4*3*2*1) = 126 combinaciones posibles.
El binomio de newton sirve para resolver fácilmente un binomio elevado a cualquier exponente
ytambien nos sirve cuando nos piden unicamente hallar el coeficiente de cualquiera de sus términos.
La fórmula del binomio de newton es:
donde (nk) representa el número combinatorio "n sobre k"
ahora veremos como se encuentra directamente el coeficiente de uno de los terminos de un binomio
tenemos el binomio (2+4x)7 y nos piden que hallemos
el coeficiente de cuando x4.
aplicamos la formula de newton y reemplazamos las variables para no tener que solucionar todo el binomio:
(74)27-4*4x4= (7!/(7-4)!4!) * 8*(256x)4=35*8*256x4 = 71.680x4
El triángulo de Pascal o Tartaglia
|
1 |
El triángulo de Pascal es un triángulo de números enteros, infinito y simétrico Se empieza con un 1 en la primera fila, y en las filas siguientes se van colocando números de forma que cada uno de ellos sea la suma de los dos números que tiene encima. Se supone que los lugares fuera del triángulo contienen ceros, de forma que los bordes del triángulo están formados por unos. Aquí sólo se ve una parte; el triángulo continúa por debajo y es infinito. |
Triángulo de Pascal y números Combinatorios
Los números del triángulo de Pascal coinciden con los números combinatorios.
El número combinatorio Cmn (n sobre m) se encuentra en el triángulo en la fila n+1, en el lugar m+1. El número combinatorio Cmn(n sobre m) que representa el número de grupos de m elementos que pueden hacerse de entre un conjunto de n (por ejemplo, (4 sobre 2) nos da el número de parejas distintas que podrían hacerse en un grupo de cuatro personas), se encuentra en el triángulo en la fila n+1, en el lugar m+1.
|
1 |
Podemos saber que el número de parejas posibles que decíamos antes es 6 si miramos el tercer número de la quinta fila.
Esto hace que el triángulo sea útil como representación de estos números, y proporciona una buena forma de intuir sus propiedades.
Por el contrario, a la fórmula de los números combinatorios se le puede dar el carácter de fórmula general del triángulo para saber, sin necesidad de construir todas las filas anteriores, cuál es el número que ocupa un lugar determinado,:
Triángulo de Pascal y Binomio de Newton
La fórmula general del llamado Binomio de Newton (a + b)n está formada por unos coeficientes que coinciden con la línea número n+1 del triángulo de Pascal (la que empieza por 1 y n).
La fórmula es:
Una forma de evitar tener que calcular uno a uno todos los coeficientes es utilizar el Triángulo de Pascal, ya que los coeficientes de la potencia n aparecen en la fila n+1 de dicho triángulo.
Un ejemplo: aplicando la fórmula y la definición de número combinatorio tendríamos:
(a + b)3 = 1·a3 + 3·a2b + 3·ab2 + 1·b3.
Pero hubiese sido más rápido ir a la fila 4 (3 + 1 ) del triángulo y ver que los números que aparecen son, precisamente, los coeficientes 1, 3, 3 y 1.
Las propiedades del triángulo de Pascal:
Lo difícil es mirar este triángulo durante un par de minutos y no encontrarle alguna regularidad oculta.
- Números poligonales
¿Podríais decir qué sucesiones son las que forman las diagonales del triángulo? Las primeras de la izquierda y la derecha no son más que unos. Las segunda forman la sucesión de los números naturales... ¿Y la tercera? ¿Y la cuarta?
En la diagonal tercera marcada aparecen
Los números triangulares
, pero además en la inmediata inferior aparecen los números tetragonales, es decir, los que forman las pirámides triangulares, cuyos pisos son a su vez números triangulares.
Los números cuadrados
se encuentran en el triángulo de Pascal recurriendo a la misma diagonal que en el caso anterior: construimos cada uno sumando dos números triangulares consecutivos. Eso nos proporciona: 1, 4, 9, 16, 25, ...
De hecho, por este método recurrente podemos construir todos los números poligonales, y en ese sentido están presentes en el triángulo de Pascal.
- Números primos
Si el primer elemento de una fila es un número primo, todos los números de esa fila serán divisibles por él (menos el 1, claro). Así, en la fila 7: (1 7 21 35 35 21 7 1), los números 7,21 y 35 son divisibles por 7. - La suma de los elementos
La suma de los elementos de cualquier fila es el resultado de elevar 2 al número que define a esa fila. Así:
20 = 1
21 = 1+1 = 2
22 = 1+2+1 = 4
23 = 1+3+3+1 = 8
24 = 1+4+6+4+1 = 16
- Sucesión de Fibonacci
La serie de Fibonacci puede ser encontrada también en el triángulo de Pascal. Dividiendo al mismo según las líneas que mostramos en el diagrama, los números atrapados entre ellas suman cada uno de los elementos de esta sucesión.
Recordemos que esta sucesión (que, por cierto, se construye de manera similar al triángulo de Pascal), es:
1,1,2,3,5,8,13,21,...
(an+1 = an + an-1cona0 = 1, a1= 1)
- Potencias de 11
Podemos interpretar cada fila como un único número. Si la fila está formada por números de un solo dígito, basta unirlos. En el caso de la fila 2 tenemos:
1-2-1............................ 121 = 112
Cuando los números de la fila constan de más de un dígito, se "reparten" para formar el número final como se observa en el ejemplo siguiente para la fila 5:
1-5-10-10-5-1........... 1-(5+1)-(0+1)-0-5-1=1-6-1-0-5-1 ............ 161051 = 115
- El "stick de hockeefefLa suma de todos los números que la integran se encuentran justo debajo del último de ellos, en la diagonal contraria.
- El triángulo de Sierpinski
El curioso dibujo que se forma al pintar de negro los números impares del triángulo y de blanco los pares, recuerda al triángulo de Sierpinski , uun famoso conjunto geométrico (un fractal determinístico que se pefefuede construir a partir de cualquier triángulo) El applet de Java de esta página muestra inicialmente las primeras filas del triángulo de Pascal. Se puede aumentar el número de filas y se puede elegir entre colorear los números pares o no colorearlos. Cuando se elige colorear se observa perfectamente que al ir aumentando el número de filas el objeto resultante se va aproximando al triángulo de Sierpinski. - Cambiando extremos
|
2 |
¿Qué pasaría si cambiamos los unos de uno de los lados externos del triángulo de Pascal por doses ?. ¿Qué relaciones numéricas se pueden encontrar? ¿Qué sucedería si en lugar de doses colocamos treses o cuatros? |