Stirling permutation (original) (raw)
En combinatòria, una permutació de Stirling d'ordre k és una permutació del multiconjunt 1, 1, 2, 2, ..., k, k (amb dues còpies de cada valor d'1 a k) amb la propietat afegida que, per cada valor i que apareix a la permutació, els valors entre les dues còpies d'i són més grans que i. Per exemple, les 15 permutacions de Stirling d'ordre tres són: 1,1,2,2,3,3; 1,2,2,1,3,3; 2,2,1,1,3,3;1,1,2,3,3,2; 1,2,2,3,3,1; 2,2,1,3,3,1;1,1,3,3,2,2; 1,2,3,3,2,1; 2,2,3,3,1,1;1,3,3,1,2,2; 1,3,3,2,2,1; 2,3,3,2,1,1;3,3,1,1,2,2; 3,3,1,2,2,1; 3,3,2,2,1,1.
| Property | Value |
|---|---|
| dbo:abstract | En combinatòria, una permutació de Stirling d'ordre k és una permutació del multiconjunt 1, 1, 2, 2, ..., k, k (amb dues còpies de cada valor d'1 a k) amb la propietat afegida que, per cada valor i que apareix a la permutació, els valors entre les dues còpies d'i són més grans que i. Per exemple, les 15 permutacions de Stirling d'ordre tres són: 1,1,2,2,3,3; 1,2,2,1,3,3; 2,2,1,1,3,3;1,1,2,3,3,2; 1,2,2,3,3,1; 2,2,1,3,3,1;1,1,3,3,2,2; 1,2,3,3,2,1; 2,2,3,3,1,1;1,3,3,1,2,2; 1,3,3,2,2,1; 2,3,3,2,1,1;3,3,1,1,2,2; 3,3,1,2,2,1; 3,3,2,2,1,1. El nombre de permutacions de Stirling d'ordre k està donat pel doble factorial (2k - 1) !!. Les permutacions de Stirling van ser introduïdes per per a demostrar que certs nombres (els nombres de les permutacions de Stirling amb un nombre fix de descendents) són no-negatius. Van triar el nom a causa d'una connexió a certs polinomis definits pels nombres de Stirling, que es van anomenar així després del segle xvii en honor del matemàtic escocès James Stirling. Les permutacions de Stirling poden usar-se per a descriure les seqüències per les quals és possible construir un arbre pla arrelat amb k vores afegint fulles una per una a l'arbre. Si les vores estan numerades per l'ordre en què van ser inserides, llavors la seqüència de nombres en una de l'arbre (formada al doblegar les vores de l'arbre i travessar als descendents de cada node d'esquerra a dreta) és una permutació de Stirling. Per contra, cada permutació de Stirling descriu una seqüència de construcció d'arbre, en la qual la següent vora més propera a l'arrel d'una vora ordenada i és aquella la qual el parell de valors envolta més estretament al parell de valors i en la permutació. Les permutacions de Stirling s'han generalitzat a les permutacions d'un multiconjunt amb més de dues còpies de cada valor. Els investigadors també han estudiat el nombre de permutacions de Stirling que eviten certs patrons. (ca) 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. Por ejemplo, las 15 permutaciones de Stirling de orden tres son 1,1,2,2,3,3; 1,2,2,1,3,3; 2,2,1,1,3,3;1,1,2,3,3,2; 1,2,2,3,3,1; 2,2,1,3,3,1;1,1,3,3,2,2; 1,2,3,3,2,1; 2,2,3,3,1,1;1,3,3,1,2,2; 1,3,3,2,2,1; 2,3,3,2,1,1;3,3,1,1,2,2; 3,3,1,2,2,1; 3,3,2,2,1,1. El número de permutaciones de Stirling de orden k está dado por el doble factorial (2k − 1)!!. Las permutaciones de Stirling fueron introducidas por para demostrar que ciertos números (los números de las permutaciones de Stirling con un número fijo de descendentes) son no-negativos. 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. 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. Por el contrario, cada permutación de Stirling describe una secuencia de construcción de árbol, en la cual el siguiente borde más cercano a la raíz de un borde ordenado i es aquel cuyo par de valores rodea más estrechamente al par de valores i en la permutación. Las permutaciones de Stirling se han generalizado a las permutaciones de un multiconjunto con más de dos copias de cada valor. Los investigadores también han estudiado el número de permutaciones de Stirling que evitan ciertos patrones. (es) In combinatorial mathematics, a Stirling permutation of order k is a permutation of the multiset 1, 1, 2, 2, ..., k, k (with two copies of each value from 1 to k) with the additional property that, for each value i appearing in the permutation, the values between the two copies of i are larger than i. For instance, the 15 Stirling permutations of order three are 1,1,2,2,3,3; 1,2,2,1,3,3; 2,2,1,1,3,3;1,1,2,3,3,2; 1,2,2,3,3,1; 2,2,1,3,3,1;1,1,3,3,2,2; 1,2,3,3,2,1; 2,2,3,3,1,1;1,3,3,1,2,2; 1,3,3,2,2,1; 2,3,3,2,1,1;3,3,1,1,2,2; 3,3,1,2,2,1; 3,3,2,2,1,1. The number of Stirling permutations of order k is given by the double factorial (2k − 1)!!. Stirling permutations were introduced by in order to show that certain numbers (the numbers of Stirling permutations with a fixed number of descents) are non-negative. They chose the name because of a connection to certain polynomials defined from the Stirling numbers, which are in turn named after 18th-century Scottish mathematician James Stirling. Stirling permutations may be used to describe the sequences by which it is possible to construct a rooted plane tree with k edges by adding leaves one by one to the tree. For, if the edges are numbered by the order in which they were inserted, then the sequence of numbers in an Euler tour of the tree (formed by doubling the edges of the tree and traversing the children of each node in left to right order) is a Stirling permutation. Conversely every Stirling permutation describes a tree construction sequence, in which the next edge closer to the root from an edge labeled i is the one whose pair of values most closely surrounds the pair of i values in the permutation. Stirling permutations have been generalized to the permutations of a multiset with more than two copies of each value. Researchers have also studied the number of Stirling permutations that avoid certain patterns. (en) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Stirling_permutation_Euler_tour.svg?width=300 |
| dbo:wikiPageID | 38851923 (xsd:integer) |
| dbo:wikiPageLength | 4361 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1102260499 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Permutation dbr:James_Stirling_(mathematician) dbc:Permutations dbr:Multiset dbr:Combinatorics dbr:Stirling_number dbr:Tree_(graph_theory) dbr:Langford_pairing dbc:Combinatorics dbr:Double_factorial dbr:Polynomial dbr:Euler_tour_technique dbr:File:Stirling_permutation_Euler_tour.svg |
| dbp:wikiPageUsesTemplate | dbt:Harvtxt dbt:Reflist dbt:Short_description |
| dct:subject | dbc:Permutations dbc:Combinatorics |
| gold:hypernym | dbr:Permutation |
| rdf:type | yago:Abstraction100002137 yago:Change107296428 yago:Event100029378 yago:Happening107283608 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Substitution107443761 yago:Variation107337390 yago:WikicatPermutations |
| rdfs:comment | En combinatòria, una permutació de Stirling d'ordre k és una permutació del multiconjunt 1, 1, 2, 2, ..., k, k (amb dues còpies de cada valor d'1 a k) amb la propietat afegida que, per cada valor i que apareix a la permutació, els valors entre les dues còpies d'i són més grans que i. Per exemple, les 15 permutacions de Stirling d'ordre tres són: 1,1,2,2,3,3; 1,2,2,1,3,3; 2,2,1,1,3,3;1,1,2,3,3,2; 1,2,2,3,3,1; 2,2,1,3,3,1;1,1,3,3,2,2; 1,2,3,3,2,1; 2,2,3,3,1,1;1,3,3,1,2,2; 1,3,3,2,2,1; 2,3,3,2,1,1;3,3,1,1,2,2; 3,3,1,2,2,1; 3,3,2,2,1,1. (ca) 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. Por ejemplo, las 15 permutaciones de Stirling de orden tres son 1,1,2,2,3,3; 1,2,2,1,3,3; 2,2,1,1,3,3;1,1,2,3,3,2; 1,2,2,3,3,1; 2,2,1,3,3,1;1,1,3,3,2,2; 1,2,3,3,2,1; 2,2,3,3,1,1;1,3,3,1,2,2; 1,3,3,2,2,1; 2,3,3,2,1,1;3,3,1,1,2,2; 3,3,1,2,2,1; 3,3,2,2,1,1. (es) In combinatorial mathematics, a Stirling permutation of order k is a permutation of the multiset 1, 1, 2, 2, ..., k, k (with two copies of each value from 1 to k) with the additional property that, for each value i appearing in the permutation, the values between the two copies of i are larger than i. For instance, the 15 Stirling permutations of order three are 1,1,2,2,3,3; 1,2,2,1,3,3; 2,2,1,1,3,3;1,1,2,3,3,2; 1,2,2,3,3,1; 2,2,1,3,3,1;1,1,3,3,2,2; 1,2,3,3,2,1; 2,2,3,3,1,1;1,3,3,1,2,2; 1,3,3,2,2,1; 2,3,3,2,1,1;3,3,1,1,2,2; 3,3,1,2,2,1; 3,3,2,2,1,1. (en) |
| rdfs:label | Permutació de Stirling (ca) Permutación de Stirling (es) Stirling permutation (en) |
| owl:sameAs | freebase:Stirling permutation yago-res:Stirling permutation wikidata:Stirling permutation dbpedia-ca:Stirling permutation dbpedia-es:Stirling permutation https://global.dbpedia.org/id/fv41 |
| prov:wasDerivedFrom | wikipedia-en:Stirling_permutation?oldid=1102260499&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Stirling_permutation_Euler_tour.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Stirling_permutation |
| is dbo:wikiPageDisambiguates of | dbr:Stirling_(disambiguation) |
| is dbo:wikiPageWikiLink of | dbr:James_Stirling_(mathematician) dbr:List_of_permutation_topics dbr:Stirling_(disambiguation) dbr:Stirling_number dbr:Ira_Gessel dbr:Langford_pairing dbr:Double_factorial |
| is foaf:primaryTopic of | wikipedia-en:Stirling_permutation |
