COMBINATORIA
Carácter: Optativa. Cuatrimestral.
Nº de créditos totales: 7,5. Distribución: 2,5
teóricos, 5 prácticos.
OBJETIVOS
El objetivo principal es iniciar al estudiante en los elementos
básicos de la combinatoria. El énfasis se pone en el estudio de
problemas concretos, y en el desarrollo de métodos de razonamiento y
resolución, que incluyen, además de los elementales, otros basados
en recurrencias y funciones generatrices. En segundo lugar, se persigue familiarizar
al estudiante con identidades combinatorias, y números (Fibonacci, Stirling,
etc.) que surgen frecuentemente en todas las áreas de las matemáticas
y en otras disciplinas.
PROGRAMA TEÓRICO
Lección 0. ¿Qué es la Combinatoria?
- Los problemas combinatorios: formas, tipos, relaciones.
- Métodos, resultados, ideas, algoritmos.
- La Combinatoria dentro de las Matemáticas.
Lección 1. Enumeraciones.
- Listados y enumeraciones.
- Soluciones enteras no negativas de una ecuación.
- Múltiplos de un entero entre dos enteros dados.
- Las funciones suelo y techo: propiedades.
- Puntos de coordenadas enteras en un círculo.
- El principio del palomar.
Lección 2. Traducciones.
- Problemas equivalentes: Traducciones.
- Elementos: sucesiones, subconjuntos, aplicaciones, etc.
- Ejemplos de traducciones.
Lección 3. El principio de inclusión-exclusión.
- Las descomposiciones y sus aplicaciones.
- El principio de inclusión-exclusión.
- Aplicaciones.
- Otras expresiones.
Lección 4. Ramificaciones.
- Árboles: El principio de la multiplicación.
- Variaciones ordinarias y con repetición.
- Permutaciones ordinarias y con repetición.
- Potencias factoriales ascendentes y descendentes.
Lección 5. Combinaciones.
- Combinaciones ordinarias.
- Números combinatorios: propiedades.
- Triángulo de Pascal.
- Combinaciones con repetición.
- Ejemplos diversos: muestreo y colocaciones.
Lección 6. Identidades combinatorias.
- Identidades básicas.
- Pruebas combinatorias.
- La fórmula de Vandermonde y otras identidades.
Lección 7. La fórmula del binomio.
- La fórmula del binomio. Varias demostraciones.
- Fórmula del binomio e identidades combinatorias.
Lección 8. Coeficientes multinomiales.
- Coeficientes multinomiales.
- Significados combinatorios.
- La fórmula del multinomio.
- Algunas aplicaciones.
Lección 9. La fórmula del binomio generalizada.
- Coeficientes binomiales: Propiedades básicas.
- La fórmula del binomio generalizada.
- Casos especiales.
- Aplicaciones.
Lección 10. Funciones generatrices.
- Series de potencias.
- Función generatriz de una sucesión numérica.
- Ejemplos.
- Problemas directos e inversos.
- Operaciones con funciones generatrices.
- Noticia sobre las series formales.
Lección 11. Funciones generatrices y problemas
combinatorios.
- Problemas combinatorios uniparamétricos.
- Número de soluciones de una ecuación.
- Aplicaciones.
Lección 12. Recurrencias.
- Ejemplos de sucesiones recurrentes.
- Problemas combinatorios y recurrencias.
- Resolución de recurrencias.
- Recurrencias y funciones generatrices.
- El caso de recurrencias lineales.
- Otros métodos.
Lección 13. Números de Fibonacci.
- La sucesión de Fibonacci.
- Problemas combinatorios relacionados.
- La función generatriz.
- Expresión explícita de Fn.
- Otras propiedades: sumas, productos, divisibilidad, etc.
Lección 14. Números de Catalan.
- La sucesión de Catalan.
- Números de Catalan y trayectorias en el plano.
- Relación de recurrencia.
- Función generatriz.
- Triangulaciones de polígonos convexos.
- Otros problemas combinatorios relacionados.
Lección 15. Particiones de números naturales.
- Particiones ordenadas.
- Particiones no ordenadas: Tipos especiales.
- Ejemplos y una conjetura.
- Funciones generatrices. Demostración de la conjetura.
- Diagramas de Ferrer.
Lección 16. Particiones de conjuntos.
- Los números de Bell.
- Una relación de recurrencia.
Lección 17. Números de Stirling de primera
especie.
- Definición y ejemplos.
- Relaciones básicas.
- Triángulo de Pascal.
Lección 18. Números de Stirling de segunda
especie.
- Definición y ejemplos.
- Relación con los números de Bell y los de primera
especie.
- Propiedades básicas.
- Triángulo de Pascal.
- Significados combinatorios.
- Otras relaciones.
PROGRAMA PRÁCTICO
Resolución de ejercicios y problemas que se propondrán
al principio de cada curso.
BIBLIOGRAFÍA BÁSICA
D.I.A. Cohen, Basic Techniques of Combinatorial Theory,
Wiley, New York, 1978.
N. Ya. Vilenkin, Combinatorics, Academic Press, New
York, 1971.
R.L. Graham, D.E. Knuth, O. Patashnik, Concrete Mathematics,
Addison Wesley, Reading, Mass., 1994.
H.S. Wilf. Generatingfunctionology. Academic Press,
Boston, 1990.
CRITERIOS DE EVALUACIÓN
Examen escrito de resolución de problemas. Eventualmente
se podrá proponer la realización de trabajos.