Поєднання із повтореннями елементів. Комбінаторні алгоритми: індекс поєднання, індекс розбиття на підмножини Приведення алгоритмів до константної складності
Все N елементів, і жоден не повторюється, це завдання про кількість перестановок. Рішення можна знайти простим. На першому місці в ряді може стояти будь-який з елементів N, отже, виходить N варіантів. На другому місці – будь-який, крім того, який уже був використаний для першого місця. Отже, кожному з N вже знайдених варіантів є (N - 1) варіантів другого місця, і кількість комбінацій стає N*(N - 1).
Це можна повторити інших елементів ряду. Для самого останнього місця залишається тільки один варіант - останній елемент, що залишився. Для передостаннього – два варіанти, і так далі.
Отже, для низки з N неповторних елементів можливих перестановок дорівнює добутку всіх від 1 до N. Цей твір називається факторіалом числа N і позначається N! (Читається «ен факторіал»).
У попередньому випадку кількість можливих елементів і кількість місць ряду збігалися, і їх число дорівнювало N. Але можлива ситуація, коли в ряду менше місць, ніж можливих елементів. Іншими словами, кількість елементів у вибірці дорівнює деякому числу M, причому M< N. В этом случае задача определения количества возможных комбинаций может иметь два различных варианта.
По-перше, може знадобитися порахувати загальну кількість можливих способів, якими можна побудувати ряд M елементів з N. Такі способи називаються розміщеннями.
По-друге, дослідника може цікавити кількість способів, якими можна вибрати M елементів з N. При цьому порядок розташування елементів вже не важливий, але будь-які два варіанти повинні відрізнятися між собою хоча б одним елементом. Такі методи називаються поєднаннями.
Щоб знайти кількість розміщень M елементів з N, можна вдатися до такого ж способу міркувань, як і у випадку з перестановками. На першому місці тут, як і раніше, може стояти N елементів, на другому (N - 1), і так далі. Але для останнього місця кількість можливих варіантів дорівнює не одиниці, а (N - M + 1), оскільки коли розміщення буде закінчено, залишиться ще (N - M) невикористаних елементів.
Таким чином, число розміщень M елементів з N дорівнює добутку всіх цілих чисел від (N - M + 1) до N, або, що те ж саме, приватному N!/(N - M)!.
Очевидно, що кількість поєднань M елементів з N буде менше кількості розміщень. Для кожного можливого поєднання є M! можливих розміщень, які від порядку елементів цього поєднання. Отже, щоб знайти цю кількість, потрібно розділити число розміщень M елементів з N на N!. Іншими словами, кількість поєднань по M елементів N дорівнює N!/(M!*(N - M)!).
Поєднанням називається невпорядкована вибірка елементів кінцевої множини з фіксованим числом і без повторень елементів. Різні поєднання повинні відрізнятися хоча б одним елементом, а порядок розташування елементів не має значення. Наприклад, з багатьох гласних латинських літер (AEIOU) можна скласти 10 різних поєднань по 3 літери, утворюючи наступні невпорядковані трійки:
AEI, AEO, AEU, AIO, AIU, AOU, EIO, EIU, EOU, IOU.
Цікаво відзначити, що з тих самих п'яти букв можна отримати також 10 різних поєднань, якщо комбінувати їх по 2 букви, склавши такі невпорядковані пари:
AE, AI, AO, AU, EI, EO, EU, IO, IU, OU.
Однак якщо комбінувати ті ж голосні латинські літери по 4, то вийде вже тільки наступні 5 різних поєднань:
AEIO, AEIU, AIOU, EIOU, AEOU.
У загальному випадку для позначення числа поєднань з n різних елементів m елементів застосовується наступна функціональна, індексна або векторна (Апеля) символіка:
Незалежно від форми позначення, число поєднань з n елементів по m елементів можна визначити за такими мультиплікативною та факторіальною формулами:
Неважко перевірити, що результат обчислень за цими формулами збігається з результатами розглянутого вище прикладу з поєднаннями голосних латинських літер. Зокрема, при n=5 та m=3 обчислення за цими формулами дадуть наступний результат:
У загальному випадку формули числа поєднань мають комбінаторний зміст і справедливі за будь-яких цілочисельних значень n і m, таких, що n > m > 0. Якщо m > n і m< 0, то число сочетаний равно 0, так как в этом случае основное множество из n элементов вообще не имеет подмножеств мощности m:
Крім того, корисно пам'ятати наступні граничні числа поєднань, які легко перевірити безпосередньою підстановкою в мультиплікативну та факторіальну формули:
Слід також зазначити, що мультиплікативна формула залишається справедливою навіть коли n є дійсним числом, як і раніше, значенні m. Однак тоді результат обчислення нею, зберігаючи формальну справедливість, втрачає комбінаторний сенс.
ТОЖНІСТЬ ПОЄДНАНЬ
Практичне використання мультиплікативної та факторіальної формул для визначення числа поєднань при довільних значеннях n і m виявляється мало продуктивно через експоненційне зростання факторіальних творів їх чисельника та знаменника. Навіть за порівняно невеликих величинах n і m ці твори часто перевершують можливості представлення цілих чисел у сучасних обчислювальних та програмних системах. При цьому їх величини виявляються значно більшими від результуючого значення числа поєднань, яке може бути порівняно невелике. Наприклад, число поєднань з n=10 по m=8 елементів дорівнює всього 45. Однак, щоб знайти це значення за факторіальною формулою, потрібно спочатку обчислити значно більші величини 10! у чисельнику та 8! у знаменнику:
Щоб виключити трудомісткі операції обробки великих величин, визначення кількості поєднань можна скористатися різними рекурентними співвідношеннями, які безпосередньо випливають з мультиплікативної і факторіальної формул. Зокрема, з мультиплікативної формули слідує наступне рекурентне співвідношення, яке дозволяє виносити за знак числа поєднань відношення його індексів:
Нарешті, збереження незмінним нижнього індексу забезпечує наступне рекурентне співвідношення, яке легко виходить із факторіальної формули числа поєднань:
Після елементарних перетворень три отримані рекурентні співвідношення можна у наступних видах:
Якщо тепер скласти ліві та праві частини 2-х перших формул і скоротити результат на n, то вийде важливе рекурентне співвідношення, яке називається тотожністю додавання чисел поєднань:
Тотожність додавання надає основне рекурентне правило для ефективного визначення числа поєднань при великих значеннях n і m, оскільки воно дозволяє замінити операції множення у факторіальних творах більш простими операціями додавання, причому для менших чисел поєднань. Зокрема, використовуючи тотожність додавання, тепер нескладно визначити число поєднань з n=10 по m=8 елементів, яке розглядалося вище, виконавши наступну послідовність рекурентних перетворень:
Крім того, з тотожності додавання можна вивести кілька корисних співвідношень для обчислення кінцевих сум, зокрема формулу підсумовування за нижнім індексом, яка має такий вигляд:
Таке співвідношення виходить, якщо в тотожності додавання розгортати рекурентність по доданку з найбільшим верхнім індексом, поки його нижній індекс більше 0. Наступний чисельний приклад ілюструє зазначений процес рекурентних перетворень:
Формула підсумовування нижнього індексу часто застосовується для обчислення суми ступенів натуральних чисел. Зокрема, вважаючи m=1, за цією формулою легко знайти суму n перших чисел натурального ряду:
Ще один корисний варіант формули підсумовування можна отримати, якщо розгортати рекурентність тотожності додавання по доданку з найменшим верхнім індексом. Наступний чисельний приклад ілюструє цей варіант рекурентних перетворень:
У загальному випадку в результаті таких перетворень виходить сума чисел поєднань, обидва індекси яких відрізняються на одиницю від сусідніх доданків, а різниця індексів зберігає постійну величину (у розглянутому прикладі вона дорівнює одиниці). Таким чином, виходить наступна формула підсумовування за обома індексами чисел поєднань:
Крім розглянутих вище рекурентних співвідношень і формул підсумовування у комбінаторному аналізі отримано багато інших корисних тотожностей для чисел поєднань. Найбільш важливим серед них є тотожність симетрії, яке має такий вигляд:
У справедливості тотожності симетрії можна переконатися на наступному прикладі, зіставивши числа поєднань з 5-ти елементів 2 і (5 2)=3:
Тотожність симетрії має очевидний комбінаторний зміст, оскільки, визначаючи кількість варіантів вибору m елементів з n елементів, воно одночасно встановлює кількість поєднань з інших (nm) невибраних елементів. Вказана симетрія негайно виходить взаємною заміною m на (nm) у факторіальній формулі числа поєднань:
Числа та тотожності поєднань широко застосовують у різних галузях сучасної обчислювальної математики. Однак найбільш популярне їхнє застосування пов'язане з біномом Ньютона і трикутником Паскаля.
Біном Ньютона
Для виконання різних математичних перетворень та обчислень важливо мати можливість представити будь-який натуральний ступінь бінома алгебри (двучлена) у формі многочлена. При малих ступенях багаточлен нескладно отримати безпосереднім перемноженням біномів. Зокрема, з курсу елементарної математики добре відомі такі формули квадрата та куба суми двох доданків:
У загальному випадку для довільного ступеня n бінома подання у формі багаточлена надає біномна теорема Ньютона, яка декларує виконання наступної рівності:
Цю рівність зазвичай називають біномом Ньютона. Багаточлен у його правій частині утворює сума творів n доданків X та Y бінома лівої частини, а коефіцієнти перед ними називаються біноміальними та дорівнюють числам поєднань з індексами, які виходять за їх ступенями. Враховуючи особливу популярність формули бінома Ньютона в комбінаторному аналізі, терміни біномний коефіцієнт та кількість поєднань прийнято вважати синонімами.
Очевидно, формули квадрата і куба суми є окремими випадками біноміальної теореми при n=2 і n=3, відповідно. Для обробки вищих ступенів (n>3) слід використовувати формулу бінома Ньютона. Її застосування для бінома четвертого ступеня (n=4) демонструє такий приклад:
Слід зазначити, що біноміальна формула була відома ще до Ньютона середньовічним математикам арабського Сходу та Західної Європи. Тому її загальноприйнята назва не є історично справедливою. Заслуга Ньютона у цьому, що він узагальнив цю формулу у разі довільного речового показника r, який може набувати будь-які позитивні чи негативні раціональні і ірраціональні значення. У загальному випадку така формула бінома Ньютона має нескінченну суму у правій частині та її прийнято записувати наступним чином:
Наприклад, при позитивному дробовому значенні показника ступеня r=1/2 з урахуванням значень біноміальних коефіцієнтів виходить наступне розкладання:
У загальному випадку формула бінома Ньютона за будь-якого показника є приватним варіантом формули Маклорена, яка дає розкладання довільної функції в статечний ряд. Ньютон показав, що з |z|< 1 этот ряд сходится, и сумма в правой части становится конечной. При любой натуральной степени r = n в правой части также получается конечная сумма из (n+1) первых слагаемых, так как все C(n, k>n) = 0. Якщо тепер покласти Z=X/Y і помножити ліву і праву частини Yn, то вийде варіант формули бінома Ньютона, розглянутий вище.
Незважаючи на свою універсальність, біномна теорема зберігає комбінаторний сенс тільки за цілих невід'ємних ступенів бінома. У цьому випадку за її допомогою можна довести кілька корисних тотожностей для біномних коефіцієнтів. Зокрема, вище були розглянуті формули підсумовування чисел поєднань по нижньому індексу та обох індексів. Відсутність тотожності підсумовування за верхнім індексом легко отримати з формули бінома Ньютона, поклавши в ній X = Y = 1 або Z = 1:
Ще одна корисна тотожність встановлює рівність сум біноміальних коефіцієнтів з парними та непарними номерами. Воно негайно виходить із формули бінома Ньютона, якщо X = 1 і Y = 1 або Z = 1:
Нарешті, з обох розглянутих тотожностей виходить тотожність суми біноміальних коефіцієнтів лише з парними чи лише з непарними номерами:
На основі розглянутих тотожності та рекурентного правила винесення індексів з-під знака числа поєднань можна отримати цілу низку цікавих співвідношень. Наприклад, якщо у формулі підсумовування верхнього індексу скрізь замінити n на (n1) і винести індекси в кожному доданку, то вийде наступне співвідношення:
Використовуючи аналогічну техніку у формулі суми біноміальних коефіцієнтів з парними та непарними номерами, можна довести справедливість, наприклад, наступного співвідношення:
Ще одна корисна тотожність дозволяє легко обчислити суму творів симетрично розташованих біномних коефіцієнтів двох біномів довільних ступенів n і k за наступною формулою Коші:
Справедливість цієї формули випливає з необхідної рівності коефіцієнтів за будь-якого ступеня m змінної Z у лівій та правій частині наступного тотожного співвідношення:
В окремому випадку, коли n=k=m при врахуванні тотожності симетрії виходить більш популярна формула суми квадратів біномних коефіцієнтів:
У великій літературі з комбінаторного аналізу можна знайти багато інших корисних тотожностей для биномиальных коефіцієнтів. Однак їх найбільш відомий практичний додаток пов'язаний із трикутником Паскаля.
ТРИКУТНИК ПАСКАЛЯ
Арифметичний трикутник Паскаля утворює нескінченну числову таблицю, складену з біномних коефіцієнтів. Її рядки впорядковані за ступенями біномів зверху донизу. У кожному рядку біноміальні коефіцієнти розташовані за зростанням верхніх індексів відповідних чисел поєднань зліва направо. Трикутник Паскаля прийнято записувати або у рівнобедреній, або у прямокутній формі.
Наочнішим і поширенішим є рівнобедрений формат, де біномні коефіцієнти, розташовуючись у шаховому порядку, утворюють нескінченний рівнобедрений трикутник. Його початковий фрагмент для біномів до 4-го ступеня (n=4) має такий вигляд:
У загальному випадку рівнобедрений трикутник Паскаля надає зручне геометричне правило визначення біномних коефіцієнтів, що ґрунтується на тотожності додавання та симетрії чисел поєднань. Зокрема, відповідно до тотожності додавання будь-який біноміальний коефіцієнт є сумою двох найближчих до нього коефіцієнтів попереднього рядка. Відповідно до тотожності симетрії рівнобедрений трикутник Паскаля симетричний щодо своєї бісектриси. Таким чином, кожен рядок є числовим паліндромом біноміальних коефіцієнтів. Зазначені алгебраїчні та геометричні особливості дозволяють легко розширювати рівнобедрений трикутник Паскаля та послідовно знаходити значення біномних коефіцієнтів довільних ступенів.
Однак для вивчення різних властивостей трикутника Паскаля зручніше застосовувати формально більш строгий прямокутний формат. У цьому форматі задає його нижньо-трикутна матриця біноміальних коефіцієнтів, де вони утворюють нескінченний прямокутний трикутник. Початковий фрагмент прямокутного трикутника Паскаля для біномів до 9-го ступеня (n=9) має такий вигляд:
Геометрично така прямокутна таблиця виходить шляхом горизонтальної деформації рівнобедреного трикутника Паскаля. В результаті числові ряди, паралельні бічним сторонам рівнобедреного трикутника Паскаля, перетворюються на вертикалі та діагоналі прямокутного трикутника Паскаля, а горизонталі обох трикутників збігаються. При цьому зберігають справедливість правила додавання та симетрії біноміальних коефіцієнтів, хоча прямокутний трикутник Паскаля втрачає візуальну симетричність, властиву його рівнобедреному аналогу. Як компенсацію стає більш зручним формальний аналіз різноманітних числових властивостей біноміальних коефіцієнтів для горизонталей, вертикалей і діагоналей прямокутного трикутника Паскаля.
Починаючи аналіз горизонталів прямокутного трикутника Паскаля, неважко помітити, що сума елементів будь-якого рядка з номером n дорівнює 2 n відповідно до формули підсумовування біномних за верхнім індексом. З цього випливає, що сума елементів над будь-якою горизонталлю з номером n дорівнює (2 n 1). Цей результат стає очевидним, якщо значення суми елементів кожної горизонталі записати в двійковій системі числення. Наприклад, для n=4 таке додавання можна записати так:
Ось ще кілька цікавих властивостей горизонталей, які також пов'язані зі ступенем двійки. Виявляється, якщо номер горизонталі є ступенем двійки (n=2 k), всі її внутрішні елементи (крім крайніх одиниць) є парними числами. Навпаки, усі числа горизонталі будуть непарними, якщо її номер на одиницю менший від ступеня двійки (n=2 k 1). У справедливості цих властивостей можна переконатися перевіркою парності внутрішніх біноміальних коефіцієнтів, наприклад, у горизонталях n=4 та n=3 або n=8 та n=7.
Нехай тепер номер рядка прямокутного трикутника Паскаля є простим числом p. Тоді всі її внутрішні биномиальные коефіцієнти поділяються на p. Цю властивість неважко перевірити для малих значень простих номерів горизонталей. Наприклад, всі внутрішні біноміальні коефіцієнти п'ятої горизонталі (5, 10 та 5), очевидно, діляться на 5. Щоб довести справедливість цього результату для будь-якого простого номера горизонталі p, потрібно записати мультиплікативну формулу її біномних коефіцієнтів таким чином:
Оскільки p є просте число і, отже, не ділиться на m!, то добуток інших співмножників чисельника цієї формули має ділитися на m!, щоб гарантувати значення биномиального коефіцієнта. Звідси випливає, що ставлення у квадратних дужках є натуральним числом N і результат, який шукається, стає очевидним:
Використовуючи цей результат, можна встановити, що номери всіх горизонталей трикутника Паскаля, внутрішні елементи яких поділяються на задане просте число p, є ступенем p тобто мають вигляд n = p k . Зокрема, якщо p=3, то просте число p ділить не тільки всі внутрішні елементи рядка 3, як було встановлено вище, але, наприклад, 9 горизонталі (9, 36, 84 і 126). З іншого боку, у трикутнику Паскаля не можна знайти горизонталь, всі внутрішні елементи якої поділяються на складову кількість. В іншому випадку номер такої горизонталі повинен бути одночасно ступенем простих дільників складового числа, на яке діляться всі її внутрішні елементи, але це з очевидних причин неможливо.
Розглянуті міркування дозволяють сформулювати наступну загальну ознаку ділимості горизонтальних елементів трикутника Паскаля. Найбільший спільний дільник (НОД) всіх внутрішніх елементів будь-якої горизонталі трикутника Паскаля з номером n дорівнює простому числу p, якщо n = pk або 1 у всіх інших випадках:
НОД(Cmn) = ( ) для будь-яких 0< m < n .
На закінчення аналізу горизонталей варто розглянути ще одну цікаву властивість, якою мають ряди, що утворюють їх, біноміальних коефіцієнтів. Якщо біноміальні коефіцієнти будь-якої горизонталі з номером n помножити на послідовні ступені числа 10, а потім скласти всі ці твори, то вийде 11 n . Формальним обґрунтуванням цього результату є підстановка значень X=10 та Y=1 (або Z=1) у формулу бінома Ньютона. Наступний чисельний приклад ілюструє виконання цієї властивості за n=5:
Аналіз властивостей вертикалей прямокутного трикутника Паскаля можна розпочати з вивчення індивідуальних особливостей складових їх елементів. Формально кожну вертикаль m утворює наступну нескінченну послідовність біноміальних коефіцієнтів з постійним верхнім індексом (m) та інкрементом нижнього індексу:
Очевидно, що при m=0 виходить послідовність одиниць, а при m=1 утворюється ряд натуральних чисел. При m=2 вертикаль становлять трикутні числа. Кожне трикутне число можна зобразити на площині як рівностороннього трикутника, який заповнюють довільні об'єкти (ядра), які у шаховому порядку. При цьому значення кожного трикутного числа T k визначає кількість зображуючих ядер, а індекс показує скільки рядів ядер потрібно для його представлення. Наприклад, 4 початкові трикутні числа представляють наступні конфігурації з відповідного числа ядерних символів "@":
Слід зазначити, що аналогічним чином можна ввести в розгляд квадратні числа S k , які виходять зведенням у квадрат натуральних чисел і взагалі багатокутні фігурні числа, утворені регулярним заповненням правильних багатокутників. Зокрема, 4 початкові квадратні числа можна зобразити таким чином:
Повертаючись до аналізу вертикалей трикутника Паскаля, можна зазначити, що наступну вертикаль при m=3 заповнюють тетраедальні (пірамідальні) числа. Кожне таке число P k задає кількість ядер, яку можна розташувати у формі тетраедра, а індекс визначає, скільки горизонтальних трикутних шарів з рядів ядер потрібно для зображення в тривимірному просторі. При цьому всі горизонтальні шари повинні бути представлені як послідовні трикутні числа. Елементи наступних вертикалей трикутника Паскаля при m>3 утворюють ряди гіпертетраедальних чисел, які не мають наочної геометричної інтерпретації на площині або тривимірному просторі, але формально відповідають багатовимірним аналогам трикутних і тетраедальних чисел.
Хоча вертикальні числові ряди Паскаля трикутника мають розглянуті індивідуальні фігурні особливості, але для них можна однаковим чином обчислювати часткові суми значень початкових елементів, використовуючи формулу підсумовування чисел поєднань по нижньому індексу. У трикутнику Паскаля ця формула має таку геометричну інтерпретацію. Сума значень n верхніх біноміальних коефіцієнтів будь-якої вертикалі дорівнює значенню елемента наступної вертикалі, розташованого на один рядок нижче. Цей результат також відповідає геометричній структурі трикутних, тетраедальних і гіпертетраедальних чисел, оскільки подання кожного такого числа складається з ядерних шарів, що зображують числа нижчого порядку. Зокрема, n трикутне число T n можна отримати, підсумовуючи всі натуральні числа, що зображують його лінійні шари:
Аналогічним чином нескладно знайти тетраедальне число P n обчисливши наступну суму n перших трикутних чисел, які складають його горизонтальні ядерні шари:
Крім горизонталей і вертикалей у прямокутному трикутнику Паскаля можна простежити діагональні ряди елементів, вивчення властивостей яких також становить певний інтерес. При цьому зазвичай розрізняють низхідні та висхідні діагоналі. Східні діагоналі паралельні до гіпотенузи прямокутного трикутника Паскаля. Їх утворюють ряди біноміальних коефіцієнтів з інкрементом обох індексів. У силу тотожності симетрії низхідні діагоналі збігаються за значеннями своїх елементів з відповідними вертикальними рядами трикутника Паскаля і тому повторюють всі властивості, розглянуті вище. Вказану відповідність можна простежити за збігом значень елементів низхідної діагоналі та вертикалі з будь-яким номером n, якщо не враховувати вертикальні нулі:
Висхідні діагоналі утворюють числові ряди, геометрично перпендикулярні до гіпотенузи прямокутного трикутника Паскаля. Вони заповнені біноміальними коефіцієнтами з декрементом нижнього та інкрементом верхнього індексів. Зокрема, 7 верхніх висхідних діагоналей утворюють такі числові послідовність без урахування хвостових нулів:
У загальному випадку на висхідній діагоналі з номером n стоять такі біномні коефіцієнти, сума індексів кожного з яких дорівнює (n1):
У силу тотожності складання для чисел поєднань кожен діагональний елемент дорівнює сумі двох відповідних за індексами елементів двох попередніх висхідних діагоналей. Це дозволяє будувати кожну наступну висхідну діагональ попарним підсумовуванням сусідніх горизонтальних елементів двох попередніх діагоналей, нескінченно розширюючи трикутник Паскаля по діагоналі. Наступний фрагмент трикутника Паскаля ілюструє побудову висхідної діагоналі з номером 8 по діагоналях з номерами 6 та 7:
При такому способі побудови сума елементів будь-якої висхідної діагоналі, починаючи з 3-ї, дорівнюватиме сумі елементів двох попередніх висхідних діагоналей, а перші 2 діагоналі складаються тільки з одного елемента, значення якого дорівнює 1. Результати відповідних обчислень утворюють наступний числовий ряд, за яким можна перевірити справедливість розглянутої властивості висхідних діагоналей прямокутного трикутника Паскаля:
Аналізуючи ці числа, можна помітити, що за аналогічним законом утворюється добре відома послідовність чисел Фібоначчі, де кожне чергове число дорівнює сумі двох попередніх, а два перших числа дорівнюють 1:
Таким чином, можна зробити наступний важливий висновок: діагональні суми елементів трикутника Паскаля становлять послідовність Фібоначчі. Ця властивість дозволяє встановити ще одну цікаву особливість Паскаля трикутника. Розкриваючи рекурсивно формулу Фібоначчі, неважко довести, що сума перших n чисел Фібоначчі дорівнює (F n+2 1).
Тому сума біноміальних коефіцієнтів, що заповнюють верхні n діагоналей, також дорівнює (F n+2 1). Звідси випливає, що сума n перших діагоналей трикутника Паскаля на 1 менша за суму біноміальних коефіцієнтів, які стоять на його діагоналі з номером (n+2).
На закінчення слід зазначити, що розглянуті властивості горизонталей, вертикалей і діагоналей трикутника Паскаля далеко не вичерпують величезну різноманітність можливостей, які пов'язують різні математичні аспекти, на перший погляд не мають нічого спільного. Такі незвичайні властивості дозволяють вважати трикутник Паскаля однією з найбільш досконалих числових систем, всі можливості якої неможливо перерахувати і важко переоцінити.
Алгоритм обчислення числа поєднань із використанням трикутника Паскаля представлений нижче:
Приватна функція SochTT (ByVal n As Integer, ByVal k As Integer) As Double Dim i As Integer Dim j As Integer Dim TT () As Double ReDim TT (n, k) For i = 0 To n TT (0, i) = 1 TT (i, i) = 1 Next For i = 2 To n For j = 1 To i - 1 TT (i, j) = TT (i - 1, j - 1) + TT (i - 1, j) Next Next SochTT = TT (n, k) End Function
Якщо Вам потрібно обчислювати кількість поєднань багато разів, то, можливо, буде зручніше один раз побудувати Паскаля трикутник, а потім отримувати з масиву дані.
Dim TT () As Double Private Sub CreateTT () ReDim TT (0, 0) BuildTT 0, 0 End Sub Private Function SochTT (ByVal n As Integer, ByVal k As Integer) As Double If n > Ubound (TT) Then BuildTT Ubound (TT) + 1, n SochTT = TT (n, k) Закінчити функцію private Sub TerminateTT () ReDim TT (0, 0) Підприємство Sub Private Sub BuildTT (ByVal Start As Integer, ByVal end As Integer) Dim i As Integer Dim j As Integer ReDim Preserve TT (end, end) For i = start To end TT (0, i) = 1 TT (i, i) = 1 Next If end< 2 Then Exit Sub If start < 2 Then start = 2 For i = start To end For j = 1 To i - 1 TT (i, j) = TT (i - 1, j - 1) + TT (i - 1, j) Next Next End Sub
Спочатку потрібно викликати процедуру CreateTT. Потім можна отримувати кількість поєднань за допомогою функції SochTT. Коли трикутник стане Вам не потрібним, викличте процедуру TerminateTT. У вищевказаному коді при виклику функції SochTT, якщо трикутник ще не добудований до необхідного рівня, він добудовується за допомогою процедури BuildTT. Потім функція одержує потрібний елемент масиву TT і повертає його.
Dim X () As Integer Dim Counter () As Integer Dim K As Integer Dim N As Integer Public Sub Soch() Dim i As Integer N = CInt(InputBox("Введіть N")) K = CInt(InputBox("Введіть K ")) K = K + 1 ReDim X(N) For i = 1 To N X(i) = i Next txtOut.Text = "" ReDim Counter(K) Counter(0) = 1 SochGenerate 1 End Sub Private Sub SochGenerate( ByVal c As Integer) Dim i As Integer Dim j As Integer Dim n1 As Integer Dim Out() As Integer Dim X1() As Integer If c = K The Redim Out(K) X1 = X For i = 1 To K - 1 n1 = 0 For j = 1 To N If X1(j)<>0 Then n1 = n1 + 1 If n1 = Counter(i) Then Out(i) = X1(j) X1(j) = 0 txtOut.Text = txtOut.Text Next txtOut.Text = txtOut.Text & vbCrLf Else For Counter(c) = Counter(c - 1) To N - c + 1 SochGenerate c + 1 Next End If End Sub
ПЕРЕЧИСЛЕННЯ ПОЄДНАНЬ НАТУРАЛЬНИХ ЧИСЕЛ
Для вирішення багатьох практичних завдань необхідно перерахувати всі поєднання фіксованої потужності, які можна отримати з елементів заданої кінцевої множини, а не тільки визначити їхнє число. Враховуючи завжди існуючу можливість цілісної нумерації елементів будь-якої кінцевої множини, в більшості випадків допустимо обмежитися використанням алгоритмів перерахування поєднань натуральних чисел. Найбільш природним і простим з них є алгоритм перерахування поєднань натуральних чисел лексиграфічному порядку.
Для формального опису цього алгоритму зручно вважати, що основна множина, всі поєднання по m елементів якого необхідно перерахувати, утворюють послідовні натуральні числа від 1 до n. Тоді будь-яке поєднання з m В результаті впорядкування значення в кожній позиції такого вектора поєднань природно виявляється обмеженим за величиною зверху та знизу таким чином: Лексиграфічний алгоритм послідовно формує такі вектори поєднань, починаючи з лексиграфічно найменшого вектора, де у всіх позиціях стоять такі мінімально можливі значення елементів, що дорівнюють їх індексам: Кожен черговий вектор поєднання формується з поточного після перегляду його елементів зліва направо з метою знайти найправіший елемент, який ще не досяг свого граничного значення: Значення такого елемента слід збільшити на 1. Кожному елементу праворуч від нього потрібно надати найменше можливе значення, яке на 1 більше, ніж у сусіда зліва. Після зазначених змін черговий вектор поєднань матиме наступний елементний склад: Таким чином, черговий вектор поєднання буде лексиграфічно більше попереднього, оскільки значення початкових (j1) елементів рівні за величиною, а значення елемента в позиції j на 1 більше, ніж у попереднього. Зазначене ставлення зростаючого лексиграфічного порядку гарантовано виконується усім ітераціях алгоритму. В результаті утворюється зростаюча лексиграфічна послідовність, яку завершує лексиграфічно найбільший вектор поєднання, де елементи у всіх позиціях мають такі максимальні значення: Розглянутий лексиграфічний алгоритм ілюструє наступний приклад, де потрібно перерахувати у зростаючому лексиграфічному порядку всі 15 поєднань з n=6 перших натуральних чисел по m=4 числа, тобто всі можливі 4-х елементні підмножини основної утворюючої множини (1, 2, 3, 4 , 5, 6) із 6-ти елементів. Результати обчислень представлені у таблиці: У цьому прикладі найбільші допустимі значення чисел у позиціях векторів поєднань рівні відповідно 3, 4, 5 і 6. Для зручності інтерпретації результатів у кожному векторі поєднань підкресленням виділено крайній правий елемент, який ще не досяг свого максимального значення. Числові індекси векторів поєднань визначають їх номери у лексиграфічному порядку. У загальному випадку лексиграфічний номер N будь-якого поєднання з n елементів m можна обчислити за наступною формулою, де з косметичних міркувань для позначення чисел поєднань використана символіка Апеля: Зокрема, такі обчислення за цією формулою номера поєднання (1, 3, 4, 6) з n=6 елементів по m=4 у лексиграфічному порядку дадуть результат N=8, який відповідає прикладу, розглянутому вище: У загальному випадку, використовуючи тотожність для суми чисел поєднань за обома індексами, можна показати номер лексиграфічно найменшого поєднання (1, … i, … m) при обчисленні його за даною формулою завжди буде дорівнює 1: Очевидно також, що номер лексиграфічно найбільшого поєднання (m, … nm+i, … n) при обчисленні його за даною формулою дорівнюватиме кількості поєднань з n елементів по m: Формулу обчислень лексиграфічних номерів поєднань можна використовуватиме вирішення зворотного завдання, де потрібно визначити вектор поєднання за його номером у лексиграфічному порядку. Для вирішення такої зворотної задачі її потрібно записати у вигляді рівняння, де всі невідомі значення елементів вектора шуканого поєднання (C 1 , … C i , … C m) зосереджені в числах поєднань його правої частини, а в лівій частині записана відома різниця L числа поєднань з n елементів по m та номери шуканого поєднання N: Рішення цього рівняння забезпечує наступний "жадібний" алгоритм, на ітераціях якого проводиться послідовний вибір значень елементів вектора поєднання, що шукається. На початковій ітерації вибирається мінімально можливе (у межах своїх обмежень) значення C 1 , при якому перший доданок правої частини матиме максимальне значення, що не перевищує L: Тепер ліву частину L слід зменшити на перше число поєднань у правій частині при обраному значенні C 1 і аналогічним чином визначити значення C 2 на другій ітерації: Аналогічно слід виконати всі наступні ітерації, щоб вибрати значення всіх інших елементів C i шуканого поєднання, аж до останнього елемента C m: З очевидних причин значення останнього елемента C m можна визначити, виходячи вже з рівності його числа поєднань залишкового значення лівої частини L: Слід зазначити, що значення останнього елемента поєднання C m можна знайти ще простіше, без перебору його можливих значень: Виконання ітерацій розглянутого алгоритму ілюструє наступний приклад, де потрібно визначити поєднання з номером N=8 у лексиграфічному порядку, якщо n=6 та m=4: Алгоритмічна можливість визначити поєднання за заданим номером у лексиграфічному порядку може бути використана в різних напрямках. Зокрема, коли при перерахуванні поєднань у лексиграфічному порядку потрібно забезпечити повернення до будь-якого поєднання, яке було отримано раніше, достатньо знати лише його номер. З іншого боку, стає можливим породжувати поєднання у порядку, який регламентує довільно задана послідовність їх лексиграфічних номерів. Тепер наведемо алгоритм генерації поєднань у лексикографічному порядку: 2 for i:= 1 to k do A[i] := i; 5 begin write(A, …, A[k]); 6 if A[k] = n then p:= p 1 else p:= k; 8 for i:= k downto p do A[i] := A[p] + i p + 1 ПОЄДНАННЯ З ПОВТОРЕННЯМИ ЕЛЕМЕНТІВ На відміну від класичного поєднання, де всі елементи різні, поєднання з повтореннями утворює невпорядкована вибірка елементів кінцевої множини, де будь-який елемент може з'являтися невизначено часто і бути необов'язково в єдиному екземплярі. При цьому кількість повторень елементів зазвичай обмежена лише довжиною поєднання, а різними вважаються поєднання, що відрізняються хоча б одним елементом. Наприклад, вибираючи по 4 необов'язково різні цифри набору 1, 2 і 3 можна скласти наступні 15 поєднань з повтореннями: 1111 1112 1113 1122 1123 1133 1222 1223 1233 1333 2222 2223 2233 2333 3333.
У випадку поєднання з повтореннями можуть бути утворені вибіркою з n елементів довільних типів. Проте їм можна порівняти послідовні натуральні числа від 1 до n. Тоді будь-яке поєднання з m необов'язково різних чисел цього діапазону можна записати у векторній формі, розташовуючи їх у неубутньому порядку зліва направо: Природно, за такої форми запису будь-які сусідні елементи можуть бути рівними внаслідок можливості необмежених повторень. Однак кожному вектору поєднання з повтореннями з n елементів m можна поставити у відповідність вектор поєднання з (n+m−1) елементів m, який конструюється наступним чином: Зрозуміло, що за будь-яких значень елементів вектора f елементи вектора C будуть гарантовано різні і строго впорядковані за зростанням своїх значень з діапазону від 1 до (n+m1): Наявність взаємно однозначної відповідності між елементами векторів поєднань f і C дозволяє запропонувати наступний простий метод систематичного перерахування поєднань із повтореннями n елементів по m. Потрібно тільки перерахувати, наприклад, в лексиграфічному порядку всі C поєднання з (n+m1) елементів m, послідовно перетворюючи елементи кожного з них у відповідні елементи поєднань з повтореннями f за такою формулою: В результаті утворюється послідовність векторів поєднань з повтореннями елементів, які розташовані у порядку, що породжується перерахуванням відповідних поєднань без повторень елементів. Зокрема, для того, щоб отримати представлену вище послідовність поєднань з 3 цифр 1, 2 і 3 з повтореннями по 4 цифри, потрібно перерахувати в лексиграфічному порядку всі поєднання без повторень з 6 цифр 1,2,3,4, 5 та 6 по 4 цифри, перетворюючи їх вказаним чином. У наступному прикладі показано таке перетворення поєднання (1,3,4,6) з лексиграфічним номером 8: Розглянута взаємно однозначна відповідність між поєднаннями з повтореннями та без повторень елементів означає, що їх множини рівносильні. Тому в загальному випадку число поєднань з повтореннями з n елементів m дорівнює числу поєднань без повторень з (n+m1) елементів m. Використовуючи однакову символіку для позначення чисел поєднань із повтореннями f і без повторень C, цю рівність можна записати так: Неважко перевірити, що для розглянутого вище прикладу, де n=3 і m=4, число поєднань з повторення дорівнюватиме 15, що збігається з результатом їх безпосереднього перерахування: Слід зазначити, що на відміну від класичного варіанту значення параметрів поєднання з повтореннями n і m безпосередньо не пов'язані між собою, тому f(n,m)>0 при будь-якій комбінації їх позитивних значень. Відповідні граничні умови визначаються з рівності між значеннями (n+m1) та (n1) або (n+m1) та m: Також має бути цілком очевидно, що якщо m дорівнює 1, то ніякі повторення елементів неможливі і, отже, за будь-якого позитивного значення n>0 буде справедливо така рівність: Крім того, для чисел поєднань з повтореннями при будь-яких позитивних значеннях n і m справедливе наступне рекурентне співвідношення, яке схоже на тотожність додавання для чисел поєднань без повторень елементів: Власне, воно і перетворюється на вказану тотожність додавання при формальній підстановці відповідних чисел поєднань без повторень у його ліву та праву частини: Розглянуте рекурентне співвідношення можна використовуватиме ефективного визначення чисел поєднань із повтореннями, коли важливо виключити трудомісткі операції обчислення факторіальних творів і замінити їх простішими операціями складання. При цьому для обчислення значення f(n,m) потрібно тільки застосовувати дане рекурентне співвідношення до отримання суми доданків виду f(1,m) і f(i,1), де i приймає значеннями в діапазоні від n до 1. За визначенням величини таких доданків дорівнюють 1 і i, відповідно. Наступний приклад ілюструє використання даної техніки перетворень для випадку n=3 та m=4: ПЕРЕЛІЧЕННЯ БІНАРНИХ ПОЄДНАНЬ При апаратній реалізації поєднань або при програмуванні мовою асемблера важливо мати можливість обробки записів поєднань у двійковому форматі. У цьому випадку будь-яке поєднання з n елементів по m слід задавати у формі n-розрядного двійкового числа (B n ... B j ... B 1), де m одиничних розрядів позначають елементи поєднання, а інші (nm) розрядів мають нульові значення. Очевидно, що при такій формі запису різні поєднання повинні відрізнятися розташуванням одиничних розрядів і існує всього C(n,m) способів розмістити m одиниць або (nm) нулів у n-розрядному двійковому наборі. Наприклад, у наступній таблиці перераховані всі 6 таких бінарних поєднань, які забезпечують запис 4-х розрядними двійковими числами всіх поєднань з 4-х елементів довільної множини (E 1 ,E 2 ,E 3 ,E 4 ) по 2: У випадку завдання перерахування таких бінарних поєднань зводиться до систематичного перебору всіх n-разрядных двійкових наборів з різним розташуванням m одиничних і (nm) нульових розрядів. У найпростішій формі такий перебір реалізують різні методи транспозиції суміжних розрядів зі зрушенням (транспозитивно-зсувні алгоритми). Це ітераційні алгоритми, які назви відбивають характер операцій, виконуваних кожному кроці. Ітераційні процедури транспозитивно-зсувних алгоритмів формують послідовності бінарних поєднань, які починаються двійковим набором, де всі одиниці зосереджені в молодших розрядах (праворуч), і завершуються, коли всі одиниці будуть у старших розрядах (ліворуч): Збігаючись за початковими та кінцевими поєднаннями, ці послідовності відрізняються порядком перерахування проміжних двійкових наборів. Однак у всіх випадках кожне наступне бінарне поєднання формується за попереднім у результаті виконання відповідних операцій транспозиції та зсуву. При цьому різні транспозитивно-зсувні алгоритми відрізняються способом вибору пари розрядів для транспозиції та групи розрядів для зсуву. Ця специфіка розглянута нижче для алгоритмів транспозиції з лівим та правим зрушенням. В алгоритмі транспозиції з лівим зрушенням на кожному кроці чергове бінарне поєднання виходить з поточного заміною крайньої лівої пари розрядів 01 на 10 (транспозиція) і зміщенням групи лідируючих одиничних розрядів, якщо є, впритул до пари 10, отриманої після транспозиції (з. Якщо при цьому в поточному бінарному поєднанні немає одиниць у старших розрядах, то зсув не проводиться навіть коли лідируюча одиниця виходить після транспозиції на даному кроці. Зсув також не проводиться, коли у старших розрядах перед парою 10, отриманої після транспозиції немає нулів. Розглянуті дії ілюструє наступний приклад виконання двох послідовних ітерацій даного алгоритму, де на одній ітерації (15) проводиться тільки транспозиція (T"), а на іншій (16) транспозицію доповнює зсув (T"+S"): В алгоритмі транспозиції з правим зрушенням на кожному кроці виконуються концептуально аналогічні дії. Тільки транспозиція забезпечує заміну крайньої правої розрядів 01 на 10 (замість крайньої лівої), а потім здійснюється зсув всіх одиниць праворуч від неї до молодших розрядів. Як і раніше, зсув проводиться тільки за наявності одиниць, які можуть бути зміщені вправо. Розглянуті дії ілюструє наступний приклад виконання двох послідовних ітерацій даного алгоритму, де на одній ітерації (3) здійснюється тільки транспозиція (T"), а на іншій ітерації (4) транспозицію доповнює зсув (T"+S"): Слід зазначити, що ітерації обох алгоритмів можна записати в адитивній формі, якщо інтерпретувати бінарні поєднання як цілі числа в системі числення на основі 2. Зокрема, для алгоритму транспозиції з правим зрушенням кожне чергове бінарне поєднання (B" n ,…B" j , …B" 1), можна завжди отримати з поточного поєднання (B n ,…B j ,…B 1), виконавши операції додавання цілих чисел за наступною адитивною формулою: У цій адитивній формулі показники ступенів двійок f і t позначають, відповідно, число нульових молодших розрядів поточного бінарного поєднання та кількість одиниць, що стоять поспіль зліва від них. Наприклад, для 4-го бінарного поєднання (001110) з n=6 розрядів f=1 та t=3. Отже, обчислення чергового бінарного поєднання за адитивною формулою на ітерації 5 дасть наступний результат, еквівалентний виконання операцій транспозиції та зсуву: Для порівняльного аналізу розглянутих алгоритмів транспозиції з лівим та правим зрушенням доцільно зіставити послідовності бінарних поєднань, які вони породжують на своїх ітераціях. У наступній таблиці показані дві такі послідовності бінарних поєднань з 4-х елементів по 2, які отримані алгоритмами з лівим (TSL) та правим (TSR) зсувом, відповідно: Порівнюючи ці 2 послідовності, можна побачити, що є обратно-зеркальными. Це означає, що будь-які два бінарних поєднання, які розташовані в них на однаковій відстані від взаємно-протилежних кінців своїх послідовностей, є дзеркальним відображенням один одного, тобто збігаються при зміні зворотної індексації розрядів у будь-якому з них. Наприклад, друге від початку послідовності TSL бінарне поєднання (0101) є дзеркальним відображенням бінарного поєднання (1010), що знаходиться на другому місці від кінця послідовності TSR. Загалом будь-яке бінарне поєднання з номером i однієї послідовності є дзеркальним відображенням бінарного поєднання з номером (ni+1) іншої послідовності. Таке співвідношення цих послідовностей є наслідком симетричного характеру операцій транспозиції та зсуву у двох розглянутих алгоритмах перерахування бінарних поєднань. Слід зазначити, що двійковий формат можна застосувати для запису поєднань з повтореннями елементів. Для цього потрібно встановити взаємно однозначну відповідність між поєднаннями з повтореннями та бінарними поєднаннями, які конструюються наступним чином. Нехай є довільне поєднання з повтореннями, яке отримано вибором m необов'язково різних елементів n елементів утворює множини. Для встановлення шуканого відповідність потрібно спочатку приєднати до поєднання всі елементи, що утворюють множини (cat), а потім відсортувати отриману конкатенацію (sort), щоб всі однакові елементи виявилися поруч. В результаті вийде послідовність (n+m) елементів, де n груп однакових елементів. Між елементами в ній буде всього (n+m1) проміжків, серед яких буде (n1) проміжків між групами однакових елементів та m проміжків між елементами усередині груп. Для наочності у вказаних проміжках можна розмістити символи "|" і відповідно. Якщо тепер зіставити 1 проміжкам між групами (|) і 0 решті всіх проміжків (), то вийде бінарне поєднання. Його утворює двійковий набір (n+m1) розрядів, де (n1) одиничних і m нульових розрядів, розташування яких однозначно відповідає вихідному поєднанню з повтореннями з елементів n по m. Розглянуту техніку перетворень ілюструє наступний приклад побудови бінарного поєднання (1001101) за поєднанням з повтореннями (BBD), елементи якого обрані з утворює безліч перших п'яти латинських літер: У загальному випадку кількість таких двійкових наборів визначає кількість способів розташувати (n1) одиниць (або m нулів) у (n+m1) двійкових розрядах. Це значення, очевидно, дорівнює числу поєднань з (n+m1) по (n1) або по m, тобто C(n+m1,n1) або C(n+m1,m), яке дорівнює числу поєднань з повтореннями f( n,m)з n елементів m. Таким чином, маючи взаємно однозначну відповідність між поєднаннями з повтореннями та бінарними поєднаннями правомірно звести перерахування поєднань з повтореннями до перебору бінарних поєднань, наприклад, алгоритмів транспозиції з лівим або правим зрушенням. Після цього потрібно тільки відновити поєднання, що шукаються, з повтореннями за отриманими бінарними сполученнями. Це можна зробити, застосувавши наступний відновлювальний прийом. Нехай основна множина, з елементів якого утворюються поєднання з повтореннями по m необов'язково різних елементів, упорядковано довільним чином так, що кожен його елемент має певний порядковий номер від 1 до n. Нехай також реалізовано перерахування бінарних поєднань із (n+m1) двійкових розрядів, де (n1) одиничних та m нульових розрядів. Кожне отримане бінарне поєднання можна доповнити ліворуч фіктивним одиничним розрядом, і пронумерувати всі одиничні розряди ліворуч праворуч цілими числами від 1 до n. Тоді число нулів, що стоять поспіль після кожної i-ї одиниці бінарного поєднання, дорівнюватиме кількості екземплярів i-го елемента основної множини у відповідному поєднанні з повтореннями. Розглянутий прийом ілюструє наступний приклад, де по бінарному поєднанню (1001101) відновлюється поєднання з повтореннями BBD, елементи якого обрані з утворює безліч перших п'яти латинських букв, записаних в алфавітному порядку, а підкреслення позначає елементи, відсутні в цьому поєднанні: Виконуючи аналогічні дії в умовах даного прикладу, можна перерахувати всі 35 бінарних поєднань, які утворюють 7-ми розрядні двійкові набори, де 4 одиниці та 3 нуля, та відновити відповідні їм поєднання з повтореннями з 5-ти елементів по 3. приклад // Поєднання по 3 із 52 for (int i1 = 0; i1< 50; ++i1)
for (int i2 = i1+1; i2 < 51; ++i2)
for (int i3 = i2+1; i3 < 52; ++i3)
// ...
Тут ми розглянемо складнішу задачу, рішення якої у рунеті я не знайшов (втім, наведу одне посилання, але та формула явно неправильна) - виходячи з самого поєднання (в даному випадку набору трьох чисел) знайти його індекс. Припустимо, для визначеності, після впорядкування i1 = 3, i2 = 7, i3 = 12. Типовий алгоритм генерації полягає в тому, що ми генеруємо поєднання по 2 з 52 і для кожного такого поєднання у вкладеному циклі генеруємо поєднання по 3 з 50, причому перевіряємо, щоб індекси (i3, i4, i5) у вкладеному поєднанні не збігалися з індексами (i1, i2) у зовнішньому поєднанні: Код C++ // ЗОВНІШНЕ ПОЄДНАННЯ for (int i1 = 0; i1< 51; ++i1)
for (int i2 = i1+1; i2 < 52; ++i2)
// ВНУТРЕННЕЕ СОЧЕТАНИЕ
for (int i3 = 0; i3 < 50; ++i3)
if (i3 != i1 && i3 != i2)
for (int i4 = i3+1; i4 < 51; ++i4)
if (i4 != i1 && i4 != i2)
for (int i5 = i4+1; i5 < 52; ++i5)
if (i5 != i1 && i5 != i2)
// ...
Код C++ if (i3> = i1) -i3; if (i3> = i2) -i2; // аналогічно для i4, i5 Приклад коду для індексу розбиття на 2, 3, 47 int get_split_2_3_47_index(int i1, int i2, int i3, int i4, int i5) ( // Індекс поєднання по 2 з 52, помножений на C(3, 50) int offset = ((52*51 - (51-i1)) *(52-i1)) / 2 + (i2 - i1 - 1)) * 19600;// "Переіндексуємо" внутрішню групу так, щоб була нумерація 0...49 if (i3 >= i1) --i3; if (i3 >= i2) --i3; if (i4 >= i1) --i4; if (i4 >= i2) --i4; if (i5 >= i1) --i5; if (i5 >= i2) --i5;// Тепер додамо індекс поєднання по 3 // 0: // СУМА для n = 0 по i3-1 ПОЄДНАНЬ (2, 49-n) // = СУМА для m = 50-i3 по 49 (m * (m-1) / 2) offset += (19600 - (((49-i3)*(50-i3)*(99-2*i3)) / 6 - ((49-i3)*(50-i3) )) / 2) / 2); - (49-i4)*(50-i4)) / 2);// 2: // СУМА для n = i4+1 по i5-1 (1) offset += (i5 - i4 - 1); ;) Взагалі комбінаторні алгоритми я б розбив на такі класи: Число поєднань Поєднаннямз nпо kназивається набір kелементів, вибраних із даних nелементів. Набори, що відрізняються тільки порядком проходження елементів (але не складом), вважаються однаковими, цим поєднання відрізняються від розміщень. Число поєднань з nпо k
дорівнює біноміальному коефіцієнту При фіксованому значенні nвиконує функцією чисел поєднань з повтореннями з nпо kє: Двовимірною функцією чисел поєднань з повтореннями є: Wikimedia Foundation. 2010 . 70 сімдесят 67 · 68 · 69 · 70 · 71 · 72 · 73 40 · 50 · 60 · 70 · 80 · 90 · 100 Факторизація: 2×5×7 Римський запис: LXX Двійковий: 100 0110 … Вікіпедія Світлове число, умовне число, що однозначно виражає зовніш. умови при зйомці (зазвичай яскравість об'єкта зйомки і світлочутливість застосовуваного фотоматеріалу). Будь-якому значенню Е. ч. можна підібрати дек. поєднань діафрагмове число. Великий енциклопедичний політехнічний словник Форма числа, що виділяє два предмети як по відношенню до одиничного предмета, так і по відношенню до безлічі предметів. У сучасній російській мові ця форма не існує, але залишки її впливу збереглися. Так, поєднання два столи (пор. мн. ч.… … Словник лінгвістичних термінів Комбінаторна математика, комбінаторика, розділ математики, присвячений вирішенню завдань вибору та розташування елементів деякої, зазвичай кінцевої, множини відповідно до заданих правил. Кожне таке правило визначає спосіб побудови. Математична енциклопедія У комбінаториці поєднанням з називається набір елементів, вибраних з даної множини, що містить різних елементів. Набори, що відрізняються тільки порядком прямування елементів (але не складом), вважаються однаковими, цим поєднанням. Займається вивченням подій, настання яких достовірно невідоме. Вона дозволяє судити про розумність очікування настання одних подій порівняно з іншими, хоча приписування чисельних значень ймовірностей подій часто буває зайвим. Енциклопедія Кольєра 1) те саме, що математичний комбінаторний аналіз. 2) Розділ елементарної математики, пов'язаний з вивченням кількості комбінацій, підпорядкованих тим чи іншим умовам, які можна скласти із заданої кінцевої множини об'єктів. Велика Радянська Енциклопедія - (грец. paradoxos несподіваний, дивний) у широкому сенсі: твердження, що різко розходиться із загальноприйнятою, усталеною думкою, заперечення того, що видається «безумовно правильним»; у вужчому сенсі два протилежні твердження, для… Філософська енциклопедія - (або принцип включень винятків) комбінаторна формула, що дозволяє визначити потужність об'єднання кінцевої кількості кінцевих множин, які в загальному випадку можуть перетинатися один з одним. Математична теорія, що займається визначенням кількості різних способів розподілу даних предметів у порядку; має особливо важливе значення в теорії рівнянь та теорії ймовірностей. Найпростіші завдання цього роду полягають у… Енциклопедичний словник Ф.А. Брокгауза та І.А. Єфрона Комбінаторика - це розділ математики, у якому вивчаються питання, скільки різних комбінацій, підпорядкованих тим чи іншим умовам, можна скласти із заданих об'єктів. Основи комбінаторики дуже важливі з метою оцінки ймовірностей випадкових подій, т.к. саме вони дозволяють підрахувати принципово можливу кількість різних варіантів розвитку подій. Нехай є k груп елементів, причому i група складається з n i елементів. Виберемо по одному елементу з кожної групи. Тоді загальна кількість N способів, якими можна зробити такий вибір, визначається співвідношенням N = n 1 * n 2 * n 3 * ... * n k . приклад 1.Пояснимо це правило простому прикладі. Нехай є дві групи елементів, причому перша група складається з n 1 елементів, а друга - n 2 елементів. Скільки різних пар елементів можна скласти із цих двох груп, таким чином, щоб у парі було по одному елементу від кожної групи? Допустимо, ми взяли перший елемент із першої групи і, не змінюючи його, перебрали всі можливі пари, змінюючи лише елементи з другої групи. Таких пар цього елемента можна скласти n 2 . Потім ми беремо другий елемент із першої групи і також складаємо для нього всі можливі пари. Таких пар також буде n 2 . Так як у першій групі всього n 1 елемент, всього можливих варіантів буде n 1 * n 2 . приклад 2.Скільки трицифрових парних чисел можна становити з цифр 0, 1, 2, 3, 4, 5, 6, якщо цифри можуть повторюватися? У разі, коли всі групи складаються з однакового числа елементів, тобто. n 1 =n 2 =...n k =n вважатимуться, кожен вибір виробляється з однієї й тієї групи, причому елемент після вибору знову повертається у групу. Тоді число всіх способів вибору дорівнює n k. Такий спосіб вибору комбінаторики носить назву вибірки із поверненням. приклад 3.Скільки всіх чотирицифрових чисел можна становити з цифр 1, 5, 6, 7, 8? Розглянемо безліч, які з n елементів. Це безліч у комбінаториці називається генеральною сукупністю. Визначення 1.Розміщенням з nелементів по mу комбінаториці називається будь-який упорядкований набірз mрізних елементів, вибраних з генеральної сукупності в nелементів. приклад 4.Різними розміщеннями з трьох елементів (1, 2, 3) по два будуть набори (1, 2), (2, 1), (1, 3), (3, 1), (2, 3), (3, 2) ). Розміщення можуть відрізнятися друг від друга як елементами, і їх порядком. Число розміщень у комбінаториці позначається A n m і обчислюється за такою формулою: Примітка: n!=1*2*3*...*n (читається: "ен факторіал"), крім того вважають, що 0!=1. Приклад 5. Скільки існує двозначних чисел, у яких цифра десятків та цифра одиниць різні та непарні? Визначення 2. Поєднаннямз nелементів по mу комбінаториці називається будь-який невпорядкований набірз mрізних елементів, вибраних з генеральної сукупності в nелементів. Приклад 6. Для множини (1, 2, 3) поєднаннями є (1, 2), (1, 3), (2, 3). Число поєднань позначається C n m і обчислюється за такою формулою: Приклад 7.Скільки способами читач може вибрати дві книжки із шести наявних? Рішення:Число методів дорівнює числу поєднань із шести книжок по дві, тобто. одно: Визначення 3. Перестановкоюз nелементів називається будь-який упорядкований набірцих елементів. Приклад 7a.Різними перестановками множини, що складається з трьох елементів (1, 2, 3) є: (1, 2, 3), (1, 3, 2), (2, 3, 1), (2, 1, 3), ( 3, 2, 1), (3, 1, 2). Число різних перестановок з елементів n позначається P n і обчислюється за формулою P n = n!. Приклад 8.Скільки способами сім книг різних авторів можна розставити на полиці в один ряд? Рішення:це завдання про кількість перестановок семи різних книг. Є P 7 =7!=1*2*3*4*5*6*7=5040 способів здійснити розміщення книг. Обговорення. p align="justify"> Ми бачимо, що число можливих комбінацій можна порахувати за різними правилами (перестановки, поєднання, розміщення) причому результат вийде різний, т.к. Принцип підрахунку і самі формули відрізняються. Уважно подивившись визначення, можна побачити, що результат залежить від кількох чинників одночасно. По-перше, з того, з якої кількості елементів ми можемо комбінувати їх набори (наскільки велика генеральна сукупність елементів). По-друге, результат залежить від того, який розмір набори елементів нам потрібні. І останнє, важливо знати, чи є для нас суттєвим порядок елементів у наборі. Пояснимо останній чинник на такому прикладі. Приклад 9.На батьківських зборах присутні 20 осіб. Скільки існує різних варіантів складу батьківського комітету, якщо до нього мають увійти 5 осіб? Інакше будуть справи, якщо кожен член комітету спочатку відповідає за певний напрямок роботи. Тоді при тому самому списковому складі комітету, всередині нього можливо 5! варіантів перестановокякі мають значення. Кількість різних (і за складом, і за сферою відповідальності) варіантів визначається у цьому випадку числом розміщеньіз 20 елементів по 5. Завдання для самоперевірки 2. Скільки існує п'ятизначних чисел, які однаково читаються зліва направо та праворуч наліво? 3. У класі десять предметів та п'ять уроків на день. Скільки способами можна скласти розклад на один день? 4. Скільки можна вибрати 4 делегати на конференцію, якщо в групі 20 осіб? 5. Скільки способами можна розкласти вісім різних листів по восьми різних конвертах, якщо кожен конверт кладеться лише одне лист? 6. З трьох математиків та десяти економістів треба скласти комісію, що складається з двох математиків та шести економістів. Скільки способами це можна зробити?Індекс поєднання
Кожному поєднанню, перестановці, розміщенню та іншим комбінаторним об'єктам можна порівняти індекс - це номер, де він з'являється при переборі даним алгоритмом.
Є варіант перебору "в лоб". Включаємо лічильник поєднань, беремо алгоритм вище і доки не дійдемо до потрібного варіанта перебираємо все поспіль. Такий варіант має дуже велику тимчасову складність, тому такий варіант відкинемо.
Припустимо, на вході є числа i1, i2, i3. Нам, перш за все, потрібно їх упорядкувати в порядку зростання (зверніть увагу, що сам алгоритм генерації, наведений вище, видає їх завжди в упорядкованому вигляді, хоча поняття «поєднання» передбачає довільний порядок).
Це означає, що ми «пройшли» всі поєднання, де i1 дорівнював 0, 1 і 2.
Для i1 = 0 ми пройшли C(2, 51) сполучень, оскільки індекси i1, i2 пробігають усі поєднання по 2 із 51 числа.
Для i1 = 1 ми пройшли C(2, 50) сполучень.
Для i1 = 2 ми пройшли C(2, 49) сполучень.
Разом ми пройшли СУМА (від n = 0 до n = i1-1) C(2, 51-n).
При i1 = 3 розглянемо вже ті поєднання, які ми пройшли, бігаючи індексом i2 (а він у нас починається з i2 = i1+1 = 4).
При i2 = 4 пройшли C(1, 47) сполучень, при i2 = 5 пройшли C(1, 46) сполучень, при i2 = 6 пройшли C(1, 45) сполучень.
За повною аналогією, при i2 = 7 розглядаємо поєднання, що пробіг індекс i3.
Отримуємо загальну формулу:
Шуканий індекс поєднання = СУМА (від n = 0 до i1-1) C(2, 51-n) + СУМА (від n = i1+1 до i2-1) C(1, 51-n) + СУМА (від n = i2+1 і3-1) C (0, 51-n).Індекс розбиття на підмножини
У комбінаториці є і складніший об'єкт - розбиття на підмножини. Наприклад, розбиття 52-елементного множини на три підмножини, що складаються відповідно, скажімо, з 2, 3 і 47 елементів, де порядок елементів усередині кожної підмножини неважливий. (До речі, поєднання по 2 з 52 - це просто окремий випадок розбиття на два підмножини з 2 і 50 елементів відповідно).
Знову ж таки, кожне таке розбиття має свій індекс.
Виявляється, наш алгоритм знаходження індексу поєднання можна модифікувати для знаходження індексу розбиття.
Треба звернути увагу, що індекси у зовнішньому поєднанні i1, i2 нам потрібно впорядковувати між собою, а індекси i3, i4, i5 - між собою, але незалежно від перших двох.
Також слід врахувати, що у "вкладеному поєднанні" по суті ми працюємо з 50-елементним безліччю, але індекси i3, i4, i5 потрібно певним чином "зрушити", щоб вони змінювалися не від 0 до 51, а від 0 до 49:
(так сказати, ми вирізаємо з нашої 52-елементної множини індекси i1, i2 і потім зрушуємо решту, щоб закрити дірки, при цьому зсуваються індекси i3-i5).
Слід врахувати при цьому, що всередині кожного зовнішнього поєднання у нас сидить рівно C (3, 50) вкладених поєднань.
Тоді алгоритм зведеться до наступного:
ІНДЕКС_ПОЄДНАННЯ (i1, i2 з 52) * ЧИСЛО_ПОЄДНАНЬ_ПО_3_З_50 + ІНДЕКС_ПОЄДНАННЯ (i3, i4, i5 з 50 після зсуву індексів). Приведення алгоритмів до константної складності
Відразу повинен звернути увагу, що у формулі виникає «помилка», якщо, наприклад, i1 = 0 (ми вважаємо суму для n = від 0 до -1) або i2 = 1 (вважаємо суму від 1 до 0). Насправді у разі відповідну суму слід приймати рівної нулю, і результат вийде коректним.
Також повинен звернути увагу на тимчасову складність наших алгоритмів: вони мають лінійну складність за умови, що C ви вважаєте за константний час. Це вже набагато краще, ніж перебір у лоб.
Але насправді (У нашому випадку 52) нічого не заважає звести алгоритм до константної складності. Для цього застосуємо знання математики та аналітично порахуємо всі суми.
Наприклад, число поєднань C(2, K), якщо розкрити його у вигляді формули K! /((K-2)!*2!), наводиться до многочлена 2-го ступеня. А оскільки він у нас під знаком суми, то можна застосувати формули суми N-х ступенів чисел натурального ряду (див. Вікіпедію) і отримати один-єдиний багаточлен 3-го ступеня. Який, мабуть, має константну тимчасову складність. (Причому «помилка», яку я навів на початку підзаголовка, ніяк не проявляє себе, формула залишається коректною).
Повторюся, це для фіксованої розмірності базової множини. Втім, певен, за допомогою метапрограмування можна «навчити» компілятор, щоб він робив цю роботу за вас. Післямова
Мені у своєму симуляторі покеру (Texas Hold'em) захотілося заздалегідь розрахувати та зберігати ймовірності виграшу для всіх можливих поєднань з моїх ручних карт (2 штуки) та всіх карт флопа (3 карти на столі). Це відповідає розбиттю 52-множини на 2, 3, 47 підмножини.
Розрахував та зберіг.
Але коли настав час прочитати дані з файлу для конкретної комбінації, дуже мені не хотілося щось там довго обчислювати або шукати в гігабайтному файлі. Тепер я просто визначаю зміщення у файлі та зчитую безпосередньо те, що мені треба.
Було б цікаво отримати довідник за комбінаторними алгоритмами для всіх комбінаторних об'єктів, включаючи перестановки, поєднання, розміщення, розбиття на підмножини, поєднання з повтореннями, розміщення з повтореннями. Явні формули
Посилання
Дивитись що таке "Кількість поєднань" в інших словниках:
Книги
Основна формула комбінаторики
Рішення: n 1 =6 (т.к. як перша цифра можна взяти будь-яку цифру з 1, 2, 3, 4, 5, 6), n 2 =7 (т.к. як другу цифру можна взяти будь-яку цифру з 0 , 1, 2, 3, 4, 5, 6), n 3 =4 (т.к. як третя цифра можна взяти будь-яку цифру з 0, 2, 4, 6).
Отже, N = n 1 * n 2 * n 3 = 6 * 7 * 4 = 168.
Рішення.До кожного розряду чотиризначного числа є п'ять можливостей, отже N=5*5*5*5=5 4 =625.Число розміщень з n елементів m
Рішення:т.к. непарних цифр п'ять, саме 1, 3, 5, 7, 9, це завдання зводиться до вибору і розміщення дві різні позиції двох із п'яти різних цифр, тобто. вказаних чисел буде:
Число поєднань з n елементів m
Перестановки з n елементів
Рішення:У цьому прикладі нас не цікавить порядок прізвищ у списку Комітету. Якщо в результаті в його складі будуть одні й ті ж люди, то за змістом для нас це один і той самий варіант. Тому ми можемо скористатися формулою для підрахунку числа поєднаньіз 20 елементів по 5.
1. Скільки трицифрових парних чисел можна становити з цифр 0, 1, 2, 3, 4, 5, 6, якщо цифри можуть повторюватися?
Значення та походження прізвища беляїв
Методика мещерякової "англійська для дітей"
Снігова королева Снігова королева аудіо