TAILIEUCHUNG - Báo cáo toán học: "On Han’s Hook Length Formulas for Trees"

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í Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: On Han’s Hook Length Formulas for Trees. | On Han s Hook Length Formulas for Trees William . Chen1 Oliver . Gao2 Peter L. Guo3 Center for Combinatorics LPMC-TJKLC Nankai University Tianjin 300071 . China 1chen@ 2oliver@ 3lguo@ Submitted Mar 22 2011 Accepted Jun 22 2011 Published Jul 29 2011 Mathematics Subject Classifications 05A15 05A19 Abstract Recently Han obtained two hook length formulas for binary trees and asked for combinatorial proofs. One of Han s formulas has been generalized to k-ary trees by Yang. Sagan has found a probabilistic proof of Yang s extension. We give combinatorial proofs of Yang s formula for k-ary trees and the other formula of Han for binary trees. Our bijections are based on the structure of k-ary trees associated with staircase labelings. Keywords hook length formula k-ary tree bijection staircase labeling. 1 Introduction Motivated by the hook length formula of Postnikov 6 Han 4 discovered two hook length formulas for binary trees. Han s proofs are based on recurrence relations. He raised the question of finding combinatorial proofs of these two formulas 3 4 . Yang 9 generalized one of Han s formulas to k-ary trees by using generating functions. A probabilistic proof of Yang s formula has been found by Sagan 7 . By extending Han s expansion technique to k-ary trees Chen Gao and Guo 1 gave another proof for Yang s formula. The objective of this paper is to give combinatorial proofs of Yang s formula for k-ary trees and the other formula of Han for binary trees. Recall that a k-ary tree is a rooted unlabeled tree where each vertex has exactly k subtrees in linear order where we allow a subtree to be empty. When k 2 resp. k 3 a k-ary tree is called a binary resp. ternary tree. A complete k-ary tree is a k-ary tree for which each internal vertex has exactly k nonempty subtrees. The hook length of a vertex u in a k-ary tree T denoted by hu is the number of vertices of the subtree rooted at u. The hook length multi-set H T of T

• Báo cáo khoa học
• báo cáo của tạp chí Department of Mathematic
• tài liệu báo cáo nghiên cứu khoa học
• cách trình bày báo cáo
• kiến thức toán học
• báo cáo toán học