TAILIEUCHUNG - Báo cáo toán học: " DESCENDANTS IN HEAP ORDERED TREES OR A TRIUMPH OF COMPUTER ALGEBRA"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: DESCENDANTS IN HEAP ORDERED TREES OR A TRIUMPH OF COMPUTER ALGEBRA. | DESCENDANTS IN HEAP ORDERED TREES OR A TRIUMPH OF COMPUTER ALGEBRA Helmut Prodinger Institut fur Algebra und Diskrete Mathematik Technical University of Vienna Wiedner Hauptstrasse 8-10 A-1040 Vienna Austria. email www http theoinf Submitted June 8 1996 Accepted September 16 1996. I dedicate this paper to Doron Zeilberger and his program Ekhad. Abstract. a heap ordered tree with n nodes size n is a planted plane tree together with a bijection from the nodes to the set 1 . . ng which is monotonically increasing when going from the root to the leaves. We consider the number of descendants of the node j in a random heap ordered tree of size n j. Precise expressions are derived for the probability distribution and all factorial moments. AMS Subject Classification. 05A15 primary 05C05 secondary 1. Heap ordered trees A heap ordered tree with n nodes size n might be described as a planted plane tree together with a bijection from the nodes to the set 1 . ng which is monotonically increasing when going from the root to the leaves. Figure 1. All 15 heap ordered trees with 4 nodes THE ELECTRONIC JOURNAL OF COMBINATORICS 3 1996 R29 2 In this note we want to concentrate on the number of descendants of the node j in a random heap ordered tree of size n j. By convention we say that the node j is a descendant of itself. For instance node 1 always has n descendants and node n has 1 descendant. The interest in the number of descendants stems from the . thesis of Janice Lent 4 compare also 5 . In 6 Conrado Martinez and myself are currently investigating this parameter and several others for binary search trees and some variants. For more information about heap ordered trees the reader is referred to 1 9 8 . We will get explicit formula for all factorial moments as well as for the probability generating functions. Finally even the probabilities themselves can be computed explicitly. Methodologically we first got the .

TÀI LIỆU LIÊN QUAN
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.