Введение в прикладную комбинаторику, Кофман А. (984071), страница 12
Текст из файла (страница 12)
(14.7) г! '] Мы употребляем временно слово «перестагговка», хотя речь фактически идет о подстановке. См. $16. В самом деле, Саге(рг, ПР; Д ... ДРг,)=(п — «)!, (14,8) т. е, равно числу перестановок из п — «элементов. Поэтому ~ Саге)(рг, П Р; Я ... Д Рг.)=С„'(и — «)!.
(14.9) Подставляя (14.7) в (14.6), получаем (Гг (0)=п! ~1 — — + — — — + ... +( — Ц" — ], (14 10) ! ! ! л И 2! 3! л! Но )Р'(О) и есть искомое число беспорядков 0„: О„=п! ~! — — + —,— —,, + ... +( — 1)" —,]. (14.11) 1 ! ! л Например, ! ! ! ! 1 ! 1 0 ="1 — — + — — — + — — — + —,16! = 1! 2! 3! 4! б! б! ] = 360 — 120+ 30 — 6+ 1 = 265. (14.12) При достаточно большом п существует хорошее приближение для (14.11). Из 1 ! ! а ! 0 =п)!! — — + — — — -)- ... ! ( 1)а 1 1! 2! 3! ~( 1) (л ! 1)! +( 1) ! ! 2)! + ° ° .
~] (14.13) следует, что 0„/п! и е-' отличаются ') не более чем на 1/(п+ 1)! Таким образом, 1пп —" =е ', (14. 14) п1 т. е, п! е-' азпроксимирует Р„тем лучше, чем больше п '). Понятие беспорядка обобщается, если рассмотреть перестановки с й совпадениями. Беспорядок — это перестановка с 0 совпадениями. Обозначим через 0 ,а число перестановок в точности с й совпадениями, через Р„,~а — число перестановок с не меньше чем А совпадениями, а через О, ~а в с не больше чем й совпадениями. В этих обозначениях 0 '= Р„,а. Положим также Ра = 1. Имеем Ра,а=С .Ря м =С 0 (14.
15) ') Известно, что остаток абсолютно сходящегося знакопеременного ряда имеет тот же знак, что и первый отброшенный член, и по абсолготнай вели. чине не превосходит модуля этого члена. з) Вероятность тога, что вытащенная наугад перестановка есть беспоряЭч док, равна р„= —. Для достаточно большого п, например для л = 10, л= ргю — е ', но и рш,з, е '.
Этот результат может показаться неогкиданным. 73 В силу (14.11) Р =(и — й)! )1 — — + — — — + ... +( — 1) ! ! ! л-» л-»,о— 1! 2! 3! (и — I!)! (14. 16) Умножая обе части (14.16) на С„", получаем Р = — "1 — — + — — — +...+( — 1) л!Г ! ! ! л-! ! »! ( 1! 2! 31 (и — »)! ~. (14.17) Легко видеть, что Рл,л=( и Рл,л ! —— О, и=1, 2, 3, „(14.18) ~~.", Рл, » — — ~ С»0„е о = и1.
(14.19) Ниже приводится таблица чисел Рл „для п(8. Положим для удобства Р,,о — — !. Числа Ри, и» и Рл,~» можно представить в виде л Р лм»= Х 0л„, (14.20) Рл, <» = ~Лл~ Рл, = П! — ~л~~ Рл . (14.21) с=о с=»е! Таблица !4.! Таблица количества перестановок л влементов с й совпадениями 1 0 21 1!2 ! 0 28 Дадим удобную рекуррентную формулу для чисел Рл = Рл о, Запишем (14.11), заменяя п на и — 1: Р =(и — 1)! [1 — — + — — — + ... +( — 1) 1 ! ! л-! л-! 1! 2! 3! (л — 1)! 1 (!4.22 ) Умножим обе части (14.22) на а: пРл ! = а! ~! — 11 + 21 31 + ' '. +( — 1) (и — !)11' (1423) ! 1 ! ! 76 )7!, » 71, » (7, » 71„» ))6» )7,, '» )О!, '» (зъ» 0 ! 2 9 44 265 1 854 !4 833 ! 0 3 8 45 264 ! 855 14 832 1 0 6 20 135 924 7 420 ! 0 10 40 315 2 464 ! 0 15 70 630 Прибавим к обеим частям равенства по ( — 1)": пР,+( — 1) =п)~1 — — + — — — +...+( — 1) — 1+ л-! 1 л-! 11 2! 3! (л — 1)! +( — !) =п) !! — — + — — — + ...
1! 2! 3! ... +( — 1)л ! +( — 1)л — )=Рл. (14.24) Таким образом '), Рл=пРл, +( — 1)", п=!, 2, 3, ..., (!4.25) так как Ро= 1 Получим теперь рекуррентную формулу для Рл ». В силу (14.15) Ри, » = СпРп-», ое (!4.26) (14.27) »+! Рл, ».!.! = Сп Ри-»-!, а Из (14,25) получаем Р„м о = (гт — А) Рл „, + ( — 1)л ". (14.28) Определяя 0„»,а из (14.26), а Рл» ьо из (14.27) и подставляя их в (14.28), находим Рл,»=()!+1)0„,»+!+(-1)" »С я=1, 2, 3, ..., й=О, 1, 2, ..., И вЂ” 1; Рл,и=1. (14.29) бп(г) = Х Рл.»г'=.)" СиРи»,,г'= »=е »=а =Рл+ СпРп-!г+СиРл-эг + ...
+Р,г". (14.30) Рассмотрим разложение (Р+ г)": (Р+ г) = Р + СиР г+ Сл0 г + ° ° ° + г . (14.31) Символически мо!кно записать с( (г)=(0+ г)"', (14.32) где (0+ г)!л' разлагается как (0+ г)", причем 0' заменяется на Р,. ') Рекуррентнан формула (14.23) подобна формуле л1 = л(л — 1)1, по этой причине последовательность а! наэыаают иногда «подфакториалом лэ, или «псевдофакториалом и».
Можно построить денумератор для чисел Рл,» следующим образом. Полагаем УПРА)!(НЕНИЯ 14А. Подсчитать число беспорядков О~« 14Б. С помощью таблицы 14.1 составить таблицу для чисел Ол ) ь, л = О, 1, 2, ..., В, Д = О, 1, 2, ..., 8. 14В. Тем же способом составить таблицу для чисел Рл <ь. 14Г. Доказать, что е'о+и', где О" — 'О„н ! — 'О,. 1 — з' 14Д.
Принимая во внимание (14.32) и упражнение 14Г, показать, что е л (О+з! 1 и 1«-11 л — е, 0 — 'Ол и ! — 'Ое. ! — и 14Е. Доказать, что Ол Ь«01, где ал01 (Е 1)л01 ~Ч~~ Сь( !)ь(л Д)! е з (используется символика (6,37)). ф 15. Перманент матрицы*) Обозначим через Ц а Ц матрицу с элементами аз 1, 1= =1,2,..., т;1=1,2,...,и; т(и. Перл1анентом регЦ а 1 матрицы Ц а Ц назовем сумму РегЦаЦ=~а~бас!, ... а !„, (15.1) 3) '] О матрицах см. Ф.
Р. Гаити а хе р, Теория матриц, «Наука», !967. 73 где суммирование производится по всем размещениям из и элементов 1, 2, ..., и по т. Предварительно рассмотрим перманенты нескольких матриц ЦаЦ: 1) ЦаЦ=(, (15.2) РегЦ а Ц = ~2~ а!г,аз! — — апазз + а~!азз + а>заз> + аиазз + + аман + а!заза, "(15.3) 2) (15.4) 3 — 2 6 регЦаЦ=лиманам =3'7+3 4+( — 2) О+ + ( — 2) 4+ 5 О+ 5 7 =60; (15.5) 3 — 2 0 ЦаЦ= 6 В (15.6) о и регЦаЦ=З 8( — 1)+3 11 4+5( — 2)( — !)+5 11 О+ + О ° ( — 2) ° 4+ О ° 8 ° О = 118; (15,7) аы а12 а12 а14 [! а Ц 1121 4222 4122 1124 аы азз азз а24 (15.8) 4) Рег Ц а Ц = ана„азз + а„а~аз4+ апагаа„+ апа„а„+ + а1гамам + апаыазз + а12аззаз4 + а12а24азз + а12а21азз + + а1241ма34+ а12азза31 + а12атза31 + а13а214134 + а131122а34 + + а1 34124а31 + а13 124азз + "13аз газз + '113а22а31 + '114 121а32 + + а,4а„аз, + а14аззазз+ а,4а„ам + а14аззаз1+ 12ыа231132.
(15 9) Основные свойства перманентов'). 1) Перманент магрицы инвариантен относительно любой перестановки строк и столбцов. 2) При умножении какой-либо строки (или столбца) на скаляр Х перманент умножается на Х. 3) Если [!а~[ — квадратная матрица, то а) регЦ а [[= регЦаЦ', (15.10) где ЦаЦ' — матрица, транспонированная к Ца[[; б) если ЦиОЦ получается из Ца12Ц вычеркиванием зчй строки и 1-го столбца, то регЦаЦ=Хаг)рег~[а12Ц 1=1, 2, ..., п, (15.11) 1-1 Эти свойства легко проверяются. Приведем пример применения (15.11). Например, для матрицы Ца~[ из (15.6) Следующая теорема облегчает вычисление перманента матрицы. Теорема.
Пуста ЦаЦ вЂ” матрица размера и эг,п, и(п, Ц аэ Ц вЂ” матрица, полученная из Ц а [, 'заменой й столбцов (й = О, 1, 2, ..., и — 1) столбцами из нулей'), Ь12 — сумма элементов 1-й строки (1'= 1, 2, ..., т) матрицы ЦаэЦ, сэ — — П Ьии а 1-1 ') За немногими исключениями свойства перманентов отличны от свойств определителей. ') Вообгце говоря, нз нулевых элементов поля, которому прннаплегквт элементы матрицы !а1), рег[[а ~[= ап рег[[ап Ц+ ам регЦ ам [[+ аз, рег~[ а„Ц= 41п (4122азз + 4132 23) + а21 (а12 33 + 1132а13) + аз1 ( 12 Зз + азза1з) =3[8( — 1)+ 11 4] — 5[( — 2)( — 1)+11 0[+ + 0[( — 2) 4+ 8 0[=118.
(15.12) суммирование в Х сг распространено на все сочетания без повторения из и по и — )г. Тогда 1 %3 г рет1! а !!= Х са-т Сп-т+1 ~! св-е+! + Сл щ+з ~ сф и+! ... +( — 1)" 'С„:!'~с„!. (15.13) Прежде чем перейти к доказательству, рассмотрим пример. Пример. Пусть 3 7 -2 8 !!а))= 2 4 6 0 (15.14) -3 5 1 -7 (15.15) Ьи 0 8 3 7 — 2 )!а !(= 2 4 6 — 3 5 1 О 12, 0 3 с, =288 с, = — 540 ь, 8 б 0 7 0 8 !!а,,!! =10 4 О О ~0 5 0 — 7 ! 0 0 — 2 у!а,!!,=( О О 6 0 0 1 0 6, — 7 — 6 с, = — 216 с, = — 120 Ьм 11 с, = 300 Ьн !О 7 — 2 8 13 /!а,!),= 0 4 6 0 !О, 0 5 1 -7 †! с = — 130 Ьм 3 0 — 2 8 9 !)а !!,= 2 0 6 0 8, ~ — 3 0 1 -7 — 9 с, = — 648 Ьн 3 7 0 8! 18 !!аь//з= 2 4 0 0 6 — 3 5 0 — 7 †~ с, = — 130 — 648 — 540 + 288 = — 1030.
ь, 0 7 — 2 0 5 3 0 0 8 11а !!,= 0 4 6 0 10, !/а !!,= 2 0 0 0 0 5 1 0 6 — 3 0 Π— 7 (!5.16) ь, 15 4, — 2 2, — 10 с, = — 220 (!5.17) ь„ 3 7 О О !О !!Озц1,= 2 4 о о в; — 3 5 О О 2 3 Π— 2 О! ! 1!О21!,= 2 о в о! 8, -3 О ! О! -2 с,= — 16 с,= 120 ~я~ сз = — 2! 6 — 120 + 800 — 220 — 16 + ! 20 = — 152.
(15. 18) с!з О 7 О О 7 !!Оз!!з= О 4 О О 4, О 5 О О 5 сз — — ! 40 (15:19) сз = — 18 О О 11 аз 1!, = о о О О с = — 12 3 ~~ сз = — 18 + ! 40 — 12 + 0 = 110. (15.20) рег!! а!1= ~ с! — Сз 2~ с! + Сз.'Е сз = = ( — 1080) — 2 ( — 152) + 8 (110) = — 896. (15.21) Д о к а з а т е л ь с т в о, Воспользуемся обобшенной формулой включения и исключения (12.24). Пусть $ — множество всех сочетаний без повторения из и элементов 1, 2, ..., а по лз: (!!1 12 ' ' > !пз) ~ 8' (15.22) Припишем элементам $ веса (15.28) а!6азг, ... а ! .
Пусть свойство,У! заключается в том, что (15.22) не содержит номера ! (!'= 1, 2, ..., и). Если !|а,!! — матрица, полученная из !!а!! заменой столбцов !!, !зь ..., з, нУлевыми, то ~Л(ж,,9", ..., ж)=ч",с, зз (г) = ~ч'.~ с,. (15.24) (! 5.25) 81 с!з 3ООО З ((о !),= 2 О О О 2, — 3 О О О -3 Ьзз ΠΠ— 2 О' -2 !! аз !!з = О О ! О ! с!з О 8 8 О О О О -7 — 7 с,=0 Отсюда следует, что рег11 а 11 равен сумме весов элементов из 3, удовлетворяющих в точности (и — и) свойствам У! (! = 1, 2, ..., и).
В силу (12.24) рег 11 а 11 = П (и — т) = и(и — и) — С"„:.",+!и (и — и + 1) + + С„": +!и (и — т + 2) — ... + ( — 1) ' С -! и (и — 1) + + ( — 1) С"„и (и). (15.26) Подставляя (!5.25) в (15.26) и замечая, что ~с„=О, имеем ! рег11а 11 '~~~с С е! ~2~с„, +!+ +С„- !.е!.оси-и+!+ ... +( — 1) 'С~~:! ~с„!. (15.27) Для квадратной матрицы формула (15.13) упрощается; рег 11 а 11 = со — Х с! + Х сз — ...
+ ( — 1) 2~ с„,. (15.28) Найдем перманенты некоторых булевых матриц. Обозначим через 11 111 единичную матрицу порядка и: о о ... о о ! о ... о 11111= о о ! ... о (15.30) о о о ... ! Очевидно, (15.31) рег!1 1 11=1. Рассмотрим перестановочную матрицу 11Р11, определяемую условиями р!! — — О или 1, (15.32) Случай булевых матриц. Рассмотрим матрицы, элементы которых — нули и единицы. Такие матрицы называют булевыми, например, о!оо 11а11= ! о о о (15.29) о Например, о!ооо оооо ооо!о оооо оо!оо !!Р!1= (15.33) Для любого и рег!1Р!1=1. Определим матрицу !! „А „АΠ— — 1, Например, !! условием 1,1=1, 2,..., и.
(15.34) ! 1 ! ! ! ! ! ! 1 ! ! ! ! ! ! ! ! ! ! 1 1 ! ! 1 1 1 !1,А !1= Очевидно, рег!1,А!1=1, рег!!эА!1=2 1, ..., рег!1„А!!=и!. (15.35) Так как для !1„А!! имеем со =и", ~ с1 =С„(п — 1)", (15.36) ~сэ=Св (п — 2)"1 ° 1 1сп 1=Сл 1 э то ввиду (15.28) рег!1,А'!!= и" — С',(и — 1)" + С'„(и — 2)" — ... и 1 ... +( — 1)" С", 1" = ~ ( — 1)'С„'(п — г)". (15.37) Сравнивая (15.37) и (15.35), получаем и-! ~~.", (-1)' С'„(и — г)" =и!. (15 38) элементами 1, 1=1, 2, ..., и, (15.39) (1,!'=1, 2, ..., и). Например, (15.4!) !! эв !1= Определим матрицу !1„В!! с „В„=„А„— „ЬО, где О, !Ф1, бО= 1, 1=1 ! ! ! !! о 1 ! ! о о ! ! ! Докажем теперь, что рег Ц „В ~!= !7„.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
