Permutaciones con repetición

Las permutaciones con repetición responden a una pregunta de conteo sencilla: si dispone de n símbolos distintos y forma secuencias ordenadas de longitud r en las que el mismo símbolo puede aparecer más de una vez, ¿cuántas secuencias existen? La regla del producto multiplica n opciones en cada una de las r posiciones, de modo que el total es exactamente n elevado a la potencia r. Esa fórmula aparece en espacios de contraseñas, códigos PIN, coloreados de cadenas de longitud fija, muestreo con reemplazo y un sinfín de problemas de matemática discreta en los que la respuesta debe ser un entero exacto y no una aproximación en coma flotante. Esta capacidad acepta un entero positivo n (el tamaño del alphabet) y un entero no negativo r (la longitud de la secuencia) y devuelve el conteo exacto como cadena decimal calculada con aritmética BigInt, de forma que valores muy por encima de los límites habituales de enteros seguros siguen siendo correctos dígito a dígito. Las entradas con n inferior a uno o con r negativo se rechazan con un error de validación claro en lugar de una respuesta errónea silenciosa.

Cómo se definen las permutaciones con repetición

Una selección ordenada de r posiciones a partir de n símbolos con repetición permitida es cualquier secuencia s1, s2, …, sr en la que cada si pertenece a un conjunto fijo de tamaño n. Como el orden importa y los símbolos pueden repetirse, la primera posición tiene n opciones, la segunda vuelve a tener n opciones, y así en cada posición hasta r. El principio fundamental del conteo multiplica esas elecciones independientes en n × n × … × n, que es n elevado a la potencia r.

Cuando r vale cero existe exactamente una secuencia vacía, en consonancia con la convención algebraica de que cualquier n positivo elevado a la potencia cero es igual a uno. Esto difiere de las permutaciones sin repetición, que prohíben la reutilización y dan el factorial decreciente n × (n − 1) × … × (n − r + 1), y de las combinaciones, que ignoran el orden.

Comprobaciones clásicas de libro incluyen dos símbolos de longitud tres que dan ocho secuencias, cinco símbolos de longitud dos que dan veinticinco, y diez símbolos de longitud cero que dan uno. Esta implementación nunca usa potencias en coma flotante, logaritmos aproximados ni muestreo: calcula la potencia entera exacta con exponentiación binaria BigInt para que cada dígito sea correcto. El recorrido es plenamente determinista —sin semillas aleatorias, sin relojes, sin red y sin deriva de modelo—, de modo que el mismo n y r siempre producen la misma cadena.

Dónde aparece el conteo n elevado a r en el trabajo real

Los equipos de seguridad y de producto estiman espacios de contraseñas o PIN tratando cada posición de carácter como una elección en un alphabet de tamaño n y longitud r, que es exactamente el conteo de permutaciones con repetición n elevado a r; los enteros exactos ayudan a comparar la fuerza de los esquemas sin aproximaciones logarítmicas.

Los concursos de programación y los cursos de matemática discreta piden a menudo el número de palabras de longitud r sobre un alphabet de n letras, el coloreado de r cuentas con n colores cuando el orden importa y los colores pueden repetirse, o las funciones de un conjunto de tamaño r en un conjunto de tamaño n —todas iguales a n elevado a r.

Los pipelines de datos y muestreo que modelan extracciones ordenadas con reemplazo necesitan el mismo producto al dimensionar espacios muestrales o validar montajes de Monte Carlo frente a un total analítico. Educadores y preparación de entrevistas suelen mostrar una tabla breve de valores pequeños de n y r; calcular el conteo en una sola llamada mantiene las demostraciones interactivas alineadas con libros de texto y claves de respuesta.

Si más adelante necesita permutaciones sin repetición, combinaciones con o sin repetición, o el listado de las tuplas reales en lugar del conteo, trátelos como intenciones de búsqueda separadas en lugar de sobrecargar esta página.