Gennady Eremin.  Discrete Mathematics. 

Russian version



Visitors to the site are offered the author's work in discrete mathematics. The material is original; the research was carried out in several directions.

First, it was interesting to factorize (decompose into simple divisors) the Catalan number and its "twin brother" – the Central binomial coefficient. Many special numbers are factorized; Catalan numbers are also interesting for modern mathematicians.

In the canonical decomposition of the Catalan number, the Prime odd divisors are distributed by Legendre's layers. In each layer, dividers are grouped into Chebyshev's segments. If we remove the most numerous first layer in the decomposition, we obtain an element of the sequence A246466 in OEIS.

Another direction is related to the study of lexicographic (non-numeric) series. Formal features of such series are considered. As examples, we consider bracket sequences consisting of Dyck words (Dyck series) and truncated Motzkin words (Motzkin series).

The analysis of the dynamics of the correct bracket sequences allowed us to obtain a four-dimensional Dyck triangle, which is a generalization of the known two-dimensional constructions.

The last articles examine some aspects of number theory. Using the Legendre's formula, the analysis of the p-adic valuation of a natural number are obtained and the increment evaluation. The odd factorial valuation is calculated. The interrelations between p-adic valuation and p-adic weight are considered. We described the operations defined on the increments of valuation and weight.

On this site, the material is often accompanied by a software service to check results. Some programs allow the reader not only to perform the control calculations, but also to conduct independent research. The programs are compiled by the author. I will try to give detailed answers to all interested readers, my e-mail The use of site materials is welcome.

Prime Factorization and p-adic analysis

2019. Layers in decomposition of Catalan number, Kummer’s theorem and sequence A246466. Kummer’s theorem is modified for Catalan numbers. In canonical decomposition of Catalan number, odd primes are distributed in Legendre’s layers. In each layer, primes are grouped into Chebyshev’s segments. If we remove the first Legendre’s layer, we obtain an element of the sequence A246466 in OEIS. In the paper, there is software online service (see Russian version)

2019. Legendre’s formula and the p-adic analysis. Legendre's formula calculates the p-adic valuation of n! as the sum of partial quotients. Another alternative formula uses the p-adic weight of n, i.e. the sum of digits of n in base a prime p. Both kinds of Legendre’s formula allow us to determine valuations of the natural number, the odd factorial, Catalan numbers, and other combinatorial objects. The article examines the relationship between the p-adic valuation and weight and considers their increments. (see Russian version)

2019. Legendre's formula. A simple arithmetic proof of classical (alternative) Legendre's formula is described. (see Russian version)

2016. Factoring a Catalan Number into Chebyshev’s Segments. This paper describes the "cutting" of the Catalan number decomposition in Chebyshev’s segments. (see Russian version)

2016. Multilayer Factorization of Catalan Numbers (see also Odd prime factors are distributed in layers. In each layer the noncrossing segments contain only non-repeated primes. (see Russian version)

2016. Interval Factorization of Middle Binomial Coefficients. Prime factors and prime powers are distributed in layers. Each layer consists of non-repeated prime numbers which are chosen (not calculated!) from the noncrossing prime intervals. (see Russian version)

2015. Prime factorization of Catalan numbers. For the Catalan number, the vast majority of Prime divisors (up to 99.9%) are chosen from fixed intervals of the prime number list. In this work, the reader can factorize an arbitrary Catalan number by its index. (In Russian)

Lexicographic Sequences

2017. Dynamics of Balanced Parentheses, I. Dyck Squares. The article deals with a strict lexicographic order on the set of balanced parentheses. A strict order generates procedures for identification, indexing, and reconstruction of balanced parentheses. On-line software service is offered to calculate or check some results.

2015. Правильные скобочные последовательности и полиномы Дика. Скобочные наборы выстроены в ряд Дика, структурированный аналогично натуральному ряду. Рассмотрены процедуры идентификации элементов ряда. Описаны полиномы Дика и полиномиальная матрица как эквивалент треугольника Дика.

2014. Motzkin Word Row. We consider the lexicographic sequence of truncated Motzkin words. The navigation procedures for the series are described. On-line software service is offered. (see Russian version)

Four-dimensional Catalan's lattice

2018. 4D Catalan’s Lattice. We consider a four-dimensional integer lattice, the projections of which are well-known Catalan objects. (see Russian version)

2018. Dyck Paths in Four-Dimensional Space. In analyzing balanced parentheses, we consider a group of related variables in Dyck paths. In the 4D space, the Dyck triangle is constructed – an integer lattice with Dyck paths. (see Russian version)

2017. Dynamics of Balanced Parentheses, II. 4D Dyck Triangle and Its Projections. The paper shows that the classic Dyck triangle, the Catalan triangle, and the Catalan convolution matrix are 2D projections of some 4D lattice.

Works of bygone years (Oriented graphs and programming)

1976. Компоновка пакетов прикладных программ. // Программирование. — 1976. — № 2. — С. 71–76. Рассматривается задача компоновки системы программных модулей (пакетов прикладных программ). Задача сведена к выделению вложенных и независимых связных областей в системе ориентированных графов. Разработаны соответствующие алгоритмы.

1986. Мониторная система для пакетной обработки заданий в ОС ЕС. // Программирование. — 1986. — № 6. — С. 48–56. Описан ППП МОНИТОР, обеспечивающий выполнение отдельного задания или их цепочек, оперативную корректировку текстов операторов языка управления заданиями. В системе предусмотрены средства для автоматической привязки (адаптации) внедряемых программных средств к условиям функционирования эксплуатируемых задач.

1987. Разбиение произвольного множества вершин бесконтурного opграфа на выпуклые подмножества. // Автоматика и телемеханика. — 1987. — № 8. — С. 137–143. Решается задача разбиения вершин ориентированного графа на выпуклые подмножества, которая встречается при проектировании системы задач. Исследуются "вогнутые" множества вершин орграфа, приведены алгоритмы.

1988. Язык технологических схем. // Программирование. — 1988. — № 1. — С. 19–25. В статье рассматривается технологический язык высокого уровня для пакетной обработки заданий в ОС ЕС. Транслятор языка схем составлен на ПЛ/1 и работает в ОС ЕС версии не ниже 6.1 (режимы MVT и SVS).

1989. Алгоритм разбиения невыпуклого множества вершин орграфа. // Автоматика и телемеханика. — 1989. — № 9. — С. 187–190. Исследуются эквивалентные преобразования бесконтурного графа, упрощающие разбиение невыпуклого множества вершин на выпуклые подмножества. Описан алгоритм минимизации разреза графа.

1989. Об одном вершинном разбиении на ориентированных графах (соавтор Цурков В. И.). Моделирование и экспертные системы, Межвуз. сб. науч. тр. МИРЭА Москва, с. 56-63.

1990. Алгоритм перебора групп элементов. // Известия РАН. Техническая кибернетика. — 1990. — № 4. — С. 221–223.