Some refined enumerations of hybrid binary trees

被引:0
作者
Lin Yang
Feng-Yun Ren
Sheng-Liang Yang
机构
[1] Lanzhou University of Technology,Department of Applied Mathematics
来源
Indian Journal of Pure and Applied Mathematics | 2024年 / 55卷
关键词
Binary tree; Hybrid binary tree; Riordan array; Generating function; Generalized Schröder path; Bijection; 05A15; 05A19; 15A24; 15A36; 11B83;
D O I
暂无
中图分类号
学科分类号
摘要
A hybrid binary tree is a complete binary tree where each internal node is labeled with 1 or 2, but with no left (1, 1)-edges. In this paper, we consider enumeration of the set of hybrid binary trees according to the number of internal nodes and some other combinatorial parameters. We present enumerative results by giving Riordan arrays, bivariate generating functions, as well as closed formulas. As a consequence, we obtain some new combinatorial matrices, one of which is analogous to the Borel triangle. We also present a bijection between the set of all hybrid binary trees with n internal nodes and the set of generalized Schröder paths from (0, 0) to (2n, 0) which are consist of up steps u=(1,1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$u=(1,1)$$\end{document}, horizontal steps h=(2,0)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$h=(2,0)$$\end{document}, down steps d=(1,-1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$d=(1,-1)$$\end{document}, and double up steps U=(2,2)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$U =(2,2)$$\end{document}, and never travel below the x-axis.
引用
收藏
页码:94 / 104
页数:10
相关论文
共 48 条
  • [1] Cai Y(2019)Counting with Borel’s Triangle Discrete Math. 342 529-539
  • [2] Yan C(2006)Old and young leaves on plane trees European J. Combin. 27 414-427
  • [3] Chen WYC(2008)Protected points in ordered trees Appl. Math. Lett. 21 516-520
  • [4] Deutsch E(2012)Combinatorics of Riordan arrays with identical A and Z sequences Discrete Math. 312 2040-2049
  • [5] Elizalde S(2017)k-protected vertices in unlabeled rooted plane trees Graphs Combin. 33 347-355
  • [6] Cheon G-S(1980)Enumeration of ordered trees Discrete Math. 31 9-28
  • [7] Shapiro LW(2002)A bijection between ordered trees and Discrete Math. 256 655-6700
  • [8] Cheon G-S(2008)-Motzkin paths and its many consequences Discrete Math. 308 1209-1221
  • [9] Kim H(2009)-Binary trees: Bijections and related issues European J. Combin. 30 969-985
  • [10] Shapiro LW(2009)Bijections for Discrete Math. 309 3962-3974