1 Dyck Numbers I. Successor Function Gennady Eremin
2025-04-28
5
0
196.71KB
11 页
10玖币
侵权投诉
1
Dyck Numbers, I. Successor Function
Gennady Eremin
ergenns@gmail.com
October 3, 2022
Abstract. Dyck paths are among the most heavily studied Catalan families. In the paper we
are dealing with the minimal numbering of Dyck paths, with the resulting numbers, the terms
of the OEIS sequence A036991, which we have called Dyck numbers. We consider the suc-
cessor function on the Dyck numbers, closed formulas are obtained. In particular, the formula
for the successor of the Mersenne number is calculated (since OEIS A000225 is a subset of
A036991). We have obtained the corresponding algorithm of the Dyck successor function,
DS-function, and a Python program has been compiled. At the end of the paper, the size of
the A036991 ranges is associated with the terms of OEIS A001405. The corresponding hy-
pothesis is formulated.
Keywords: numbering, Dyck path, Dyck word, OEIS, successor function.
1 Introduction
Dyck paths are among the most heavily studied Catalan families [1]. In the paper we are
dealing with the numbering of Dyck paths, with the resulting numbers, which we have
called the Dyck numbers. In computability theory, numbering is the assignment of natural
numbers to a set of objects, such as functions, graphs, words in some formal language,
etc. We can say that numbering is a numerical ordering of objects that makes it easier to
refer to them.
The Dyck alphabet includes two characters: up step U = (1, 1) and down step
D = (1, –1) (in the case of bracket expressions, we are dealing with left and right paren-
theses, respectively). In Dyck word, the characters of the alphabet are precisely balanced;
in such words, Dyck dynamics are observed [2]. Each Dyck path has the same number of
U's and D's, and this is the first rule of Dyck dynamics. Any up step has a matching down
step and they must be correctly nested.
The second rule of Dyck dynamics is as follows: in any initial fragment of Dyck path
(aka Dyck word prefix), the number of U's is at least the number of D's. Zoltan Kasa pro-
posed a simple formula for the second rule (see [3], p. 111). Let the Dyck word have
length 2n (there are n U's and n D's); in this case, the i-th down step, di , satisfies the ine-
quality
2i ≤ di ≤ n + i, 1 ≤ i ≤ n.
We get the Dyck path numbering if we simply encode the words in the binary alphabet
{0, 1}. The On-Line Encyclopedia of Integer Sequences (OEIS, [4]) has a sequence of
binary numbers A063171, which is obtained by encoding Dyck words in the following
way: the up step is replaced by 1, and the down step is replaced by zero. Here is the be-
2
ginning of the A063171 (terms sorted in ascending order, initial term 0 corresponds to the
empty Dyck path):
0, 10, 1010, 1100, 101010, 101100, 110010, 110100, 111000, 10101010 …
As you can see, all terms are even (multiples of 2, binary suffix 0). The OEIS sequence
A014486 shows the decimal representations of the binary codes:
0, 2, 10, 12, 42, 44, 50, 52, 56, 170, 172, 178, 180, 184, 202, 204, 210 …
In this paper, we will be interested in the reverse binary encoding of Dyck words, the
OEIS sequence A036991. In this sequence, we get much smaller natural numbers (some-
thing like the minimal numbering), all terms are odd, among which there are many prime
numbers.
We consider a significant group (bush) of OEIS sequences associated with A036991.
Two sequences of such a bush are developed by the author, these are A350346 and
A350577.
2 Minimal numbering of Dyck paths
In conventional decimal expansion, the reverse Dyck path (or Dyck word) codes are
shown in OEIS A036991 in ascending order. Here is the beginning of the A036991:
0, 1, 3, 5, 7, 11, 13, 15, 19, 21, 23, 27, 29, 31, 39, 43, 45, 47, 51, 53, 55 …
The reverse binary encoding of Dyck words is OEIS A350346: the up step is replaced
by 0, and the down step is replaced by 1. Here are the first A350346 terms (leading zeros
are shown in small print):
0, 01, 0011, 0101, 000111, 001011, 001101, 00001111, 010011, 010101, 00010111 …
In natural numbers, it is customary to omit leading zeros (as in any number system).
Without leading zeros, binary codes are greatly reduced:
(1) 0, 1, 11, 101, 111, 1011, 1101, 1111, 10011, 10101, 10111, 11011, 11101 …
And again, in sequence (1), the initial null term corresponds to an empty Dyck path (or
an empty Dyck word).
More often we will work with binary strings. Each non-zero A350346 term starts and
ends with unit, so there are fewer zeros than units. Obviously, there is no need for the
first rule of Dyck dynamics, since in any binary string it is possible to restore the leading
zeros and by recoding back get the corresponding Dyck path. Therefore, we can simplify
the Dyck dynamics. It all comes down to a single rule: in each final fragment (suffix) of
the binary code, the number of 0’s does not exceed the number of 1’s. Further, working
with numerical sequences, we will adhere to exactly this formulation of the Dyck dy-
namics.
3
It is easy to see that Kasa's formula will take the following form for the position of the
i-th zero in the binary code, zi (recall that in integers, digits are numbered from right to
left, starting from 0):
2i – 1 ≤ zi ≤ n + i – 1, 1 ≤ i ≤ n.
In each binary term, the number of leading zeros varies from 1 to n (assuming the corre-
sponding Dyck word has length 2n). Without leading zeros the length of such terms var-
ies from n to 2n-1.
Thus, using OEIS A036991, we get hopefully the minimal numbering of Dyck paths.
At the moment, there is no more suitable numbering option. For example, in [5], for each
natural number, based on prime factorization, the correct bracket sequence is calculated
(among other things, here huge natural numbers correspond to compact Dyck words). In
our case, in A036991, each Dyck word corresponds to a certain natural number; but for
most natural numbers there are no corresponding Dyck paths. Now we can formulate an
obvious definition.
Definition 1. A Dyck number is a natural number, in the binary expansion of which in
each suffix the number of zeros does not exceed the number of units.
The following statement is obvious.
Proposition 2. There is a one-to-one correspondence (bijection) A036991 and the set of
Dyck paths.
Dyck numbers are fairly common in the OEIS. The author found more than twenty
numerical sequences, the terms of which are either Dyck numbers or are associated with
the A036991 in some way. We can say that we are dealing with an extensive bush of in-
terconnected sequences. There are hundreds of thousands of sequences in the OEIS, and
the author believes that the interested reader can add my list.
Further in the formulas, we will try to adhere to the notation adopted in the OEIS. For
example, a(n) is the n-th term of the current sequence, * is a multiplication, ^ is a power,
sqrt is the square root, etc. Binary expansion can be considered as strings (or words), in
this case the concatenation operation is convenient, let’s denote it ∘. Grouping of repeated
fragments of words is possible, for example,
10111112 = 10∘15, 111011011011012 = 11∘101∘101∘101∘101 = 11∘ (101)4.
For many sequences in the OEIS, the following recurrent formula is true:
(2) a(n+1) = 2^s * a(n) + t,
where s is a non-negative integer, and t is an arbitrary integer (possibly negative).
For example, for odd natural numbers (OEIS A005408), we get a well-known recurrent
formula a(n+1) = a(n) + 2 if we take s = 0 and t = 2.
In sequence (1), the terms are arranged in order of increasing length of the binary
code. A group of terms of the same length is often called a range. For example, in the
4-th range there are three binary terms of length 4: 1011, 1101 and 1111.
In each range, the last binary term is a repunits (repeating units) [7], a term from OEIS
A002275: 0, 1, 11, 111, 1111 … Here the Dyck dynamics is observed, since binary re-
摘要：
展开>>
收起<<
1DyckNumbers,I.SuccessorFunctionGennadyEreminergenns@gmail.comOctober3,2022Abstract.DyckpathsareamongthemostheavilystudiedCatalanfamilies.InthepaperwearedealingwiththeminimalnumberingofDyckpaths,withtheresultingnumbers,thetermsoftheOEISsequenceA036991,whichwehavecalledDycknumbers.Weconsiderthesuc-ce...
声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！
分类：图书资源
价格：10玖币
属性：11 页
大小：196.71KB
格式：PDF
时间：2025-04-28
作者详情
-
Voltage-Controlled High-Bandwidth Terahertz Oscillators Based On Antiferromagnets Mike A. Lund1Davi R. Rodrigues2Karin Everschor-Sitte3and Kjetil M. D. Hals1 1Department of Engineering Sciences University of Agder 4879 Grimstad Norway10 玖币0人下载
-
Voltage-controlled topological interface states for bending waves in soft dielectric phononic crystal plates10 玖币0人下载
渝公网安备50010702506394
