Some classes of random mappings of finite sets and non-homogeneous branching processes

摘要

Let X = ∪_(t=0)~TX_t be a finite set, where X_t, t = 1, 2,... , T, are pairwise non-overlapping sets, N_t = |X_t| be the cardinality of the set X_t, t = 0, 1,...,T. Let F_1 be the class of all mappings f of the set X' = XX_0 into X such that the image y = f(x) ∈ X_(T-1)∪X_t for any .x e X_t, t-l,...,T. The cardinality of the set of all mappings of the class F_1 is Π_(t=1)~T (N_(tr=1)~T) (N_(t-1) + N_t)~N_t. With the use of non-homogeneous branching processes, we study some asymptotical properties of the uniformly distributed on Wr random mapping f as Nt → ∞, t = 1,2,..., T. Similar results are obtained for some other classes of random mappings f of the set X. This research was supported by the Russian Foundation for Basic Research, grant 02.01.00266, and the grant 1758.2003.1 of the President of Russian Federation for support of leading scientific schools.