Combinatoria

La combinatoria estudia todo lo vinculado con el proceso de combinar, que es unir dos o más objetos para formar un nuevo objeto compuesto de aquellos. Se preocupa por conocer el número de esos nuevos objetos, que puede ser interpretado como el número de posibilidades de ocurrencia de un determinado acontecimiento, experiencia o evento, sin necesariamente describir todas esas posibilidades. Por ello, se dice que el análisis combinatorio es la matemática de las opciones o el arte de contar sin ver.

Combinatoria Simple

Factorial

El factorial de un número natural m, denotado como m!, es el producto de los primeros m números naturales. Se define como:

m! = 1 * 2 * 3 * … * (m-2) * (m-1) * m, si m >= 1

Permutaciones

Las permutaciones de m elementos de un conjunto son todas y cada una de las ordenaciones diferentes de esos m elementos.

Pm = m * (m-1) * (m-2) * … * 3 * 2 * 1 = m!

Permutaciones Circulares

Las permutaciones circulares de m elementos de un conjunto son todas y cada una de las ordenaciones diferentes de esos m elementos alrededor de un círculo.

Pm,c = (m-1)! = m! / m

Arreglos

Los arreglos de m elementos de un conjunto tomados de a n, siendo n <= m, son todos y cada uno de los grupos diferentes que se pueden formar de modo que:

  1. En cada grupo entran n elementos distintos de los m dados.
  2. Dos grupos se consideran distintos si y solo si difieren en algún elemento, o si teniendo los mismos elementos, difieren en el orden de los mismos.

Amn = m * (m-1) * (m-2) * … * [m-(n-1)]

Despejando:

Amn = m! / (m–n)!

Ejemplo: Arreglo de 9 objetos tomados de 5: A95 = 9! / (9-5)! = 15120

Combinaciones

Las combinaciones de m elementos de un conjunto tomados de a n, siendo n <= m, son todos y cada uno de los grupos diferentes que se pueden formar de modo que:

  1. En cada grupo entran n elementos distintos de los m dados.
  2. Dos grupos se consideran distintos si y solo si difieren en alguno de sus elementos.

Cmn = m! / (n! * (m–n)!)

Ejemplo: Conjunto (a, b, c, d) tomados de a 3: abc, abd, acd y bcd. C43 = 4! / (3! * (4-3)!) = 4

Combinatoria con Elementos Repetidos

Permutaciones

Las permutaciones de m elementos entre los cuales hay α elementos idénticos entre sí, otros β elementos idénticos entre sí, y así siguiendo hasta que finalmente hay λ elementos idénticos entre sí, siendo α + β + … + λ = m, son todos y cada uno de los grupos diferentes que se pueden formar de modo que:

  1. En cada grupo entran los m elementos dados.
  2. Dos grupos se consideran distintos si y solo si difieren en el orden de sus elementos.

Pmα,β,…,λ = m! / (α! * β! * … * λ!)

Ejemplo: Al arrojar 10 veces un dado, el 1 y el 4 salieron 3 veces, el 3 dos veces, el 5 y el 6 una vez y no salió el 2. El primer número salió también último. ¿De cuántas maneras puede haber ocurrido la secuencia? 2 * P83,2 + P83,3 = 6720 + 1120 = 7840

Combinaciones

Las combinaciones de m elementos distintos, que se pueden repetir hasta n veces, son todos y cada uno de los grupos diferentes que se pueden formar de modo que:

  1. En cada grupo entran n elementos, no necesariamente distintos de los m dados.
  2. Dos grupos se consideran distintos si y solo si difieren en alguno de sus elementos.

Cmn,r = Cm+n-1n

Ejemplo: Conjunto (a, b, c) tomados de 2: C32,r = C42 = (4 * 3) / 2 = 6

Arreglos

Los arreglos de m elementos distintos, que se pueden repetir hasta n veces, son todos y cada uno de los grupos diferentes que se pueden formar de modo que:

  1. En cada grupo entran n elementos, no necesariamente distintos de los m dados.
  2. Dos grupos se consideran distintos si y solo si difieren en algún elemento, o si teniendo los mismos elementos, difieren en el orden de los mismos.

Amn,r = mn

Ejemplo: Conjunto (a, b, c) tomados de 2: A32,r = 32 = 9

La combinatoria no tiene un método sistemático de resolución y no tiene muchos resultados generales que sirvan para resolver situaciones distintas. A pesar de ello, hay estrategias que se pueden utilizar al momento de enfrentar un problema:

  • Si se intuye que la cantidad de grupos es reducida, formarlos, contarlos y verificarlos.
  • Si se sabe resolver un problema usando PGM o PGS, hacerlo.
  • Elegir una buena notación y observar si los elementos pueden repetirse o no.
  • Observar si se toman todos los elementos o algunos, y si el orden tiene o no importancia.
  • Encontrar similitudes con otros problemas resueltos. Imaginar el problema resuelto mediante un árbol parcial. Dibujar, diagramar, etc.
  • Resolver usando el complemento, cuando hay condiciones especiales.

Nociones de Álgebra Lineal

Espacios Vectoriales

Para entender los espacios vectoriales, debemos empezar por los vectores:

  • El punto de aplicación de un vector es el punto origen de la flecha.
  • El módulo de un vector es la longitud de la flecha, en una unidad determinada.
  • La dirección de un vector está dada por la recta que lo contiene.
  • En cada dirección hay dos sentidos posibles.

Ejemplos:

  • El módulo de u es 4: |u| = 4, el de |v| = 2 y el |w| = 3.
  • u y w tienen la misma dirección (paralelas) pero sentidos contrarios. v no tiene la misma dirección.

Suma de vectores:

  • u y v colineales e igual sentido: |u| = 2 y |v| = 5 => 2 + 5 = 7.
  • u y v colineales y distintos sentidos: |u| = 3 y |v| = 2 => 3 – 2 = 1.
  • u y v no alineados: se aplica la regla del paralelogramo.

Para multiplicar un vector por un escalar, se repite el vector tantas veces como lo indica el escalar.

Un espacio vectorial sobre un cuerpo K consiste en un conjunto V (vectores) provisto de dos operaciones:

  • Una operación interna: + : V x V -> V, llamada suma de vectores.
  • Una operación externa: . : K x V -> V, que es el producto de elementos de K por los de V y que da por resultado un vector.

Con las siguientes condiciones:

  1. (V, +) es grupo abeliano.
  2. ∀ x ∈ V, ∀ a, b ∈ K: a . (b . x) = (a . b) . x
  3. ∀ x ∈ V, ∀ a, b ∈ K: (a + b) . x = a . x + b . x
  4. ∀ x, y ∈ V, ∀ a ∈ K: a . (x + y) = a . x + a . y
  5. ∀ x ∈ V: 1 . x = x (1 es el neutro del producto en K)

Abreviatura: (V, K, +, .) tiene estructura de espacio vectorial. A los elementos de K se los llama escalares.

Dado que (V, +) es grupo abeliano, se verifica:

  • Elemento neutro: ∃ 0 ∈ V / ∀ x ∈ V: x + 0 = 0 + x = x, vector nulo de V.
  • Elemento inverso: ∀ x ∈ V, ∃ x’ ∈ V / x + x’ = x’ + x = 0, vector opuesto de x (-x).

El conjunto de vectores flecha con las operaciones definidas es un espacio vectorial.

Ejemplos de Espacios Vectoriales

El Espacio Vectorial de n-uplas de Números Reales

Consideremos el producto cartesiano: R x R = R2 = {(x, y) / x, y ∈ R}

Es el conjunto de todos los pares ordenados de primera y segunda componentes reales, llamado el espacio de dos dimensiones. Se lo puede representar con gráficos cartesianos.

Si consideramos dos elementos de este conjunto, u y v, cada uno de ellos es un par ordenado; llamamos x1 e y1 a las componentes del primer par y x2, y2 a las del segundo. Tenemos:

u, v ∈ R2 => u = (x1, y1) ∧ v = (x2, y2)

Del mismo modo, se puede definir R3 = R x R x R = {(x, y, z) / x, y, z ∈ R}

Es el conjunto de todas las ternas ordenadas de primera, segunda y tercera componente real, llamado el espacio de tres dimensiones. Cada elemento de R3 es una terna ordenada de números reales:

u, v ∈ R3 => u = (x1, y1, z1) ∧ v = (x2, y2, z2)

Análogamente, esta idea puede extenderse y definir ∀ n ∈ N:

Rn = R x R x … x R = {(x1, x2, …, xn) / x1, x2, …, xn ∈ R}

Que es el conjunto de todas las n-uplas de números reales, llamado el espacio de n dimensiones.

Cada elemento de Rn es una n-upla de números reales. Si n = 2 ó n = 3, tenemos los espacios de 2 y de 3 dimensiones ya vistos; si n = 4, los elementos son cuaternas ordenadas; si n = 5, tenemos 5-uplas ordenadas y estamos en el espacio de 5 dimensiones; etc.

Por ejemplo, si tenemos dos elementos u, v de R4, cada uno de ellos es una cuaterna:

u, v ∈ R4 => u = (x1, y1, z1, v1) ∧ v = (x2, y2, z2, v2)

Estructura de (Rn, R, +, .)

En Rn (∀ n ∈ N), definimos las dos operaciones siguientes:

  1. Suma: Dados u = (x1, x2, …, xn), v = (y1, y2, …, yn) ∈ Rn, se define:

u + v = (x1, x2, …, xn) + (y1, y2, …, yn) = (x1 + y1, x2 + y2, …, xn + yn)

  1. Producto por un escalar: ∀ v = (x1, x2, …, xn) ∈ Rn, ∀ a ∈ R, se define:

a . v = a . (x1, x2, …, xn) = (a . x1, a . x2, …, a . xn)

Demostración de que el conjunto Rn, ∀ n ∈ N: (Rn, R, +, .) es un espacio vectorial.

En todo lo que sigue, dados x, y, z ∈ Rn, llamaremos:

x = (x1, x2, …, xn); y = (y1, y2, …, yn); z = (z1, z2, …, zn)

(Rn, +, .) es grupo abeliano

a) Asociatividad: ∀ x, y, z ∈ Rn: (x + y) + z = x + (y + z)

Dados x, y, z ∈ Rn:

(x + y) + z = [(x1, x2, …, xn) + (y1, y2, …, yn)] + (z1, z2, …, zn) =

(x1 + y1, x2 + y2, …, xn + yn) + (z1, z2, …, zn) =

[(x1 + y1) + z1, (x2 + y2) + z2, …, (xn + yn) + zn] =

[x1 + (y1 + z1), x2 + (y2 + z2), …, xn + (yn + zn)] =

(x1, x2, …, xn) + [(y1 + z1, y2 + z2, …, yn + zn)] =

(x1, x2, …, xn) + [(y1, y2, …, yn) + (z1, z2, …, zn)] = x + (y + z), como se quería demostrar.

b) Conmutatividad: ∀ x, y ∈ Rn: x + y = y + x

c) Existencia de elemento neutro: ∃ 0 ∈ Rn / ∀ x ∈ Rn: x + 0 = 0 + x = x

x + 0 = (x1, x2, …, xn) + (0, 0, …, 0) = (x1 + 0, x2 + 0, …, xn + 0) = (x1, x2, …, xn) = x

d) Existencia de elemento inverso: ∀ x ∈ Rn, ∃ x’ ∈ Rn: x + x’ = x’ + x = 0

Por lo tanto, (Rn, +) es grupo abeliano.

2) ∀ x ∈ Rn, ∀ a, b ∈ R: a . (b . x) = (a . b) . x

Dados a, b ∈ R y x ∈ Rn:

a . (b . x) = a . [b . (x1, x2, …, xn)] = a . (b . x1, b . x2, …, b . xn) =

(a . (b . x1), a . (b . x2), …, a . (b . xn)) = ((a . b) . x1, (a . b) . x2, …, (a . b) . xn) =

(a . b) . (x1, x2, …, xn) = (a . b) . x

3) ∀ x ∈ Rn, ∀ a, b ∈ R: (a + b) . x = a . x + b . x

(a + b) . x = (a + b) . (x1, x2, …, xn) = a . (x1, x2, …, xn) + b . (x1, x2, …, xn) = a . x + b . x

4) ∀ x, y ∈ Rn, ∀ a ∈ R: a . (x + y) = a . x + a . y

5) ∀ x ∈ Rn: 1 . x = x

1 . x = 1 . (x1, x2, …, xn) = (1 . x1, 1 . x2, …, 1 . xn) = (x1, x2, …, xn) = x

Por lo tanto, (Rn, R, +, .) es un espacio vectorial.

El Espacio Vectorial de Matrices de Clase m x n

Dado un cuerpo K, sean m, n ∈ N. Se llama matriz de clase m x n con coeficientes en K a toda disposición ordenada de m * n elementos de K en m filas y n columnas. Al conjunto de todas las matrices de clase m x n con elementos en el cuerpo K lo anotaremos: Km x n. Así, R2 x 3 es un ejemplo.

Igualdad de matrices: Dadas dos matrices de la misma clase, son iguales si los elementos que ocupan la misma posición en cada matriz son iguales entre sí. Dadas A = [aij]m x n y B = [bij]m x n, se define:

A = B <=> aij = bij, ∀ i = 1, …, m; ∀ j = 1, …, n

Suma de matrices:

  • Dos matrices son conformables para la suma si y solo si son de la misma clase.
  • La suma de dos matrices de la misma clase es otra matriz de la misma clase que las dadas; cada coeficiente de esta matriz se obtiene sumando los coeficientes de las matrices dadas que están en la misma posición.

Es decir: A = [aij]m x n + B = [bij]m x n => C = [cij]m x n / cij = aij + bij, ∀ i, j

Subespacios

:Sea V un espacio vectorial sobre un cuerpo K y sea S c V/S ≠ Ɵ. Se dice q S es un subesp de V y solo si S es un esp vect para las operaciones de V restringidas a S. No todo subconj S  no vacio de V es un subesp; una 1° condición para q lo sea, es que el vector nulo del esp vect pertenezca a S, porque de lo contrario no se cumpliría que (S,+) sea un grupo abeliano.   Dados un esp vect V y ScV, S es un subesp de V si y sólo si:   a) S ≠ Ɵ  b) V x, y ε S: (x+y) ε S  c) Vx e S, V a ε K: (a . x) ε S            Comb lineales: Sea V un espa vect sobre un cuerpo K   y consideramos los e-: X1, X2,…, Xn ε V;    a1, a2,…, an ε K.                                                           Def: Se llama comb lineal  de  los vectores x1, x2,…, xn con coefi a1, a2,…, an al vector   x = a1x1 + a2x2 +…+ anxn. En ese caso se dice tambien q x es comb lineal de x1: x2, …. xn.      Ejem: Comb lineal de los vectores    v =(1, 0, 1); u=(2, -4, 2) con chef:  3, 1/2es el vector: x = 3v + 1/2  u=3(1,0, 1} + 1/2(2, -4, 2)= (3, 0,3)+(1, -2, 1)=(4, -2, 4)                         Dep e Indep lineal:Sea un v un esp vect sobre un cuerpo k. Los vectores x1, x2,…, xn  ε v son linealmente depend si y solo si existen escalares a1, a2,…, an ε k, no todos nulos, tales q: a1x1 + a2x2 +…+ anxn = 0   Sea v un esp vect sobre un cuerpo k. Se dice q los vectores x1, x2,…, xn  son linealmente indepen si y solo si no son linealmente depend. Esto es equivalente a decir q la unica forma de expresar el vector nulo como comb lineal de los xi es la comb nula trivial: x1, x2,…, xn  son linealmente independ ->a1x1 + …+ anxn = 0 -> a1 =…= an = 0     Ejem: R2, los vectores: v1 = (1, -1) y v2 = (2, -2) son lineal// dep   porque:      2. v1 + (-1) v2 = 2 (1, -1) + (-1) (2, -2) = (2, -2) + (-2, 2) = (0. 0)  Es decir: existe una comb lineal nula de v1 y v2con escalares no nulos                                                                                     PROPIEDADES:   Dados x1x2 x3…, xn ε V se verifica:    1) Si 2 de los vectores son =, el conj de vectores es lineal// dependiente.         2) Si algunos de los vectores es el vector nulo, los vectores son LD.              3) Si algunos d los vectores es múltiplo d otro, entonces los vectores son LD. 4)Un conj de vectores es LD, si y solo si, uno de ello es comb lineal de los restantes.                      Ejem: 1) A={(0,0), (1,3), (2,4)}  es LD,  según la propiedad 2, pues (0,0) ε A.                                                             2) B={(1,2), (2,4)} es LD, según la propiedad 3, porq: (2,4) = 2. (1,2), es decir: (2,4) es múltiplo de (1,2)                                                    Sist de Generadores:  Sea {x1, x2,…, xn } c V. Se dice q {x1, x2,…, xn }es un conj de generadores de V o que genera V si y solo si todo e- de V se puede escribir como una comb lineal de x1, x2,…, xn .                                         { x1:x2, … xn} gnra V Vx ε ->V :  Э a1, a2,…, an  εK tales q: x = a1x1+ a2x2+…+ anxn Ej: Sea S={(x,y) ε R2 / x = y} tomando cualqr vctor vε S. VxεS: x = a(1,1)con a R.           (2,2) = 2.(1,1)       (-4, -4) = -4 (1,1) es decir, todo e- de S puede escribirse como una comb lineal de (1, 1); luego {(1,1)} genera S.                                        Base de un esp vect: Sea V un esp vect sobre K y sea { x1:x2, … xn} un conj incluido en V q verifica: 1) {x1, x2,…, xn } es LI     2) {x1, x2,…, xn } genera V Entonces, {x1, x2,…, xn }es una base de V.                                                  Rango de una matriz: se llama al máximo n° de filas o de columnas LI de A. r(A)  Ejem: a=1 -1 3; 2 -2 6. Clara// (2, -2, 6)=2(1, -1, 3). Las 2 filas de A son LD. Por lo tanto r(A)=1