Factorial, principios de conteo, arreglos y permutaciones

Más formas de las que parece

Un equipo del INE necesita visitar los 9 departamentos de Bolivia, uno por uno, para un relevamiento nacional. El orden de las visitas no es indiferente: afecta costos de traslado, tiempos, y la logística completa del operativo. ¿Cuántos órdenes de visita distintos son posibles?

La intuición suele quedarse corta acá. No son 9, ni 18, ni siquiera 100: el número real es mucho más grande, y la teoría combinatoria da la herramienta exacta para calcularlo sin tener que listar cada posibilidad a mano.

Factorial: el conteo de todos los órdenes posibles

El factorial de un número natural n, escrito n!, es el producto de todos los enteros positivos desde 1 hasta n: n! = n × (n−1) × (n−2) × ... × 2 × 1. Por convención, 0! = 1. El factorial responde exactamente la pregunta del problema inicial: la cantidad de formas de ordenar n elementos distintos (sin repetir ninguno) es n!.

Principios de conteo: multiplicativo y aditivo

El principio multiplicativo dice que, si una tarea se puede descomponer en pasos sucesivos, y el primer paso tiene m formas de realizarse, el segundo n formas, etc., el total de formas de completar toda la tarea es el producto de esas cantidades. Es exactamente lo que da origen al factorial: para ordenar 9 departamentos, hay 9 opciones para el primer lugar, 8 para el segundo (ya se usó uno), 7 para el tercero, y así sucesivamente: 9 × 8 × 7 × ... × 1 = 9!.

El principio aditivo aplica cuando hay que elegir entre alternativas mutuamente excluyentes: si una tarea se puede hacer de m formas de una manera, o de n formas de otra manera distinta e incompatible con la primera, el total es m + n (no un producto).

Arreglos (permutaciones): elegir Y ordenar

Un arreglo (o permutación) de r elementos tomados de un conjunto de n elementos distintos es una selección de r de esos elementos, en un orden específico. El número de arreglos posibles es: A(n,r) = n! / (n−r)!

Por ejemplo, si el INE solo tiene tiempo de visitar 3 de los 9 departamentos en una primera etapa, y el orden de esas 3 visitas importa (porque el itinerario y los costos cambian), el número de arreglos posibles es A(9,3) = 9!/(9−3)! = 9!/6! = 9×8×7 = 504.

Esto se distingue de las permutaciones circulares (ordenar n elementos alrededor de un círculo, donde solo importa la posición relativa, no cuál queda "primero": (n−1)! formas) y de las permutaciones con repetición (cuando algunos elementos son indistinguibles entre sí, dividiendo el factorial total entre los factoriales de cada grupo repetido).

Preguntas para pensar

• Si el equipo del INE tuviera que elegir 3 departamentos para visitar, pero el orden de la visita no importara (solo importa cuáles 3 se eligen), ¿crees que el resultado sería mayor, menor, o igual a A(9,3) = 504? (Vas a poder verificarlo en E.2.)
• Piensa en otra situación boliviana real donde el orden de una secuencia de decisiones importe económicamente (por ejemplo, el orden de desembolso de un préstamo, o el orden de prioridades de un presupuesto). Aplica el principio multiplicativo.
• ¿Por qué crees que los factoriales crecen tan rápido (9! ya es más de 360.000)? ¿Qué implicancias prácticas tiene esto para planificar operativos con muchos elementos a ordenar?
• Si dos de los 9 departamentos fueran, en los hechos, intercambiables para la planificación (por ejemplo, por tener características logísticas idénticas), ¿cómo cambiaría el cálculo de 9!? (Pista: piensa en las permutaciones con repetición.)