Journal of the
Korean Mathematical Society
JKMS

ISSN(Print) 0304-9914 ISSN(Online) 2234-3008

Article

HOME ALL ARTICLES View

J. Korean Math. Soc. 2016; 53(1): 187-199

Printed January 1, 2016

https://doi.org/10.4134/JKMS.2016.53.1.187

Copyright © The Korean Mathematical Society.

A link between ordered trees and Green-Red trees

Gi-Sang Cheon, Hana Kim, and Louis W. Shapiro

Sungkyunkwan University, National Institute for Mathematical Sciences, Howard University

Abstract

The $r$-ary number sequences given by $$(\mathfrak{b}_{n}^{(r)})_{n\ge0} ={\frac{1}{(r-1)n+1}}{\binom{rn}{n}}$$ are analogs of the sequence of the Catalan numbers ${\frac{1}{n+1}}{\binom{2n}{n}}$. Their history goes back at least to Lambert \cite{BLam} in 1758 and they are of considerable interest in sequential testing. Usually, the sequences are considered separately and the generalizations can go in several directions. Here we link the various $r$ first by introducing a new combinatorial structure related to GR trees and then algebraically as well. This GR transition generalizes to give $r$-ary analogs of many sequences of combinatorial interest. It also lets us find infinite numbers of combinatorially defined sequences that lie between the Catalan numbers and the Ternary numbers, or more generally, between $\mathfrak{b}_n^{(r)}$ and $\mathfrak{b}_n^{(r+1)}$.

Keywords: $r$-ary numbers, Riordan array, green-red tree

MSC numbers: Primary 05A15; Secondary 05C05

Stats or Metrics

Share this article on :

Related articles in JKMS