Letters of a given type in Catalan words: A continued fraction approach
Helmut Prodinger · 2026
Read Letters of a given type in Catalan words: A continued fraction approach by Helmut Prodinger (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-23378.txt.
Introduction
Prodinger counts letters of a given type inside Catalan words. He works with generating functions tied to Catalan words and digit frequencies. Continued fractions supply those functions in a fast and flexible way. The method follows the philosophy Philippe Flajolet laid out in 1980. Prodinger presents the approach as elegant as well as quick. The counts cover how often each chosen digit or letter type appears across the words.
Catalog record
| CREATOR | Helmut Prodinger |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 5955 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.23378
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Letters of a given type in Catalan words: A continued fraction approach
Helmut Prodinger
Abstract
. Generating functions related to Catalan words and frequencies of digits are obtained using continued fractions. This is fast, elegant, and flexible. It follows the philosophy of Philippe Flajolet from 1980.
2020 Mathematics Subject Classification
05A15
1.
Catalan words
Dyck paths consist of
n
up steps and
n
down steps. They begin at the
x
-axis and end at the
x
-axis and never go below the
x
-axis. Stanley’s book
[
5
]
contains them and many equivalent combinatorial objects. They might be described by a graph (automaton) checking the conditions.
\dots
{z}
{z}
{z}
{z}
{z}
{z}
{z}
{z}
Figure 1.
Starting and ending at the bullet node. If
2n
steps are done, the coefficient of
z^{n}
is the Catalan number
\frac{1}{n+1}\binom{2n}{n}
.
For the generating function
C(z)
, a decomposition whenever one returns to the beginning leads to
C(z)=\frac{1}{1-C(z)}
and the usual
C(z)=\frac{1-\sqrt{1-4z}}{2z}=\sum_{n\geq 0}\frac{1}{n+1}\binom{2n}{n}z^{n}.
The recursion can be iterated:
C(z)=\cfrac{1}{1-\cfrac{z}{1-\cfrac{z}{1-\cdots}}}
For the relation between lattice paths and continued fractions we cite the pioneering paper
[
4
]
.
\dots
{1}
{2}
{3}
{4}
{5}
{6}
{7}
{8}
Figure 2.
Starting and ending at the bullet node. If
2n
steps are done, the labels of the
n
forward steps form a
Catalan word
. For
n=3
, these words are possible:
111
,
112
,
121
,
122
,
123
.
Catalan words are built from letters
1,2,3,\dots
. If the word is written as
a_{1}a_{2}\dots a_{n}
then
a_{1}=1
and
a_{i+1}\leq a_{i}+1
.
I recommend the papers
[
3
,
1
]
as a references for Catalan words.
If one wants to keep track of what types of forward steps are done, one can use variables
v_{1},v_{2},\dots
as in Figure
3
.
\dots
zv_{1}
zv_{2}
zv_{3}
zv_{4}
zv_{5}
zv_{6}
zv_{7}
zv_{8}
Figure 3.
Using variables to track forward letters (up steps).
2.
Catalan words and continued fractions
The continued fraction is now
C(z)=\cfrac{1}{1-\cfrac{zv_{1}}{1-\cfrac{zv_{2}}{1-\ddots}}}
Table 1.
h_{i}=h_{i-1}-a_{i}h_{i-2}
,
k_{i}=k_{i-1}-a_{i}k_{i-2}
n
-1
0
1
2
3
4
a_{n}
1
zv_{1}
zv_{2}
zv_{3}
zv_{4}
h_{n}
0
1
1
1-zv_{2}
1-zv_{2}-zv_{3}
…
k_{n}
1
1
1-zv_{1}
1-zv_{1}-zv_{2}
1-zv_{1}-zv_{2}-zv_{3}+z^{2}v_{1}v_{3}
\dots
With the recursive scheme as in Table
1
, we find the representation (the traditional method to unwind a continued fraction).
\frac{h_{4}}{k_{4}}=\cfrac{1}{1-\cfrac{zv_{1}}{1-\cfrac{zv_{2}}{1-\cfrac{zv_{3}}{1-zv_{4}C(z)}}}}
and similar in general for
\frac{h_{n}}{k_{n}}
. Replacing
C(z)
by 1 leads to the generating function where forward letters
>n
do not occur. In other words, these are Dyck paths of bounded height, a very classical subject
[
2
]
, and we are in the realm of Chebyshev polynomials. If we replace
C(z)
by
\frac{1-\sqrt{1-4z}}{2z}
, we have the generating function
F(z;v_{1},\dots,v_{n})
and count the semilength of the Catalan words, and the occurrences of letters
1,2,\dots,n
. As an example, we cite
\displaystyle\frac{h_{5}}{k_{5}}
\displaystyle=\frac{1-zv_{5}C-v_{4}z-zv_{3}+z^{2}v_{3}v_{5}C-zv_{2}+z^{2}v_{2}v_{5}C+z^{2}v_{2}v_{4}}{\displaystyle{\genfrac{}{}{0.0pt}{}{1-zv_5C-v_4z-zv_3+z^2v_3v_5C-zv_2+z^2v_2v_5C+z^2v_2v_4-zv_1}{+z^2v_1v_5C+z^2v_1v_4+z^2v_1v_3-z^3v_1v_3v_5C}}}
\displaystyle=1+zv_{1}+(v_{1}v_{2}+v_{1}^{2})z^{2}+(v_{1}v_{2}v_{3}+v_{1}v_{2}^{2}+2v_{1}^{2}v_{2}+v_{1}^{3})z^{3}
\displaystyle\qquad+(3v_{1}^{2}v_{2}^{2}+3v_{1}^{3}v_{2}+2v_{1}^{2}v_{2}v_{3}+2v_{1}v_{2}^{2}v_{3}+v_{1}v_{2}v_{3}v_{4}+v_{1}v_{2}v_{3}^{2}+v_{1}v_{2}^{3}+v_{1}^{4})z^{4}+\dots;
\frac{h_{3}}{k_{3}}=1+zv_{1}+(v_{1}v_{2}+v_{1}^{2})z^{2}+\mathbf{(v_{1}v_{2}v_{3}+v_{1}v_{2}^{2}+2v_{1}^{2}v_{2}+v_{1}^{3})}z^{3}+\dots
The 5 terms in bold correspond to
123
,
122
,
112
,
121
,
111
.
Blecher and Knopfmacher
[
1
]
were interested in more manageable generating functions, namely by setting all variables
v_{j}=1
, except for one variable
v_{i}
, for which we write simply
V
. In an ad hoc notation, we can write these functions for the first few values of
i=1,2,\dots,10
:
\displaystyle\mathscr{A}_{1}(z)
\displaystyle=\frac{1}{1-zVC},
\displaystyle\mathscr{A}_{2}(z)
\displaystyle=\frac{1-zVC}{1-zVC-z},
\displaystyle\mathscr{A}_{3}(z)
\displaystyle=\frac{1-zVC-z}{1-zVC-2z+z^{2}VC},
\displaystyle\mathscr{A}_{4}(z)
\displaystyle=\frac{1-zVC-2z+z^{2}VC}{1-zVC-3z+2z^{2}VC+z^{2}},
\displaystyle\mathscr{A}_{5}(z)
\displaystyle=\frac{1-zVC-3z+2z^{2}VC+z^{2}}{1-zVC-4z+3z^{2}VC+3z^{2}-z^{3}VC},
\displaystyle\mathscr{A}_{6}(z)
\displaystyle=\frac{1-zVC-4z+3z^{2}VC+3z^{2}-z^{3}VC}{1-zVC-5z+4z^{2}VC+6z^{2}-3z^{3}VC-z^{3}},
\displaystyle\mathscr{A}_{7}(z)
\displaystyle=\frac{1-zVC-5z+4z^{2}VC+6z^{2}-3z^{3}VC-z^{3}}{1-zVC-6z+5z^{2}VC+10z^{2}-6z^{3}VC-4z^{3}+z^{4}VC},
\displaystyle\mathscr{A}_{8}(z)
\displaystyle=\frac{1-zVC-6z+5z^{2}VC+10z^{2}-6z^{3}VC-4z^{3}+z^{4}VC}{1-zVC-7z+6z^{2}VC+15z^{2}-10z^{3}VC-10z^{3}+4z^{4}VC+z^{4}},
\displaystyle\mathscr{A}_{9}(z)
\displaystyle=\frac{1-zVC-7z+6z^{2}VC+15z^{2}-10z^{3}VC-10z^{3}+4z^{4}VC+z^{4}}{1-zVC-8z+7z^{2}VC+21z^{2}-15z^{3}VC-20z^{3}+10z^{4}VC+5z^{4}-z^{5}VC},
\displaystyle\mathscr{A}_{10}(z)
\displaystyle=\frac{1-zVC-8z+7z^{2}VC+21z^{2}-15z^{3}VC-20z^{3}+10z^{4}VC+5z^{4}-z^{5}VC}{1-zVC-9z+8z^{2}VC+28z^{2}-21z^{3}VC-35z^{3}+20z^{4}VC+15z^{4}-5z^{5}VC-z^{5}}.
Expanding, we get for example
\displaystyle\mathscr{A}_{5}(z)
\displaystyle=1+z+2{z}^{2}+5{z}^{3}+14{z}^{4}+(41+V){z}^{5}+(122+9V+{V}^{2}){z}^{6}
\displaystyle+(365+52V+11{V}^{2}+{V}^{3}){z}^{7}+(1094+247V+75{V}^{2}+13{V}^{3}+{V}^{4}){z}^{8}
\displaystyle+(3281+1053V+410{V}^{2}+102{V}^{3}+15{V}^{4}+{V}^{5}){z}^{9}
\displaystyle+(9842+4199V+1975{V}^{2}+629{V}^{3}+133{V}^{4}+17{V}^{5}+{V}^{6}){z}^{10}+\dots
3.
Final thoughts