Principios de conteo y combinatoria enumerativa

Luz y Omar pueden formar un mismo equipo sin importar a quién nombramos primero. Pero si una persona coordina y otra revisa, intercambiar sus nombres cambia la asignación. Para decidir si importa el orden, toma un resultado concreto, intercambia dos posiciones y pregunta si sigue siendo el mismo objeto según el enunciado.

Una biyección codifica cada objeto mediante un código único y permite recuperarlo. Si dos objetos distintos reciben el mismo código, se ha perdido información. Si un objeto recibe varios códigos, hay duplicados que contar. Precisar esa correspondencia convierte una intuición de conteo en una justificación.

Si un resultado pertenece a una y solo una de varias familias, el total es la suma de sus tamaños. Si construimos un resultado en etapas y cada elección de la primera admite exactamente n continuaciones, m primeras elecciones producen m·n resultados. Se cuentan posibilidades, no se necesita independencia probabilística.

Si las continuaciones cambian de una rama a otra, sumamos las cantidades de esas ramas. Tampoco basta encontrar las palabras “y” u “o”: hay que comprobar si la construcción es única, si existen restricciones y si los casos se solapan. Un árbol o una tabla permite ver qué multiplica o suma cada número.

Si hay n símbolos disponibles y k posiciones, con repetición y sin otras restricciones, hay nᵏ listas: en cada posición se puede volver a elegir cualquiera de los n símbolos. La posición distingue resultados; AB y BA no son la misma lista.

Las restricciones modifican las opciones. Un código puede empezar por cero si se permite; un número de tres cifras no. Prohibir símbolos iguales consecutivos deja n posibilidades al principio y n−1 después, para k≥1 y n≥1. No equivale a prohibir toda repetición: ABA no tiene iguales consecutivos pero repite A.

Una permutación coloca n objetos distintos en las n posiciones: n opciones, luego n−1, hasta una. El producto es n!. Una lista de k objetos distintos escogidos entre n, con 0≤k≤n, se detiene tras k factores: P(n, k)=n!/(n−k)!.

Existe exactamente una lista vacía. Por eso el producto vacío y 0! valen uno: elegir cero objetos no es tener cero soluciones. Si k>n, no hay listas sin repetición; no se intenta evaluar factoriales de enteros negativos en la fórmula anterior.

Para elegir k objetos distintos sin orden, primero contamos las listas sin repetición. Cada subconjunto de tamaño k tiene exactamente k! órdenes, todos diferentes porque sus elementos son distintos. Las listas se parten en bloques del mismo tamaño; por eso C(n, k)=n!/[k!(n−k)!].

La división solo funciona con multiplicidad constante. En objetos con simetrías, como collares que identifican rotaciones, algunos pueden tener menos representaciones que otros. Antes de dividir hay que demostrar el tamaño de cada bloque, no asumirlo por la apariencia de la fórmula.

Con n posiciones y cantidades n₁,…, nᵣ de cada tipo, etiquetamos temporalmente las copias para contar n! órdenes. Al borrar etiquetas, cada palabra aparece n₁!⋯nᵣ! veces, por los intercambios internos de cada tipo. Por tanto hay n!/(n₁!⋯nᵣ!) palabras.

La fórmula conserva exactamente las cantidades dadas; no impone condiciones de adyacencia ni de posición. Las restricciones se cuentan aparte, mediante una construcción por huecos, casos disjuntos o inclusión-exclusión. Es útil comprobar una palabra concreta para ver cuántos intercambios de etiquetas la dejan igual.

Distribuir k unidades indistinguibles entre r categorías distinguibles, r≥1, equivale a resolver x₁+⋯+xᵣ=k con enteros xᵢ≥0. Escribimos k estrellas y r−1 barras: las estrellas antes de la primera barra son x₁, entre las dos siguientes son x₂, y así. Barras juntas permiten categorías vacías.

Cada solución determina una única cadena y viceversa. Elegir las posiciones de las barras da C(k+r−1, r−1). Para xᵢ≥bᵢ, con bᵢ enteros no negativos, se restan primero esas cantidades y se distribuye k−Σbᵢ. Las cotas superiores no quedan garantizadas por esta fórmula simple.

Elegir k elementos de un conjunto de n determina sus n−k excluidos.

Para Pascal se fija un elemento: los subconjuntos de tamaño k o lo contienen o no lo contienen, dos casos disjuntos.

En (1+z)ⁿ, producir zᵏ consiste en elegir z en exactamente k de los n factores. Por eso su coeficiente es C(n, k). Se puede interpretar z como una marca formal y no hace falta asignarle un valor numérico para justificar el recuento. Usamos C(n, k)=0 fuera de 0≤k≤n para expresar cómodamente identidades de borde.

Antes de calcular, escribe el objeto, el número de posiciones, si importan, si se admite repetición y qué cantidades se conservan. Una lista con repetición se cuenta de manera distinta que un multiconjunto sin orden. Una colección de tamaños variables también necesita definir si se permite el vacío.

Después comprueba un caso pequeño y los extremos.

Si divides por algo, explica cuántas representaciones tiene cada resultado; si multiplicas, explica cuántas continuaciones tiene cada rama. Esa revisión evita aplicar una fórmula correcta al conjunto equivocado.