VI Международная студенческая научная конференция Студенческий научный форум - 2014

АБСТРАКТ

В работе рассматриваются разбиение натуральных чисел –комбинаторная трактовка оперирования натуральными числами и их суммами. Проведены и исследованы различные характеристики разбиений чисел и связанные сними другие задачи перечислительной комбинаторики. В частности исследованы сравнения двух различных разбиений находящиеся в соответствии по определенному правилу, а также были исследованы графические представления разбиение диаграммами Юнга.

В результате исследования авторами получены некоторые экстремальные характеристики разбиений чисел, и доказаны 2 теоремы. Приведены примеры с использованием полученных результатов.

Задача о разложений и таблицы Юнга

Разбиение. Говоря о натуральных числах, разбиение(англ. –partition) – это представление числа в виде суммы нескольких чисел: , где слагаемые называются частями, а количество слагаемых число —рангом разбиения, а само разбиение -разложением.

Очевидно, число можно представлять в виде суммы различными способами.

Композиция — это представление натурального числа упорядоченной суммой натуральных слагаемых. Таким образом, композиции можно рассматривать как «упорядоченные разбиения».

Таким образом, разбиение числа определяется как последовательность , такую, что и . Мы считаем, что два разбиение одинаковыми, если они отличаются только числом заключительных нулей, например . Неформально разбиение (где скажем ) можно рассматривать как способ представить в виде суммы положительных целых, игнорируя порядок слагаемых (так как существует единственный способ записи слагаемых в невозрастающем порядке, при котором мы не различаем равные слагаемые между собой). Если разбиение числа , то мы пишем: или .

Следовательно, и композиции, и разбиения можно понимать как упорядоченные и неупорядоченные мультимножества, элементы которых суть натуральные числа В соответствии с этим разбиения обычно изображают при помощи векторной записи

,

которая означает, что

,

или сокращенной записью

,

означающей, что часть наличествует в этом разбиении ровно раз, так что

,

и ранг этого разбиения равен

.

Таким образом, всякое разбиение можно представить в виде ,

где целое неотрицательное число, указывающее, сколько раз число присутствует в этом разбиении числа в виде части, т.е. и ранг этого разбиения. Например,

Мы также будем обозначать общее число разбиений , число разбиений имеющих в точности частей, число разбиений имеющих не более чем частей, наибольшая из которых не превосходит .

Например, для разбиениями являются:

ранга один: 6 = 6;

ранга два: 6 = 5 + 1, 6 = 4 + 2, 6 = 3 + 3;

ранга три: 6 = 4 + 1 + 1,6 = 3 + 2 + 1,6 = 2 + 2 + 2;

ранга четыре: 6 = 3 + 1 + 1 + 1, 6 = 2 + 2 + 1 + 1;

ранга пять: 6 = 2 + 1 + 1 + 1 + 1 + 1;

ранга шесть: 6 = 1 + 1 + 1 + 1 + 1 + 1 + 1.

Композициями для являются:

ранга один: 6 = 6;

ранга два: 6 = 5 + 1, 6 = 4 + 2, 6 = 3 + 3;

6 = 1 + 5, 6 = 2 + 4;

ранга три: 6 = 4 + 1 + 1,6 = 3 + 2 + 1,6 = 2 + 2 + 2,

6 = 1 + 4 + 1, 6 = 3 + 1 + 2,

6 = 1 + 1 + 4, 6 = 2 + 3 + 1,

6 = 2 + 1 + 3,

6 = 1 + 3 + 2,

6 = 1 + 2 + 3;

ранга четыре: 6 = 3 + 1 + 1 + 1,6 = 2 + 2 + 1 + 1,

6 = 1 + 3 + 1 + 1,6 = 2 + 1 + 2 + 1,

6 = 1 + 1 + 3 + 1, 6 = 2 + 1 + 1 +2,

6 = 1 + 1 + 1 + 3, 6 = 1 + 2 + 2 + 1,

6 = 1 + 2 + 1 + 2,

6 = 1 + 1 + 2 + 2;

ранга пять: 6 = 2 + 1 + 1 + 1 + 1,

6 = 1 + 2 + 1 + 1 + 1,

6 = 1 + 1 + 2 + 1 + 1,

6 = 1 + 1 + 1 + 2 + 1,

6 = 1 + 1 + 1 + 1 + 2;

ранга шесть: 6 = 1 + 1 + 1 + 1 + 1 + 1.

Здесь для разбиений

и т.д.

Примем соглашение, что .

1 Задача о разбиениях в заданном соответствии

Между разбиениями существует различные виды соответствий. Достаточно общий вид экстремальной задачи о разбиениях может быть сформулирован в виде вопроса: сколь много существует разбиений, состоящих в заданном соответствии? Выбор конкретного соответствия между разбиениями определяется условиями практической задачи, именно той, для которой разбиения с таким соответствием служат комбинаторной схемой. Поэтому далее мы вводим и рассматриваем такое соответствие между разбиениями, посредством которого решается широкий круг важных прикладных задач.

Экстремальные задачи о разбиениях чисел долгое время не составляли специального направления, однако отдельные основополагающие факты проявлялись и ранее. Полезно обратить внимание на один из них, именно на частный случай одной весьма общей теоремы, именуемой ныне в честь ее автора-английского логика Рамсея.

Пусть между разбиениямии определено соответствие по следующему правилу: разбиение находится в соответствии к разбиению , если найдется при котором , т.е. если во втором разбиении найдется часть, не превосходящая соответствующей части первого разбиения. Тогда спрашивается: Каково для заданного разбиения то наименьшее , при котором для каждого разбиения этого на частей будет выполняться соответствие ?

Можно поставить обратную задачу. Для данного разбиения вычислить наибольшее , каждое разбиение которого на частей будет обладать тем свойством, что.

Исследуем эти взаимно обратные задачи. 1) Значение не может быть меньше, чем , так как в этом случае нашлось бы разбиение, для которого требуемое соответствие не выполняется:

если же равно , то в любом разбиении всегда найдется часть , так как в противном случае все и, значит, получаем противоречивую систему неравенств

2) Значений не может быть больше, чем , так как в этом случае нашлось бы разбиение, для которого требуемое соответствие не выполняется:

Если же к равно , то и, следовательно, согласно предыдущему утверждению требуемому соответствию будут удовлетворять все разбиения ранга не только для разбиения , но вообще для всех разбиений ранга . Это означает, что если выражается по формуле (1’), то каждое разбиение ранга находится в заданном соответствии с каждым разбиением ранга . Таким образом мы доказали следующую теорему:

Теорема 1.Если для заданныхразбиенийи найдется при котором , то для разбиения наименьшее и для разбиения наибольшее при котором для каждого разбиения этого на частей будет выполняться соответствие , равны соответственно, и .

2 Задача о количестве путей диаграмм ЮНГА

Можно изображать разбиения натурального числа графически посредством точечных диаграмм, называемых графами Феррера, например,

Такие изображения удобны для представления различных преобразований разбиений. Например, если приведенную диаграмму повернуть, то получиться граф Феррера вида

отвечающий очевидно, разбиению (1, 3, 5, 6), которые называется сопряженным разбиению (1, 2², 3², 4).

Если заменить точки, поставив на их места квадраты, получившуюся диаграмму называют диаграммой Юнга(англ. –Youngtableaux, часто также называемые Диаграммы Феррара, англ.- Ferrar’sdiagrams или просто Ferrars) разбиения .

В силу коммутативности сложения, при разбиении интерес представляет только состав слагаемых, но не их порядок. Поэтому, например

и

принято считать одним и тем же разбиением, которого принято представлять в виде суммы невозрастающей последовательности слагаемых. Если считать единицу за базовый «строительный элемент» натуральных чисел,

то каждое число можно наглядно представить графически в виде кирпичиков-клеточек единиц, объединенных вместе. В частности диаграмма

Юнга представляют собой способ графического представления не только самого числа, но и его разбиения.

Идея такого представления очевидна из рисунка: число клеток в первой строке не имеющих под собой других клеток –есть число единиц в данном разбиения; число клеток в первой строке, имеющих под собой только одну клетку –есть число двоек в разбиении и т.д. Добавляя сюда требование, чтобы высота столбцов в каждой диаграмме могла разве что только увеличиваться при перемещении слева-направо, получим однозначное представление каждого разбиение натурального числа диаграммой Юнга. Договоримся далее, диаграмму состоящую из клеток будем называть диаграммой размера .

Понятно то, что каждая диаграмма размера может быть получена путем добавления к одной из диаграмм размера дополнительной клетки справа в одной из строк. Рассмотрим следующий пример диаграммы Юнга:

Из этого примера видно, что диаграмм «предшественниц» может быть несколько!

Безусловно, при добавлении клетки начиная со второй, надо следить тем, чтобы над добавленной клетки не было пустого пространства.

Юнга для выглядит следующим образом:

Пусть -множество диаграмм Юнга из клеточек. Давайте для удобства рассмотрения объединим все диаграммы Юнга соответствующих для различных в так называемый граф Юнга.

Он начинается пустой диаграммы, т.е. диаграммы без клеточек, дальше диаграмма с одной клеточки, далее с диаграммы с двумя клеточками и т.д. Диаграммы с клеточками различаются от строения этих самих клеточек.

Основное правило построения графа Юнга: ребро от предыдущей диаграммы к следующей проводится, если следующая получается от предыдущей с добавлением клеточки (рис. 1).

Рис.1 Граф путей диаграмм Юнга до размерности N=4.

Легко заметить, что если продолжать построение графа, то крайними слева всегда будут стоять диаграммы, соответствующие разбиению

,

а справа разбиению

.

Из вершины графа в такие диаграммы будет вести всегда только один путь. В то же время для диаграмм одного размера, наибольшим числом путей, очевидно, будут характеризоваться диаграммы расположенные ближе к центру в соответствующем ярусе графа.

Очевидно, в случае нечетного размера максимальное число путей будет иметь одна диаграмма, а в случае четного размера - две.

Если теперь попытаться ввести вероятностную меру для диаграмм одного и того же размера, то логично было бы придать большую вероятность тем диаграммам, в которые ведет большее число путей, то есть лежащим ближе к центру. Действительно, если начать двигаться вниз по графу начиная с вершины, и произвольным образом но с равной вероятностью выбирать на каждом ярусе путь направо или налево, то после конечного числа шагов мы с большей вероятностью попадем в одну из диаграмм центральной части яруса, нежели чем в диаграмму расположенную на «периферии». В этой работе нас прежде всего будет интересовать вопрос: среди всех диаграмм заданного размера N какую форму будет иметь диаграмма имеющая наибольшее число ведущих в нее путей? Везде далее, если мы хотим подчеркнуть размер диаграммы λ, будем обозначать ее . Также, введя обозначение для числа путей ведущих в диаграмму как (размерность диаграммы), определим так называемую меру Планшереля, которой и будем пользоваться в дальнейшем:

(1)

Для получения возможности вычисления размерности dim λ, снова обратимся к построению диаграмм путем добавления клеток. Если, спускаясь вниз по графу к выбранной диаграмме λ, мы будем каждый раз нумеровать вновь добавляемые клетки, увеличивая на каждом этапе спуска нумерацию на единицу, то получим новое обозначение диаграмм с точностью до ведущего в них конкретного пути (рис. 2) .

Рис.2-Два различных пути построения диаграммы размерности N=6

Легко заметить, что при такой нумерации добавляемых клеток, в каждой построенной диаграмме при следовании по строке слева-направо и по столбцу сверху-вниз, номера могут только возрастать.

Последнее понятие, которое нам понадобится на начальном этапе это понятие – крюка (угловая длина).

Крюком клетки в диагамме λ являтся сама клетка, а также все клетки, расположенные от нее справа в той же строке и снизу в том же столбце. Соответственно, длиной крюка клетки называется число составляющих этот крюк клеток. В дальнейшем длину крюка клетки будем обозначать как h() (англ.- hook). На Рисунке 3 показан пример крюка одной из клеток диаграммы размера N=33.

Рис.3 -Пример крюка длины h=10

Теорема 2.Число путей dim λ, ведущих в диаграмму заданной формы и размера N равно

dim λ= N!h()(2)

где в знаменателе стоит произведение длин крюков всех клеток диаграммы.

Т.е. количество заполнений таблицы (диаграммы) равно факториалу количества её клеток, делённому на произведение длин всех её крюков.

Доказательство: Наше доказательство основано на свойствах анти симметрических многочленов.

Сначала введём удобные обозначения. Обозначим буквой количество строк рассматриваемой таблицы; —их длины, причём нумеруем сверху вниз: первая строка самая длинная, вторая той же длины или короче первой, и так далее: . Например, для таблицы рисунка 4 имеем:

Рис. 4

Длина крюка верхней левой (угловой) клетки равна . Длина крюка клетки, расположенной непосредственно под ней, равна . Вообще, длина крюка m-й сверху клетки левого столбца равна . Очевидно, последовательность длин крюков строго убывающая: .

Крюки клеток первой строки и левого столбца:

Среди длин крюков верхней строки рисунка 4 отсутствуют числа 5, 10, 11, 15, 18,19, 20, 21 и 22. И вот что интересно: 28−23=5, 28−18=10, 28−17=11, 28−13=15, 28−10=18, 28−9=19, 28−8=20, 28−7=21, 28−2=26 и 28−1=27.

Лемма 3. Среди длин крюков клеток верхней строки присутствуют все числа от 1 до , кроме разностей , где .

Идея доказательства. При движении вдоль верхней строки рисунка 4 справа-налево сначала длины крюков — последовательные числа 1, 2,3 и 4. Первое отсутствующее число — 5. Разность количества клеток крюка длины 28, состоящего из всех клеток верхней строки и левого столбца, и синего крюка длины 23 равна количеству зелёных клеток — числу 5.

Разность между числом 28 и числом 8 — количеством клеток синего крюка рисунка 5 — равна количеству зелёных клеток этого рисунка. Дальше все понятно.

Рис. 5

Вывод новой формулы крюков

Вследствие леммы 3, произведение длин крюков первой строки таблицы равно числу , делённому на произведение .

Отбросив верхнюю строку исходной таблицы, мы получаем новую таблицу, к верхней строке которой, т.е. второй строке исходной таблицы — применима та же лемма. Таким образом, длины крюков второй строки—числа от 1 до , кроме разностей , где . Рассуждая так же для третьей, четвёртой и всех следующих строк, приходим к выводу: произведение длин крюков всех клеток таблицы равно произведению факториалов , делённому на произведение всевозможных разностей , где .

Поэтому формула крюков означает, что интересующее нас количество расстановок равно величине

(*)

где

.

Умножение на нуль

В числителе дроби F присутствуют все разности вида . Поэтому величина равна нулю, если в последовательности есть совпадающие числа: при .

Учитывая, что этого не должно происходить. Тем не менее, вышесказанное — истина, хотя вам наверняка пока кажется, что она не ко двору.

Сформулируем это свойство функции F чуть иначе. Поменяем местами и .

Разность заменится на , а другие множители числителя и знаменателя поменяются друг с другом местами или останутся неизменными. Значит,

.

Немного подумав, можно понять, что величина F меняется на противоположную не только при замене на и на , но и при перестановке любых двух аргументов — так называемой транспозиции. Такие функции F называют антисимметрическими.

Симметрическими называют функции, не меняющие своё значение ни при какой перестановке аргументов.

Вычитание нуля. Пусть . (Мы помним, что такого не бывает. Но хотим рассмотреть эту ситуацию — может пригодится!) Поскольку

и

то,

_.

Индукционный переход

Для и формула крюков тривиальна: .

Применим индукцию.

Предположив, что формула крюков верна для всех таблиц, состоящих из клеток, докажем её для клеточной таблицы. Для этого воспользуемся приёмом, который мы уже обсуждали— отбрасыванием клеток.

Рассмотрим следующую таблицу из 13 клеток:

Рис.6 –Таблица из 13 клеток с указанием возможного расположение 13-ой клетки

7А)

7Б)

7В)

7г)

Рис.7-Таблицы из 12 клеток потенциальные «предшественники» таблицы из рис.6.

Переход от таблицы рисунка 6 к таблицам рисунка 7 соответствуют формуле

F(9,6,4,3,1)=F(9,5,4,3,1)+F(8,5,3,2)+F(8,6,4,3,1)+ F(9,6,4,2,1)

Поскольку

F(8,5,3,2)= F(9,6,4,3,0)

и

F(9,6,3,3,1)=0

F(9,6,4,3,1)=F(8,6,4,3,1)+F(9,5,4,3,1)+F(9,6,3,3,1)+

+F(9,6,4,2,1)+F(9,6,4,3,0)

По очереди каждый аргумент уменьшаем на 1. В общем виде формула такова:

(1)

В правой части k слагаемых: мы как бы по очереди отбрасываем из каждой строки её самую правую клетку (хотя, на самом деле следует отбрасывать самые правые клетки не из всех подряд строк, а только те, под которыми нет клеток таблицы,— «лишние» слагаемые всё равно нулевые).

Лемма 2. Если функция F антисимметрична, то антисимметрична и функция

Доказательство. Меняя местами и , получаем

Очевидно,

При любой другой транспозиции ситуация аналогична.

Лемма доказана.

Теперь, учитывая равенство

разделив обе части (1) на и умножая на , приходим к

(**)

Здесь принципиально то, что вследствие леммы 2 правая часть (∗∗) — антисимметрический многочлен от так, что правая часть делится на всевозможные разности этих переменных, а частное от деления — симметрический многочлен первой степени. (Первой —поскольку степень правой части больше степени левой части вследствие наличия множителей соответственно в каждом из слагаемых правой части.)

Коэффициент при в правой части формулы (∗∗) равен произведению , а коэффициент при в многочлене ровно такой же.

Следовательно,

где величина a зависит только от k, а не от .

Сделаем последний шаг — обосновать равенство : поскольку для любого натурального k формула крюков верна для столбика высотой k, то для обеспечения правильного перехода от столбика высотой k−1 к столбику высотой k величина a соответствует.

Таким образом

dim λ= N!h()(2)

где величина в знаменателе - теорема доказана.

Связь между максимальным числом инверсий перестановок из чисел и количеством диаграмм Юнга из клеток: .

Вывод

Комбинаторные методы оказываются полезными не только для формализации и решения ряда инженерных задач, но и других прикладных задач.

Получены следующие результаты: 1) Решена задача о разбиении в данном соответствии;

2) решена задача о количестве путей диаграммы Юнга.

Результаты работы сформулированы в виде теорем и предложений.

СПИСОКИСПОЛЬЗОВАННОЙЛИТЕРАТУРЫ

1. Combinatorics of permutations. M. Bona. University of Florida Gainesville, Florida, USA./ Discrete mathematics and its applications. Series Editor Kenneth H.Rosen.-Taylor end Francis GROUP, 2012.

2. A Probabilistic Proof of a Formula for the Number of Young Tableaux of a Given Shape // Department of Mathematics, University of Pennsylvania, Philadelphia, Pennsylvania 19174// Advances in mathematics 31, 104-109 (1979).

1. Дональд Кнут (Donald E. Knuth). Искусство программирования. Том 1,2,3. М. "Вильямс", 2007 г.

Код для цитирования: Скопировать