Additive functionals of d-ary increasing trees

الأصل · EN

A tree functional is called additive if it satisfies a recursion of the form F(T) = ∑ⱼ₌₁ᵏ F(Bⱼ) + f(T), where B₁,,Bₖ are the branches of the tree T and f(T) is a toll function. We prove a general central limit theorem for additive functionals of d-ary increasing trees under suitable assumptions on the toll function. The same method also applies to generalised plane-oriented increasing trees (GPORTs). One of our main applications is a log-normal law that we prove for the size of the automorphism group of d-ary increasing trees, but many other examples (old and new) are covered as well.