×

zbMATH — the first resource for mathematics

On the number of \(A\)-mappings. (English. Russian original) Zbl 1176.60005
Math. Notes 86, No. 1, 132-139 (2009); translation from Mat. Zametki 86, No. 1, 139-147 (2009).
Summary: Suppose that \(\mathfrak{S}_n\) is the semigroup of mappings of the set of \(n\) elements into itself, \(A\) is a fixed subset of the set of natural numbers \(\mathbb N\), and \(V_n (A)\) is the set of mappings from \(\mathfrak{S}_n\) whose contours are of sizes belonging to \(A\). Mappings from \(V_n (A)\) are usually called \(A\)-mappings. Consider a random mapping \(\sigma _n\) , uniformly distributed on \(V_n(A)\). Suppose that \(\nu _n\) is the number of components and \(\lambda _n\) is the number of cyclic points of the random mapping \(\sigma _n\) . In this paper, for a particular class of sets \(A\), we obtain the asymptotics of the number of elements of the set \(V_n (A)\) and prove limit theorems for the random variables \(\nu _n\) and \(\lambda _n\) as \(n \rightarrow \infty \).

MSC:
60C05 Combinatorial probability
60F05 Central limit and other weak theorems
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] V. N. Sachkov, Combinatorial Methods of Discrete Mathematics (Nauka, Moscow, 1977) [in Russian].
[2] V. N. Sachkov, Probability Methods in Combinatorial Analysis (Nauka, Moscow, 1978) [in Russian]. · Zbl 0517.05001
[3] V. N. Sachkov, Introduction to Combinatorial Methods of Discrete Mathematics (MTsNMO, Moscow, 2004) [in Russian].
[4] E. A. Bender, ”Asymptotic methods in enumeration,” SIAM Rev. 16(4), 485–515 (1974). · Zbl 0294.05002 · doi:10.1137/1016082
[5] Yu. V. Bolotnikov, V. N. Sachkov, and V. E. Tarakanov, ”Asymptotic normality of certain quantities that are related to the cyclic structure of random permutations,” Mat. Sb. 99(1), 121–133 (1976).
[6] L. M. Volynets, ”An example of nonstandard asymptotics of the number of permutations with constraints on the cycle length,” in Probability Processes and Their Applications (MIÉM, Moscow, 1989), pp. 85–90 [in Russian].
[7] A. A. Grusho, ”Properties of random permutations with constraints on the maximum cycle length,” in Probabilistic Methods in Discrete Mathematics, Progr. Pure Appl. Discrete Math., Petrozavodsk, 1992 (VSP, Utrecht, 1993), Vol. 1, pp. 60–63. · Zbl 0816.60009
[8] G. I. Ivchenko and Yu. I. Medvedev, ”On the random permutations,” in Works in Discrete Mathematics (Fizmatlit, Moscow, 2002), Vol. 5, pp. 73–92 [in Russian].
[9] A. V. Kolchin, ”Equations that contain an unknown permutation,” Diskret. Mat. 6(1), 100–115 (1994) [DiscreteMath. Appl. 4 (1), 59–71 (1994)].
[10] V. F. Kolchin, ”The number of permutations with cycle lengths from a fixed set,” in Random Grafs, Wiley-Intersci. Publ., Poznań, Poland, 1989 (Wiley, New York, 1992), Vol. 2, pp. 139–149. · Zbl 0820.05001
[11] E. Manstavičius, ”On random permutations without cycles of some lengths,” Period. Math. Hungar. 42(1–2), 37–44 (2001). · Zbl 0980.60015 · doi:10.1023/A:1015288321931
[12] M. P. Mineev and A. I. Pavlov, ”An equation in permutations,” in Trudy Mat. Inst. Steklov, Vol. 142: Differential Equations and Dynamical Systems (Nauka, Moscow, 1976), pp. 182–194 [in Russian]; [Proc. Steklov Inst. Math. 142, 195–208 (1979)]. · Zbl 0422.20005
[13] A. I. Pavlov, ”On two classes of permutations with number-theoretic constraints on cycle lengths,” Mat. Zametki 62(6), 881–891 (1997) [Math. Notes 62 (5–6), 739–746 (1997)]. · doi:10.4213/mzm1677
[14] A. N. Timashev, ”Limit theorems in schemes for allocating particles to different cells with restrictions on the filling of cells,” Teor. Veroyatnost. Primenen. 49(4), 712–725 (2004) [Theory Probab. Appl. 49 (4), 659–670 (2005)]. · doi:10.4213/tvp190
[15] A. L. Yakymiv, Probability Applications of Tauberian Theorems (Fizmatlit, Moscow, 2005) [in Russian]. · Zbl 1114.60002
[16] V. N. Sachkov, ”Mappings of a finite set with limitations on contours and height,” Teor. Veroyatnost. Primenen. 17, 679–694 (1972) [Theory Probab. Appl. 17, 640–656 (1972)]. · Zbl 0315.05103
[17] V. N. Sachkov, ”Random mappings with bounded height,” Teor. Veroyatnost. Primenen. 18(1), 122–132 (1973) [Theory Probab. Appl. 18, 120–130 (1973]. · Zbl 0327.60006
[18] Yu. L. Pavlov, Random Forests (Karel Scientific Center (KNTs), Russian Academy of Sciences, Petrozavodsk, 1996) [in Russian]. · Zbl 0921.60077
[19] V. F. Kolchin, Random Mappings, in Probability Theory and Mathematical Statistics (Nauka, Moscow, 1984) [in Russian].
[20] V. F. Kolchin, Random Graphs, in in Probability Theory and Mathematical Statistics (Fizmatlit, Moscow, 2000) [in Russian]. · Zbl 0997.05001
[21] Yu. L. Pavlov, ”Limit theorems for sizes of trees in the unlabelled graph of a random mapping,” Diskret.Mat. 16(3), 63–75 (2004) [Discrete Math. Appl. 14 (4), 329–342 (2004)]. · Zbl 1103.60301 · doi:10.4213/dm163
[22] B. A. Sevast’yanov, ”Convergence in distribution of random mappings of finite sets to branching processes,” Diskret. Mat. 17(1), 18–21 (2005) [Discrete Math. Appl. 15 (2), 105–108 (2005)]. · doi:10.4213/dm84
[23] I. A. Cheplyukova, ”The limit distribution of the number of cyclic vertices in a random mapping in a special case,” Diskret. Mat. 16(3), 76–84 (2004) [Discrete Math. Appl. 14 (4), 343–352 (2004)]. · Zbl 1103.60304 · doi:10.4213/dm164
[24] E. Seneta, Regularly Varying Functions (Springer-Verlag, Berlin-Heidelberg-New York, 1976; Nauka, Moscow, 1985). · Zbl 0324.26002
[25] A. L. Yakymiv, ”On the distribution of the mth maximal cycle lengths of random A-permutations,” Diskret. Mat. 17(4), 40–58 (2005) [Discrete Math. Appl. 15 (5), 527–546 (2005)]. · doi:10.4213/dm128
[26] A. L. Yakymiv, ”Limit theorem for the general number of cycles in a random A-permutation,” Teor. Veroyatnost. Primenen. 52(1), 69–83 (2007) [Theory Probab. Appl. 52 (1), 133–146 (2007)]. · doi:10.4213/tvp5
[27] V. S. Vladimirov and B. I. Zav’yalov, ”Tauberian theorems in quantum field theory,” in Current Problems in Mathematics, Vsesoyuz. Inst. Nauchn. i Tekhn. Informatsii, Moscow, 1980 (VINITI, Moscow, 1980), Vol. 15, pp. 95–130 [in Russian].
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.