ON SEQUENCES OF ELEMENTARY TRANSFORMATIONS IN THE INTEGER PARTITIONS LATTICE

Abstract

An integer partition, or simply, a partition is a nonincreasing sequence \(\lambda = (\lambda_1, \lambda_2, \dots)\) of nonnegative integers that contains only a finite number of nonzero components. The length \(\ell(\lambda)\) of a partition \(\lambda\) is the number of its nonzero components. For convenience, a partition \(\lambda\) will often be written in the form \(\lambda=(\lambda_1, \dots, \lambda_t)\), where \(t\geq\ell(\lambda)\); i.e., we will omit the zeros, starting from some zero component, not forgetting that the sequence is infinite. Let there be natural numbers \(i,j\in\{1,\dots,\ell(\lambda)+1\}\) such that (1) \(\lambda_i-1\geq \lambda_{i+1}\); (2) \(\lambda_{j-1}\geq \lambda_j+1\); (3) \(\lambda_i=\lambda_j+\delta\), where \(\delta\geq2\). We will say that the partition \(\eta={(\lambda_1, \dots, \lambda_i-1, \dots, \lambda_j+1, \dots, \lambda_n)}\) is obtained from a partition \(\lambda=(\lambda_1, \dots, \lambda_i, \dots, \lambda_j, \dots, \lambda_n)\) by an elementary transformation of the first type. Let \(\lambda_i-1\geq \lambda_{i+1}\), where \(i\leq \ell(\lambda)\). A transformation that replaces \(\lambda\) by \(\eta=(\lambda_1, \dots, \lambda_{i-1}, \lambda_i-1, \lambda_{i+1}, \dots)\) will be called an elementary transformation of the second type. The authors showed earlier that a partition \(\mu\) dominates a partition \(\lambda\) if and only if \(\lambda\) can be obtained from \(\mu\) by a finite number (possibly a zero one) of elementary transformations of the pointed types. Let \(\lambda\) and \(\mu\) be two arbitrary partitions such that \(\mu\) dominates \(\lambda\). This work aims to study the shortest sequences of elementary transformations from \(\mu\) to \(\lambda\). As a result, we have built an algorithm that finds all the shortest sequences of this type.

Keywords

• integer partition, ferrers diagram, integer partitions lattice, elementary transformation