martes, 2 de junio de 2015

Tema III (Factoriales, Teoría Combinatoria)




FACTORIALES 





El factorial de un entero positivo n, el factorial de n o n factorial se define en principio como el producto de todos los números enteros positivos desde 1 (es decir, los números naturales) hasta n. Por ejemplo,
5! = 1 \times 2 \times 3 \times 4 \times 5 = 120. \
La operación de factorial aparece en muchas áreas de las matemáticas, particularmente en combinatoria y análisis matemático. De manera fundamental, el factorial de n representa el número de formas distintas de ordenar n objetos distintos (elementos sin repetición). Este hecho ha sido conocido desde hace varios siglos, en el s. XII por los estudiosos hindúes. La notación actual n! fue usada por primera vez por Christian Kramp en 1803.
La definición de la función factorial también se puede extender a números no naturales manteniendo sus propiedades fundamentales, pero se requieren matemáticas avanzadas, particularmente del análisis matemático.

Definición


La función factorial es formalmente definida mediante el producto
n! = 1 \times 2 \times 3 \times 4 \times ... \times (n-1) \times n .
La multiplicación anterior se puede simbolizar también utilizando el operador productorio:
n! = \prod_{k=1}^n k .
También es posible definirlo mediante la relación de recurrencia
n! = \begin{cases} 1 & \text{si, } n = 0 \\ (n-1)!\times n & \text{si, } n > 0 \end{cases}
En esta segunda definición el dominio de la función es el conjunto de los enteros no negativos ℤ≥0 y el codominio es el conjunto de los enteros positivos ℤ+.1 En este caso hay una sucesión recurrente, el cálculo sucesivo de sus elementos se llama proceso recurrente y la igualdad n! = (n - 1)!n se nombra ecuación recurrente.
Todas las definiciones anteriores incorporan la premisa de que
0! = 1
Cero factorial
La definición indicada de factorial es válida para números positivos. Es posible extender la definición a otros contextos introduciendo conceptos más sofisticados, en especial es posible definirla para cualquier número real excepto para los números enteros negativos y para cualquier número complejo exceptuando de nuevo los números enteros negativos.
Una extensión común, sin embargo, es la definición de factorial de cero. De acuerdo con la convención matemática de producto vacío, el valor de 0! debe definirse como:
0! = 1
Es posible, sin embargo, dar un argumento intuitivo para justificar la elección, como sigue:
  • Para cada número entero positivo n mayor que 1, es posible determinar el valor del factorial anterior mediante el uso de la siguiente identidad:
(n-1)! = \frac{n!}{n}
válida para todo número mayor o igual que 1.
Así, si se conoce que 5! es 120, entonces 4! es 24 porque
\frac{5!}{5} = \frac{120}{5} = 24
y por tanto 3! debe ser necesariamente 6 puesto que
\frac{4!}{4} = \frac{24}{4} = 6
El mismo proceso justifica el valor de 2! = 2 y 1!=1 ya que:
2! = \frac{3!}{3} = \frac{6}{3} = 2 ,\qquad 1! = \frac{2!}{2} = \frac{2}{2} = 1
Si aplicamos la misma regla para el caso extremo en que n!=1 tendríamos que 0! corresponde a:
0! = \frac{1!}{1} = \frac{1}{1} = 1
Aunque el argumento puede resultar convincente, es importante tener en cuenta que no es más que un argumento informal y que la razón real por la cual se toma la convención de 0! = 1 es por ser un caso especial de la convención de producto vacío usada en muchas otras ramas de las matemáticas.





COMBINATORIA 






La combinatoria es una rama de la matemática perteneciente al área de matemáticas discretas que estudia la enumeración, construcción y existencia de propiedades de configuraciones que satisfacen ciertas condiciones establecidas.

Áreas

No existe una clasificación tajante de lo que constituye una subárea, sino que todas comparten cierto grado de traslape entre sí, al igual que con otras ramas de la matemática discreta. Diferentes autores proponen varias divisiones de la combinatoria por lo que cualquier listado es meramente indicativo. Por ejemplo, algunos autores consideran lateoría de grafos como una subárea de la combinatoria, mientras que otros la consideran un área independiente.
Entre las subdivisiones más comunes se encuentran las siguientes.

Combinatoria Enumerativa 

La combinatoria enumerativa o enumeración estudia los métodos para contar (enumerar) las distintas configuraciones de los elementos de un conjunto que cumplan ciertos criterios especificados.
Esta fue una de las primeras áreas de la combinatoria en ser desarrollada, y como otras áreas más recientes se estudian sólo en cursos especializados, es común que se haga referencia a esta subárea cuando se menciona combinatoria en entornos escolares.
Ejemplo.
Considérese el conjunto S=\{A, E, I, O, U\}. Podemos imaginar que estos elementos corresponden a tarjetas dentro de un sombrero.
  • Un primer problema podría consistir en hallar el número de formas diferentes en que podemos sacar las tarjetas una después de otra (es decir, el número de permutaciones del conjunto).
Por ejemplo, dos formas distintas podrían ser: EIAOU o OUAIE.
  • Después, se puede preguntar por el número de formas en que se puede sacar sólo 3 tarjetas del sombrero (es decir, el número de 3-permutaciones del conjunto).
En este caso, ejemplos pueden ser IOU, AEI o EAI.
  • También se puede preguntar sobre cuáles son los posibles grupos de 3 tarjetas que se pueden extraer, sin dar consideración al orden en que salen (en otras palabras, el valor de un coeficiente binomial).
Aquí, consideraríamos AOU y UAO como un mismo resultado.
  • Otro problema consiste en hallar el número de formas en que pueden salir 5 tarjetas, una tras otra, pero en cada momento se regresa la tarjeta escogida al sombrero.
En este problema los resultados posibles podrían ser EIOUO, IAOEU o IEAEE.
La combinatoria enumerativa estudia las técnicas y métodos que permiten resolver problemas anteriores, así como otros más complejos, cuando el número de elementos del conjunto es arbitrario. De esta forma, en el primer ejemplo la generalización correspondiente es determinar el número de formas en que se pueden ordenar todos los elementos de un conjunto con n elementos, siendo la respuesta el factorial de n.

Combinatoria Extremal

El enfoque aquí es determinar qué tan grande o pequeña debe ser una colección de objetos para que satisfaga una condición previamente establecida;
Ejemplo.
Considérese un conjunto S. con n elementos. A continuación se empieza a hacer un listado de subconjuntos de tal manera que cualquier pareja de subconjuntos del listado tenga algún elemento en común.
Para clarificar, sea S=\{A, B, C, D\} y un posible listado de subconjuntos podría ser
\{B, C\}, \{A, B\}, \{A, B, C, D\}, \{B, D\}, \ldots
Conforme aumenta el listado (y dado que hay una cantidad finita de opciones), el proceso se hace cada vez más complicado. Por ejemplo, no podríamos añadir el conjunto {A, D} al listado pues aunque tiene elementos en común con los últimos 3 subconjuntos del listado, no comparte ningún elemento con el primero.
La pregunta sobre qué tan grande puede hacerse el listado de forma que cualquier pareja de subconjuntos tenga un elemento en común es un ejemplo de problema de combinatoria extremal (o combinatoria extrema). La respuesta a este problema es que si el conjunto original tiene n elementos, entonces el listado puede tener como máximo 2^{n-1} subconjuntos.
Publicado por en

No hay comentarios:

Publicar un comentario

Suscribirse a: Enviar comentarios (Atom)