\input style \hyphenation{юб-рн-лн-ах-кеи} %% 4 \UDC{681.142.2} \vfill Рперхи рнл хгбеярмни лнмнцпютхх ндмнцн хг йпсомеиьху юлепхйюмяйху яоежхюкхярнб он опнцпюллхпнбюмхч Д. Ймсрю (оепбши рнл бшьек б хгдюрекэярбе \rlq{}Лхп\rrq{} б 1976 ц., брнпни---б 1977 ц.) янярнхр хг дбсу вюяреи: \rlq{}Янпрхпнбйю\rrq{} х \rlq{}Онхяй\rrq{}. Б мху ондпнамн хяякедсчряъ пюгкхвмше юкцнпхрлш бмсрпеммеи х бмеьмеи янпрхпнбйх, хгсвючряъ лерндш онхяйю хмтнплюжхх б рюакхжюу мю нямнбе япюбмемхе хкх опенапюгнбюмхъ йкчвеи, дючряъ нжемйх щттейрхбмнярх опедкюцюелшу юкцнпхрлнб. Ймхцю ямюафемю анкэьхл йнкхвеярбнл гюдюв х опхлепнб пюгмни яреоемх рпсдмнярх, ясыеярбеммн днонкмъчыху нямнбмни рейяр. Нр дпсцху псйнбндярб он опнцпюллхпнбюмхч ймхцю бшцндмн нркхвюеряъ ярпнцнярэч хгкнфемхъ х ьхпнйхл опхлемемхел люрелюрхвеяйнцн юооюпюрю. Блеяре я рел нмю днярсомю ярсдемрюл оепбнцн йспяю. Гмюйнлярбн я дбслъ оепбшлх рнлюлх фекюрекэмн, мн ме наъгюрекэмн. Йюфдши, йрн унвер мюсвхрэяъ йбюкхтхжхпнбюммн опнцпюллхпнбюрэ, мюидер б меи лмнцн онкегмнцн. Пюяявхрюмю мю ьхпнйхи йпсц опнцпюллхярнб. \vfill \vfill \centerline{{\it Педюйжхъ кхрепюрспш он люрелюрхвеяйхл мюсйюл}} \line{$Й{20204-022\over 041(01)-78}22-78$ \hfill \copyright\ Оепебнд мю псяяйхи ъгшй, \rlq{}Лхп\rrq{}. 1978} \eject %% 5 \chapter{ОПЕДХЯКНБХЕ ПЕДЮЙРНПНБ ОЕПЕБНДЮ} Д. Щ. Ймср унпньн гмюйнл янберяйнлс вхрюрекч он оепебндюл дбсу оепбшу рнлнб ецн наьхпмни лнмнцпютхх "Хяйсяярбн опнцпюллхпнбюмхъ дкъ ЩБЛ" х ме мсфдюеряъ б юрреярюжхх. Мюярнъыюъ ймхцю опедярюбкъер янани рперхи рнл х онябъыемю юкцнпхрлюл янпрхпнбйх х онхяйю хмтнплюжхх. Хярнпхвеяйх гюпнфдемхе лернднб люьхммни янпрхпнбйх лнфмн нрмеярх еые й опнькнлс ярнкерхч, х гю ярнкэ дкхрекэмне бпелъ лмнцхе яоежхюкхярш сяоекх хяопнанбюрэ ябнх яхкш б щрни накюярх. Мюохяюмн мелюкн нрвернб, ярюреи, лнмнцпютхи. Х дюфе б щрху сякнбхъу ймхцю Д. Ймсрю ярюкю янашрхел. Он ясыеярбс щрн щмжхйкноедхъ, б йнрнпни лнфмн мюирх кчасч яопюбйс, йюяючысчяъ юкцнпхрлнб, лернднб ху нжемнй, хярнпхх бнопняю х мепеьеммшу опнакел. Мер мсфдш цнбнпхрэ н бюфмнярх яюлни накюярх. Опюйрхвеяйх янпрхпнбйю х онхяй б рни хкх хмни лепе опхясрярбсчр бн бяеу опхкнфемхъу; б вюярмнярх, опх напюанрйе анкэьху на╝елнб дюммшу щттейрхбмнярэ хлеммн щрху ноепюжхи нопедекъер щттейрхбмнярэ, ю хмнцдю х пюанрняонянамнярэ бяеи яхярелш. Онщрнлс, йюй яопюбедкхбн нрлевюер юбрнп, ймхцю юдпеянбюмю ме рнкэйн яхярелмшл опнцпюллхярюл, гюмхлючыхляъ пюгпюанрйни опнцпюлл янпрхпнбйх х онхяйю хмтнплюжхх. Лнфмн яйюгюрэ, врн днярюрнвмн верйхе опедярюбкемхъ на щрни накюярх мсфмш опх пеьемхх кчани гюдювх мю ЩБЛ йюй наъгюрекэмше щкелемрш хяйсяярбю опнцпюллхпнбюмхъ. Йпнле ренперхвеяйни х опюйрхвеяйни жеммнярх, ймхцю хлеер анкэьне лерндхвеяйне гмювемхе. Лмнцхе юбрнпш х опеондюбюрекх ялнцср хгбкевэ хг мее мнбше х онкегмше ябедемхъ ме рнкэйн он ясыеярбс пюяялюрпхбюелшу бнопнянб, мн х он яонянас ху хгкнфемхъ. Юбрнпс люярепяйх сдюеряъ "пюяякнхрэ" беяэ люрепхюк рюйхл напюгнл, врн ймхцс лнфмн хяонкэгнбюрэ опюйрхвеяйх мю кчанл спнбме гмюйнлярбю я опедлернл х опх пюгкхвмни наыеи люрелюрхвеяйни ондцнрнбкеммнярх вхрюрекъ. Оепебнд бшонкмем он хгдюмхч 1973 ц. (оепбюъ педюйжхъ) я бмеяемхел лмнцху (нйнкн 700) хяопюбкемхи х днаюбкемхи, кчаегмн опеднярюбкеммшу юбрнпнл. Пюгдекш я 5.1 он 5.3.2 оепе- бедемш. М. Х. Бэчйнбни; пюгдекш я 5.3.3 он 5.5 х опедхякнбхе--- Ю. А. Ундскебшл; цкюбс а оепебек Б. Ю. Цюкюремйн. \rightline{Ч. Л. Аюъйнбяйхи} \rightline{ Б. Я. Ьрюпйлюм} %% 6 \chapter{ОПЕДХЯКНБХЕ} \epigraph Йскхмюпхъ ярюкю хяйсяярбнл, бшянйни мюсйни;\nl онбюпю реоепэ---акюцнпндмше кчдх. \signed Рхр Кхбхи, ЮЭ Urbe Condita, XXXIX.vi\nl (Пнаепр Аепрнм, Anatomy of Melancholy, 1.2.2.2)% \note{1}{ Пнаепр Аепрнм (1577--1640) --- юмцкхияйхи свемши, охяюрекэ х ренкнц. {\sl Опхл. Оепеб.\/}} Люрепхюк щрни ймхцх кнцхвеяйх опнднкфюер люрепхюк он хмтнплюжхнммшл ярпсйрспюл, хгкнфеммши б цк. 2, оняйнкэйс гдеяэ й сфе пюяялнрпеммшл йнмжеожхъл ярпсйрсп днаюбкъеряъ онмърхе кхмеимн сонпъднвеммшу дюммшу. Ондгюцнкнбнй "Янпрхпнбйю х онхяй" лнфер опхбеярх й лшякх, врн щрю ймхцю опедмюгмювемю кхьэ дкъ яхярелмшу опнцпюллхярнб, гюмхлючыхуяъ онярпнемхел смхбепяюкэмшу опнцпюлл янпрхпнбйх хкх ябъгюммшу я бшанпйни хмтнплюжхх. Ндмюйн б деиярбхрекэмнярх опедлер янпрхпнбйх х онхяйю дюер мюл опейпюямсч нямнбс дкъ наясфдемхъ ьхпнйнцн йкюяяю бюфмшу наыху бнопнянб: Йюй мюундхрэ унпньхе юкцнпхрлш? Йюй сксвьюрэ дюммше юкцнпхрлш х опнцпюллш? Йюй хяякеднбюрэ щттейрхбмнярэ юкцнпхрлнб люрелюрхвеяйх? Йюй пюгслмн бшапюрэ ндхм хг меяйнкэйху юкцнпхрлнб дкъ пеьемхъ йнмйпермни гюдювх? Б йюйнл ялшяке лнфмн днйюгюрэ, врн мейнрнпше юкцнпхрлш ъбкъчряъ "мюхксвьхлх хг бнглнфмшу"? Йюй ренпхъ бшвхякемхи янцкюясеряъ я опюйрхвеяйхлх яннапюфемхълх? Йюй щттейрхбмн хяонкэгнбюрэ пюгкхвмше бхдш бмеьмеи оюлърх---кемрш, аюпюаюмш, дхяйх---дкъ анкэьху аюг дюммшу? %% 7 Ъ дслюч, врн мю яюлнл деке б йнмрейяре янпрхпнбйх х онхяйю бярпевюеряъ опюйрхвеяйх \emph{кчани} бюфмши юяоейр опнцпюллхпнбюмхъ. Мюярнъыхи рнл янярнхр хг цк.~5 х~6 лнмнцпютхх. Б цк.~5 пюяялюрпхбюеряъ янпрхпнбйю (сонпъднвемхе); щрн нвемэ анкэьюъ релю, нмю пюгахрю мю дбе цкюбмше вюярх---бмсрпеммчч х бмеьмчч янпрхпнбйс. Б щрс цкюбс бундър рюйфе днонкмхрекэмше пюгдекш, пюгбхбючыхе бяонлнцюрекэмсч ренпхч оепеярюмнбнй (\S~5.1) х ренпхч норхлюкэмшу юкцнпхрлнб янпрхпнбйх (\S~5.3). Б цк.~6 лш хлеел декн я онхяйнл нопедекеммнцн щкелемрю б рюакхже хкх тюике; яндепфхлне щрни цкюбш ондпюгдекъеряъ мю лерндш онякеднбюрекэмнцн онхяйю, лерндш онхяйю ян япюбмемхел йкчвеи, онхяйю я хяонкэгнбюмхел ябниярб жхтп, онхяйю я онлныэч "уеьхпнбюмхъ"; гюрел пюяялюрпхбюеряъ анкее якнфмюъ гюдювю бшанпйх он брнпхвмшл йкчвюл. Нае цкюбш онпюгхрекэмн реямн оепеокерючряъ лефдс янани, лефдс ху опедлерюлх хлечряъ акхгйхе юмюкнцхх. Б днонкмемхе й цк. 2 пюяялюрпхбючряъ дбю бюфмшу бхдю хмтнплюжхнммшу ярпсйрсп, ю хлеммн опхнпхрермше нвепедх (о.~5.2.3) х кхмеимше яохяйх, опедярюбкъелше оняпедярбнл яаюкюмяхпнбюммшу депебэеб (о.~6.2.3). Вхрюрекч, ме гмюйнлнлс я оепбшл рнлнл щрни лнмнцпютхх, пейнлемдсеряъ напюыюрэяъ й сйюгюрекч нангмювемхи (опхкнфемхе Б), рюй йюй мейнрнпше хг бярпевючыхуяъ б ймхце нангмювемхи ме ъбкъчряъ наыеопхмършлх. Щрю ймхцю аег анкэьеи вюярх люрелюрхвеяйнцн люрепхюкю ашкю хяонкэгнбюмю лмни б йювеярбе свеамхйю он брнпнлс йспяс кейжхи "Ярпсйрспш дюммшу" дкъ ярсдемрнб лкюдьху х япедмху йспянб. Люрелюрхвеяйхе вюярх щрни ймхцх, нянаеммн \S~5.1, о.5.2.2, \S~6.3 х 6.4, лнцкх аш янярюбхрэ свеамхй он юмюкхгс юкцнпхрлнб дкъ ярсдемрнб япедмху х ярюпьху йспянб. Йпнле рнцн, мю нямнбе о.~4.3.3, 4.6.3, 4.6.4, \S~5.3 х о.~5.4.4 лнфмн онярпнхрэ йспя кейжхи "Якнфмнярэ бшвхякемхи" дкъ ярюпьейспямхйнб. Ашярпне пюгбхрхе хмтнплюрхйх х бшвхякхрекэмшу мюсй гюдепфюкн бшунд б ябер щрни ймхцх онвръ мю рпх цндю, оняйнкэйс нвемэ лмнцхе юяоейрш янпрхпнбйх х онхяйю ондбепцюкхяэ дерюкэмни пюгпюанрйе. Ъ нвемэ акюцндюпем Мюжхнмюкэмнлс мюсвмнлс тнмдс, Нрдекемхч бнеммн-лнпяйху хяякеднбюмхи, Хмярхрсрс нанпнмш, тхплюл IBM х Norges Almemitenskapelige Forskningsrad гю онярнъммсч онддепфйс лнху хяякеднбюмхи. %% 8 Б ондцнрнбйе щрнцн рнлю й оевюрх лме нйюгюкх онлныэ лмнцхе кхжю, нянаеммн Щдбюпд Ю. Аемдеп, Йкюпй Щ. Йпщим, Дщбхд Щ. Тепцчянм, Пнаепр С. Ткнид, Пнмюкэд К. Цпщуел, Кенмхдюя Цчхаю, Дфнм Унойпнтр, Пхвюпд Л. Йюпо, Цщпх Д. Ймнрр, Псднкэт Ю. Йпсрюп, Ьемэ Кхмэ, Бнцюм П. Опюрр, Яретюм Н. Пюие, Пхвюпд О; Ярщмкх, Ъ. Ю. бюм деп Оск х Дфнм С. Пемв лк., ю рюйфе ярсдемрш Ярщмтнпдю х Аепйкх, йнрнпшл опхькняэ хяйюрэ ньхайх б псйнохях. \line{Някн, Мнпбецхъ, \hfill {\sl Д. Щ. Ймср\/} яемръапэ 1972} \vskip 1 cm \epigraph Охяюрекэ онкэгсеряъ хгбеярмшлх опхбхкецхълх, б акюцндерекэмнярх йнрнпшу, мюдечяэ, мер мхйюйху нямнбюмхи янлмебюрэяъ. Рюй, бярперхб с лемъ меонмърмне леярн, вхрюрекэ днкфем опедонкнфхрэ, врн онд мхл йпнеряъ меврн беяэлю онкегмне х цксанйнлшякеммне% \note{1}{Оепебнд Ю. Ю. Тпюмйнбяйнцн.---{\sl Опхл. Оепеб.\/}}). \signed (Дфнмюрюм Ябхтр, Яйюгйю анвйх, опедхякнбхе, 1704) %% 9 \chapter{ГЮЛЕВЮМХЪ НА СОПЮФМЕМХЪУ} Сопюфмемхъ, онлеыеммше б ймхцюу мюярнъыеи яепхх, опедмюгмювемш йюй дкъ яюлнярнърекэмни опнпюанрйх, рюй х дкъ яелхмюпяйху гюмърхи. Рпсдмн, еякх ме мебнглнфмн хгсвхрэ опедлер, рнкэйн вхрюъ ренпхч х ме опхлемъъ онксвеммсч хмтнплюжхч дкъ пеьемхъ яоежхюкэмшу гюдюв х рел яюлшл ме гюярюбкъъ яеаъ надслшбюрэ рн, врн ашкн опнвхрюмн. Йпнле рнцн, лш ксвье бяецн гюсвхбюел рн, врн яюлх нрйпшбюел дкъ яеаъ. Онщрнлс сопюфмемхъ напюгсчр бюфмсч вюярэ дюммни пюанрш; ашкх опедопхмърш нопедекеммше оношрйх, врнаш нрнапюрэ сопюфмемхъ, б йнрнпшу аш яндепфюкняэ йюй лнфмн анкэье хмтнплюжхх х йнрнпше ашкн аш хмрепеямн пеьюрэ. Бн лмнцху ймхцюу кецйхе сопюфмемхъ дючряъ боепелеьйс я хяйкчвхрекэмн рпсдмшлх. Гювюярсч щрн нвемэ месднамн, рюй йюй оепед рел, йюй опхярсоюрэ й пеьемхч гюдювх, вхрюрекэ наъгюрекэмн днкфем опедярюбкърэ яеае, яйнкэйн бпелемх сидер с мецн мю щрн пеьемхе (хмюве нм лнфер пюгбе рнкэйн опнялнрперэ бяе гюдювх). Йкюяяхвеяйхл опхлепнл гдеяэ ъбкъеряъ ймхцю Пхвюпдю Аекклюмю "Дхмюлхвеяйне опнцпюллхпнбюмхе"; щрн бюфмюъ охнмепяйюъ пюанрю, б йнрнпни б йнмже йюфдни цкюбш онд псапхйни "Сопюфмемхъ х хяякеднбюрекэяйхе опнакелш" дюеряъ жекши пъд гюдюв, цде мюпъдс я цксанйхлх еые мепеьеммшлх опнакелюлх бярпевючряъ хяйкчвхрекэмн рпхбхюкэмше бнопняш. Цнбнпър, врн ндмюфдш йрн-рн яопняхк д-пю Аекклюмю, йюй нркхвхрэ сопюфмемхъ нр хяякеднбюрекэяйху опнакел, х рнр нрберхк: "Еякх бш лнфере пеьхрэ гюдювс, щрн---сопюфмемхе; б опнрхбмнл яксвюе щрн---опнакелю". Лнфмн опхбеярх лмнцн днбнднб б онкэгс рнцн, врн б ймхце рхою щрни днкфмш ашрэ йюй хяякеднбюрекэяйхе опнакелш, рюй х нвемэ опнярше сопюфмемхъ, х дкъ рнцн врнаш вхрюрекч ме опхундхкняэ кнлюрэ цнкнбс мюд рел, йюйюъ гюдювю кецйюъ, ю йюйюъ рпсдмюъ, лш ббекх "нжемйх", йнрнпше сйюгшбючр яреоемэ рпсдмнярх йюфднцн сопюфмемхъ. Щрх нжемйх хлечр якедсчыее гмювемхе: \halign{ # & \vtop{\hsize=15cm \noindent#\par} \cr \bf Нжемйю & На╝ъямемхе \cr 00 & Впегбшвюимн кецйне сопюфмемхе, мю йнрнпне лнфмн нрберхрэ япюгс фе, еякх онмър люрепхюк рейярю, х йнрнпне онврх бяецдю лнфмн пеьхрэ "б сле". \cr %% 10 10 & Опнярюъ гюдювю, йнрнпюъ гюярюбкъер гюдслюрэяъ мюд опнвхрюммшл люрепхюкнл, мн ме опедярюбкъер мхйюйху нянашу рпсдмняреи. Мю пеьемхе рюйни гюдювх рпеасеряъ ме анкэье ндмни лхмсрш; б опнжеяяе пеьемхъ лнцср онмюднахрэяъ йюпюмдюь х аслюцю. \cr 20 & Гюдювю япедмеи рпсдмнярх, онгбнкъчыюъ опнбепхрэ, мюяйнкэйн унпньн онмър рейяр. Мю рн врнаш дюрэ хявепошбючыхи нрбер, рпеасеряъ опхлепмн 15--20 лхмср.\cr 30 & Гюдювю слепеммни рпсдмнярх х/хкх якнфмнярх, дкъ сднбкербнпхрекэмнцн пеьемхъ йнрнпни рпеасеряъ анкэье дбсу вюянб. \cr 40 & Нвемэ рпсдмюъ хкх рпсднелйюъ гюдювю, йнрнпсч, бепнърмн, якедсер бйкчвхрэ б окюм опюйрхвеяйху гюмърхи. Опедонкюцюеряъ, врн ярсдемр лнфер пеьхрэ рюйсч гюдювс, мн дкъ щрнцн елс онрпеасеряъ гмювхрекэмши нрпегнй бпелемх; гюдювю пеьюеряъ мерпхбхюкэмшл напюгнл. \cr 50 & Хяякеднбюрекэяйюъ опнакелю, йнрнпюъ (мюяйнкэйн щрн ашкн хгбеярмн юбрнпс б лнлемр мюохяюмхъ) еые ме онксвхкю сднбкербнпхрекэмнцн пеьемхъ. Еякх вхрюрекэ мюидер пеьемхе щрни гюдювх, ецн мюярнърекэмн опняър носакхйнбюрэ ецн; йпнле рнцн, юбрнп дюммни ймхцх асдер нвемэ опхгмюрекем, еякх елс яннаыюр пеьемхе йюй лнфмн ашярпее (опх сякнбхх, врн нмн опюбхкэмн).\cr } Хмрепонкхпсъ он щрни "кнцюпхтлхвеяйни" ьйюке, лнфмн опхйхмсрэ, врн нгмювюер кчаюъ опнлефсрнвмюъ нжемйю. Мюопхлеп, нжемйю 17 цнбнпхр н рнл, врн дюммне сопюфмемхе всрэ кецве, вел сопюфмемхе япедмеи рпсдмнярх. Гюдювю я нжемйни 50, еякх нмю асдер пеьемю йюйхл-кхан вхрюрекел, б якедсчыху хгдюмхъу дюммни ймхцх лнфер хлерэ сфе нжемйс 45. Юбрнп веярмн ярюпюкяъ дюбюрэ на╝ейрхбмше нжемйх, мн рнлс, йрн янярюбкъер гюдювх, рпсдмн опедбхдерэ, мюяйнкэйн рпсдмшлх щрх гюдювх нйюфсряъ дкъ йнцн-рн дпсцнцн; й рнлс фе с йюфднцн векнбейю ясыеярбсер нопедекеммши рхо гюдюв, йнрнпше нм пеьюер ашярпее. Мюдечяэ, врн бшярюбкеммше лмни нжемйх дючр опюбхкэмне опедярюбкемхе н яреоемх рпсдмнярх гюдюв, мн б наыел ху мсфмн бняопхмхлюрэ йюй нпхемрхпнбнвмше, ю ме юаянкчрмше. Щрю ймхцю мюохяюмю дкъ вхрюрекеи яюлшу пюгмшу яреоемеи люрелюрхвеяйни ондцнрнбйх х хяйсьеммнярх, онщрнлс мейнрнпше сопюфмемхъ опедмюгмювемш рнкэйн дкъ вхрюрекеи я люрелюрхвеяйхл сйкнмнл. Еякх б йюйнл-кхан сопюфмемхх люрелюрхвеяйхе онмърхъ хкх пегскэрюрш хяонкэгсчряъ анкее ьхпнйн, вел щрн менаундхлн дкъ реу, йнцн б оепбсч нвепедэ хмрепеясер опнцпюллхпнбюмхе юкцнпхрлнб, рн оепед нжемйни рюйнцн сопюфмемхъ ярюбхряъ асйбю \rlq{}Л". Еякх дкъ пеьемхъ сопюфмемхъ рпеасеряъ гмюмхе бшяьеи люрелюрхйх б анкэьел на╝еле, вел щрн дюмн б мюярнъыеи %%11 ймхце, рн ярюбъряъ асйбш "БЛ". Онлерйю "БЛ" нрмчдэ ме ъбкъеряъ ябхдерекэярбнл рнцн, врн дюммне сопюфмемхе рпсдмне. Оепед мейнрнпшлх сопюфмемхълх ярнхр ярпекйю "\btr"; щрн нгмювюер, врн дюммне сопюфмемхе нянаеммн онсвхрекэмн х ецн пейнлемдсеряъ наъгюрекэмн бшонкмхрэ. Яюлн янани пюгслееряъ, мхйрн ме нфхдюер, врн вхрюрекэ (хкх ярсдемр) асдер пеьюрэ бяе гюдювх, онрнлс-рн мюханкее онкегмше хг мху х бшдекемш. Щрн янбяел ме гмювхр, врн дпсцхе гюдювх ме ярнхр пеьюрэ! Йюфдши вхрюрекэ днкфем он йпюимеи лепе оношрюрэяъ пеьхрэ бяе гюдювх я нжемйни 10 х мхфе; ярпекйх фе онлнцср бшапюрэ, йюйхе гюдювх я анкее бшянйхлх нжемйюлх якедсер пеьхрэ б оепбсч нвепедэ. Й анкэьхмярбс сопюфмемхи опхбедемш нрберш; нмх онлеыемш б яоежхюкэмнл пюгдеке б йнмже ймхцх. Онкэгсиреяэ хлх лсдпн; б нрбер ялнрпхре рнкэйн оняке рнцн, йюй бш опхкнфхкх днярюрнвмн сяхкхи, врнаш пеьхрэ гюдювс яюлнярнърекэмн, хкх фе еякх дкъ пеьемхъ дюммни гюдювх с бюя мер бпелемх. Еякх онксвем янаярбеммши нрбер, кхан еякх бш деиярбхрекэмн ошрюкхяэ пеьхрэ гюдювс, рнкэйн б щрнл яксвюе нрбер, онлеыеммши б ймхце, асдер онсвхрекэмшл х онкегмшл. Йюй опюбхкн, нрберш й гюдювюл хгкюцючряъ нвемэ йпюрйн, яуелюрхвмн, рюй йюй опедонкюцюеряъ, врн вхрюрекэ сфе веярмн ошрюкяъ пеьхрэ гюдювс янаярбеммшлх яхкюлх. Хмнцдю б опхбедеммнл пеьемхх дюеряъ лемэье хмтнплюжхх, вел яопюьхбюкняэ, вюые---мюнанпнр. Бонкме бнглнфмн, врн онксвеммши бюлх нрбер нйюферяъ ксвье нрберю, онлеыеммнцн б ймхце, хкх бш мюидере ньхайс б щрнл нрбере; б рюйнл яксвюе юбрнп ашк аш нвемэ наъгюм, еякх аш бш йюй лнфмн яйнпее ондпнамн яннаыхкх елс на щрнл. Б онякедсчыху хгдюмхъу мюярнъыеи ймхцх асдер онлеыемн сфе хяопюбкеммне пеьемхе блеяре я хлемел ецн юбрнпю. \halign{ # & # \hfill\cr \span \bf \hfill Ябндйю сякнбмшу нангмювемхи \cr \btr & Пейнлемдсеряъ \cr Л & Я люрелюрхвеяйхл сйкнмнл \cr БЛ & Рпеасер гмюмхъ "бшяьеи люрелюрхйх"\cr 00& Рпеасер меледкеммнцн нрберю \cr 10 & Опнярне (мю ндмс лхмсрс) \cr 20 & Япедмеи рпсдмнярх (мю вербепрэ вюяю) \cr 30 & Онбшьеммни рпсдмнярх. \cr 40 & Дкъ "люропюйрхйслю" \cr 50 & Хяякеднбюрекэяйюъ опнакелю\cr } \excercises \rex[00] Врн нгмювюер онлерйю "Л20"? \ex[10] Йюйне гмювемхе дкъ вхрюрекъ хлечр сопюфмемхъ, онлеыюелше б свеамхйюу? \ex[Л50] Днйюфхре, врн еякх $n$---жекне вхякн, $n > 2$, рн спюбмемхе $x^n+y^n=z^n$ мепюгпеьхлн б жекшу онкнфхрекэмшу вхякюу $у$, $с$,$z$. %% 13 \chapnotrue \chapno=4 \chapter{Янпрхпнбйю} \epigraph Мер декю анкее рпсдмнцн он гюлшякс, анкее янлмхрекэмнцн он сяоеус, анкее ноюямнцн опх нясыеярбкемхх, вел ббндхрэ мнбше онпъдйх. \signed Мхййнкн Люйэъбеккх, "Цнясдюпэ" (1513) \epigraph "Мн лш ме сяоеел, опнялнрперэ бяе мнлепю юбрнлнахкеи",---бнгпюгхк Дпеий. "Ю мюл х ме мсфмн щрнцн декюрэ. Онк. Лш опнярн пюяонкнфхл ху он онпъдйс х онхыел ндхмюйнбше". \signed Оеппх Леиянм% \note{1}{ Оеппх Леиянм---цепни яепхх дерейрхбмшу пнлюмнб оноскъпмнцн юлепхйюмяйнцн охяюрекъ Щпкю Яремкх Цюпдмепю.--- {\sl Опхл. оепеб.\/}}. Хг "The Case of Angry Mourner" (1951) \epigraph Янпрхпнбйю депебэеб я хяонкэгнбюмхел ЩБЛ.\nl Опх рюйнл мнбнл, "люьхммнл ондунде" й хгсвемхч опхпндш бш онксвхре бнглнфмнярэ ашярпн пюяонгмюбюрэ анкее 260 пюгкхвмшу депебэеб ЯЬЮ, Юкъяйх, Йюмюдш, бйкчвюъ оюкэлш, депебэъ осяршмэ х опнвсч щйгнрхйс. Врнаш нопедекхрэ онпндс депебю, днярюрнвмн опнярн бярюбхрэ яохжс. \signed Йюрюкнц "Edmund Scientific Company" (1964) Б щрни цкюбе лш хгсвхл бнопня, йнрнпши вюярн бнгмхйюер б опнцпюллхпнбюмхх: оепепюглеыемхе щкелемрнб б бнгпюярючыел хкх сашбючыел онпъдйе. Опедярюбэре, мюяйнкэйн рпсдмн ашкн аш онкэгнбюрэяъ якнбюпел, еякх аш якнбю б мел ме пюяонкюцюкхяэ б юктюбхрмнл онпъдйе. Рнвмн рюй фе нр онпъдйю, б йнрнпнл упюмъряъ щкелемрш б оюлърх ЩБЛ, бн лмнцнл гюбхяхр яйнпнярэ х опнярнрю юкцнпхрлнб, опедмюгмювеммшу дкъ ху напюанрйх. Унръ б якнбюпъу якнбн "янпрхпнбйю" (sorting) нопедекъеряъ йюй "пюяопедекемхе, нранп он янпрюл; декемхе мю йюрецнпхх, янпрю, пюгпъдш", опнцпюллхярш рпюдхжхнммн хяонкэгсчр щрн якнбн б цнпюгдн анкее сгйнл ялшяке, нангмювюъ хл янпрхпнбйс опедлернб б бнгпюярючыел хкх сашбючыел онпъдйе. Щрнр опнжеяя, онфюкси, якеднбюкн аш мюгбюрэ ме янпрхпнбйни, ю \emph{сонпъднвемхел} (ordering), мн хяонкэгнбюмхе щрнцн якнбю опхбекн аш й осрюмхже хг-гю оепецпсфеммнярх гмювемхълх якнбю "онпъднй". Пюяялнрпхл, мюопхлеп, якедсчыее опедкнфемхе: "Рюй йюй рнкэйн дбю мюьху кемрнопнръфмшу сярпниярбю б онпъдйе, лемъ опхгбюкх й онпъдйс х наъгюкх б япнвмнл онпъдйе гюйюгюрэ еые меяйнкэйн сярпниярб, врнаш лнфмн ашкн сонпъднвхбюрэ дюммше пюгмнцн онпъдйю мю меяйнкэйн онпъдйнб ашярпее% \note{2}{Б нпхцхмюке "Since only two of our tape drives were in working order I was ordered to order more tape units in short order, in order to order the data several orders of magnitude faster".--- {\sl Опхл. оепеб.\/}}. Б люрелюрхвеяйни реплхмнкнцхх %% 14 щрн якнбн рюйфе хгнахксер гмювемхълх (онпъднй цпсоош, онпъднй оепеярюмнбйх, онпъднй рнвйх бербкемхъ, нрмньемхе онпъдйю х р. о.). Хрюй, якнбн "онпъднй" опхбндхр й уюняс. Б йювеярбе нангмювемхъ дкъ опнжеяяю сонпъднвемхъ опедкюцюкняэ рюйфе якнбн "пюмфхпнбюмхе"% \note{1}{Б нпхцхмюке "sequencing".---{\sl Опхл. оепеб.\/}}, мн нмн бн лмнцху яксвюъу, он-бхдхлнлс, ме бонкме нрпюфюер ясрэ декю, нянаеммн еякх опхясрярбсчр пюбмше щкелемрш, х, йпнле рнцн, хмнцдю ме янцкюясеряъ я дпсцхлх реплхмюлх. Йнмевмн, якнбн "янпрхпнбйю" х яюлн хлеер днбнкэмн лмнцн гмювемхи% \note{2}{Щрн б анкэьеи яреоемх нрмняхряъ й юмцкхияйнлс якнбс "sorting". Гдеяэ юбрнп опхбндър опхлеп: "Ме was sort of out sorts after sorting that sort of data". (Нм ашк йюй асдрн ме б дсуе оняке янпрхпнбйх рюйнцн янпрю деммшу), йнрнпши б псяяйнл оепебнде ме ярнкэ бшпюгхрекем.--- {\sl Опхл. оепеб.\/}}, мн нмн опнвмн бнькн б опнцпюллхяряйхи фюпцнм. Онщрнлс лш аег дюкэмеиьху хгбхмемхи асдел хяонкэгнбюрэ якнбн "янпрхпнбйю" б сгйнл ялшяке "янпрхпнбйю он онпъдйс". \medskip Бнр мейнрнпше хг мюханкее бюфмшу опхлемемхи янпрхпнбйх: \item{a)} Пеьемхе гюдювх "цпсоохпнбйх", йнцдю мсфмн янапюрэ блеяре бяе щкелемрш я ндхмюйнбшл гмювемхел мейнрнпнцн опхгмюйю. Дносярхл, хлееряъ 10000 щкелемрнб, пюяонкнфеммшу б яксвюимнл онпъдйе, опхвел гмювемхъ лмнцху хг мху пюбмш; х опедонкнфхл, мюл мсфмн оепесонпъднвхрэ тюик рюй, врнаш щкелемрш я пюбмшлх гмювемхълх гюмхлюкх яняедмхе онгхжхх б тюике. Щрн, он ясыеярбс, гюдювю "янпрхпнбйх" б ьхпнйнл ялшяке якнбю, х нмю кецйн лнфер ашрэ пеьемю осрел янпрхпнбйх тюикю б сгйнл ялшяке якнбю, ю хлеммн пюяонкнфемхел щкелемрнб б месашбючыел онпъдйе $v_1\le v_2 \le \ldots \le v_{10000}$. Щттейрхбмнярэч, йнрнпюъ лнфер ашрэ днярхцмсрю б щрни опнжедспе, х на╝ъямъеряъ хглемемхе оепбнмювюкэмнцн ялшякю якнбю "янпрхпнбйю". \item{b)} Еякх дбю хкх анкее тюикю нрянпрхпнбюрэ б ндмнл х рнл фе онпъдйе, рн лнфмн нршяйюрэ б мху бяе наыхе щкелемрш гю ндхм онякеднбюрекэмши опнялнрп бяеу тюикнб, аег бнгбпюрнб. Щрн рнр яюлши опхмжхо, йнрнпшл бняонкэгнбюкяъ Оеппх Леиянм дкъ пюяйпшрхъ декю на сахиярбе (ял. щохцпютш й щрни цкюбе). Нйюгшбюеряъ, врн, йюй опюбхкн, цнпюгдн щйнмнлмее опнялюрпхбюрэ яохянй онякеднбюрекэмн, ю ме оепеяйюйхбюъ я леярю мю леярн яксвюимшл напюгнл, еякх рнкэйн яохянй ме мюярнкэйн люк, врн нм жекхйнл онлеыюеряъ б ноепюрхбмни оюлърх. Янпрхпнбйю онгбнкъер хяонкэгнбюрэ онякеднбюрекэмши днярсо й анкэьхл тюикюл б йювеярбе опхелкелни гюлемш опълни юдпеяюжхх. \item{c)} Йюй лш сбхдхл б цк. 6, янпрхпнбйю онлнцюер х опх онхяйе, я ее онлныэч лнфмн ядекюрэ бшдювх ЩБЛ анкее сднамшлх дкъ векнбевеяйнцн бняопхърхъ. Б яюлнл деке, кхярхмц (мюоевюрюммши %% 15 люьхмни днйслемр), нрянпрхпнбюммши б юктюбхрмнл онпъдйе, гювюярсч бшцкъдхр беяэлю бмсьхрекэмн, дюфе еякх яннрберярбсчыхе вхякнбше дюммше ашкх пюяявхрюмш мебепмн. Унръ янпрхпнбйю рпюдхжхнммн х анкэьеи вюярэч хяонкэгнбюкюяэ дкъ напюанрйх йнллепвеяйху дюммшу, мю яюлнл деке нмю ъбкъеряъ хмярпслемрнл, онкегмшл б яюлшу пюгмшу яхрсюжхъу, х онщрнлс н мел ме якедсер гюашбюрэ; Б соп. 2.3.2--17 лш наясдхкх ее опхлемемхе дкъ сопныемхъ юкцеапюхвеяйху тнплск. Сопюфмемхъ, опхбедеммше мхфе, хккчярпхпсчр пюгмннапюгхе рхохвмшу опхлемемхи янпрхпнбйх. Ндмни хг оепбшу йпсомшу яхярел опнцпюллмнцн наеяоевемхъ, опнделнмярпхпнбюбьху анцюрше бнглнфмнярх янпрхпнбйх, ашк йнлохкърнп Larc Scientific Compiler, пюгпюанрюммши тхплни Computer Sciences Corporation б 1960~ц. Б щрнл норхлхгхпсчыел йнлохкърнпе дкъ пюяьхпеммнцн ТНПРПЮМю янпрхпнбйю хяонкэгнбюкюяэ беяэлю хмремяхбмн, рюй врн пюгкхвмше юкцнпхрлш йнлохкъжхх пюанрюкх я нрмняъыхлхяъ й мхл вюярълх хяундмни опнцпюллш, пюяонкнфеммшлх б сднамни онякеднбюрекэмнярх. Опх оепбнл опнялнрпе нясыеярбкъкяъ кейяхвеяйхи юмюкхг, р. е. бшдекемхе б хяундмни опнцпюлле кейяхвеяйху едхмхж (кейяел), йюфдюъ хг йнрнпшу яннрберярбсер кхан хдемрхтхйюрнпс (хлемх оепелеммни), кхан йнмярюмре, кхан ноепюрнпс х р. д. Йюфдюъ кейяелю онксвюкю меяйнкэйн онпъдйнбшу мнлепнб. Б пегскэрюре янпрхпнбйх он хлемюл х яннрберярбсчыхл онпъдйнбшл мнлепюл бяе хяонкэгнбюмхъ дюммнцн хдемрхтхйюрнпю нйюгшбюкхяэ янапюммшлх блеяре. "Нопедекъчыхе бунфдемхъ", яоежхтхжхпсчыхе хдемрхтхйюрнп йюй хлъ тсмйжхх, оюпюлерп хкх лмнцнлепмсч оепелеммсч, онксвюкх лемэьхе мнлепю, онщрнлс нмх нйюгшбюкхяэ оепбшлх б онякеднбюрекэмнярх кейяел, нрбевючыху щрнлс хдемрхтхйюрнпс. Рел яюлшл накецвюкюяэ опнбепйю опюбхкэмнярх сонрпеакемхъ хдемрхтхйюрнпнб, пюяопедекемхе оюлърх я свернл дейкюпюжхи щйбхбюкемрмнярх х р. д. Янапюммюъ рюйхл напюгнл хмтнплюжхъ н йюфднл хдемрхтхйюрнпе опхянедхмъкюяэ й яннрберярбсчыеи кейяеле. Онщрнлс ме ашкн менаундхлнярх упюмхрэ б ноепюрхбмни оюлърх "рюакхжс яхлбнкнб", яндепфюысч ябедемхъ на хдемрхтхйюрнпюу. Оняке рюйни напюанрйх кейяелш ямнбю янпрхпнбюкхяэ он дпсцнлс онпъдйнбнлс мнлепс; б пегскэрюре б опнцпюлле, он ясыеярбс, бняярюмюбкхбюкяъ оепбнмювюкэмши онпъднй, еякх ме явхрюрэ рнцн, врн юпхтлерхвеяйхе бшпюфемхъ нйюгшбюкхяэ гюохяюммшлх б анкее сднамни, "онкэяйни опетхйямни" тнпле. Янпрхпнбйю хяонкэгнбюкюяэ х мю онякедсчыху тюгюу йнлохкъжхх---дкъ накецвемхъ норхлхгюжхх жхйкнб, бйкчвемхъ б кхярхмц яннаыемхи на ньхайюу х р. д. Йнпнве цнбнпъ, йнлохкърнп ашк сярпнем рюй, врн бяч напюанрйс тюикнб, упюмъыхуяъ мю аюпюаюмюу, тюйрхвеяйх лнфмн ашкн беярх онякеднбюрекэмн. Онщрнлс-рн дюммше х ямюафюкхяэ рюйхлх онпъдйнбшлх мнлепюлх, %% 16 йнрнпше онгбнкъкх сонпъднвхбюрэ щрх дюммше пюгкхвмшлх сднамшлх яонянаюлх. Дпсцне, анкее нвебхдмне опхлемемхе янпрхпнбйх бнгмхйюер опх педюйрхпнбюмхх тюикнб, цде йюфдюъ ярпнйю ямюафемю йкчвнл. Онйю онкэгнбюрекэ бмняхр я йкюбхюрспш хглемемхъ х днаюбкемхъ, менаъгюрекэмн депфюрэ беяэ тюик б ноепюрхбмни оюлърх. Бяе хглемъелше ярпнйх лнфмн онгдмее нрянпрхпнбюрэ (ю нмх х рюй нашвмн б нямнбмнл сонпъднвемш) х якхрэ я хяундмшл тюикнл. Щрн дюер бнглнфмнярэ пюгслмн хяонкэгнбюрэ оюлърэ б пефхле лскэрхопнцпюллхпнбюмхъ. [Яп. я Я. Я. Foster, {\sl Comp. J.\/}, {\bf 11} (1968), 134--137]. Онярюбыхйх бшвхякхрекэмшу люьхм явхрючр, врн б япедмел анкее 25\% люьхммнцн бпелемх яхярелюрхвеяйх рпюрхряъ мю янпрхпнбйс. Бн лмнцху бшвхякхрекэмшу яхярелюу мю мее сундхр анкэье онкнбхмш люьхммнцн бпелемх. Хг щрни ярюрхярхйх лнфмн гюйкчвхрэ, врн кхан (i) янпрхпнбйю хлеер лмнцн бюфмшу опхлемемхи, кхан (ii) еч вюярн онкэгсчряъ аег мсфдш, кхан (iii) опхлемъчряъ б нямнбмнл мещттейрхбмше юкцнпхрлш янпрхпнбйх. Он-бхдхлнлс, йюфдне хг рпеу опедонкнфемхи яндепфхр днкч хярхмш. Бн бяъйнл яксвюе ъямн, врн янпрхпнбйю гюяксфхбюер яепэегмнцн хгсвемхъ я рнвйх гпемхъ ее опюйрхвеяйнцн хяонкэгнбюмхъ. Мн дюфе еякх аш янпрхпнбйю ашкю онврх аеяонкегмю, мюькюяэ аш люяяю дпсцху опхвхм гюмърэяъ еч! Хгнаперюрекэмше юкцнпхрлш янпрхпнбйх цнбнпър н рнл, врн нмю х яюлю он яеае хмрепеямю йюй на╝ейр хяякеднбюмхъ. Б щрни накюярх ясыеярбсер лмнфеярбн сбкейюрекэмшу мепеьеммшу гюдюв мюпъдс я беяэлю мелмнцхлх сфе пеьеммшлх. Пюяялюрпхбюъ бнопня б анкее ьхпнйнл окюме, лш намюпсфхл, врн юкцнпхрлш янпрхпнбйх опедярюбкъчр янани хмрепеямши вюярмши опхлеп рнцн, йюй якедсер ондундхрэ й пеьемхч опнакел опнцпюллхпнбюмхъ бннаые. Лш онгмюйнлхляъ ян лмнцхлх бюфмшлх опхмжхоюлх люмхоскхпнбюмхъ ян ярпсйрспюлх дюммшу х опнякедхл гю щбнкчжхеи пюгкхвмшу лернднб янпрхпнбйх, опхвел вхрюрекч вюярн асдер опеднярюбкърэяъ бнглнфмнярэ яюлнлс "нрйпшбюрэ" ре фе хдех, йюй асдрн аш дн мецн мхйрн я онднамшлх гюдювюлх ме ярюкйхбюкяъ. Нанаыемхе щрху вюярмшу лернднб онгбнкхр мюл б гмювхрекэмни яреоемх нбкюдерэ релх яонянаюлх лшькемхъ, йнрнпше онлнцср янгдюбюрэ днапнрмше юкцнпхрлш дкъ пеьемхъ дпсцху опнакел, ябъгюммшу я ЩБЛ. Лерндш янпрхпнбйх яксфюр бекхйнкеомни хккчярпюжхеи хдеи \emph{ юмюкхгю юкцнпхрлнб}, р. е. хдеи, онгбнкъчыху нжемхбюрэ пюанвхе уюпюйрепхярхйх юкцнпхрлнб, ю гмювхр, пюгслмн бшахпюрэ япедх. йюгюкняэ аш, пюбмнжеммшу лернднб. Вхрюрекх, хлечыхе яйкнммнярэ й люрелюрхйе, мюидср б щрни цкюбе мелюкн яонянанб нжемйх яйнпнярх пюанрш юкцнпхрлнб х лернднб пеьемхъ якнфмшу пейсппемрмшу %% 17 яннрмньемхи. Я дпсцни ярнпнмш, хгкнфемхе онярпнемн рюй, врн вхрюрекх, ме хлечыхе рюйни яйкнммнярх, лнцср аеганкегмеммн опносяйюрэ бшйкюдйх. Опефде вел дбхцюрэяъ дюкэье, менаундхлн анкее верйн нопедекхрэ гюдювс х ббеярх яннрберярбсчысч реплхмнкнцхч. Осярэ мюдн сонпъднвхрэ $N$ щкелемрнб $$ R_1, R_2, \ldots, R_N. $$ Мюгнбел ху \dfn{гюохяълх}, ю бяч янбнйсомнярэ N гюохяеи мюгнбел \dfn{тюикнл}. Йюфдюъ гюохяэ $R_j$ хлеер \dfn{йкчв} $K_j$, йнрнпши х сопюбкъер опнжеяянл янпрхпнбйх. Онлхлн йкчвю, гюохяэ лнфер яндепфюрэ днонкмхрекэмсч, "яносрярбсчысч хмтнплюжхч", йнрнпюъ ме бкхъер мю янпрхпнбйс, мн бяецдю нярюеряъ б щрни гюохях. Нрмньемхе онпъдйю "$<$" мю лмнфеярбе йкчвеи ббндхряъ рюйхл напюгнл, врнаш дкъ кчашу рпеу гмювемхи йкчвеи $a$, $b$, $c$ бшонкмъкхяэ якедсчыхе сякнбхъ: \item{i)} яопюбедкхбн ндмн х рнкэйн ндмн хг яннрмньемхи $a (b_n, ..., b_1)$; \cr & $|ЯI|=0$, еякх $(a_n, \dots, a_1) = (b_n, ..., b_1)$;\cr & $|CI|=-1$, еякх $(a_n, \dots, a_1)< (b_n, ..., b_1)$; \cr & |rX| х |rI1|, бнглнфмн, хглемхкхяэ.\cr } Гдеяэ нрмньемхе $(a_n, \dots, a_1) < (b_n, ..., b_1)$ нангмювюер кейяхйнцпютхвеяйне сонпъднвемхе якебю мюопюбн, р. е. ясыеярбсер хмдейя $j$, рюйни, врн $a_k=b_k$ опх $о\ge{} k > j$, мн $ю_j < b_j$. \ex[30] Б ъвеийюу |A| х |Б| яндепфюряъ яннрберярбеммн вхякю $ю$ х~$b$. Онйюфхре, врн лнфмн мюохяюрэ \MIX-опнцпюллс, йнрнпюъ аш бшвхякъкю $\min (a, b)$ х гюохяшбюкю пегскэрюр б ъвеийс |Я|, \emph{ме онкэгсъяэ йнлюмдюлх оепеундю.} (\emph{Опеднярепефемхе:} оняйнкэйс юпхтлерхвеяйне оепеонкмемхе мебнглнфмн намюпсфхрэ аег йнлюмд оепеундю, пюгслмн рюй онярпнхрэ опнцпюллс, врнаш оепеонкмемхе ме лнцкн бнгмхймсрэ мх опх йюйху гмювемхъу $ю$ х~$b$) \ex[Л27] Йюйнбю бепнърмнярэ рнцн, врн оняке янпрхпнбйх б месашбючыел онпъдйе |N| мегюбхяхлшу пюбмнлепмн пюяопедекеммшу мю нрпегйе $[0, 1]$ яксвюимшу бекхвхм $r$-е нр мювюкю вхякн нйюферяъ $\le{} x$? \excercises СОПЮФМЕМХЪ (БРНПЮЪ ВЮЯРЭ) Б йюфднл хг щрху сопюфмемхи онярюбкемю гюдювю, я йнрнпни лнфер ярнкймсрэяъ опнцпюллхяр. Опедкнфхре "унпньее" пеьемхе гюдювх, опедонкюцюъ, врн хлееряъ япюбмхрекэмн меанкэьюъ ноепюрхбмюъ оюлърэ х нйнкн онксдчфхмш, кемрнопнръфмшу сярпниярб (щрнцн йнкхвеярбю днярюрнвмн дкъ янпрхпнбйх). \ex[75] Хлееряъ кемрю, мю йнрнпни гюохяюм лхккхнм якнб дюммшу. Йюй нопедекхрэ, яйнкэйн мю щрни кемре пюгкхвмшу якнб? \ex[18] Бннапюгхре яеаъ б пнкх Сопюбкемхъ бмсрпеммху днунднб Лхмхярепярбю тхмюмянб ЯЬЮ. Бш онксвюере лхккхнмш "хмтнплюжхнммшу" йюпрнвей нр нпцюмхгюжхи н рнл, яйнкэйн, демец нмх бшокюрхкх пюгкхвмшл кхжюл, х лхккхнмш "мюкнцнбшу" йюпрнвей нр пюгкхвмшу кхж на ху днундюу. Йюй аш бш ярюкх нршяйхбюрэ кчдеи, йнрнпше яннаыхкх ме нан бяеу ябнху днундюу? %% 20 \ex[Л25]{\sl (Рпюмяонмхпнбюмхе люрпхжш.)\/} Хлееряъ люцмхрмюъ кемрю, яндепфюыюъ лхккхнм якнб, йнрнпше опедярюбкъчр янани щкелемрш $1000\times1000$-люрпхжш, гюохяюммше он ярпнйюл: $a_{1,1}$ $a_{1,2}$ \dots $a_{1,1000}$ $a_{2,1}$ \dots $a_{2,1000}$ \dots $a_{1000, 1000}$. Бюью гюдювю---онксвхрэ кемрс, мю йнрнпни щкелемрш щрни люрпхжш ашкх аш гюохяюмш он ярнкажюл: $a_{1,1}$ $a_{2,1}$ \dots $a_{1000,1}$ $a_{1,2}$\dots $a_{1,2}$\dots $a_{1000,2}$ \dots $a_{1000, 1000}$ (Онярюпюиреяэ ядекюрэ ме анкее деяърх опнялнрпнб дюммшу.) \ex[Л26] Б бюьел пюяонпъфемхх днбнкэмн анкэьни тюик хг $N$ якнб. Йюй аш бш ецн "оеперюянбюкх" яксвюимшл напюгнл? \rex[24] Б мейнл смхбепяхрере пюанрюер нйнкн 1000 опеондюбюрекеи х хлееряъ 500 йнлхрернб. Явхрюеряъ, врн йюфдши опеондюбюрекэ ъбкъеряъ вкемнл он йпюимеи лепе дбсу йнлхрернб. Бюл мсфмн ондцнрнбхрэ я онлныэч люьхмш сднанвхрюелше яохяйх вкемнб бяеу йнлхрернб. Бш пюяонкюцюере йнкндни хг опхакхгхрекэмн 1500 оептнйюпр, якнфеммшу опнхгбнкэмшл напюгнл х яндепфюыху якедсчысч хмтнплюжхч: {\it Вкемяйхе йюпрнвйх:\/} йнкнмйю 1---опнаек; йнкнмйх 2--18---тюлхкхъ я онякедсчыхлх опнаекюлх; йнкнмйх 19--20---хмхжхюкш; йнкнмйх 21--23---мнлеп оепбнцн Йнлхрерю; йнкнмйх 24--26---мнлеп брнпнцн йнлхрерю; \dots; йнкнмйх 78--80--- мнлеп дбюджюрнцн йнлхрерю (еякх мсфмн) хкх опнаекш. {\it Йнлхреряйхе йюпрнвйх:\/} йнкнмйю 1---"*"; йнкнмйх 2--77---мюгбюмхе йнлхрерю; йнкнмйх 78--80---мнлеп йнлхрерю. Йюй бш днкфмш деиярбнбюрэ? (Нохьхре ябни лернд днярюрнвмн ондпнамн.) \ex[20] Бш пюанрюере я дбслъ бшвхякхрекэмшлх яхярелюлх, б йнрнпшу он-пюгмнлс сонпъднвемш кхрепш (асйбш х жхтпш). Йюй гюярюбхрэ оепбсч ЩБЛ янпрхпнбюрэ тюикш я асйбеммн-жхтпнбни хмтнплюжхеи, опедмюгмювеммше дкъ хяонкэгнбюмхъ мю брнпни ЩБЛ? \ex[18] Хлееряъ днбнкэмн анкэьни яохянй кчдеи, пндхбьхуяъ б ЯЬЮ, я сйюгюмхел ьрюрю, б йнрнпнл нмх пндхкхяэ. Йюй ондявхрюрэ вхякн кчдеи, пндхбьхуяъ б йюфднл ьрюре? (Опедонкюцюеряъ, врн мх ндхм векнбей ме сйюгюм б яохяйе анкее ндмнцн пюгю.) \ex[20] Врнаш накецвхрэ бмеяемхе хглемемхи б анкэьхе опнцпюллш, мюохяюммше мю ТНПРПЮМе, бш унрхре мюохяюрэ опнцпюллс, бшоевюршбючысч рюакхжс "оепейпеярмшу яяшкнй". Бундмшлх дюммшлх дкъ мее яксфхр опнцпюллю мю ТНПРПЮМе, ю б пегскэрюре онксвюеряъ кхярхмц хяундмни опнцпюллш, ямюафеммши сйюгюрекел бяеу яксвюеб сонрпеакемхъ йюфднцн хдемрхтхйюрнпю (р. е. хлемх) б опнцпюлле. Йюй мюохяюрэ рюйсч опнцпюллс? {\def\cell#1{\vtop{\hsize=.49\hsize\noindent #1\par}} \def\+#1\cr{\line{\cell{#1}\hfil\cell{#2}}\smallskip} \ex[33] (Янпрхпнбйю йюрюкнфмшу йюпрнвей.) Яонянаш янярюбкемхъ юктюбхрмшу йюрюкнцнб б пюгмшу ахакхнрейюу меяйнкэйн нркхвючряъ дпсц нр дпсцю. Б якедсчыел "юктюбхрмнл" яохяйе яндепфюряъ пейнлемдюжхх, бгърше хг опюбхк пецхярпюжхх х упюмемхъ йюрюкнфмшу йюпрнвей Юлепхйюмяйни ахакхнревмни юяянжхюжхх (Вхйюцн, 1942): \medskip \+ \centerline{\bf Рейяр йюпрнвйх}% &\centerline{\bf Гюлевюмхъ}\cr \+ R. Accademia nazionale dei Lincei, Rome &Б мюгбюмхъу хмнярпюммшу (йпнле апхрюмяйху) свпефдемхи якнбн "royalty" (йнпнкебяйхи) хцмнпхпсеряъ\cr \+ 1812; ein historischer roman. &Achtzehnhundert zw\"olf \cr \+ Biblioth\`eque d'histoire r\'evolutionnaire. &Бн тпюмжсгяйнл рейяре юонярпнт пюяялюрпхбюеряъ йюй опнаек \cr \+ Biblioth\`eque des curiosit\'es. &Мюдярпнвмше гмюйх хцмнпхпсчряъ \cr \+ Brown, Mrs. J. Crosby &Сйюгюмхе онкнфемхъ (Mrs.) хцмнпхпсеряъ \cr \+ Brown, John &Тюлхкхх я дюрюлх якедсчр гю тюлхкхълх аег дюр~\dots \cr \+ Brown, John, mathematician &\dots{} йнрнпше сонпъднвхбючряъ он \cr \+ Brown, John, of Boston &нохяюрекэмшл якнбюл \cr \+ Brown, John, 1715--1766 &Ндхмюйнбше тюлхкхх сонпъднвхбючряъ он дюрюл пнфдемхъ \cr %% 21 \+ BROWN, JOHN, 1715--1766 &Пюанрш "н мел" хдср оняке ецн пюанр \cr \+ Brown, John, d. 1811 &Хмнцдю цнд пнфдемхъ нопедекъеряъ опхакхгхрекэмн \cr \+ Brown, Dr. John, 1810--1882 &Сйюгюмхе онкнфемхъ (Dr.) хцмнпхпсеряъ \cr \+ Brown-Williams, Reginald Makepeace &Детхя пюяялюрпхбюеряъ йюй опнаек \cr \+ Brown America. &Мюгбюмхъ ймхц хдср оняке янярюбмшу тюлхкхи \cr \+ Brown \& Dallison's Nevada directory. &\& б юмцкхияйнл рейяре опебпюыюеряъ б "and" \cr \+ Brownjohn, Alan &\cr \+ Den', Vladimir \'Eduardovich, 1867-- &Юонярпнт б хлемюу хцмнпхпсеряъ\cr \+ The den. &Юпрхйкэ б мювюке рейярю хцмнпхпсеряъ\cr \+ Den lieben s\"ussen m\"adeln. &\dots{} еякх ясыеярбхрекэмне ярнхр б хлемхрекэмнл оюдефе\cr \+ Dix, Morgan, 1827--1908 &Тюлхкхх хдср пюмэье дпсцху якнб \cr \+ 1812 ouverture. &Dix-huit cent douze \cr \+ Le XIXe si\`ecle fran\c{c}ais. &Dix-neuvi\`eme \cr \+ The 1847 issue of U. S. stamps. &Eighteen forty-seven \cr \+ 1812 overture. &Eighteen twelve \cr \+ I am a mathematician, &(by Norbert Weiner)\cr \+ IBM journal of research and development. &Юаапебхюрспш пюяялюрпхбючряъ йюй пъд ндмнасйбеммшу якнб \cr \+ ha-I ha-e\d had. &Юпрхйкэ б мювюке рейярю хцмнпхпсеряъ \cr \+ Ia; a love story. &Гмюйх опеохмюмхъ б мюгбюмхъу хцмнпхпсчряъ \cr \+ International Business Machines Corporation &\cr \+ al-Khuw\={a}rizm\={\i}, Mu\d{h}ammad ibn M\={u}s\={a}, {\it fl.\/} 813--846 &Мювюкэмне "юl-" б юпюаяйху хлемюу хцмнпхпсеряъ \cr \+ Labour; a magazine for all workers. &Гюлемъеряъ мю "Labor" \cr \+ Labor research association &\cr \+ Labour, {\it see\/} Labor &Яяшкйю мю дпсцсч йюпрнвйс б йюпрнрейе \cr \+ McCall's cookbook &Юонярпнт б юмцкхияйнл рейяре хцмнпхпсеряъ \cr \+ McCarthy, John, 1927-- &Mc = Mac \cr \+ Machine-independent computer programming. &Детхя пюяялюрпхбюеряъ йюй опнаек \cr \+ MacMahon, Maj. Percy Alexander, 1854--1929 &Сйюгюмхе онкнфемхъ (Maj) хцмнпхпсеряъ \cr \+ Mrs. Dalloway. &"Mrs. "= "Mistress" \cr \+ Mistress of mistresses. &\cr \+ Royal society of London &\cr \+ St. PetersburgerZeitung. &"St."= "Saint" дюфе б мележйнл рейяре \cr \+ Saint-Sa\"ens, Camille, 1835--1921 &Детхя пюяялюрпхбюеряъ йюй опнаек \cr \+ Ste. Anne des Monts, Quebec &Sainte \cr \+ Seminumerical algorithms. &\cr \+ Uncle Tom's cabin. &\cr \+ U.S. Bureau of the census. &"U.S." = "United States" \cr \+ Vandermonde, Alexander Th\'eophile, 1735--1796 &\cr \+ Van Valkenburg, Mac Elwyn, 1921-- & Опнаек оняке опетхйяю б тюлхкхъу хцмнпхпсеряъ \cr \+ Von Neumann, John, 1903--1957 &\cr \+ The whole art of legerdemain. &\cr %% 22 \+ Who's afraid of Virginia Woolf? & Юонярпнт б юмцкхияйнл рейяре хцмнпхпсеряъ\cr \+ Wijngaarden, Adriaan van, 1916-- & Тюлхкхъ мхйнцдю ме мювхмюеряъ я люкни асйбш \cr \medskip \noindent(С анкэьхмярбю хг щрху опюбхк еярэ хяйкчвемхъ; йпнле рнцн, ясыеярбсер лмнцн дпсцху опюбхк, йнрнпше гдеяэ ме сонлъмсрш.) \par } Опедонкнфхл, бюл опхькняэ янпрхпнбюрэ анкэьне йнкхвеярбн рюйху йюпрнвей я онлныэч бшвхякхрекэмни люьхмш х бонякедярбхх наяксфхбюрэ нцпнлмсч йюпрнрейс, опхвел с бюя мер бнглнфмнярх хглемхрэ сфе якнфхбьхеяъ онпъдйх гюонкмемхъ йюпрнвей. Йюй аш бш нпцюмхгнбюкх хмтнплюжхч, врнаш сопнярхрэ ноепюжхх бйкчвемхъ мнбшу йюпрнвей х янпрхпнбйх? \ex[Л21]\exhead(Дхяйпермше кнцюпхтлш.) Осярэ хгбеярмн, врн $p$---(днбнкэмн анкэьне) опнярне вхякн, ю $a$---оепбннапюгмши йнпемэ он лндскч $p$. Якеднбюрекэмн, дкъ кчанцн $b$ б дхюоюгнме $1\le{} b < p$ ясыеярбсер едхмярбеммне $n$, рюйне, врн $a^n \bmod p=b$, $1\le{} n < п$. Йюй он гюдюммнлс $b$ мюирх $n$ лемее вел гю $Н(n)$ ьюцнб? [Сйюгюмхе. Осярэ $m=\lceil\sqrt p\rceil$. Оношрюиреяэ пеьхрэ спюбмемхе $a^{mn_1}\equiv b a^{-n_2} \pmod{p}$ опх $0 \le{} n_1$, $n_2 < m$.] \ex[Л25] (Щ. Р. Оюпйеп.) Щикеп бшдбхмск опедонкнфемхе, врн спюбмемхе $$ u^6+v^6+ w^6 + у^6 + y^6 = z^6 $$ ме хлеер пеьемхи (гю хяйкчвемхел рпхбхюкэмшу) япедх жекшу менрпхжюрекэмшу вхяек $u$, $v$, $w$, $x$, $y$, $z$, йнцдю он йпюимеи лепе вершпе оепелеммше пюбмш мскч. Онлхлн щрнцн, нм опедонкюцюк, врн спюбмемхе $$ x_1^n+\cdots+x_{n-1}^n=x_n^n $$ ме хлеер мерпхбхюкэмшу пеьемхи опх $n\ge 3$, мн щрн опедонкнфемхе ашкн нопнбепцмсрн: я онлныэч бшвхякхрекэмни люьхмш мюидемн рнфдеярбн $27^5+84^5+110^5+133^5=144^5$; ял. К. Дф. Кщмдеп, Р. П. Оюпйхм х Дф. К. Яектпхдф, {\sl Math. Comp.\/}, {\bf 21} (1967), 446--459. Опхдслюире, йюй лнфмн ашкн аш хяонкэгнбюрэ янпрхпнбйс дкъ онхяйю опхлепнб, нопнбепцючыху опедонкнфемхе Щикепю опх $n=6$. \rex[24] Тюик яндепфхр анкэьне йнкхвеярбн 30-пюгпъдмшу дбнхвмшу якнб: $x_1$, \dots $x_N$. Опхдслюире унпньхи яоняна мюунфдемхъ б мел бяеу \emph{днонкмхрекэмшу} оюп $(x_i, у_j)$. (Дбю якнбю мюгшбючряъ днонкмхрекэмшлх, еякх брнпне яндепфхр 0 бн бяеу пюгпъдюу, б йнрнпшу ашкх 1 б оепбнл якнбе, х напюрмн; рюйхл напюгнл, нмх днонкмхрекэмш рнцдю х рнкэйн рнцдю, йнцдю ху ясллю пюбмю $(11\ldots1)_2$, еякх нмх пюяялюрпхбючряъ йюй дбнхвмше вхякю.) \rex[25] Хлееряъ тюик. яндепфюыхи 1000 30-пюгпъдмшу дбнхвмшу якнб $x_1$, \dots, $x_{1000}$. Йюй аш бш ярюкх янярюбкърэ яохянй бяеу оюп $(x_i, x_j)$, рюйху, врн $x_i$ нркхвюеряъ нр $x_j$ ме анкее вел б дбсу пюгпъдюу? \ex[22] Йюй аш бш онярсохкх опх нршяйюмхх бяеу оърхасйбеммшу юмюцпюлл, рюйху, йюй \strong{CARET, CARTE, CATER, CRATE, REACT, TRACE; CRUEL, LUCRE, ULCER; DOWRY, ROWDY, WORDY?} [Еякх аш бш, яйюфел, гюунрекх сгмюрэ, ясыеярбсчр кх б юмцкхияйнл ъюшйе мюанпш хг деяърх хкх анкее юмюцпюлл, йпнле гюлевюрекэмни яепхх: $$ \vtop{\strong{ APERS, ASPER,PARES,PARSE,PEARS, PRASE, RAPES, REAPS, SPARE, SPEAR, }} $$ й йнрнпни лнфмн днаюбхрэ еые тпюмжсгяйне якнбн \strong{APRES.}] \ex[Л28] Осярэ дюмш нохяюмхъ беяэлю анкэьнцн вхякю мюопюбкеммшу цпютнб. Йюйхл осрел лнфмн яцпсоохпнбюрэ \emph{хгнлнптмше} цпютш? (Дбю мюопюбкеммшу цпютю мюгшбючряъ хгнлнптмшлх, еякх ясыеярбсер бгюхлмн ндмнгмювмне яннрберярбхе лефдс ху бепьхмюлх х бгюхлмн ндмнгмювмне яннрберярбхе %% 23 лефдс ху дсцюлх, опхвел щрх яннрберярбхъ янупюмъчр хмжхдемрмнярэ бепьхм х дсц.) \ex[30] Б мейнрнпни цпсоое хг 4096 векнбей йюфдши хлеер нйнкн 100 гмюйнлшу. Ашк янярюбкем яохянй бяеу оюп кчдеи, гмюйнлшу лефдс янани. (Щрн нрмньемхе яхллерпхвмн, р. е. еякх $у$ гмюйнл я $с$, рн х $с$ гмюйнл я $у$. Онщрнлс яохянй яндепфхр опхлепмн 200000 оюп.) Опхдслюире юкцнпхрл, йнрнпши он гaдaммoлy $k$ бшдюбюк аш бяе \emph{йкхйх} хг $k$ векнбей. (Йкхйю --- щрн цпсоою кчдеи, б йнрнпни бяе лефдс янани гмюйнлш.) Опедонкюцюеряъ, врн якхьйнл анкэьху йкхй ме ашбюер. \ex[30] Рпх лхккхнмю векнбей я пюгкхвмшлх хлемюлх ашкх скнфемш пъднл меопепшбмни жеонвйни нр Мэч-Инпйю дн Йюкхтнпмхх. Йюфднлс хг мху дюкх кхярнй аслюцх, мю йнрнпнл нм мюохяюк ябне хлъ х хлъ ябнецн акхфюиьецн гюоюдмнцн яняедю. Векнбей, мюундхбьхияъ б яюлни гюоюдмни рнвйе жеох, ме онмък, врн елс декюрэ, х бшйхмск ябни кхярнй. Нярюкэмше 2999999 кхярйнб янапюкх б анкэьсч йнпгхмс х нропюбхкх б Мюжхнмюкэмши юпухб, б Бюьхмцрнм, нйпсц Йнкслахъ. Рюл яндепфхлне йнпгхмш рыюрекэмн оеперюянбюкх х гюохяюкх мю люцмхрмше кемрш. Яоежхюкхяр он ренпхх хмтнплюжхх нопедекхк, врн хлееряъ днярюрнвмн хмтнплюжхх дкъ бняярюмнбкемхъ яохяйю кчдеи б хяундмнл онпъдйе. Яоежхюкхяр он опнцпюллхпнбюмхч мюьек яоняна ядекюрэ щрн лемее вел гю 1000 опнялнрпнб кемр я дюммшлх, хяонкэгсъ кхьэ онякеднбюрекэмши днярсо й тюикюл мю кемрюу х меанкэьне йнкхвеярбн оюлърх я опнхгбнкэмшл днярсонл. Йюй елс щрн сдюкняэ? [Дпсцхлх якнбюлх, йюй, хлеъ пюяонкнфеммше опнхгбнкэмшл напюгнл оюпш $(x_i, x_{i+1})$, $1 \le i < N$, цде бяе $x_i$ пюгкхвмш, онксвхрэ онякеднбюрекэмнярэ $x_1$, $x_2$, \dots, $x_N$, опхлемъъ кхьэ лерндш онякеднбюрекэмни напюанрйх дюммшу, опхцндмше дкъ пюанрш я люцмхрмшлх кемрюлх? Щрн гюдювю янпрхпнбйх б яксвюе, йнцдю рпсдмн нопедекхрэ, йюйни хг дбсу йкчвеи опедьеярбсер дпсцнлс; лш сфе ондмхлюкх щрнр бнопня б соп. 2.2.3--25.] %% 24 \subchap{* ЙНЛАХМЮРНПМШЕ ЯБНИЯРБЮ ОЕПЕЯРЮМНБНЙ} Оепеярюмнбйни йнмевмнцн лмнфеярбю мюгшбюеряъ мейнрнпне пюяонкнфемхе ецн щкелемрнб б пъд. Оепеярюмнбйх нянаеммн бюфмш опх хгсвемхх юкцнпхрлнб янпрхпнбйх, рюй йюй нмх яксфюр дкъ опедярюбкемхъ месонпъднвеммшу хяундмшу дюммшу. Врнаш хяякеднбюрэ щттейрхбмнярэ пюгкхвмшу лернднб янпрхпнбйх, мсфмн слерэ ондявхршбюрэ вхякн оепеярюмнбнй, йнрнпше бшмсфдючр онбрнпърэ мейнрнпши ьюц юкцнпхрлю нопедекеммне вхякн пюг. Лш, йнмевмн, сфе ме пюг бярпевюкхяэ я оепеярюмнбйюлх б цк. 1, 2 х~3. Мюопхлеп, б о. 1.2.5 наясфдюкхяэ дбю нямнбмшу ренперхвеяйху лерндю онярпнемхъ $n!$ оепеярюмнбнй хг $n$ на╝ейрнб; б о. 1.3.3 опнюмюкхгхпнбюмш мейнрнпше юкцнпхрлш, ябъгюммше я жхйкхвеяйни ярпсйрспни х лскэрхокхйюрхбмшлх ябниярбюлх оепеярюмнбнй; б о. 3.3.2 хгсвемш ху нрпегйх лнмнрнммнярх. Жекэ мюярнъыецн оюпюцпютю---хгсвхрэ мейнрнпше дпсцхе ябниярбю оепеярюмнбнй х пюяялнрперэ наыхи яксвюи, йнцдю дносяйюеряъ мюкхвхе ндхмюйнбшу щкелемрнб. Оносрмн лш сгмюел лмнцне н йнлахмюрнпмни люрелюрхйе. Ябниярбю оепеярюмнбнй мюярнкэйн йпюяхбш, врн опедярюбкъчр х яюлнярнърекэмши хмрепея. Сднамн асдер дюрэ ху яхярелюрхвеяйне хгкнфемхе б ндмнл леяре, ю ме пюгапюяшбюрэ люрепхюк он бяеи цкюбе. Вхрюрекъл, ме хлечыхл яйкнммнярх й люрелюрхйе, ю рюйфе рел, йрн фюфдер оняйнпее днапюрэяъ дн яюлху лернднб янпрхпнбйх, пейнлемдсеряъ оепеирх япюгс й \S~5.2, онрнлс врн мюярнъыхи оюпюцпют \emph{меоняпедярбеммнцн} нрмньемхъ й янпрхпнбйе онврх ме хлеер. \subsubchap{*Хмбепяхх} Осярэ $a_1$ $a_2$ \dots\ $a_n$ ---оепеярюмнбйю лмнфеярбю $\{1, 2, \dots, n\}$. Еякх $i < j$, a $a_i>a_j$, рн оюпю $(ю_i, a_j)$ мюгшбюеряъ хмбепяхеи оепеярюмнбйх; мюопхлеп, оепеярюмнбйю 3 1 4 2 хлеер рпх хмбепяхх: $(3, 1)$, $(3, 2)$ х $(4, 2)$. Йюфдюъ хмбепяхъ---щрн оюпю щкелемрнб, "мюпсьючыху онпъднй"; якеднбюрекэмн, едхмярбеммюъ оепеярюмнбйю, ме яндепфюыюъ хмбепяхи,---щрн нрянпрхпнбюммюъ оепеярюмнбйю 1 2 \dots $n$. Рюйюъ ябъгэ я янпрхпнбйни х еярэ цкюбмюъ опхвхмю мюьецн хмрепеяю й хмбепяхъл, унръ щрн онмърхе сфе хяонкэгнбюкняэ мюлх опх юмюкхге юкцнпхрлю дхмюлхвеяйнцн пюяопедекемхъ оюлърх (ял. соп. 2.2.2--9). %% 25 Онмърхе хмбепяхх ббек Ц. Йпюлеп б 1750 ц. [Intr. \`a 1'Analyse des Lignes Courbes alg\'ebriques (Geneva, 1750), 657--659; яп. я Рнлюя Лчхп, Рhенцс of Determinants, 1 (1906), 11--14] б ябъгх ян ябнхл гюлевюрекэмшл опюбхкнл пеьемхъ кхмеимшу спюбмемхи. Б ясымнярх, нм нопедекхк дереплхмюмр $n\times n$-люрпхжш якедсчыхл напюгнл: $$ \det\pmatrix{ x_{11} & x_{12} &\ldots & x_{1n} \cr \vdots & \vdots & & \vdots \cr x_{n1} & x_{n2} & \ldots & x_{nn} \cr }=\sum (-1)^{I(a_1 a_2 \ldots a_n)}x_{1a_1}x_{2a_2}\ldots x_{na_n}, $$ цде ясллю аеперяъ он бяел оепеярюмнбйюл $a_1$ $a_2$ \dots\ $a_n$, ю $I(a_1 a_2 \ldots a_n)$---вхякн хмбепяхи б оепеярюмнбйе. \dfn{Рюакхжеи хмбепяхи} оепеярюмнбйх $a_1$ $a_2$ \dots\ $a_n$ мюгшбюеряъ онякеднбюрекэмнярэ вхяек $b_1$ $b_2$ \dots\ $b_n$, цде $b_j$---вхякн щкелемрнб, \emph{а\'нкэьху} $j$ х пюяонкнфеммшу \emph{кебее} $j$. (Дпсцхлх якнбюлх, $b_j$---вхякн хмбепяхи, с йнрнпшу брнпни щкелемр пюбем~$j$.) Мюопхлеп, рюакхжеи хмбепяхи оепеярюмнбйх $$ 5\;9\;1\;8\;2\;6\;4\;7\;3 \eqno (1) $$ асдер $$ 2\;3\;6\;4\;0\;2\;2\;1\;0,\eqno (2) $$ оняйнкэйс 5 х 9 пюяонкнфемш кебее 1; 5, 9, 8---кебее 2 х р.д., бяецн 20 хмбепяхи. Он нопедекемхч $$ 0\le{} b_1\le{} n-1, 0\le{} b_2 \le{} n-2,\ldots ,0\le{} b_{n-1}\le{} 1, b_n=0.\eqno (3) $$ Онфюкси, мюханкее бюфмши тюйр, йюяючыхияъ оепеярюмнбнй, х сярюмнбкеммши Люпьюккнл Унккнл, щрн рн, врн \emph{рюакхжю хмбепяхи едхмярбеммшл напюгнл нопедекъер яннрберярбсчысч оепеярюмнбйс.} [Ял. Proc. Symp. Applied Math., {\bf 6} (American Math. Society, 1956), 203.] Хг кчани рюакхжш хмбепяхи $b_1$ $b_2$ \dots\ $b_n$, сднбкербнпъчыеи сякнбхъл (3), лнфмн ндмнгмювмн бняярюмнбхрэ оепеярюмнбйс, йнрнпюъ онпнфдюер дюммсч рюакхжс, осрел онякеднбюрекэмнцн нопедекемхъ нрмняхрекэмнцн пюяонкнфемхъ щкелемрнб $n$, $n-1$, \dots, $1$ (б щрнл онпъдйе). Мюопхлеп, оепеярюмнбйс, яннрберярбсчысч (2), лнфмн онярпнхрэ якедсчыхл напюгнл: бшохьел вхякн 9; рюй йюй $b_8=1$, рн 8 ярнхр опюбее 9. Оняйнкэйс $b_7=2$, рн 7 ярнхр опюбее 8 х~9. Рюй йюй $b_6=2$, рн 6 ярнхр опюбее дбсу сфе бшохяюммшу мюлх вхяек; рюйхл напюгнл, хлеел $$ 9\; 8\; 6\; 7. $$ %% 26 Опхохьел реоепэ 5 якебю, онрнлс врн $b_5=0$; онлеыюел 4 бякед гю вершпэлъ хг сфе гюохяюммшу вхяек, 3---оняке ьеярх бшохяюммшу вхяек (р. е. б опюбши йнмеж) х онксвюел $$ 5\;9\;8\;6\;4\;7\;3. $$ Бярюбхб юмюкнцхвмшл напюгнл 2 х 1, опхдел й (1). Рюйне яннрберярбхе бюфмн, онрнлс врн вюярн лнфмн гюлемхрэ гюдювс, ятнплскхпнбюммсч б реплхмюу оепеярюмнбнй, щйбхбюкемрмни еи гюдювеи, ятнплскхпнбюммни б реплхмюу рюакхж хмбепяхи, йнрнпюъ, бнглнфмн, пеьюеряъ опные. Пюяялнрпхл, мюопхлеп, яюлши опнярни бнопня: яйнкэйн ясыеярбсер оепеярюмнбнй лмнфеярбю $\{1, 2, \ldots, n\}$? Нрбер днкфем ашрэ пюбем вхякс бяебнглнфмшу рюакхж хмбепяхи, ю ху кецйн оепеявхрюрэ, рюй йюй $b_1$ лнфмн бшапюрэ $n$ пюгкхвмшлх яонянаюлх, $b_2$ лнфмн мегюбхяхлн нр $b-1$ бшапюрэ $n-1$ яонянаюлх, \dots, $b_n$---ндмхл яонянанл; хрнцн $о(о-1)\ldots 1=n!$ пюгкхвмшу рюакхж хмбепяхи. Рюакхжш хмбепяхи оепеявхрюрэ кецве, онрнлс врн $b$ мегюбхяхлш, б рн бпелъ йюй $ю$ днкфмш ашрэ бяе пюгкхвмш. Б о. 1:2.10 лш хяякеднбюкх гюдювс н вхяке кнйюкэмшу люйяхлслнб оепеярюмнбйх, еякх вхрюрэ ее яопюбю мюкебн; хмшлх якнбюлх, рпеанбюкняэ ондявхрюрэ йнкхвеярбн щкелемрнб, йюфдши хг йнрнпшу анкэье кчанцн хг якедсчыху оняке мецн. (Мюопхлеп, опюбнярнпнммхе люйяхлслш б (1)---щрн 9, 8, 7 х 3.) Нмн пюбмн йнкхвеярбс хмдейянб $j$, рюйху, врн $b_j=n-j$. Рюй йюй $b_1$ опхмхлюер гмювемхе $n-1$ я бепнърмнярэч $1/n$, $b_2$ (мегюбхяхлн) опхмхлюер гмювемхе $n-2$ я бепнърмнярэч $1/(n-1)$ х р.д., рн хг пюяялнрпемхъ хмбепяхи ъямн, врн япедмее вхякн опюбнярнпнммху люйяхлслнб пюбмн $$ {1\over n}+{1\over n-1}+\cdots+1=H_n. $$ Юмюкнцхвмшл яонянанл кецйн онксвхрэ х яннрберярбсчысч опнхгбндъысч тсмйжхч. Дпсцхе опхлемемхъ рюакхж хмбепяхи бярперъряъ дюкее б щрни цкюбе б ябъгх я йнмйпермшлх юкцнпхрлюлх янпрхпнбйх. Ъямн, врн еякх онлемърэ леярюлх \emph{яняедмхе} щкелемрш оепеярюмнбйх, рн наыее вхякн хмбепяхи сбекхвхряъ хкх слемэьхряъ мю едхмхжс. Мю пхя. 1 онйюгюмш 24 оепеярюмнбйх лмнфеярбю $\{1, 2, 3, 4\}$; кхмхълх янедхмемш оепеярюмнбйх, нркхвючыхеяъ дпсц нр дпсцю онкнфемхел дбсу яняедмху щкелемрнб; дбхцюъяэ бднкэ кхмхх бмхг, лш .сбекхвхбюел вхякн хмбепяхи мю едхмхжс. Якеднбюрекэмн, вхякн хмбепяхи б оепеярюмнбйе $о$ пюбмн дкхме мхяундъыецн осрх хг 1 2 3 4 б $n$ мю пхя.~1; бяе рюйхе осрх днкфмш хлерэ ндхмюйнбсч дкхмс. Гюлерхл, врн щрс дхюцпюллс лнфмн пюяялюрпхбюрэ йюй рпеулепмне рбепдне рекн---"сяевеммши нйрющдп", хлечыхи 8 ьеярхсцнкэмшу %% 27 х 6 йбюдпюрмшу цпюмеи. Щрн ндхм хг пюбмнлепмшу лмнцнцпюммхйнб, йнрнпше наясфдюк Юпухлед (ял. соп.,10). \picture{ Пхя. 1. Сяевеммши нйрющдп, мю йнрнпнл онйюгюмн хглемемхе вхякю хмбепяхи, йнцдю лемъчряъ леярюлх дбю яняедмху щкелемрю оепеярюмнбйх; } Ме якедсер осрюрэ "хмбепяхх" оепеярюмнбнй я напюрмшлх оепеярюмнбйюлх. Бяонлмхл, врн оепеярюмнбйс лнфмн гюохяшбюрэ б бхде дбсу ярпнй $$ \pmatrix{ 1 & 2 & 3 & \ldots & n \cr a_1 & a_2 & a_3 & \ldots & a_n \cr };\eqno (4) $$ \dfn{напюрмни} й щрни оепеярюмнбйе мюгшбюеряъ оепеярюмнбйю $a'_1$, $a'_2$, \dots\ $a'_n$, йнрнпюъ онксвюеряъ, еякх б (4) онлемърэ леярюлх ярпнйх, ю гюрел сонпъднвхрэ ярнкажш б бнгпюярючыел онпъдйе он бепумхл щкелемрюл: $$\pmatrix{ a_1 & a_2 & a_3 & \ldots & a_n \cr 1 & 2 & 3 & \ldots & n \cr }=\pmatrix{ 1 & 2 & 3 & \ldots & n \cr a'_1 & a'_2 & a'_3 & \ldots & a'_n \cr }; \eqno(5) $$ Мюопхлеп, напюрмни й оепеярюмнбйе 5 9 1 8 2 6 4 7 3 асдер оепеярюмнбйю %% 28 3 5 9 7 1 6 8 4 2, рюй йюй $$ \pmatrix{ 5 & 9 &1 &8 &2 &6 &4 &7 &3\cr 1 & 2 & 3&4 &5 &6 &7 &8 &9\cr }=\pmatrix{ 1 &2 &3 &4 &5 &6 &7 &8 &9\cr 3 &5 &9 &7 &1 &6 &8 &4 &2\cr }. $$ Лнфмн дюрэ дпсцне нопедекемхе напюрмни оепеярюмнбйх: $a'_j=k$ рнцдю х рнкэйн рнцдю, йнцдю $ю_k=j$. Напюрмсч оепеярюмнбйс боепбше бб╦к X. Ю. Пнре [б Й.F.~Hindenburg(ed.)., Sammlung combinatorisch-analytischer Abhandlungen, 2 (Leipzig, 1800), 263--305]; нм гюлерхк хмрепеямсч ябъгэ лефдс напюрмшлх оепеярюмнбйюлх х хмбепяхълх: \emph{напюрмюъ оепеярюмнбйю яндепфхр пнбмн ярнкэйн фе хмбепяхи, яйнкэйн хяундмюъ}. Пнре дюк ме яюлне опнярне днйюгюрекэярбн щрнцн тюйрю, мн нмн онсвхрекэмн х опхрнл днбнкэмн йпюяхбн. Онярпнхл рюакхжс пюглепю $n\times n$ х онярюбхл рнвйх б $j$-и йкерйе $i$-и ярпнйх, еякх $a_i=j$. Оняке щрнцн пюяярюбхл йпеярхйх бн бяеу йкерйюу, ямхгс нр йнрнпшу (б рнл фе ярнкаже) х яопюбю (б рни фе ярпнйе) еярэ рнвйх. Мюопхлеп, дкъ 5 9 1 8 2 6 4 7 3 дхюцпюллю асдер рюйни: $$ %% picture $$ Йнкхвеярбн йпеярхйнб пюбмн вхякс хмбепяхи, рюй йюй мерпсдмн бхдерэ, врн $b_j$ пюбмн вхякс йпеярхйнб б $j$-л ярнкаже. Еякх лш реоепэ рпюмяонмхпсел дхюцпюллс (онлемъб пнкълх ярпнйх х ярнкажш), рн онксвхл дхюцпюллс дкъ напюрмни он нрмньемхч й хяундмни оепеярюмнбйх; гмювхр, вхякн йпеярхйнб (вхякн хмбепяхи) ндхмюйнбн б нанху яксвюъу. Пнре хяонкэгнбюк щрнр тюйр дкъ днйюгюрекэярбю рнцн, врн дереплхмюмр люрпхжш ме лемъеряъ опх рпюмяонмхпнбюмхх. Дкъ юмюкхгю мейнрнпшу юкцнпхрлнб янпрхпнбйх менаундхлн гмюрэ вхякн оепеярюмнбнй $о$ щкелемрнб, яндепфюыху пнбмн $k$ хмбепяхи. Нангмювхл щрн вхякн вепег $I_n(k)$; б рюак. 1 опхбедемш оепбше меяйнкэйн гмювемхи щрни тсмйжхх. %% 29 \htable{Рюакхжю 1}{Оепеярюмнбйх я $k$ хмбепяхълх}% {$#$\bskip\hfill&&\hfill\bskip$#$\bskip\hfill\cr n & I_n(0) & I_n(1) & I_n(2) & I_n(3) & I_n(4) & I_n(5) & I_n(6) & I_n(7) & I_n(8) & I_n(9) & I_n(10) & I_n(11)\cr 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\cr 2 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\cr 3 & 1 & 2 & 2 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\cr 4 & 1 & 3 & 5 & 6 & 5 & 3 & 1 & 0 & 0 & 0 & 0 & 0\cr 5 & 1 & 4 & 9 & 15 & 20 & 22 & 20 & 15 & 9 & 4 & 1 & 0\cr 6 & 1 & 5 & 14 & 29 & 49 & 71 & 90 & 101 & 101 & 90 & 71 & 49 \cr } Хг пюяялнрпемхъ рюакхжш хмбепяхи $b_1$ $b_2$ \dots.$b_n$ ъямн, врн $I_k(0)=1$, $I_n(1)=n-1$ х врн бшонкмъеряъ ябниярбн яхллерпхх: $$ I_n\left(\left({n \atop 2}\right)-k\right)=I_n(k)\eqno (6) $$ Дюкее, рюй йюй гмювемхъ $b$ лнфмн бшахпюрэ мегюбхяхлн дпсц нр дпсцю, рн мерпсдмн бхдерэ, врн опнхгбндъыюъ тсмйжхъ $$ G_n(z)=I_n(0)+I_n(1)z+I_n(2)z^2+\cdots \eqno (7) $$ сднбкербнпъер яннрмньемхч $G_n(z) = (1 +z+ \cdots +z^{n-1})G_{n-1}(z)$; якеднбюрекэмн, нмю хлеер днбнкэмн, опнярни бхд $$ (1+z+\cdots+z^{n-1})\ldots(1+z)(1)=(1-z^n)\ldots(l-z^2)(l-z)/(l-z)^n. \eqno(8) $$ Я онлныэч щрни опнхгбндъыеи тсмйжхх лнфмн кецйн опнднкфхрэ рюак. 1 х саедхрэяъ, врн вхякю, пюяонкнфеммше онд ярсоемвюрни кхмхеи б рюакхже, сднбкербнпъчр яннрмньемхч $$ I_n(k)=I_n(k-1)+I_{n-1}(k) \rem{опх $ka_{j+1}$, $1 \le < n$. Мюопхлеп, хмдейя оепеярюмнбйх 5 9 1 8 2 6 4 7 3 пюбем $2+4+6+8=20$. Хмдейя яксвюимн янбоюк я вхякнл хмбепяхи. Еякх янярюбхрэ яохянй бяеу 24 оепеярюмнбнй лмнфеярбю $\{1, 2, 3, 4\}$, ю хлеммн %% 31 { \def|{\,\vrule} \offinterlineskip \ctable{ \strut\hfill$#$\bskip\hfill&&\hfill$#$\bskip\hfill\cr \multispan{4}Оепеярюмнбйю & Хмдейя & Хмбепяхх & \multispan{4}Оепеярюмнбйю& Хмдейя &Хмбепяхх \cr 1 & 2 & 3 & 4 & 0 & 0 & 3| & 1 & 2 & 4 & 1 & 2 \cr 1 & 2 & 4|& 3 & 3 & 1 & 3| & 1 & 4|& 2 & 4 & 3 \cr 1 & 3|& 2 & 4 & 2 & 1 & 3| & 2|& 1 & 4 & 3 & 3 \cr 1 & 3 & 4|& 2 & 3 & 2 & 3| & 2 & 4|& 1 & 4 & 4 \cr 1 & 4|& 2 & 3 & 2 & 2 & 3 & 4|& 1 & 2 & 2 & 4 \cr 1 & 4|& 3|& 2 & 5 & 3 & 3 & 4|& 2|& 1 & 5 & 5 \cr 2|& 1 & Г & 4 & 1 & 1 & 4| & 1 & 2 & 3 & 1 & 3 \cr 2|& 1 & 4|& 3 & 4 & 2 & 4| & 1 & 3|& 2 & 4 & 4 \cr 2 & 3|& 1 & 4 & 2 & 2 & 4| & 2|& 1 & 3 & 3 & 4 \cr 2 & 3 & 4|& 1 & 3 & 3 & 4| & 2 & 3|& 1 & 4 & 5 \cr 2 & 4|& 1 & 3 & 2 & 8 & 4| & 3|& 1 & 2 & 3 & 5 \cr 2 & 4|& 3|& 1 & 5 & 4 & 4| & 3|& 2|& 1 & 6 & 6 \cr } } рн бхдмн, врн \emph{вхякн оепеярюмнбнй, хлечыху дюммши хмдейя $k$, пюбмн вхякс оепеярюмнбнй, хлечыху $k$ хмбепяхи.} Мю оепбши бгцкъд щрнр тюйр лнфер онйюгюрэяъ онврх нвебхдмшл, ндмюйн оняке мейнрнпшу пюглшькемхи нм мювхмюер йюгюрэяъ всрэ кх ме лхярхвеяйхл, х ме бхдмн мхйюйнцн опнярнцн опълнцн ецн днйюгюрекэярбю. Люй-Люцнм мюьек якедсчыее нярпнслмне йнябеммне днйюгюрекэярбн: осярэ $J(ю_1 ю_2 \ldots a_n)$---хмдейя оепеярюмнбйх $a_1$ $a_2$ \dots $a_n$, х яннрберярбсчыюъ опнхгбндъыюъ тсмйжхъ еярэ $$ H_n(z)=\sum z^{J(a_1 a_2 \ldots a_n)}, \eqno (14) $$ цде ясллю аеперяъ он бяел оепеярюмнбйюл лмнфеярбю $\{1, 2, \ldots., о\}$. Лш унрекх аш днйюгюрэ, врн $H_n(z)=G_n(z)$. Дкъ щрнцн нопедекхл бгюхлмн ндмнгмювмне яннрберярбхе лефдс $n$-йюлх $(q_1, q_2, \ldots, q_n)$ менрпхжюрекэмшу жекшу вхяек, я ндмни ярнпнмш, х сонпъднвеммшлх оюпюлх $n$-нй $$ ((a_1, a_2, \ldots, a_n), (p_1, p_2, \ldots, p_n)), $$ я дпсцни ярнпнмш; гдеяэ $ю_1$ $ю_2$ \dots\ $a_n$---оепеярюмнбйю лмнфеярбю $\{1, 2, \ldots, о\}$ х $p_1\ge p_2\ge \ldots \ge p_n \ge 0$.. Щрн яннрберярбхе асдер сднбкербнпърэ сякнбхч $$ q_1+q_2+\cdots+q_n=J(a_1 a_2 \ldots a_n)+(p_1+p_2+\cdots+p_n). \eqno (15) $$ Опнхгбндъыюъ тсмйжхъ $\sum z^{q_1+q_2+\cdots+q_n}$, цде ясллю аеперяъ он бяел $n$-йюл менрпхжюрекэмшу жекшу вхяек $(q_1, q_2, \ldots, q_n)$, пюбмю $Q_n (z) =1/(1-z)^z$; ю опнхгбндъыюъ тсмйжхъ $\sum z^{p_1+p_2+\cdots+p_n}$, цде ясллю аеперяъ он бяел $n$-йюл жекшу вхяек $(п_1, п_2, \ldots p_n)$, рюйху, врн $p_1\ge p_2\ge \ldots \ge p_n \ge 0$, пюбмю, йюй онйюгюмн б соп.~15, $$ P_n(z)=1/(1-z)(1-z^2)\ldots(1-z^n). \eqno(16) $$ %% 32 Ясыеярбнбюмхе бгюхлмн ндмнгмювмнцн яннрберярбхъ, йнрнпне сднбкербнпъер сякнбхч (15) х йнрнпне лш янахпюеляъ сярюмнбхрэ, днйюгшбюер пюбемярбн $Q_n(z)=H_n(z) P_n(z)$, р.е. $$ H_n(z)=Q_n(z)/P_n(z)=G_n(z). $$ Рпеаселне яннрберярбхе нопедекъеряъ я онлныэч юкцнпхрлю "янпрхпнбйх". Мювюб я осярнцн яохяйю, опх $k=1$, $2$, \dots, $n$ (б рюйнл онпъдйе) бярюбкъел б щрнр яохянй вхякю $q_k$ якедсчыхл напюгнл: осярэ оняке $k-1$ ьюцнб б яохяйе яндепфюряъ щкелемрш $p_1$, $p_2$, \dots, $p_{k-1}$, цде $p_1\ge p_2\ge \ldots \ge p_{k-1}$, х нопедекемю оепеярюмнбйю $a_1$ $a_2$ \dots $a_n$ лмнфеярбю $\{n, n-1, \ldots, n-k+2\}$. Осярэ $j$---едхмярбеммне жекне вхякн, рюйне, врн $p_j>q_k\ge p_{j+1}$; еякх $q_k\ge p_1$, рн онкюцюел $j=0$, ю еякх $p_{k-1}>q_k$, рн онкюцюел $j=k-1$. Бярюбхл реоепэ $q_k$ б яохянй лефдс $p_j$ х $p_{j+1}$, ю жекне вхякн $(n-k+1)$---б оепеярюмнбйс лефдс $a_j$, х $a_{j+1}$. Опндекюб щрн дкъ бяеу $k$, онксвхл оепеярюмнбйс $a_1$ $a_2$ \dots $a_n$ лмнфеярбю $\{1,2, \ldots, n\}$ х $n$-йс вхяек $(p_1, p_2, \ldots, p_n)$, рюйху, врн $p_1\ge p_2 \ge \ldots \ge p_n\ge 0$ х $$ p_j > p_{j+1}, \rem{еякх $a_j>a_{j+1}$.} $$ Мюйнмеж, дкъ $1 \le j < n$ бшврел едхмхжс хг бяеу вхяек $p_1$, \dots, $p_j$ опх бяеу $j$, рюйху, врн $a_j>a_{j+1}$. Онксвеммюъ оюпю $((ю_1, ю_2, \ldots, ю_n), (p_1, p_2, \ldots, p_n))$ сднбкербнпъер сякнбхч (15). Осярэ, мюопхлеп, $n=6$ х $(q_1, \ldots, q_6)=(3, 1, 4, 0, 0, 1).$ Онярпнемхе опнхяундхр якедсчыхл напюгнл: { \offinterlineskip \ctable{ \strut\hfil$#$\bskip\hfil&&\hfil$#$\bskip\hfil\cr k & \multispan{6} $p_1\ldots p_k$\hfill & \multispan{5} $a_1\ldots a_k$\hfill \cr 1 & 3 & & & & & & 6 \cr 2 & 3 & 1 & & & & & 6 & 5 \cr 3 & 4 & 3 & 1 & & & & 4 & 6 & 5 \cr 4 & 4 & 3 & 1 & 0 & & & 4 & 6 & 5 & 3 \cr 5 & 4 & 3 & 1 & 0 & 0 & & 4 & 6 & 5 & 2 & 3 \cr 6 & 4 & 3 & 1 & 1 & 0 & 0 & 4 & 6 & 1 & 5 & 2 & 3 \cr } } Оняке гюйкчвхрекэмни йнппейрхпнбйх онксвюел $(p_1, \ldots, p_6)=(2, 1, 0, 0, 0,0)$. Мерпсдмн опнбепхрэ, врн щрнр опнжеяя напюрхл; рюйхл напюгнл, рпеаселне яннрберярбхе сярюмнбкемн х ренпелю Люй-Люцнмю днйюгюмю. Юмюкнцхвмне бгюхлмн ндмнгмювмне яннрберярбхе бярперхряъ мюл б о.~5.1.4. \excercises \ex[10] Йюйнбю рюакхжю хмбепяхи дкъ оепеярюмнбйх 2 7 1 8 4 5 9 3 а? Йюйни оепеярюмнбйе яннрберярбсер рюакхжю хмбепяхи 5 0 1 2 1 2 0 0? \ex[M15] Пеьемхел гюдювх Хняхтю, ятнплскхпнбюммни б соп. 1.3.2--22, ъбкъеряъ оепеярюмнбйю лмнфеярбю $\{1, 2, \ldots n\}$; пеьемхе дкъ опхбедеммнцн рюл опхлепю $(n=8,m=4)$---оепеярюмнбйю 5 4 6 1 3 8 7 2. Яннрберярбсчыюъ щрни оепеярюмнбйе рюакхжю хмбепяхи---3 6 3 1 0 0 1 0. Мюидхре опнярне пейсппемрмне %% 33 яннрмньемхе дкъ щкелемрнб $b_1$ $b_2$ \dots $b_n$ рюакхжш хмбепяхи б наыеи гюдюве Хняхтю дкъ $n$ векнбей, еякх йюгмър йюфднцн $m$-цн векнбейю. \ex[18] Осярэ оепеярюмнбйе $a_1$ $a_2$ \dots $a_n$ яннрберярбсер рюакхжю хмбепяхи $b_1$ $b_2$ \dots $b_n$; йюйни оепеярюмнбйе $\bar a_1$ $\bar a_2$ \dots $\bar a_n$ яннрберярбсер рюакхжю хмбепяхи $$ (n-1-b_1) (n-2-b_2) \ldots (0-b_n)? $$ \rex[20] Опхдслюире юкцнпхрл, цндмши дкъ пеюкхгюжхх мю ЩБЛ, йнрнпши он дюммни рюакхже хмбепяхи $b_1$ $b_2$ \dots $b_n$, сднбкербнпъчыеи сякнбхъл (3), ярпнхк аш яннрберярбсчысч оепеярюмнбйс $a_1$ $a_2$ \dots $a_n$. [{\sl Сйюгюмхе:\/} бяонлмхре лерндш пюанрш ян ябъгюммни оюлърэч.] \ex[35] Дкъ бшонкмемхъ мю рхохвмни ЩБЛ юкцнпхрл хг соп.~4 рпеасер бпелемх, опхакхгхрекэмн опнонпжхнмюкэмнцн $n^2$; лнфмн кх янгдюрэ юкцнпхрл, бпелъ пюанрш йнрнпнцн ашкн аш ясыеярбеммн лемэье $n^2$? \rex[26] Опхдслюире юкцнпхрл бшвхякемхъ рюакхжш хмбепяхи $b_1$ $b_2$ \dots $b_n$, яннрберярбсчыеи дюммни оепеярюмнбйе $a_1$ $a_2$ \dots $a_n$ лмнфеярбю $\{1, 2, \ldots, о\}$,, бпелъ пюанрш йнрнпнцн мю рхохвмни ЩБЛ ашкн аш онпъдйю $n\log n$. \ex[20] Онлхлн рюакхжш $b_1$ $b_2$ \dots $b_n$, нопедекеммни б щрнл осмйре, лнфмн нопедекхрэ мейнрнпше дпсцхе рхош рюакхж хмбепяхи, яннрберярбсчыху дюммни оепеярюмнбйе $a_1$ $a_2$ \dots $a_n$ лмнфеярбю $\{ 1, 2, \ldots, n\}$. Б щрнл сопюфмемхх лш пюяялнрпхл рпх дпсцху рхою рюакхж хмбепяхи, йнрнпше бнгмхйючр б опхкнфемхъу. Осярэ $c_j$---вхякн хмбепяхи, \emph{оепбюъ} йнлонмемрю йнрнпшу пюбмю $j$, р.~е. вхякн щкелемрнб, лемэьху $j$ х пюяонкнфеммшу \emph{опюбее} $j$. [Оепеярюмнбйе (1) яннрберярбсер рюакхжю $0$ $0$ $0$ $1$ $4$ $2$ $1$ $5$ $7$; ъямн, врн$ 0\le c_ja_j\}$---лмнфеярбн ее хмбепяхи, a $$ \overline{E}(\pi)=\{(a_i, a_j)\vert i>j, a_i>a_j\} $$ ---лмнфеярбн ее '"мехмбепяхи". Днйюфхре, врн $E(\pi)$ х~$\overline{E}(\pi)$ рпюмгхрхбмш. [Лмнфеярбн $S$ сонпъднвеммшу оюп мюгшбюеряъ \dfn{рпюмгхрхбмшл}, еякх дкъ кчашу $(a, b)$ х~$(b,c)$, опхмюдкефюыху $S$, оюпю $(a, c)$ рюйфе опхмюдкефхр $S$.] (b) Напюрмн, осярэ $E$---кчане рпюмгхрхбмне ондлмнфеярбн лмнфеярбю $T=\{(x, y)\vert 1\le y < x\le n\}$, днонкмемхе йнрнпнцн $T\backslash E$ рпюмгхрхбмн. Днйюфхре, врн ясыеярбсер оепеярюмнбйю $\pi$, рюйюъ, врн $E(\pi)=E$. \ex[Л28] Хяонкэгсъ нангмювемхъ опедшдсыецн сопюфмемхъ, днйюфхре, врн еякх $\pi_1$ х $\pi_2$---оепеярюмнбйх, ю $E$---лхмхлюкэмне рпюмгхрхбмне лмнфеярбн, яндепфюыее $E(\pi_1)\cup E(\pi_2)$, рн $\overline{E}$---рнфе рпюмгхрхбмне лмнфеярбн. [Якеднбюрекэмн, еякх лш асдел цнбнпхрэ, врн $\pi_1$ мюундхряъ "мюд" $\pi_2$, йнцдю $E(\pi_1)\subseteq E(\pi_2)$, рн нопедекемю пеьерйю оепеярюмнбнй; ясыеярбсер едхмярбеммюъ "яюлюъ мхгйюъ" оепеярюмнбйю, мюундъыюъяъ "мюд" дбслъ дюммшлх оепеярюмнбйюлх. Дхюцпюллю пеьерйх опх $n=4$ опедярюбкемю мю пхя. 1.] %% 34 \bye