DOI

Разбиением Л = (Ai, Л2,... ) называется последовательность неотрицательных целых чисел с конечным числом ненулевых компонент такая, что Ai > Л2 >.... Весом sum(A) разбиения Л называется сумма его компонент. Мы определяем два типа элементарных преобразований разбиений решётки разбиений NPL - перекидывание блока и удаление блока. Отметим, что разбиение Л = (Ai,A2,... ) доминирует разбиение ^ = (^i,^2,...) (пишем Л > р.) тогда и только тогда, когда ^ можно получить из Л с помощью конечной последовательности элементарных преобразований. Пусть Л и ^ два разбиения таких, что Л > ^. Высотой height(A, ^) разбиения Л над разбиением ^ называется число преобразований в кратчайшей последовательности элементарных преобразований, преобразующей Л в ^. Цель работы состоит в доказательстве следующих равенств height(A,^) = j=l,Xj >^j где C = sum(A) - sum(^). Кроме того, мы указываем алгоритм, который строит некоторые полезные кратчайшие последовательности элементарных преобразований от Л до ^.
Переведенное названиеON THE SHORTEST SEQUENCES OF ELEMENTARY TRANSFORMATIONS IN THE PARTITION LATTICE
Язык оригиналаРусский
Страницы (с-по)844-852
Число страниц9
ЖурналSiberian Electronic Mathematical Reports
Том15
DOI
СостояниеОпубликовано - 2018

    Уровень публикации

  • Перечень ВАК

    ГРНТИ

  • 27.45.00 Комбинаторный анализ. Теория графов

    Предметные области WoS

  • Математика

    Предметные области ASJC Scopus

  • Mathematics(all)

ID: 8587908