Stirling-permutation
I kombinatorisk matematik är en Stirling-permutation av ordningen k en permutation av multiuppsättningen 1, 1, 2, 2, ..., k , k (med två kopior av varje värde från 1 till k ) med den ytterligare egenskapen som för för varje värde i som visas i permutationen, är värdena mellan de två kopiorna av i större än i . Till exempel är de 15 Stirling-permutationerna av ordning tre
- 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.
Antalet Stirling-permutationer av ordningen k ges av dubbelfaktorialen (2 k − 1)!!. Stirling-permutationer introducerades av Gessel & Stanley (1978) för att visa att vissa siffror (antal Stirling-permutationer med ett fast antal nedgångar) är icke-negativa. De valde namnet på grund av en koppling till vissa polynom definierade från Stirlingtalen , som i sin tur är uppkallade efter den skotske matematikern James Stirling från 1700-talet .
Stirling-permutationer kan användas för att beskriva sekvenserna genom vilka det är möjligt att konstruera ett rotat platan med k kanter genom att lägga till löv en efter en till trädet. För, om kanterna är numrerade i den ordning som de infogades, då sekvensen av siffror i en Euler-rundtur i trädet (bildad genom att dubbla kanterna på trädet och korsa barnen i varje nod i vänster till höger ordning) är en Stirling-permutation. Omvänt beskriver varje Stirling-permutation en trädkonstruktionssekvens, där nästa kant närmare roten från en kant märkt i är den vars värdepar närmast omger paret av i- värden i permutationen.
Stirling-permutationer har generaliserats till permutationer för en multiset med fler än två kopior av varje värde. Forskare har också studerat antalet Stirling-permutationer som undviker vissa mönster.
Se även
- Langford-parning , en annan typ av permutation av samma multiset