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