matematicas discretas

25

Parte I

Enumeración

En esta parte se presentan diversas técnicas para contar los elementos de un conjunto. Paralelamente a la descripción de técnicas usuales de enumeración, se presentan también problemas
clásicos de combinatoria, a los cuales se aplican los resultados que se van obteniendo.
Las técnicas más sencillas basadas en la enumeración de permutaciones y combinaciones
setratan en el primero de los tres capítulos que componen esta primera parte, y se aplican
estas técnicas a problemas de enumeración de funciones entre conjuntos, palabras de alfabetos,
distribuciones, particiones de enteros y la fórmula del binomio. En el segundo capítulo se
analizan algunos principios básicos de enumeración, especialmente el principio de inclusiónexclusión, y se consideran losproblemas de desarreglos, función de Euler, números de Catalan
y particiones de enteros. Aunque no son estrictamente principios de enumeración, se incluyen
también en este capítulo el principio del palomar y el teorema de Ramsey. El último capítulo de
esta parte está dedicado a las ecuaciones de recurrencia y las funciones generadoras. Aunque
hemos intentado mantener un nivel asequible, estosson los temas que requieren más nivel
matemático, y resultarán más fáciles al lector que tenga cierta familiaridad con las series de
potencias. Esta primera parte se cierra con los números de Stirling y de Bell. Algunos temas
de enumeración que requieren conocimientos adicionales se ven en otras partes del texto. Así,
por ejemplo, ciertos problemas de enumeración de grafos se tratan en lasegunda parte, y la
teoría de enumeración de Pólya se presenta en la tercera parte.

© Los autores, 2001; © Edicions UPC, 2001.

2 Combinaciones y permutaciones

27

Capítulo 2

Combinaciones y permutaciones
1. Selecciones ordenadas y no ordenadas
2. Algunos ejemplos de aplicación
3. Propiedades de los coeficientes binomiales

En este capítulo se exponen los problemas más simples deenumeración que forman parte de
la combinatoria elemental. Los modelos básicos se basan en la enumeración de selecciones
ordenadas y no ordenadas, con o sin repetición, de los elementos de un cierto conjunto. En la
sección 1 se obtienen las fórmulas de enumeración de estas selecciones. A pesar de su simplicidad, estos problemas de enumeración permiten resolver una diversidad considerable deproblemas, de los cuales hay algunos ejemplos interesantes en la sección 2: el número de palabras que pueden formarse a partir de un alfabeto, el número de soluciones de ciertas ecuaciones
enteras, el número de aplicaciones entre dos conjuntos, la fórmula del binomio y problemas relacionados, y los problemas de distribuciones. Los llamados coeficientes binomiales tienen una
importancia singular ypermiten expresar muchos de los resultados de enumeración; la tercera
sección está dedicada a analizar las propiedades más importantes de estos números.

2.1 Selecciones ordenadas y no ordenadas
Comenzaremos con un recorrido por la combinatoria elemental contando de cuántas maneras
diferentes se pueden seleccionar un cierto número de elementos de un conjunto. Para contar
este número es precisofijar los criterios con que se diferencia una selección de otra. Aquí
tendremos en cuenta dos tipos de criterios: el orden de los elementos y el número de veces que
puede aparecer cada uno.

© Los autores, 2001; © Edicions UPC, 2001.

28

MATEMÁTICA DISCRETA

Si distinguimos dos selecciones: cuando tienen elementos diferentes, o bien, cuando los
elementos aparecen en un orden diferente,hablaremos de permutaciones. En cambio, si no
distinguimos dos selecciones que sólo difieren en la ordenación de sus elementos, entonces
hablaremos de combinaciones. Por otra parte, si cada elemento puede aparecer como mucho
una vez, hablaremos de selecciones sin repetición, mientras que, si no hay esta restricción,
hablaremos de seleccciones con repetición. Por ejemplo, en el conjunto
X...