본문 바로가기 메뉴바로가기

Papers

A link between ordered trees and Green-Red trees

http://dx.doi.org/10.4134/JKMS.2016.53.1.187

 The r-ary number sequences given by (b (r) n )n≥0 = 1 (r − 1)n + 1 rn n  are analogs of the sequence of the Catalan numbers 1 n+1 2n n  . Their history goes back at least to Lambert [8] 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 b (r) n and b (r+1) n 

 The r-ary number sequences given by (b (r) n )n≥0 = 1 (r − 1)n + 1 rn n  are analogs of the sequence of the Catalan numbers 1 n+1 2n n  . Their history goes back at least to Lambert [8] 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 b (r) n and b (r+1) n