On coincidences of tuples in a binary tree with random labels of vertices. (English. Russian original) Zbl 1345.05092

Discrete Math. Appl. 26, No. 3, 145-153 (2016); translation from Diskretn. Mat. 27, No. 4, 38-48 (2015).
Summary: Let all vertices of a complete binary tree of finite height be independently and equiprobably labeled by the elements of some finite alphabet. We consider the numbers of pairs of identical tuples of labels on chains of subsequent vertices in the tree. Exact formulae for the expectations of these numbers are obtained. Convergence to the compound Poisson distribution is proved.


05C78 Graph labelling (graceful graphs, bandwidth, etc.)
05C05 Trees


Full Text: DOI


[1] Erhardsson T., “Stein’s method for Poisson and compound Poisson approximation”, An introduction to Stein’s method, eds. Barbour A.D., Chen L. H. Y., Singapore Univ. Press, 2005, 61-113.
[2] Guibas L. J., Odlyzko A. M., “Long repetitive patterns in random sequences”, Z. Wahrscheinlichkeitstheorie verw. Geb., 53(1980), 241-262. · Zbl 0424.60036
[3] Hoffmann C. M., O’Donnell M. J., “Pattern matching in trees”, J. ACM, 29:1 (1982), 68-95. · Zbl 0477.68067
[4] Karlin S., Ost F., “Counts of long aligned word matches among random letter sequences”, Adv. Appl. Probab., 19:2 (1987), 293-351. · Zbl 0621.60074
[5] Karnin E.D., “The first repetition of a pattern in a symmetric Bernoulli sequence”, J. Appl. Prob., 20:3 (1983), 413-418. · Zbl 0518.60017
[6] Rowland E. S., “Pattern avoidance in binary trees”, J. Comb. Theory, Ser. A, 117:6 (2010), 741-758. · Zbl 1221.05058
[7] Steyaert J.-M., Flajolet P., “Patterns and pattern-matching in trees: an analysis”, Inf. & Control, 58:1 (1983), 19-58. · Zbl 0567.68053
[8] Zubkov A.M., Mikhailov V.G., “Limit distributions of random variables associated with long duplications in a sequence of independent trials”, Theory Probab. Appl., 19:1 (1974), 172-179. · Zbl 0326.60024
[9] Mikhailov V.G., “Estimate of the accuracy of the compound Poisson approximation for the distribution of the number of matching patterns”, Theory Probab. Appl., 46:4 (2002), 667-675.
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.