|
Эта публикация цитируется в 5 научных статьях (всего в 5 статьях)
Дискретная математика и математическая кибернетика
О кратчайших последовательностях элементарных преобразований в решетке разбиений натуральных чисел
В. А. Баранский, Т. А. Сеньчонок Ural Federal University,
pr. Lenina, 51,
620083, Ekaterinburg, Russia
Аннотация:
A partition $\lambda= (\lambda_1, \lambda_2, \dots)$ is a sequence of non-negative integers (the parts) in non-increasing order $\lambda_1\geq\lambda_2\geq\dots$ with a finite number of non-zero elements. A weight of $\lambda$ is the sum of parts, denoted by $\mathrm{sum}(\lambda)$. We define two types of elementary transformations of the partition lattice $NPL$. The first one is a box transference, the second one is a box destroying. Note that a partition $\lambda= (\lambda_1, \lambda_2, \dots)$ dominates a partition $\mu= (\mu_1, \mu_2, \dots)$, denoted by $\lambda\geq\mu$, iff $\mu$ is obtained from $\lambda$ by a finite sequence of elementary transformations.
Let $\lambda$ and $\mu$ be two partitions such that $\lambda\geq\mu$. The height of $\lambda$ over $\mu$ is the number of transformations in a shortest sequence of elementary transformations which transforms $\lambda$ to $\mu$, denoted by $\mathrm{height}(\lambda, \mu)$. The aim is to prove that $$\mathrm{height}(\lambda,\mu)= \sum^\infty_{j=1,\lambda_j>\mu_j}(\lambda_j-\mu_j)= \frac{1}{2}C+\frac{1}{2}\sum^\infty_{j=1}|\lambda_j-\mu_j|,$$ where $C=\mathrm{sum}(\lambda)-\mathrm{sum}(\mu)$. Also we found an algorithm that builds some useful shortest sequences of elementary transformations from $\lambda$ to $\mu$.
Ключевые слова:
integer partition, lattice, Ferrer's diagram.
Поступила 20 июня 2018 г., опубликована 14 августа 2018 г.
Образец цитирования:
В. А. Баранский, Т. А. Сеньчонок, “О кратчайших последовательностях элементарных преобразований в решетке разбиений натуральных чисел”, Сиб. электрон. матем. изв., 15 (2018), 844–852
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/semr959 https://www.mathnet.ru/rus/semr/v15/p844
|
|