Combinatoria elemental y el binomio de Newton

Los principios de conteo

Contar los elementos de un conjunto finito es la operación más elemental de la aritmética mientras el conjunto puede recorrerse elemento a elemento. Ahora bien, cuando los elementos son las maneras de realizar una elección compuesta, como ordenar diez libros en un estante o elegir tres representantes entre treinta personas, la enumeración se vuelve impracticable, y el número se obtiene descomponiendo la elección en partes o en etapas. Toda la combinatoria elemental descansa en dos principios, que se demuestran a partir de una definición precisa de lo que significa contar.

Contar los elementos de un conjunto es numerarlos: asignar a cada número desde $1$ hasta $n$ un elemento, sin repetir ninguno y sin omitir ninguno. Se dice que un conjunto $A$ tiene $n$ elementos, con $n$ natural, cuando existe una biyección del conjunto $\{1, 2, \ldots, n\}$ en $A$, es decir, una función que lleva números distintos a elementos distintos y alcanza a todos los elementos de $A$; el conjunto vacío tiene $0$ elementos, y un conjunto es finito si es vacío o tiene $n$ elementos para algún natural $n$. Las biyecciones, su composición y su inversa se estudian en la clase sobre conjuntos, relaciones y funciones.

Hecho admitido (número de elementos). Se admite sin demostración que el número de elementos de un conjunto finito está bien definido: un conjunto no puede tener a la vez $m$ elementos y $n$ elementos si $m \neq n$. Se admite también que todo subconjunto de un conjunto finito es finito.

Ambos hechos se demuestran por inducción sobre $n$; el primero es, en el fondo, el principio del palomar, según el cual no hay una función que lleve los $n + 1$ números de $\{1, \ldots, n + 1\}$ a números distintos de $\{1, \ldots, n\}$. Sus demostraciones son largas y no aportan ideas que se usen después, y por eso se admiten. Sin el primero, la expresión «el número de elementos» no tendría sentido, y una demostración combinatoria, que cuenta un mismo conjunto de dos maneras, no podría concluir que los dos resultados son iguales.

Por inducción sobre el número de partes, el principio se extiende a cualquier número finito de conjuntos sin elementos comunes dos a dos: la unión de $A_1, \ldots, A_r$, con $n_1, \ldots, n_r$ elementos, tiene $n_1 + \cdots + n_r$ elementos, porque la unión de los $r + 1$ primeros es la de los $r$ primeros con el último, que no tiene elementos comunes con ellos. De él se deduce el segundo principio, que cuenta las elecciones que se hacen por etapas.

Del mismo modo, por inducción sobre el número de etapas, el principio multiplicativo se extiende a cualquier número finito de ellas: una elección en $r$ etapas, que pueden realizarse de $n_1, n_2, \ldots, n_r$ maneras respectivamente, puede realizarse de $n_1 n_2 \cdots n_r$ maneras. Por ejemplo, en el sistema decimal estudiado en la clase sobre los sistemas de numeración posicional hay $9 \cdot 10 \cdot 10 = 900$ números de tres cifras, porque la primera cifra no puede ser $0$ y las otras dos son libres. Conviene advertir que el principio multiplicativo exige que el número de opciones de cada etapa no dependa de lo elegido antes, aunque las opciones mismas sí dependan; si esa condición falla, se separan casos en los que se cumple y se suman sus resultados con el principio aditivo.

Las etapas sucesivas de una elección se representan con un diagrama de árbol: de un punto inicial, la raíz, salen tantas ramas como opciones tiene la primera etapa; del extremo de cada rama, tantas como opciones tiene la segunda, y así sucesivamente. Cada recorrido desde la raíz hasta un extremo final, u hoja, es una elección completa, y el principio multiplicativo cuenta las hojas sin dibujarlas.