Леонард Ейлер (1707-1783). Портрет роботи Я. Е. Хандманна, 1753 р Зображення з сайту ru.wikipedia.org
Теорема Ейлера.Колічество розбиття числа N на попарно різні складові ( «суворі розбиття») дорівнює кількості розбиттів N на непарні складові ( «непарні розбиття»).
У підказці був зазначений спосіб, що дозволяє отримати з будь-якого суворого розбиття непарне. Для цього кожне парне число, що входить в розбиття на різні складові, потрібно було розділити навпіл, тобто представити у вигляді суми двох рівних половинок. А потім повторювати цей процес до тих пір, поки парних чисел не залишиться.
Наприклад, з розбиття 75 = 18 + 15 + 13 + 9 + 8 + 7 + 4 + 1 вийде 15 + 13 + 9 3 +7 + 1 13. де верхні індекси означають зведення в ступінь, а кількість повторень доданка (тобто фактично є множником, але в математичній літературі про розбитті усталене саме таке позначення).
Щоб довести взаємну однозначність такого відповідності, тепер потрібно пояснити, як по непарному розбиття (наприклад, 15 + 13 + 9 3 + 7 + 1 13) відновити вихідне суворе. З тими непарними числами, які зустрічаються лише один раз, все зрозуміло - вони були і в вихідному розбитті. А ось з чого вийшло 9 3. Так як число повторень непарній, то саме число 9 у разі необхідності розділення було. Крім нього, залишається ще 9 2. яке могло бути отримано тільки з числа 18. Отже, ми відновили, що 9 3 ← (9, 18). Подібним же чином можна послідовно розібратися і з 1 13:
1 13 ← (1, 2 6) ← (1, 4 3) ← (1, 4, 4 2) ← (1, 4, 8).
Ви вже зрозуміли закономірність? Вона настільки ж проста, як і красива: кожен «показник ступеня» записується у вигляді суми різних ступенів двійки (тобто виписується його двійковий запис), після чого кожної з наявних ступенів відповідає своє доданок в вихідному «строгому» розбитті. Це стає зовсім зрозумілим, якщо збагнути, що з одного парного доданка в строгому розбитті могли вийти тільки 2, 4, 8, 16 і т. Д. Непарних - тобто «внесок» кожного доданка в загальна кількість завжди є ступенем двійки, а так як рівних доданків немає, то все ступеня виявляються різними.
Джеймс Уітбред Лі Глейшер (1848-1928). Зображення з сайту ru.wikipedia.org
Це чудове відповідність було придумано в кінці XIX століття англійським математиком Джеймсом Уітбред Лі Глейшер (на жаль, його наукові результати в основному стосувалися областей математики, які не вивчаються ні в середній школі, ні навіть в нематематичних вузах, тому широкому загалу він абсолютно невідомий). Проте він був удостоєний двох дуже важливих математичних нагород свого часу - медалі де Моргана в 1908 році (це найвища нагорода Лондонського математичного товариства, присуджується раз на три роки) і медалі Сильвестра в 1913 році (вища нагорода Лондонського королівського товариства).
У задачі про непарних розбитті заслуга Глейшер в тому, що він придумав не тільки новий підхід до вирішення, але і дав чудове узагальнення завдання:
Теорема Глейшера.Колічество розбиття цілого числа N на частині, що не діляться на число d, дорівнює кількості розбиттів N на складові, в яких жодна частина не повторюється d або більше разів.
Але розповідь про відповідності між непарними і строгими розбивками був би свідомо неповним без згадки іншого чудового відповідності між ними, придуманого Джеймсом Джозефом Сильвестром (тим самим, в честь якого названа згадана вище медаль).
Джеймс Джозеф Сильвестр (1814-1897). Зображення з сайту ru.wikipedia.org
Сильвестр був, мабуть, першим математиком, який досліджував розбиття чисел на складові за допомогою картатих картинок. Згодом ці картинки отримали назву «діаграми Юнга» або «діаграми Феррерс» на честь двох інших британських математиків, молодших сучасників Дж. Сильвестра.
Нехай є розбиття на непарні складові. Сильвестр пропонував намалювати діаграму, в якій цим доданком відповідають горизонтальні ряди (рядки), причому розташовувати ці ряди симетрично щодо центру (це можна зробити саме завдяки непарності всіх доданків, рис. 1). А для встановлення відповідності він розглядав «гаки», які на малюнку 1 зображені чергуються кольоровими рядами. Перший гак йде знизу по центральному ряду до верхнього рядка, а потім продовжується по цьому рядку вправо. Наступний гак - по сусідньому зліва ряду знову до верхнього рядка, а потім по першому рядку у крайнє ліве положення. Потім - знову гак справа, але вже до другого рядка, і так далі. У підсумку виходить вже знайоме нам по відповідності Глейшер розбиття (18, 15, 13, 9, 8, 7, 4, 1). Чи не правда, красиво? На жаль, настільки ж красивого зворотного відповідності Сильвестр не дав. Замість цього він просто привів алгебраїчне доказ того, що таке відповідність є взаємно-однозначним.
До слова, Сильвестр не обмежився одним новим відповідністю, а попутно в тій же роботі довів і кілька інших нових фактів про непарні і строгі розбиття. Зокрема, він виявив відповідність між непарними розбивками, що містять рівно k різних чисел, і розбиття на різні числа, що містять рівно k «ланцюжків» - підпослідовностей з йдуть підряд натуральних чисел. Це привело його до наступній теоремі.
Теорема Сильвестра (1882) .Кількість розбиття числа N на непарні частини, серед яких рівно k різних чисел, дорівнює кількості розбиттів N на різні частини, в яких зустрічаються рівно k ланцюжків.
Ясно, що вихідний результат Ейлера виходить в якості слідства з теореми Сильвестра - простим додаванням по всьому k.
Намалюємо картинку розбиття на різні частини, почавши з самих маленьких частин, тобто з одиниці: 1 + 4 + 7 + 8 + 9 + 13 + 15 + 18 (рис. 2). Якщо кількість частин непарній, то в якості найменшої частини додамо 0. Першу частину помістимо в перший рядок, другу - в рядок під нею, причому вирівнявши її по лівому краю першого рядка. Третю частину помістимо в третій рядок, але вирівняємо її з другим рядком по правому краю, і так далі, чергуючи вирівнювання по лівому і на правому краях. Так як всі частини різні, то в результаті все вертикальні краю (і ліві, і праві), крім останнього, будуть мати висоту 2.
Крім того, намалюємо жирну вертикальну риску - роздільник - на відстані від правого краю, рівному Знакозмінні сумі частин d = 18 - 15 + 13 - 9 + 8 - 7 + 4 - 1 = 11. Тоді всі стовпці правіше роздільник містять непарне число клітин ( адже кожна вертикаль складається з однієї нижньої рядки і парного числа інших рядків) і можуть розглядатися як сума непарних доданків: 7 + 7 + 7 + 5 + 3 + 3 + 3 + 3 + 1 + 1 + 1 (ці числа підписані в першому ряду під діаграмою, праворуч від роздільника). При цьому всі послідовні непарні числа від 1 до 7 зустрічаються хоча б один раз. Отже, до 1 можна додати число клітин в парі нижніх рядків зліва від роздільника (тобто 14), до 3 - число клітин в парі наступних рядків (10), до 5 - клітини з наступної пари (8), а до 7 - клітини останньої пари рядків (2). Ці складові підписані у другому рядку під діаграмою. Нарешті, в третьому рядку виписані суми першої та другої рядки - теж непарні, оскільки вся друга рядок складається з парних чисел. Ясно, що кожна клітина діаграми врахована рівно один раз - клітини правіше роздільник увійшли в доданки першого рядка. А клітини лівіше роздільник увійшли в доданки другого рядка. Тим самим ми отримали відповідність між різними складовими і непарними складовими, причому - те ж саме відповідність, яке було запропоновано Сильвестром.
А як побудувати зворотне відповідність? Метод Кіма - І тут багато в чому повторює спосіб Сильвестра, але виглядає, мабуть, навіть природніше.
Випишемо спадаючу послідовність з чисел непарного розбиття (a1 = 15, a2 = a3 = 13, a4 = 9, a5 = a6 = 7, a7 = a8 = a9 = 3, a10 = a11 = 1) і будемо від першого члена віднімати 1, від другого - 3, від третього - 5, і так далі до тих пір, поки різниці будуть позитивні. Тобто запишемо рівності 15 = 1 + 14, 13 = 3 + 10, 13 = 5 + 8, 9 = 7 + 2. Це відразу дасть нам потрібне розбиття третього рядка під діаграмою на першу і другу. Потім все числа першого рядка перенесемо в діаграму праворуч від роздільника, а кожне парне число другого рядка «укладемо» в два рядки зліва від роздільника. В результаті отримаємо діаграму, в якій нижня рядок буде найдовшою, а кожна наступна рядок буде коротше попередньої. Підсумовуючи клітини цієї діаграми по рядках, отримаємо розбиття на різні складові.
Результат Кіма - І - навіть при тому, що вони фактично просто переформулювали Сильвестра - використовує поняття роздільник, якого не було в оригіналі. А значить, теж дозволяє довести сильніший факт. Але дивно навіть не це, а те, що цей факт був відкритий на кілька років раніше, ніж з'явилася гарна картинка від корейців!