Permutación de Stirling

En combinatoria, una permutación de Stirling de orden k es una permutación del multiconjunto 1, 1, 2, 2, ..., k, k (con dos copias de cada valor de 1 a k) con la propiedad añadida de que, por cada valor i que aparece en la permutación, los valores entre las dos copias de i son mayores que i.

Eligieron el nombre a causa de una conexión a ciertos polinomios definidos por los números de Stirling, que se llamaron así después del siglo XVII en honor al matemático escocés James Stirling.

[1]​ Las permutaciones de Stirling pueden usarse para describir las secuencias por las cuales es posible construir un árbol plano arraigado con k bordes añadiendo hojas una por una al árbol.

Si los bordes están numerados por el orden en que fueron insertados, entonces la secuencia de números en una torre de Euler del árbol (formada al doblar los bordes del árbol y atravesar a los descendientes de cada nodo de izquierda a derecha) es una permutación de Stirling.

Los investigadores también han estudiado el número de permutaciones de Stirling que evitan ciertos patrones.