En matemáticas combinatorias , 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 adicional de que, para cada valor i que aparece en la permutación, los valores entre las dos copias de i son mayores que i . Por ejemplo, las 15 permutaciones de Stirling de orden tres son
El número de permutaciones de Stirling de orden k viene dado por el factorial doble (2 k − 1)!!. Las permutaciones de Stirling fueron introducidas por Gessel y Stanley (1978) para demostrar que ciertos números (los números de permutaciones de Stirling con un número fijo de descensos) no son negativos. Eligieron el nombre debido a una conexión con ciertos polinomios definidos a partir de los números de Stirling , que a su vez reciben su nombre del matemático escocés del siglo XVIII James Stirling . [1]
Las permutaciones de Stirling se pueden utilizar para describir las secuencias mediante las cuales es posible construir un árbol plano con raíz y k aristas, añadiendo hojas una a una al árbol. Porque, si las aristas están numeradas según el orden en el que se insertaron, entonces la secuencia de números en un recorrido de Euler por el árbol (formado al duplicar las aristas del árbol y recorrer los hijos de cada nodo en orden de izquierda a derecha) es una permutación de Stirling. A la inversa, cada permutación de Stirling describe una secuencia de construcción de árboles, en la que la arista siguiente más cercana a la raíz desde una arista etiquetada i es aquella cuyo par de valores rodea más de cerca al par de valores i en la permutación. [2]
Las permutaciones de Stirling se han generalizado a las permutaciones de un multiconjunto con más de dos copias de cada valor. [3] Los investigadores también han estudiado el número de permutaciones de Stirling que evitan ciertos patrones. [4]