2007/03/09 by Antonio Bernini, Elisabetta Grazzini, Bernini, Antonio +5
Computer Science · Mathematics · #05A05 #68R05 #Advanced Combinatorial Mathematics #Advanced Mathematical Identities #Algorithms and Data Compression #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05A05 #msc:68R05
paper · pdf · doi:10.48550/arxiv.math/0703262
21 pages, 3 figures
arxiv created 2007/03/09 · openalex publication_date 2007/03/09 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Starting from a succession rule for Catalan numbers, we define a procedure encoding and listing the objects enumerated by these numbers such that two consecutive codes of the list differ only for one digit. Gray code we obtain can be generalized to all the succession rules with the stability property: each label (k) has in its production two labels c1 and c2, always in the same position, regardless of k. Because of this link, we define Gray structures the sets of those combinatorial objects whose construction can be encoded by a succession rule with the stability property. This property is a characteristic that can be found among various succession rules, as the finite, factorial or transcendental ones. We also indicate an algorithm which is a very slight modification of the Walsh's one, working in a O(1) worst-case time per word for generating Gray codes.