RUS  ENG
Full version
JOURNALS // Matematicheskie Voprosy Kriptografii [Mathematical Aspects of Cryptography] // Archive

Mat. Vopr. Kriptogr., 2011 Volume 2, Issue 2, Pages 95–118 (Mi mvk33)

This article is cited in 1 paper

Random mappings with fixed elements

V. N. Sachkov

Academy of Cryptography of Russian Federation, Moscow

Abstract: We consider orgraphs of random mappings of $n$-element set having uniform distribution on the set of all mappings with fixed points. Formulas for exact and limit distributions of the number of vertices in a tree or in a forest containing a given vertex are derived along with analogous results for the height of a given vertex conditioned to belong to a forest. Exact and limit distributions of the height of a given vertex in a random rooted tree or forest with $n$ vertices are derived also.

Key words: random mappings with fixed elements, orgraphs, rooted trees, forests, height of a vertex, limit distributions.

UDC: 519.212.2

Received 22.IV.2010

DOI: 10.4213/mvk33



© Steklov Math. Inst. of RAS, 2024