Новиков Ф.А. Дискретная математика для программистов (860615), страница 36
Текст из файла (страница 36)
. + |tn| = / ( / ) .СЛЕДСТВИЕ•Всякая сортировка может быть выполнена перестановкой соседнихэлементов.ОТСТУПЛЕНИЕДоказанная теорема утверждает, что произвольную перестановку можно представить ввиде композиции определённого числа транспозиций, но не утверждает, что такое представление является эффективным. Метод сортировки, основанный на предшествующейтеореме, известен как метод пузырька. Заметим, что при перемещении элемента на своё186Глава 5. Комбинаторика'место транспозициями соседних элементов все элементы остаются на своих местах, кромедвух соседних элементов, которые, возможно, меняются местами. Таким образом, методпузырька может быть выражен в форме алгоритма 5.1.
Этот алгоритм прост, но являетсядалеко не самым эффективным алгоритмом сортировки.Алгоритм 5.1 Сортировка методом пузырькаВход: массив А : array [l..n] of В, где значения элементов массива расположеныв произвольном порядке и для значений типа В задано отношение <.Выход: массив А : array [l..n] of В, в котором значения расположены в порядкевозрастания,for г from 2 to п dofor j from n downto i doif A[j) < A[j - 1] thenA[j] <-• A[j - 1] { транспозиция соседних элементов }end ifend forend for5.2.3. Генерация перестановокНа множестве перестановок естественным образом можно определить порядок паоснове упорядоченности элементов. А именно, говорят, что перестановка( a i , .
. . , ап) лексикографически предшествует перестановке (Ь\,..., Ьп), если3 k ^ п (ак < bk SzVi < к (a* = bi)) (см. также упражнение 1.8). Аналогично,говорят, что перестановка ( a i , . . . ,a n ) антилексикографически предшествует перестановке ( 6 i , . . . , Ьп), если 3 k ^ п (ак > bk & Уг > к (ai = bi)).Следующий алгоритм генерирует все перестановки элементов 1 , . . .
, п в аитилексикографическом порядке. Массив Р : array [l..n] of 1 ..п является глобальными предназначен для хранения перестановок.Алгоритм 5.2 Генерация перестановок в антилексикографическом порядкеВход: п — количество элементовВыход: последовательность перестановок элементов 1 , . . . , п в аптилексикографическом порядке,for г from 1 to n doР[г]: = г { инициализация }end forAntilex(n) { вызов рекурсивной процедуры Antilex }Основная работа по генерации перестановок выполняется рекурсивной процедурой Antilex.I 5.2. Перестановки187Вход: тп — параметр процедуры — количество первых элементов массива Р, для которыхгенерируются перестановки.Выход: последовательность перестановок 1,... ,тп в антилексикографическом порядке,if га = 1 thenyield Р { очередная перестановка }elsefor г from 1 to тп do-Antilex(ra - 1) { рекурсивный вызов }if г < га thenP[i] *-* P[m] { следующий элемент }Reverse(ra - 1) { изменение порядка элементов }end ifend forend ifВспомогательная процедура Reverse переставляет элементы заданного отрезкамассива Р в обратном порядке.Вход: к — помер элемента, задающий отрезок массива Р, подлежащий перестановкев обратном порядке.Выход: первые к элементов массива Р переставлены в обратном порядкеj : = 1 { нижняя граница обращаемого диапазона }while j < к doP[j] P[k] { меняем местами элементы }j ; = j + 1 { увеличиваем нижнюю границу }к\ = к — 1 { уменьшаем верхнюю границу }end whileЗаметим, что искомую последовательность перестановок п элементов можно получить из последовательности перестановок п — 1 элементовследующим образом.
Нужно выписать п блоков по (п—1)! перестановок в каждом,соответствующих последовательности перестановок п - 1 элементов в антилексикографическом порядке. Затем ко всем перестановкам в первом блоке нужноприписать справа п, во втором — п - 1 и т. д. в убывающем порядке. Затемв каждом из блоков (кроме первого), к перестановкам которого справа приписан элемент г, нужно в перестановках блока заменить все вхождения элементаг на элемент п. В полученной последовательности все перестановки различны,и их п(п - 1)! = п\, то есть перечислены все перестановки.
При этом антилексикографический порядок соблюден для последовательностей внутри одногоблока, потому что этот порядок был соблюден в исходной последовательности,а для последовательностей па границах двух блоков — потому что происходитуменьшение самого правого элемента. Обратимся к процедуре Antilex — легковидеть, что в ней реализовано указанное построение. В основном цикле сначала строится очередной блок — последовательность перестановок первых тп - 1элементов массива Р (при этом элементы Р[тп],..., Р[п] остаются неизменными). Затем элемент Р[тп] меняется местами с очередным элементом Р[г\. Вызоввспомогательной процедуры Reverse необходим, поскольку последняя перестановка в блоке является обращением первой, а для генерации следующего блокана очередном шаге цикла нужно восстановить исходный порядок.•ОБОСНОВАНИЕ188Глава 5.
Комбинаторика'ПримерПоследовательность перестановок в антилексикографическом порядАке для п = 3: (1, 2, 3), (2,1,3), (1,3, 2), (3,1, 2), (2,3,1), (3, 2,1).I5.2.4. Двойные факториалыСодержание этого подраздела не имеет отношения к основной теме раздела —перестановкам и включено в раздел по сходству обозначений и с целью -привести две формулы, которые иногда используются в практических комбинаторныхрасчётах и требуются в последующих разделах.Двойным факториалом натурального числа п (обозначается п!!) называется произведение числа п и всех меньших натуральных чисел той же чётности.Пример10!! = 10 • 8 • 6 • 4 • 2 = 3840.ТЕОРЕМА1.
(2/с)!! = 2к • k\.ДОКАЗАТЕЛЬСТВО[ 1 ] (2fc)!! = 2 - 4(2к — 2) • 2к = (2 • 1) • (2 • 2)= 4(2 • 22 • 2)-(1•2(к - I) • к) — 2к • к\./(2 • (к - 1)) • (2 • к) =vк раз[ 2 ] Достаточно заметить, что (2к + 1)! = (2к + 1)!!(2к)\\.•5.3. Биномиальные коэффициентыЧисло сочетаний С(т,п) — это число различных n-элементпых подмножествга-элементного множества (см.
5.1.5). Числа С(т,п) обладают целым рядомсвойств, рассматриваемых в этом разделе, которые оказываются очень полезными при решении различных комбинаторных задач.5.3.1. Элементарные тождестваОсновная формула для числа сочетанийпозволяет получить следующие простые тождества.ТЕОРЕМА1. С(т,п)= С(т,т - п ) .2. C(m, п) = С { т - 1, п) + С ( т - 1, п - 1).3. С(п, г)С(г, гп) = С(п, т)С(п - т, г - т).189,5.3. Биномиальные коэффициентыДОКАЗАТЕЛЬСТВО[1][2]Ш !С{тп,т- п) =———гтт = 7Ц—: = С(т, п).(га — п)! (га — (га — п))\{тп — п)\п\С(тп — 1, n) + С(га — 1, п — 1) =(ш-1)!( т — 1)!п!(т-п-1)!(п-1)! ( m - l - ( n - l ) ) !( т — 1)!(т-1)!п(п — 1)! (га — п — 1)! (п — 1)! (тп — n)(m — п — 1)!(т — п)(т — 1)! + п(тп — 1)!п(п — 1)! (тп — п)(тп — п — 1)!(тп — п + п)(тп — 1)!т!- С ( т , п).п\ (тп — п)\п\ (тп — п)![3]ч^,/чп\г!п!г\(п — г)! т!(г — тп)! т!(г — тп)\(п — г)!п\(п — тп)\m\(i — тп)\(п — i)\(n — т)!гг!(п — тп)\тп\(п — т ) ! (г — тп)\(п — г)!= C(n,m)C(n — m,i — т).С(п,г)С(г,т) =•5.3.2.
Бином НьютонаЧисла сочетаний С(ш, п) называются также биномиальными коэффициентами.Смысл этого названия устанавливается следующей теоремой, известной такжекак формула бинома Ньютона}.тТЕОРЕМА(Х + У ) Т = ^ 2 С ( Т , П ) Х П У Т - П .п=ОДОКАЗАТЕЛЬСТВОПОиндукции. База, ш = 1:1(х + у)1 = х + у = 1 х1у° + 1хУ= С(1,0)х1у°+ С( 1, l ) ^1=С( 1,п-ОИндукционный переход:1Исаак Ньютон ( 1 6 4 3 - 1 7 2 7 ) .п)хпу1~п.190Глава 5. Комбинаторика'(х + у)т = (х + у)(х + у)т~1 = (х + у)тп— 1С т(1,п)хпут-п~1=71=0rn—1т— 1= Y^ хС(т - 1,п)хпут~п~1уС{т - 1,п)хпут-п-1+п=О=-=п=0тп—1C m(l,n)xn+1ym~n_1+71=07Птп — 1С{т - 1,гь)хпут~п=71=0771 — 1—1,п- 1)хпут"п+ ^=71=1С ( т — 1, п ) х п у т ~ п =71 = 0ТП—1= С ( т - 1,0)ж°у то + ^( С ( т - 1, п - 1) + C ( m - 1, п ) ) х п у ш " п +71=1гтг+ С(т - 1, m - l)xmy°С(т,п)япг/ш-п.=•71=0СЛЕДСТВИЕ 1ДОКАЗАТЕЛЬСТВОСЛЕДСТВИЕ 2£ C ( m , п) = 2 m .71=077171=071 = 0•£ ( - 1 ) п С ( т , т г ) = 0.71 =ДОКАЗАТЕЛЬСТВОП2 m = (1 + 1 ) т = £ С ( т , п ) 1 п 1 т " п = £ С(т,тг).00 = ( - 1 + 1)Т =£ С{т,п){71=01)п1т~п= £(-1)ПС(Т,ТГ).•71=05.3.3.
Свойства биномиальных коэффициентовБиномиальные коэффициенты обладают целым рядом замечательных свойств.ТЕОРЕМА 1771£ пС{т,п)71=0= m2m_1.ДОКАЗАТЕЛЬСТВОРассмотрим следующую последовательность, составленную изчисел 1 , . . . , т . Сначала выписаны все подмножества длины 0, потом все подмножества длины 1 и т. д. Имеется С ( т , тг) подмножеств мощности тг, и каждое из них имеет длину тг, таким образом, всего в этой последовательноститY^ nC(m,n) чисел. С другой стороны, каждое число х входит в эту последо71=0вателыюсть= 2 т _ 1 раз, а всего чисел т .•191,5.3. Биномиальные коэффициентыкТЕОРЕМА 2С(т + п, А;) = £ С{т, г)С(п, к - г).<=оДОКАЗАТЕЛЬСТВОC(n + m,fc)— это число способов выбрать к предметов из m + nпредметов.
Предметы можно выбирать в два приема: сначала выбрать г предметов из первых тп предметов, а затем выбрать недостающие к - г предметов изоставшихся п предметов. Отсюда общее число способов выбрать к предметовксоставляет ^ С(тп, г)С(п, к — г).г=0•ЗАМЕЧАНИЕПоследнее свойство известно как тождество Кошу}.ОТСТУПЛЕНИЕДанные свойства биномиальных коэффициентов нетрудно доказать, проводя алгебраические выкладки обычным образом.
Например, первое свойство можно получить так:пт1т(т- sr— — 1)!_2j(V_ „ ) ! ( „V_ i)! ~4m(n)!n!mn=071 = 1'71— 1''m— 1 /m—1=m V ,;, , = m V C(m— 1, 7n) = m2 m _ 1 .vv(m-n^l)!n!n=0>n=0В доказательстве использованы рассуждения «в комбинаторном духе», чтобы проиллюстрировать «неалгебраические» способы решения комбинаторных задач.ч _5.3.4. Треугольник ПаскаляИз второй формулы теоремы 5.3.1 вытекает эффективный способ рекуррентноговычисления значений биномиальных коэффициентов, который можно представить в графической форме, известной как треугольник Паскаля2.111113412136141В этом равнобедренном треугольнике каждое число (кроме единиц на боковых сторонах) является суммой двух чисел, стоящих над ним.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
