RUS  ENG
Полная версия
ЖУРНАЛЫ // Сибирские электронные математические известия // Архив

Сиб. электрон. матем. изв., 2018, том 15, страницы 844–852 (Mi semr959)

Эта публикация цитируется в 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.

УДК: 519.165

MSC: 05A17

Поступила 20 июня 2018 г., опубликована 14 августа 2018 г.

DOI: 10.17377/semi.2018.15.072



Реферативные базы данных:


© МИАН, 2024