\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{РТЕДЙУМПЧЙЕ ТЕДБЛФПТПЧ РЕТЕЧПДБ} Д. Ь. Лохф иптпып ъоблпн упчефулпнх юйфбфема рп ретечпдбн дчхи ретчщи фпнпч езп пвыйтопк нпопзтбжйй "Йулхууфчп ртпзтбннйтпчбойс дмс ЬЧН" й ое охцдбефус ч бффеуфбгйй. Обуфпсэбс лойзб ртедуфбчмсеф упвпк фтефйк фпн й рпучсэеоб бмзптйфнбн уптфйтпчлй й рпйулб йожптнбгйй. Йуфптйюеулй ъбтпцдеойе нефпдпч нбыйоопк уптфйтпчлй нпцоп пфоеуфй еэе л ртпымпнх уфпмефйа, й ъб уфпмш дмйфемшопе чтенс нопзйе урегйбмйуфщ хуремй йуртпвпчбфш учпй уймщ ч ьфпк пвмбуфй. Обрйубоп оенбмп пфюефпч, уфбфек, нпопзтбжйк. Й дбце ч ьфйи хумпчйси лойзб Д. Лохфб уфбмб упвщфйен. Рп ухэеуфчх ьфп ьогйлмпредйс, ч лпфптпк нпцоп обкфй мавха уртбчлх, лбубаэхаус бмзптйфнпч, нефпдпч йи пгеопл, йуфптйй чпртпуб й оетеыеоощи ртпвмен. Оеф охцдщ зпчптйфш п чбцопуфй убнпк пвмбуфй. Ртблфйюеулй уптфйтпчлб й рпйул ч фпк ймй йопк нете ртйухфуфчхаф чп чуеи ртймпцеойси; ч юбуфопуфй, ртй пвтбвпфле впмшыйи пвRенпч дбоощи ьжжелфйчопуфш йнеооп ьфйи претбгйк пртедемсеф ьжжелфйчопуфш, б йопздб й тбвпфпурпупвопуфш чуек уйуфенщ. Рпьфпнх, лбл уртбчедмйчп пфнеюбеф бчфпт, лойзб бдтеупчбоб ое фпмшлп уйуфенощн ртпзтбннйуфбн, ъбойнбаэйнус тбътбвпфлпк ртпзтбнн уптфйтпчлй й рпйулб йожптнбгйй. Нпцоп улбъбфш, юфп дпуфбфпюоп юефлйе ртедуфбчмеойс пв ьфпк пвмбуфй охцощ ртй теыеойй мавпк ъбдбюй об ЬЧН лбл пвсъбфемшоще ьменеофщ йулхууфчб ртпзтбннйтпчбойс. Лтпне фептефйюеулпк й ртблфйюеулпк геоопуфй, лойзб йнееф впмшыпе нефпдйюеулпе ъобюеойе. Нопзйе бчфптщ й ртерпдбчбфемй унпзхф йъчмеюш йъ оее опчще й рпмеъоще учедеойс ое фпмшлп рп ухэеуфчх тбуунбфтйчбенщи чпртпупч, оп й рп урпупвх йи йъмпцеойс. Бчфптх нбуфетулй хдбефус "тбуумпйфш" чеуш нбфетйбм фблйн пвтбъпн, юфп лойзх нпцоп йурпмшъпчбфш ртблфйюеулй об мавпн хтпчое ъоблпнуфчб у ртеднефпн й ртй тбъмйюопк пвэек нбфенбфйюеулпк рпдзпфпчмеоопуфй юйфбфемс. Ретечпд чщрпмоео рп йъдбойа 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 Пгеолб & ПвRсуоеойе \cr 00 & Ютеъчщюбкоп мезлпе хртбцоеойе, об лпфптпе нпцоп пфчефйфш утбъх це, еумй рпосф нбфетйбм фелуфб, й лпфптпе рпюфй чуездб нпцоп теыйфш "ч хне". \cr %% 10 10 & Ртпуфбс ъбдбюб, лпфптбс ъбуфбчмсеф ъбдхнбфшус обд ртпюйфбоощн нбфетйбмпн, оп ое ртедуфбчмсеф ойлблйи пупвщи фтхдопуфек. Об теыеойе фблпк ъбдбюй фтевхефус ое впмшые пдопк нйохфщ; ч ртпгеууе теыеойс нпзхф рпобдпвйфшус лбтбодбы й вхнбзб. \cr 20 & Ъбдбюб утедоек фтхдопуфй, рпъчпмсаэбс ртпчетйфш, обулпмшлп иптпып рпосф фелуф. Об фп юфпвщ дбфш йуюетрщчбаэйк пфчеф, фтевхефус ртйнетоп 15--20 нйохф.\cr 30 & Ъбдбюб хнетеоопк фтхдопуфй й/ймй умпцопуфй, дмс хдпчмефчптйфемшопзп теыеойс лпфптпк фтевхефус впмшые дчхи юбупч. \cr 40 & Пюеош фтхдобс ймй фтхдпенлбс ъбдбюб, лпфптха, четпсфоп, умедхеф члмаюйфш ч рмбо ртблфйюеулйи ъбосфйк. Ртедрпмбзбефус, юфп уфхдеоф нпцеф теыйфш фблха ъбдбюх, оп дмс ьфпзп енх рпфтевхефус ъобюйфемшощк пфтеъпл чтенеой; ъбдбюб теыбефус оефтйчйбмшощн пвтбъпн. \cr 50 & Йуумедпчбфемшулбс ртпвменб, лпфптбс (обулпмшлп ьфп вщмп йъчеуфоп бчфптх ч нпнеоф обрйубойс) еэе ое рпмхюймб хдпчмефчптйфемшопзп теыеойс. Еумй юйфбфемш обкдеф теыеойе ьфпк ъбдбюй, езп обуфпсфемшоп ртпусф прхвмйлпчбфш езп; лтпне фпзп, бчфпт дбоопк лойзй вхдеф пюеош ртйъобфемео, еумй енх уппвэбф теыеойе лбл нпцоп вщуфтее (ртй хумпчйй, юфп поп ртбчймшоп).\cr } Йофетрпмйтхс рп ьфпк "мпзбтйжнйюеулпк" ылбме, нпцоп ртйлйохфш, юфп пъобюбеф мавбс ртпнецхфпюобс пгеолб. Обртйнет, пгеолб 17 зпчптйф п фпн, юфп дбоопе хртбцоеойе юхфш мезюе, юен хртбцоеойе утедоек фтхдопуфй. Ъбдбюб у пгеолпк 50, еумй поб вхдеф теыеоб лблйн-мйвп юйфбфемен, ч умедхаэйи йъдбойси дбоопк лойзй нпцеф йнефш хце пгеолх 45. Бчфпт юеуфоп уфбтбмус дбчбфш пвRелфйчоще пгеолй, оп фпнх, лфп упуфбчмсеф ъбдбюй, фтхдоп ртедчйдефш, обулпмшлп фтхдощнй ьфй ъбдбюй плбцхфус дмс лпзп-фп дтхзпзп; л фпнх це х лбцдпзп юемпчелб ухэеуфчхеф пртедемеоощк фйр ъбдбю, лпфптще по теыбеф вщуфтее. Обдеауш, юфп чщуфбчмеооще нопк пгеолй дбаф ртбчймшопе ртедуфбчмеойе п уфереой фтхдопуфй ъбдбю, оп ч пвэен йи охцоп чпуртйойнбфш лбл птйеофйтпчпюоще, б ое бвупмафоще. Ьфб лойзб обрйубоб дмс юйфбфемек убнщи тбъощи уфереоек нбфенбфйюеулпк рпдзпфпчлй й йулхыеоопуфй, рпьфпнх оелпфптще хртбцоеойс ртедобъобюеощ фпмшлп дмс юйфбфемек у нбфенбфйюеулйн хлмпопн. Еумй ч лблпн-мйвп хртбцоеойй нбфенбфйюеулйе рпосфйс ймй теъхмшфбфщ йурпмшъхафус впмее ыйтплп, юен ьфп оепвипдйнп дмс феи, лпзп ч ретчха пюетедш йофетеухеф ртпзтбннйтпчбойе бмзптйфнпч, фп ретед пгеолпк фблпзп хртбцоеойс уфбчйфус вхлчб \rlq{}Н". Еумй дмс теыеойс хртбцоеойс фтевхефус ъобойе чщуыек нбфенбфйлй ч впмшыен пвRене, юен ьфп дбоп ч обуфпсэек %%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}$. Ьжжелфйчопуфша, лпфптбс нпцеф вщфш дпуфйзохфб ч ьфпк ртпгедхте, й пвRсуосефус йънеоеойе ретчпобюбмшопзп унщумб умпчб "уптфйтпчлб". \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) ртйнеосафус ч пуопчопн оеьжжелфйчоще бмзптйфнщ уптфйтпчлй. Рп-чйдйнпнх, лбцдпе йъ фтеи ртедрпмпцеойк упдетцйф дпма йуфйощ. Чп чуслпн умхюбе суоп, юфп уптфйтпчлб ъбумхцйчбеф уетшеъопзп йъхюеойс у фпюлй ътеойс ее ртблфйюеулпзп йурпмшъпчбойс. Оп дбце еумй вщ уптфйтпчлб вщмб рпюфй веурпмеъоб, обымбуш вщ нбууб дтхзйи ртйюйо ъбосфшус еа! Йъпвтефбфемшоще бмзптйфнщ уптфйтпчлй зпчптсф п фпн, юфп поб й убнб рп уеве йофетеуоб лбл пвRелф йуумедпчбойс. Ч ьфпк пвмбуфй ухэеуфчхеф нопцеуфчп хчмелбфемшощи оетеыеоощи ъбдбю обтсдх у чеушнб оенопзйнй хце теыеоощнй. Тбуунбфтйчбс чпртпу ч впмее ыйтплпн рмбое, нщ пвобтхцйн, юфп бмзптйфнщ уптфйтпчлй ртедуфбчмсаф упвпк йофетеуощк юбуфощк ртйнет фпзп, лбл умедхеф рпдипдйфш л теыеойа ртпвмен ртпзтбннйтпчбойс чппвэе. Нщ рпъоблпнйнус уп нопзйнй чбцощнй ртйогйрбнй нбойрхмйтпчбойс уп уфтхлфхтбнй дбоощи й ртпумедйн ъб ьчпмагйек тбъмйюощи нефпдпч уптфйтпчлй, ртйюен юйфбфема юбуфп вхдеф ртедпуфбчмсфшус чпънпцопуфш убнпнх "пфлтщчбфш" фе це йдей, лбл вхдфп вщ дп оезп ойлфп у рпдпвощнй ъбдбюбнй ое уфбмлйчбмус. Пвпвэеойе ьфйи юбуфощи нефпдпч рпъчпмйф обн ч ъобюйфемшопк уфереой пчмбдефш фенй урпупвбнй нщымеойс, лпфптще рпнпзхф упъдбчбфш дпвтпфоще бмзптйфнщ дмс теыеойс дтхзйи ртпвмен, учсъбоощи у ЬЧН. Нефпдщ уптфйтпчлй умхцбф чемйлпмеропк йммауфтбгйек йдек \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$ пвRелфпч; ч р. 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