On edge-weighted recursive trees and inversions in random permutations. (English) Zbl 1130.05019
Summary: We introduce random recursive trees, where deterministically weights are attached to the edges according to the labeling of the trees. We give a bijection between recursive trees and permutations, which relates the arising edge-weights in recursive trees with inversions of the corresponding permutations. Using this bijection we obtain exact and limiting distribution results for the number of permutations of size \(n\), where exactly \(m\) elements have \(j\) inversions. Furthermore we analyze the distribution of the sum of labels of the elements, which have exactly \(j\) inversions, where we can identify Dickman’s infinitely divisible distribution as the limit law. Moreover we give a distributional analysis of weighted depths and weighted distances in edge-weighted recursive trees.
References:
| [1] | Bender, E. A., Central and local limit theorems applied to asymptotic enumeration, J. Combin. Theory Ser. A, 15, 91-111 (1973) · Zbl 0242.05006 |
| [2] | Bergeron, F.; Flajolet, P.; Salvy, B., Varieties of increasing trees, Lecture Notes in Computer Science, vol. 581 (1992), Springer: Springer Berlin, pp. 24-48 |
| [3] | Chan, D. Y.C.; Hughes, B. D.; Leong, A. S.; Reed, W. J., Stochastically evolving networks, Phys. Rev. E, 68, 066124, 24 (2003) |
| [4] | Chow, Y. S.; Teicher, H., Probability Theory (1978), Springer: Springer New York · Zbl 0399.60001 |
| [5] | Curtiss, J. H., A note on the theory of moment generating functions, Ann. Math. Statist., 13, 4, 430-433 (1942) · Zbl 0063.01024 |
| [6] | Feller, W., The fundamental limit theorems in probability, Bull. Amer. Math. Soc., 51, 800-832 (1945) · Zbl 0060.28702 |
| [7] | Gastwirth, J. L.; Bhattacharya, P. K., Two probability models of pyramid or chain letter schemes demonstrating that their promotional claims are unreliable, Oper. Res., 32, 527-536 (1984) · Zbl 0544.90062 |
| [8] | Hwang, H.-K.; Tsai, T.-H., Quickselect and the Dickman function, Combin. Probab. Comput., 11, 353-371 (2002) · Zbl 1008.68044 |
| [9] | Janson, S., Asymptotic degree distribution in random recursive trees, Random Structures Algorithms, 26, 69-83 (2005) · Zbl 1059.05094 |
| [10] | Knuth, D., The Art of Computer Programming, vol. 3: Sorting and Searching (1973), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0302.68010 |
| [11] | M. Kuba, Analysis of node isolation procedures and label-based parameters in tree structures, Ph.D. Thesis, TU Wien, Wien, 2006.; M. Kuba, Analysis of node isolation procedures and label-based parameters in tree structures, Ph.D. Thesis, TU Wien, Wien, 2006. |
| [12] | Kuba, M.; Panholzer, A., On the degree distribution of the nodes in increasing trees, J. Combin. Theory Ser. A, 114, 597-618 (2007) · Zbl 1116.05020 |
| [13] | M. Kuba, A. Panholzer, On the distribution of the node degree and related parameters in recursive trees, manuscript, 2007.; M. Kuba, A. Panholzer, On the distribution of the node degree and related parameters in recursive trees, manuscript, 2007. · Zbl 1116.05020 |
| [14] | Mahmoud, H., Sorting. A Distribution Theory (2000), Wiley: Wiley New York · Zbl 0985.68015 |
| [15] | Mahmoud, H.; Smythe, R., A survey of recursive trees, Theoret. Probab. Math. Statist., 51, 1-37 (1995) · Zbl 0933.05038 |
| [16] | Meir, A.; Moon, J. W., Cutting down recursive trees, Math. Biosci., 21, 173-181 (1974) · Zbl 0288.05102 |
| [17] | Najock, D.; Heyde, C. C., On the number of terminal vertices in certain random trees with an application to stemma construction in philology, J. Appl. Probab., 19, 675-680 (1982) · Zbl 0487.60012 |
| [18] | A. Panholzer, H. Prodinger, The level of nodes in increasing trees revisited, Random Structures Algorithms, accepted for publication, available at \(\langle;\) http://info.tuwien.ac.at/panholzer/levelinc3.pdf \(\rangle;\).; A. Panholzer, H. Prodinger, The level of nodes in increasing trees revisited, Random Structures Algorithms, accepted for publication, available at \(\langle;\) http://info.tuwien.ac.at/panholzer/levelinc3.pdf \(\rangle;\). · Zbl 1131.05029 |
| [19] | Sachkov, V. N., Probabilistic Methods in Combinatorial Analysis (1997), Cambridge University Press: Cambridge University Press New York, NY · Zbl 0947.68542 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
