Metraipolis › archive › dc_7c036eff614c

Random permutation statistics — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/Random_permutation_statistics
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-07T17:23:16.608Z
SHA-256 of the archived text
f5914ef1dfae6ce89189dcc51f5d8308a5f5a45b9463a1371d876a0886f4ccc9
Stable URL of this page
https://metraipolis.com/documento/dc_7c036eff614c

How to cite

Random permutation statistics — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Random_permutation_statistics (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_7c036eff614c (Metraipolis archive dc_7c036eff614c, sha256 f5914ef1dfae6ce89189dcc51f5d8308a5f5a45b9463a1371d876a0886f4ccc9)
BibTeX
@misc{dc7c036eff614c,
  title = {Random permutation statistics — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Random_permutation_statistics},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_7c036eff614c; sha256 f5914ef1dfae6ce89189dcc51f5d8308a5f5a45b9463a1371d876a0886f4ccc9},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Random_permutation_statistics. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

The statistics of random permutations, such as the cycle structure of a random permutation, are of fundamental importance in the analysis of algorithms, especially of sorting algorithms, which operate on random permutations. Suppose, for example, that we are using quickselect (a cousin of quicksort) to select a random element of a random permutation. Quickselect will perform a partial sort on the array, as it partitions the array according to the pivot. Hence a permutation will be less disordered after quickselect has been performed. The amount of disorder that remains may be analysed with generating functions. These generating functions depend in a fundamental way on the generating functions of random permutation statistics. Hence it is of vital importance to compute these generating functions. The article on random permutations contains an introduction to random permutations.

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; categoria «Combinatorics»).
Fonte: Wikipedia in inglese, voce «Random permutation statistics» — https://en.wikipedia.org/wiki/Random_permutation_statistics
Wikidata Q17165867 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q17165867
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Random_permutation_statistics?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1372935669, consultata il 2026-10-07T16:54:30.493Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 5929e47a7629addaf5f7a6cd0d407cd8013f07eb4aa11591b0a0b5200bffd977