\input style \chapno=5\subchno=3\chapnotrue \def\tape#1{{\hbox{\sl Кемрю~#1\/}}\quad} \subchap {БМЕЬМЪЪ ЯНПРХПНБЙЮ} %5.4 Опхькн бпелъ гюмърэяъ хмрепеямшлх гюдювюлх, бнгмхйючыхлх б рнл яксвюе, йнцдю вхякн янпрхпселшу гюохяеи опебшьюер на╝ел ашярпндеиярбсчыецн ноепюрхбмнцн гюонлхмючыецн сярпниярбю. Бмеьмъъ янпрхпнбйю б йнпме нркхвмю нр бмсрпеммеи (унръ б нанху яксвюъу менаундхлн пюяонкнфхрэ гюохях дюммнцн тюикю б месашбючыел онпъдйе), х на╝ъямъеряъ щрн рел, врн бпелъ днярсою й тюикюл мю бмеьмху мняхрекъу мюя феярнвюиьхл напюгнл кхлхрхпсер. Ярпсйрспю дюммшу днкфмю ашрэ рюйни, врнаш япюбмхрекэмн ледкеммше оепхтепхимше гюонлхмючыхе сярпниярбю (кемрш, дхяйх, аюпюаюмш х р.~д.) лнцкх яопюбхрэяъ я онрпеамнярълх юкцнпхрлю янпрхпнбйх. Онщрнлс анкэьхмярбн хгсвеммшу дн яху онп лернднб бмсрпеммеи янпрхпнбйх (бярюбйю, налем, бшанп) тюйрхвеяйх аеяонкегмн дкъ бмеьмеи янпрхпнбйх; менаундхлн пюяялнрперэ бяч опнакелс гюмнбн. Опедонкнфхл, мюопхлеп, врн опедмюгмювеммши дкъ янпрхпнбйх тюик янярнхр хг 5000~гюохяеи $R_1$ $R_2$~\dots{} $R_{5000}$ дкхмни он 20~якнб (унръ йкчвх~$K_i$ ме наъгюрекэмн рюйни дкхмш). Йюй ашрэ, еякх бн бмсрпеммеи оюлърх дюммни люьхмш онлеыюеряъ ндмнбпелеммн рнкэйн~1000 хг щрху гюохяеи? Япюгс мюопюьхбюеряъ рюйне пеьемхе: мювюрэ я янпрхпнбйх йюфднцн хг оърх ондтюикнб~$R_1$~\dots{} $R_{1000}$, $R_{1001}$~\dots{} $R_{2000}$,~\dots, $R_{4001}$~\dots{} $R_{5000}$ он нрдекэмнярх х гюрел якхрэ онксвеммше ондтюикш. Й явюярэч, якхъмхе ноепхпсер рнкэйн нвемэ опняршлх ярпсйрспюлх дюммшу, хлеммн кхмеимшлх яохяйюлх, опнирх йнрнпше лнфмн онякеднбюрекэмшл напюгнл, йюй ярейх хкх нвепедх. Онщрнлс дкъ якхъмхъ цндъряъ яюлше деьебше бмеьмхе гюонлхмючыхе сярпниярбю. Рнкэйн врн нохяюммши опнжеяя---бмсрпеммъъ янпрхпнбйю я онякедсчыхл "бмеьмхл якхъмхел"---беяэлю оноскъпем, х мюье хгсвемхе бмеьмеи янпрхпнбйх ябедеряъ б нямнбмнл й бюпхюжхъл мю щрс релс. Бнгпюярючыхе онякеднбюрекэмнярх гюохяеи, онксвюелше мю мювюкэмни тюге бмсрпеммеи янпрхпнбйх, б кхрепюрспе н янпрхпнбйе вюярн мюгшбючряъ \emph{жеонвйюлх;} щрю реплхмнкнцхъ днбнкэмн ьхпнйн пюяопнярпюмемю, мн, й янфюкемхч, нмю опнрхбнпевхр еые анкее пюяопнярпюмеммнлс хяонкэгнбюмхч реплхмю "жеонвйю" б дпсцху пюгдекюу бшвхякхрекэмни мюсйх, цде нм нгмювюер \emph{опнхгбнкэмсч} онякеднбюрекэмнярэ яхлбнкнб. Опх хгсвемхх оепеярю- %%296 мнбнй сфе ашкн дюмн бонкме ондундъыее мюгбюмхе дкъ сонпъднвеммшу яецлемрнб тюикю, йнрнпше лш днцнбнпхкхяэ мюгшбюрэ бнгпюярючыхлх нрпегйюлх хкх опнярн \emph{нрпегйюлх.} Б яннрберярбхх я щрхл асдел хяонкэгнбюрэ якнбн "нрпегйх" дкъ нангмювемхъ сонпъднвеммшу вюяреи тюикю. Рюйхл напюгнл, хяонкэгнбюмхе онмърхи "жеонвйх нрпегйнб" х "нрпегйх жеонвей" ме опхбедер мх й йюйхл меднпюгслемхъл. Пюяялнрпхл ямювюкю опнжеяя бмеьмеи янпрхпнбйх, хяонкэгсчыеи б йювеярбе бяонлнцюрекэмни оюлърх \emph{люцмхрмше кемрш.} Бепнърмн, опняреиьхл х мюханкее опхбкейюрекэмшл яонянанл якхъмхъ я опхлемемхел кемр яксфхр яаюкюмяхпнбюммне дбсуосребне якхъмхе, б нямнбе йнрнпнцн кефхр хдеъ, хяонкэгнбюбьюъяъ пюмее б юкцнпхрлюу~5.2.4N, S х~L. Б опнжеяяе якхъмхъ мюл онрпеасчряъ вершпе "пюанвхе кемрш". Мю опнръфемхх оепбни тюгш бнгпюярючыхе нрпегйх, онксвюелше опх бмсрпеммеи янпрхпнбйе, онлеыючряъ оннвепедмн мю кемрш~1 х~2 дн реу онп, онйю ме хявепоючряъ хяундмше дюммше. Гюрел кемрш~1 х~2 оепелюршбюел й мювюкс х якхбюел нрпегйх, мюундъыхеяъ мю щрху кемрюу, онксвюъ мнбше нрпегйх, бдбне дкхммее хяундмшу. Щрх мнбше нрпегйх гюохяшбючряъ он лепе ху тнплхпнбюмхъ оноепелеммн мю кемрш~3 х~4. (Еякх мю кемре~1 мю ндхм нрпегнй анкэье, вел мю кемре~2, рн опедонкюцюеряъ, врн кемрю~2 яндепфхр днонкмхрекэмши "тхйрхбмши" нрпегнй дкхмш~0.) Гюрел бяе кемрш оепелюршбючряъ й мювюкс х яндепфхлне кемр~3 х~4 якхбюеряъ б сдбнеммше он дкхме нрпегйх, гюохяшбюелше оннвепедмн мю кемрш~1 х~2. Опнжеяя опнднкфюеряъ (опх щрнл дкхмю нрпегйнб йюфдши пюг сдбюхбюеряъ) дн реу онп, онйю ме нярюмеряъ ндхм нрпегнй (ю хлеммн беяэ сонпъднвеммши тюик). Еякх оняке бмсрпеммеи янпрхпнбйх ашкн онксвемн $S$~нрпегйнб, опхвел~$2^{k-1}|RMAX|$, рн юкцнпхрл гюбепьем; б опнрхбмнл яксвюе сярюмнбхрэ~$|RC|\asg|RQ|$. \st[Бшбнд бепьхмш депебю.] (Яеивюя |Q|~сйюгшбюер мю "велохнмю", х~|RQ|---мнлеп ецн нрпегйю.) Еякх~$|RQ|\ne 0$, рн бшбеярх~$|RECORD|(|Q|)$ х сярюмнбхрэ~$|LASTKEY|\asg|KEY|(|Q|)$. \st[Ббнд мнбни гюохях.] Еякх бундмни тюик хявепоюм, сярюмнбхрэ~$|RQ|\asg|RMAX|+1$ х оепеирх й ьюцс~\stp{5}. Б опнрхбмнл яксвюе онлеярхрэ мнбсч гюохяэ хг бундмнцн тюикю б~$|RECORD|(|Q|)$. Еякх~$|KEY|(|Q|)<|LASTKEY|$ (р.~е.~щрю гюохяэ ме опхмюдкефхр рейсыелс нрпегйс), рн~$|RQ|\asg|RQ|+1$, х реоепэ, еякх~$|RQ|>|RMAX|$, сярюмнбхрэ~$|RMAX|\asg|RQ|$. %%308 \st[Ондцнрнбйю й хглемемхч.] (Яеивюя~|Q| сйюгшбюер мю мнбсч гюохяэ я мнлепнл нрпегйю~|RQ|.) Сярюмнбхрэ~$|T|\asg|FE|(|Q|)$. (|T|---оепелеммши сйюгюрекэ, йнрнпши асдер дбхцюрэяъ он депебс.) \st[Сярюмнбйю мнбнцн опнхцпюбьецн.] Еякх~$|RN|(|T|)<|RQ|$ хкх еякх~$|RN|(|T|)=|RQ|$ х~$|KEY|(|LOSER|(|T|))<|KEY|(|Q|)$. рн онлемърэ леярюлх $|LOSER|(|T|)\xchg |Q|$, $|RN|(|T|)\xchg |RQ|$. (Б оепелеммшу~|Q| х~|RQ| гюонлхмюеряъ рейсыхи онаедхрекэ х мнлеп ецн нрпегйю.) \st[Ядбхц ббепу.] Еякх~$|T|=|LOC|(X[1])$, рн бепмсрэяъ й ьюцс~\stp{2}, б опнрхбмнл яксвюе~$|T|\asg|FI|(|T|)$ х бепмсрэяъ й~\stp{6}. \algend Б юкцнпхрле~R цнбнпхряъ н ббнде х бшбнде гюохяеи он ндмни, рнцдю йюй опюйрхвеяйх нйюгшбюеряъ ксвье вхрюрэ х гюохяшбюрэ нрмняхрекэмн анкэьхе акнйх гюохяеи. Якеднбюрекэмн, мю яюлнл деке гю йскхяюлх опъвсряъ астепш ббндю х бшбндю; ху опхясрярбхе б оюлърх опхбндхр й слемэьемхч гмювемхъ~$P$. Щрн асдер онъямемн б о.~5.4.6. Щ.~X.~Тпщмд [{\sl JACM,\/} {bf 3} (1956), 154] опедкнфхк якедсчыее нанаыемхе лерндю бшанпю я гюлеыемхел. Б реу яксвюъу, йнцдю ббндхлши йкчв лемэье, вел~|LASTKEY| (рюй врн нм ме оноюдер б рейсыхи нрпегнй), мн анкэье хкх пюбем онякедмелс йкчвс, деиярбхрекэмн гюохяюммнлс мю кемрс (рюй врн ецн тюйрхвеяйх лнфмн ашкн аш онлеярхрэ б рейсыхи нрпегнй), бярюбкърэ щрнр йкчв бмсрпэ астепю бшбндю. Йпнле рнцн, мейнрнпше ЩБЛ слечр бшонкмърэ "времхе бпюгапня" х "гюохяэ ян яанпйни", р.~е.~ббндхрэ хмтнплюжхч бн бмсрпеммчч оюлърэ ме наъгюрекэмн б онякеднбюрекэмше ъвеийх, ю "бпюгапня" х бшбндхрэ ее, янахпюъ хг пюгмшу леяр. Щрн онгбнкъер янблеыюрэ оюлърэ дкъ астепнб я оюлърэч дкъ депебю бшанпю. \section *Опенапюгнбюмхе нрпегйнб я гюдепфйни. П.~Дф.~Дхмялнп [{\sl CACM,\/} {\bf 8} (1965), 48] опедкнфхк хмрепеямне сянбепьемярбнбюмхе бшанпю я гюлеыемхел, хяонкэгсчыее онмърхе, йнрнпне асдел мюгшбюрэ \dfn{яреоемэч ябнандш.} Йюй лш бхдекх, йюфдши акнй гюохяеи, мюундъыхияъ мю кемре б янярюбе нрпегйю, яндепфхр гюохях б месашбючыел онпъдйе, рюй врн оепбши щкелемр мюхлемэьхи, ю онякедмхи мюханкэьхи. Б нашвмнл опнжеяяе бшанпю я гюлеыемхел мюхлемэьхи щкелемр йюфднцн акнйю б мейнрнпнл нрпегйе бяецдю ме лемэье, вел мюханкэьхи щкелемр б опедшдсыел акнйе щрнцн нрпегйю; щрн яннрберярбсер "1~яреоемх ябнандш". Дхмялнп опедкнфхк някюахрэ щрн сякнбхе дн "$m$~яреоемеи ябнандш"; мнбне сякнбхе ме рпеасер, врнаш мюхлемэьхи щкелемр йюфднцн акнйю ашк ме лемэье, вел мюханкэьхи щкелемр опедшдсыецн акнйю, мн нм \emph{ме днкфем ашрэ лемэье, вел мюханкэьхе щкелемрш йюйху-рн $m$~опедшдсыху акнйнб рнцн фе нрпегйю.} Гюохях б нрдекэмнл акнйе сонпъднвемш, йюй х пюмее, мн яняедмхе акнйх ме наъгюмш ашрэ бгюхлмн сонпъднвеммшлх. %%309 Опедонкнфхл, мюопхлеп, врн акнйх яндепфюр рнкэйн он дбе гюохях; якедсчыюъ онякеднбюрекэмнярэ акнйнб ъбкъеряъ нрпегйнл я рпелъ яреоемълх ябнандш: $$ \vert 08\ 50 \vert 06\ 90 \vert 17\ 27 \vert 42\ 67 \vert 51\ 89 \vert \eqno (1) $$ Якедсчыхи акнй, йнрнпши лнфер ашрэ вюярэч щрнцн нрпегйю, днкфем мювхмюрэяъ я щкелемрю, ме лемэьецн, вел рперхи он онпъдйс щкелемр лмнфеярбю~$\set{50, 90, 27, 67, 89}$, явхрюъ нр мюханкэьецн, р.~е.\ ме лемэье~67. Онякеднбюрекэмнярэ~(1) ме ъбкъеряъ нрпегйнл я дбслъ яреоемълх ябнандш, рюй йюй 17~лемэье, вел~50 х~90. Нрпегнй я $m$~яреоемълх ябнандш б опнжеяяе времхъ б якедсчыеи тюге янпрхпнбйх лнфер ашрэ опенапюгнбюм рюйхл напюгнл, врн дкъ бяеу опюйрхвеяйху жекеи нм асдер нрпегйнл б нашвмнл ялшяке. Мювмел я времхъ оепбшу $m$~акнйнб б $m$~астепнб х асдел опнхгбндхрэ $m\hbox{-осребне}$ якхъмхе ху; йнцдю ндхм хг астепнб хявепоюеряъ, онлеярхл б мецн $(m+1)\hbox{-и}$~акнй х~р.~д. Рюйхл напюгнл, лш лнфел бняярюмнбхрэ нрпегнй б бхде ндмни сонпъднвеммни онякеднбюрекэмнярх, рюй йюй оепбне якнбн йюфднцн бмнбэ явхршбюелнцн акнйю днкфмн ашрэ анкэье хкх пюбмн онякедмелс якнбс рнкэйн врн хявепоюммнцн акнйю (еякх нмн ме ашкн лемэье, вел мюханкэьхе щкелемрш йюйху-кхан $m$~акнйнб, опедьеярбсчыху елс). Щрнр лернд опенапюгнбюмхъ нрпегйю, б ясымнярх, ъбкъеряъ $m\hbox{-осребшл}$ якхъмхел, хяонкэгсчыхл рнкэйн ндмн кемрнвмне сярпниярбн дкъ бяеу бундмшу акнйнб! Опнжедспю опенапюгнбюмхъ деиярбсер йюй янопнцпюллю, й йнрнпни напюыючряъ йюфдши пюг, йнцдю мсфмн онксвхрэ ндмс нвепедмсч гюохяэ нрпегйю. Лш лнфел опенапюгнбшбюрэ пюгкхвмше нрпегйх я пюгкхвмшу кемрнвмшу сярпниярб х я пюгкхвмшлх яреоемълх ябнандш х якхбюрэ онксвючыхеяъ нрпегйх---бяе б ндмн х рн фе бпелъ. Щрн, он ясыеярбс, онднамн рнлс, йюй еякх аш лш вершпеуосребне якхъмхе, пюяялнрпеммне б мювюке щрнцн осмйрю, опедярюбхкх яеае йюй меяйнкэйн дбсуосребшу якхъмхи, опнхяундъыху ндмнбпелеммн. Щрю нярпнслмюъ хдеъ дн яху онп ме опнюмюкхгхпнбюмю дн йнмжю. Хлечряъ мейнрнпше опедбюпхрекэмше пегскэрюрш, онйюгшбючыхе, врн, йнцдю $P$~бекхйн он япюбмемхч я пюглепнл акнйю, дкхмю нрпегйю опх~$m=2$ опхакхгхрекэмн пюбмю~$2.1P$, нмю пюбмю~$2.3P$ опх~$m=4$ х~$2.5P$ опх~$m=8$. Рюйне сбекхвемхе, ашрэ лнфер, меднярюрнвмн, врнаш нопюбдюрэ сякнфмемхе юкцнпхрлю. Я дпсцни ярнпнмш, лернд лнфер нйюгюрэяъ бшцндмшл, еякх мю. опнръфемхх брнпнцн щрюою янпрхпнбйх еярэ леярн дкъ днбнкэмн анкэьнцн вхякю астепнб. %%310 \section *Мюрспюкэмши бшанп. Дпсцни осрэ сбекхвемхъ дкхмш нрпегйнб, онпнфдюелшу бшанпнл я гюлеыемхел, ашк хяякеднбюм С.~Д.~Тпщигепнл х~В.~Й.~Снмнл. Ху хдеъ янярнхр б рнл, врнаш якеднбюрэ юкцнпхрлс~R, мн, йнцдю мю ьюце~R4 $|KEY|(|Q|)<|LASTKEY|$, мнбюъ гюохяэ~$|RECORD|(|Q|)$ ме нярюеряъ б депебе,, ю бшбндхряъ б мейнрнпши бмеьмхи \emph{пегепбсюп} х вхрюеряъ мнбюъ гюохяэ. Щрнр опнжеяя опнднкфюеряъ дн реу онп, онйю б пегепбсюпе ме нйюферяъ нопедекеммне йнкхвеярбн гюохяеи~$P'$; рнцдю нярюрнй рейсыецн нрпегйю бшбндхряъ хг депебю, х щкелемрш пегепбсюпю хяонкэгсчряъ б йювеярбе хяундмшу дюммшу дкъ якедсчыецн нрпегйю. Щрнр лернд днкфем онпнфдюрэ анкее дкхммше нрпегйх, вел бшанп я гюлеыемхел, оняйнкэйс нм "наундхр" бмнбэ онярсоючыхе "лепрбше" гюохях, блеярн рнцн врнаш онгбнкърэ хл гюонкмърэ депебн; мн елс рпеасеряъ днонкмхрекэмне бпелъ мю налем я пегепбсюпнл. Йнцдю~$P'>P$, мейнрнпше гюохях лнцср нйюгшбюрэяъ б пегепбсюпе дбюфдш, мн опх~$P'\le P$ рюйнцн яксвхрэяъ ме лнфер. Тпщигеп х~Снм, опнбедъ наьхпмше щлохпхвеяйхе хяошрюмхъ ябнецн лерндю, гюлерхкх, врн, йнцдю~$P$ днярюрнвмн бекхйн (яйюфел, $P\ge 32$) х~$P'=P$, япедмъъ дкхмю нрпегйю дкъ яксвюимшу дюммшу нйюгшбюеряъ пюбмни~$eP$, цде~$e\approx 2.718$---нямнбюмхе мюрспюкэмшу кнцюпхтлнб. Щрн ъбкемхе, ю рюйфе рнр тюйр, врн лернд ашк онксвем йюй щбнкчжхнммне пюгбхрхе опнярнцн бшанпю я гюлеыемхел, оняксфхкх дкъ мху меоняпедярбеммшл нямнбюмхел мюгбюрэ ябни лернд \dfn{мюрспюкэмшл бшанпнл.} Лнфмн днйюгюрэ "мюрспюкэмши" гюйнм дкъ дкхмш нрпегйю, бмнбэ бняонкэгнбюбьхяэ юмюкнцхеи ян ямецннвхярхрекел мю пхя.~64 х опхлемхб щкелемрюпмши люрелюрхвеяйхи юмюкхг. Осярэ~$L$ нангмювюер дкхмс осрх, a~$x(t)$---онкнфемхе ямецннвхярхрекъ б лнлемр~$t$ опх~$0 \le t \le T$. Опедонкнфхл, врн б лнлемр~$T$ пегепбсюп гюонкмъеряъ; б щрнр лнлемр оюдемхе ямецю бпелеммн опейпюыюеряъ, онйю ямецннвхярхрекэ бнгбпюыюеряъ б хяундмне онкнфемхе (явхыюъ $P$~ямефхмнй, нярюбьхуяъ мю ецн осрх). Яхрсюжхъ рюйюъ фе, йюй х пюмее, рнкэйн "сякнбхъ пюбмнбеяхъ" дпсцхе---блеярн $P$~ямефхмнй мю бяеи днпнце б кчани лнлемр бпелемх лш хлеел $P$~ямефхмнй оепед ямецннвхярхрекел х пегепбсюп (гю ямецннвхярхрекел), гюонкмъчыхияъ дн спнбмъ б $P$~ямефхмнй. Б ревемхе хмрепбюкю бпелемх~$dt$ ямецннвхярхрекэ опндбхцюеряъ мю~$dx$, еякх бшбндъряъ $h(x, t)dx$~гюохяеи, цде~$h(x, t)$---рнкыхмю якнъ ямецю б лнлемр бпелемх~$t$ б рнвйе~$x=x(t)$, хглепъелюъ б яннрберярбсчыху едхмхжюу; якеднбюрекэмн, $h(x, t)=h(x, 0)+Kt$ дкъ бяеу~$x$. Рюй йюй вхякн гюохяеи б оюлърх нярюеряъ онярнъммшл, рн $h(x, t)dx$~еярэ рюйфе вхякн гюохяеи, ббндхлшу \emph{оепед} ямецннвхярхрекел, ю хлеммн~$Kdt(L-x)$, цде~$K$---яйнпнярэ оюдемхъ ямецю (пхя.~67). Рюйхл напюгнл, $$ {dx\over dt}={K(L-x)\over h(x,t)}. \eqno(2) $$ %%311 Й явюярэч, нйюгшбюеряъ, врн~$h(x,t)$---йнмярюмрю, х нмю пюбмю~$KT$ опх бяеу~$x=x(t)$ х~$0\le t \le T$, рюй йюй ямец оюдюер пюбмнлепмн б рнвйс~$x(t)$ б ревемхе $T-t$~едхмхж бпелемх оняке рнцн, йюй ямецннвхярхрекэ опнундхр щрс рнвйс, окчя $t$~едхмхж бпелемх оепед рел, йюй нм бепмеряъ. Хмшлх якнбюлх, ямецннвхярхрекэ бхдхр оепед янани бяе бпелъ ндхмюйнбши якни ямецю мю опнръфемхх бяецн осрх, еякх дносярхрэ, врн днярхцмср сярюмнбхбьхияъ пефхл, йнцдю щрнр осрэ бяе бпелъ ндхм х рнр фе. Якеднбюрекэмн, наыее йнкхвеярбн явхыюелнцн ямецю (дкхмю нрпегйю) еярэ~$KTL$, \picture{Пхя.~67. Ббндхряъ х бшбндхряъ пюбмне йнкхвеярбн ямецю; гю бпелъ~$dt$ ямецннвхярхрекэ оепелеыюеряъ мю~$dx$.} ю йнкхвеярбн ямецю б оюлърх еярэ йнкхвеярбн ямецю, явхыюелнцн оняке лнлемрю~$T$, ю хлеммн~$KT(L-x(T))$. Пеьемхел спюбмемхъ~(2) опх сякнбхх, врн~$x(0)=0$, асдер $$ x(t)=L(1-e^{-t/T}). \eqno(3) $$ Якеднбюрекэмн, $P=KTLe^{-1}=\hbox{(дкхмю нрпегйю)}/e$---щрн йюй пюг рн, врн лш х унрекх днйюгюрэ. Б соп.~21--23 онйюгюмн, врн щрнр юмюкхг лнфмн пюяопнярпюмхрэ мю яксвюи опнхгбнкэмнцн~$P'$; мюопхлеп, йнцдю~$P'=2P$, япедмъъ дкхмю нрпегйю нйюгшбюеряъ пюбмни~$e^\theta(e-\theta)P$, цде~$\theta={1\over2}(e-\sqrt{e^2-4})$,---пегскэрюр, йнрнпши бпъд кх лнфмн ашкн опедонкнфхрэ гюпюмее! Б рюак.~2 опхбндхряъ гюбхяхлнярэ лефдс дкхмни нрпегйю х пюглепнл пегепбсюпю; я онлныэч щрни рюакхжш лнфмн нжемхрэ онкегмнярэ мюрспюкэмнцн бшанпю дкъ йнмйпермни люьхмш б рни хкх хмни яхрсюжхх. \section *Юмюкхг бшанпю я гюлеыемхел. Бепмеляъ реоепэ й яксвюч бшанпю я гюлеыемхел аег бяонлнцюрекэмнцн пегепбсюпю. Юмюкнцхъ ян ямецннвхярхрекел дюер днбнкэмн унпньсч нжемйс япедмеи дкхмш нрпегйнб, онксвюелшу опх бшанпе я гюлеыемхел "б опедеке", рел ме лемее лнфмн онксвхрэ гмювхрекэмн анкее рнвмсч хмтнплюжхч на юкцнпхрле~R, опхлемъъ тюйрш на нрпегйюу б оепеярюмнбйюу, хгсвеммшу мюлх б о.~5.1.3. Дкъ сднаярбю асдел явхрюрэ, врн бундмни тюик ъбкъеряъ онякеднбюрекэмнярэч (опнхгбнкэмни дкхмш) мегюбхяхлшу яксвюимшу деиярбхрекэмшу вхяек, пюяонкнфеммшу лефдс~0 х~1. %%312 \htable{Рюакхжю 2}% {Дкхмю нрпегйнб опх мюрспюкэмнл бшанпе}% {\strut\hfill$#$\bskip&\bskip\hfill$#$\bskip&\bskip\hfill$#$\bskip& \hfill$\qquad#$\bskip&\bskip\hfill$#$\bskip&\bskip\hfill$#$\cr \omit\hfill Пюглеп \hfill & \omit\hfill Дкхмю\hfill & & \omit\hfill Пюглеп \hfill & Дкхмю \hfill\cr \omit\hfill пегепбсюпю \hfill & \omit\hfill нрпегйю\hfill &\omit\hfill Оюпюлерп\hfill &\omit\hfill пегепбсюпю \hfill & \omit\hfill нрпегйю\hfill & \omit\hfill Оюпюлерп\hfill \cr \noalign{\hrule} 1.00000P & 2.71828P & 1.00000 & 0.38629P & 2.00000P & 0.69315\cr 2.00000P & 3.53487P & 1.43867 & 1.30432P & 3.НННННP & 1.15881\cr 3.00000P & 4.16220P & 1.74773 & 2.72294P & 4.00000P & 1.66862\cr 4.00000P & 4.69445P & 2.01212 & 4.63853P & 5.00000P & 2.16714\cr 5.00000P & 5.16369P & 2.24038 & 21.72222P & 10.00000P & 4.66667\cr 10.00000P& 7.00877P & 3.17122 & 5.29143P & 5.29143P & 2.31329\cr \noalign{\hrule} \noalign{\hbox{\strut "Оюпюлерп"~$k+\theta$ нопедекем б соп.~22}} } Осярэ $$ g_P(z_1, z_2,~\ldots, z_k)=\sum_{l_1, l_2,~\ldots, l_k\ge 0} a_P(l_1, l_2,~\ldots, l_k)z_1^{l_1} z_2^{l_2}\ldots z_k^{l_k} $$ ---опнхгбндъыюъ тсмйжхъ дкъ дкхмш нрпегйю, онксвеммнцн опх $P\hbox{-осребнл}$~бшанпе я гюлеыемхел, опхлемеммнл й. рюйнлс тюикс, цде $a_P(l_1, l_2,~\ldots, l_k)$~еярэ бепнърмнярэ рнцн, врн оепбши нрпегнй хлеер дкхмс~$l_1$, брнпни---дкхмс~$l_2$,~\dots, $k\hbox{-и}$ хлеер дкхмс~$l_k$. Асдел нямнбшбюрэяъ мю якедсчыеи "ренпеле мегюбхяхлнярх", Рюй йюй нмю ябндхр мюь юмюкхг й яксвюч~$P=1$. \proclaim Ренпелю~K. $g_P(z_1, z_2,~\ldots, z_k)=g_1(z_1, z_2,~\ldots, z_k)^P$. \proof Осярэ хяундмше йкчвх ясрэ~$X_1$, $X_2$, $X_3$,~$\ldots\, $. Юкцнпхрл~R пюгдекъер ху мю $P$~ондонякеднбюрекэмняреи б яннрберярбхх я рел, б йюйни бмеьмхи сгек депебю нмх оноюдючр; ондонякеднбюрекэмнярэ, яндепфюыюъ~$X_n$, нопедекъеряъ гмювемхълх~$X_1$, ~\dots, $X_{n-1}$. Рюйхл напюгнл, щрх ондонякеднбюрекэмнярх ъбкъчряъ мегюбхяхлшлх онякеднбюрекэмнярълх мегюбхяхлшу яксвюимшу вхяек, пюяонкнфеммшу лефдс~0 х~1. Йпнле рнцн, бшунд бшанпю я гюлеыемхел б рнвмнярх янбоюдюер я пегскэрюрнл $P\hbox{-осребнцн}$ якхъмхъ, еякх ецн опнхгбеярх мюд щрхлх ондонякеднбюрекэмнярълх; мейнрнпши щкелемр опхмюдкефхр $j\hbox{-лс}$~нрпегйс ондонякеднбюрекэмнярх рнцдю х рнкэйн рнцдю, йнцдю нм опхмюдкефхр $j\hbox{-лс}$~нрпегйс, онксвеммнлс опх бшанпе я гюлеыемхел (рюй йюй мю ьюце~R4 йкчвх~|LASTKEY| х~$|KEY|(|Q|)$ опхмюдкефюр ндмни ондонякеднбюрекэмнярх). Хмюве цнбнпъ, лнфмн явхрюрэ, врн юкцнпхрл~R опхлемъеряъ й $P$~яксвюимшл мегюбхяхлшл хяундмшл тюикюл х врн ьюц~R4 вхрюер якедсчысч гюохяэ хг тюикю, яннрберярбсчыецн бмеьмелс сгкс~|Q|; б щрнл ялшяке пюяялюрпхбюелши юкцнпхрл щйбхбюкемрем $P\hbox{-осребнлс}$ якхъмхч, цде йнмжш нрпегйнб нрлевючряъ сашбюмхел щкелемрнб. Рюйхл напюгнл, мю бшунде асдср нрпегйх дкхм~$(l_1,~\ldots, l_k)$ рнцдю х рнкэйн рнцдю, йнцдю ондонякеднбюрекэмнярх янярнър хг %% 313 нрпегйнб дкхм~$(l_{11},~\ldots, l_{1k})$,~\dots, $(l_{P1},~\ldots, l_{Pk})$ яннрберярбеммн; цде~$l_{ij}$---мейнрнпше менрпхжюрекэмше жекше вхякю, сднбкербнпъчыхе яннрмньемхч~$\sum_{1\le i \le P} l_{ij}=l_j$ опх~$1\le j \le k$. Нрячдю якедсер, врн $$ a_P(l_1,~\ldots, l_k)=\sum_{ {\scriptstyle l_{11}+\cdots+l_{P1}=l_1 \atop \scriptstyle \vdots} \atop \scriptstyle l_{1k}+\cdots+l_{Pk}=l_k }a_1(l_{11},~\ldots, l_{1k})\ldots a_1(l_{P1},~\ldots, l_{Pk}), $$ врн щйбхбюкемрмн хяйнлнлс пегскэрюрс. \proofend Б о.~5.1.3 лш хгсвхкх япедмее гмювемхе~$L_k$---дкхмш $k\hbox{-цн}$~нрпегйю опх~$P=1$ (щрх гмювемхъ опхбедемш б рюак.~5.1.3-2). Хг ренпелш~K якедсер, врн япедмъъ дкхмю $k\hbox{-цн}$~нрпегйю опх кчанл~$P$ б $P$~пюг анкэье япедмеи дкхмш опх~$P=1$, нмю пюбмю~$L_kP$; дхяоепяхъ рюйфе б $P$~пюг анкэье, рюй врн ярюмдюпрмне нрйкнмемхе дкхмш нрпегйю опнонпжхнмюкэмн~$\sqrt{P}$. Щрх пегскэрюрш ашкх боепбше онксвемш А.~Дф.~Цщяямеп нйнкн 1958~ц. Рюйхл напюгнл, оепбши нрпегнй, онксвеммши дкъ яксвюимшу дюммшу юкцнпхрлнл~R, асдер хлерэ дкхмс, опхакхфеммн пюбмсч $(e-1)P\approx 1.718P$~гюохяеи, брнпни---опхакхфеммн~$(e^2-2e)P\approx 1.952P$, рперхи---$1.996P$; дкхмю якедсчыху нрпегйнб асдер нвемэ акхгйю й~$2P$, онйю лш ме днидел дн онякедмху дбсу нрпегйнб (ял. соп.~14). Ярюмдюпрмне нрйкнмемхе дкхмш анкэьхмярбю щрху нрпегйнб опхакхфеммн пюбмн~$\sqrt{(4e-10)P}\approx 0.934 \sqrt{P}$ [{\sl CACM,\/} {\bf 6} (1963), 685--687]. Йпнле щрнцн, янцкюямн соп.~5.1.3-10, \emph{ясллюпмюъ} дкхмю оепбшу $k$~нрпегйнб асдер днбнкэмн акхгйю й~$\left(2k-{1\over3}\right)P$ ян ярюмдюпрмшл нрйкнмемхел~$\left(\left({2\over3}k+{2\over9}\right)P\right)^{1/2}$. Опнхгбндъыхе тсмйжхх~$g_1(z, z,~\ldots, z)$ х~$g_1(1,~\ldots, 1, z)$ бшбндъряъ б соп.~5.1.3-9 х~11. Б опхбедеммнл бшье юмюкхге опедонкюцюкняэ, врн хяундмши тюик аеяйнмевмн дкхммши, мн днйюгюрекэярбн ренпелш~K онйюгшбюер, врн рнвмн рюйюъ фе бепнърмнярэ~$a_P(l_1,~\ldots, l_k)$ онксвхкюяэ аш б яксвюе кчани яксвюимни хяундмни онякеднбюрекэмнярх, яндепфюыеи он йпюимеи лепе $l_1+\cdots+l_k+P$~щкелемрнб. Якеднбюрекэмн, онксвеммше пегскэрюрш опхлемхлш дкъ тюикю пюглепю, яйюфел, $N > (2K+1)P$ б яхкс люкни бекхвхмш ярюмдюпрмнцн нрйкнмемхъ. Лш онгмюйнлхляъ я пъднл опхлемемхи, б йнрнпшу яуелю якхъмхъ рпеасер, врнаш мейнрнпше нрпегйх ашкх бнгпюярючыхлх, ю мейнрнпше---сашбючыхлх. Оняйнкэйс нярюрнй, мюйюокхбючыхияъ б оюлърх с йнмжю бнгпюярючыецн нрпегйю, хлеер ремдемжхч яндепфюрэ вхякю, б япедмел лемэьхе, вел яксвюимше дюммше, рн хглемемхе мюопюбкемхъ сонпъднвемхъ слемэьюер япедмчч дкхмс нрпегйнб. Пюяялнрпхл, мюопхлеп, ямецннвхярхрекэ, йнрнпши днкфем %%314 бшонкмърэ пюгбнпнр йюфдши пюг, йюй нм днярхцюер йнмжю опълни днпнцх; нм асдер нвемэ ашярпн оепедбхцюрэяъ он рнкэйн врн нвхыеммнлс свюярйс. Б яксвюе хглемъелнцн мюопюбкемхъ дкхмю нрпегйнб дкъ яксвюимшу дюммшу хглемъеряъ лефдс~$1.5P$ х~$2P$ (ял.~соп.~24). \excercises \ex[10] Йюйхл асдер ьюц 4 б опхлепе вершпеу осребнцн якхъмхъ б мювюке щрнцн осмйрю? \ex[12] Йюйхе хглемемхъ опнхгнькх аш б депебе пхя.~63, еякх аш йкчв~$061$ ашк гюлемем йкчвнл~$612$? \ex[16] (Щ.~Т.~Лсп.) Врн онксвхряъ б пегскэрюре опхлемемхъ вершпеуосребнцн бшанпю я гюлеыемхел й онякеднбюрекэмшл якнбюл якедсчыецн опедкнфемхъ\note{1}% {Бняелэдеяър яелэ кер рнлс мюгюд мюьх опедйх нямнбюкх мю щрнл йнмрхмемре мнбсч мюжхч, онябърхбьсч яеаъ декс ябнандш х саефдеммсч б рнл, врн бяе кчдх янгдюмш пюбмшлх.---{\sl Опхл. оепеб.\/}} {\medskip\narrower\tt\noindent fourscore and seven years ago our fathers brought forth on this continent a new nation conceived in liberty and dedicated to the proposition that all men are created equal. \medskip\noindent} (Хяонкэгсире нашвмши юктюбхрмши онпъднй, пюяялюрпхбюъ йюфдне якнбн йюй ндхм йкчв.) \ex[16] Опхлемхре вершпеуосребни \emph{мюрспюкэмши} бшанп й опедкнфемхч хг соп.~3, хяонкэгсъ пегепбсюп елйнярх~4. \ex[00] Бепмн кх, врн бшанп я гюлеыемхел, хяонкэгсчыхи депебн, пюанрюер, рнкэйн еякх $P$~еярэ яреоемэ дбнийх хкх ясллю дбсу яреоемеи дбнийх? \ex[15] Б юкцнпхрле~R сйюгшбюеряъ, врн $P$~днкфмн ашрэ~$\ge2$; йюйхе нрмняхрекэмн меанкэьхе хглемемхъ мюдн ядекюрэ б щрнл юкцнпхрле, врнаш нм опюбхкэмн пюанрюк дкъ бяеу~$P\ge 1$? \ex[17] Врн декюер юкцнпхрл~R б яксвюе нрясрярбхъ хяундмни хмтнплюжхх? \ex[20] Юкцнпхрл~R хяонкэгсер хяйсяярбеммши йкчв~"$\infty$", йнрнпши днкфем ашрэ анкэье кчанцн бнглнфмнцн йкчвю. Онйюфхре, врн еякх аш йюйни-мхасдэ пеюкэмши йкчв нйюгюкяъ пюбмшл~$\infty$, рн юкцнпхрл лнц аш ньхахрэяъ, х на╝ъямхре, йюй хглемхрэ юкцнпхрл б яксвюе, йнцдю пеюкхгюжхъ "мюярнъыеи" аеяйнмевмнярх месднамю. \rex[23] Йюй бш хглемхкх аш юкцнпхрл~R, врнаш нм бшбндхк мейнрнпше гюдюммше нрпегйх (нопедекъелше~|RC|) б бнгпюярючыел онпъдйе, ю дпсцхе б сашбючыел? \ex[26] Мювюкэмюъ сярюмнбйю сйюгюрекеи~|LOSER| мю ьюце~R1 нашвмн ме яннрберярбсер мхйюйнлс деиярбхрекэмнлс рспмхпс, рюй йюй бмеьмхи сгек~$P+j$ лнфер ме кефюрэ б онддепебе я бепьхмни бн бмсрпеммел сгке~$j$. На╝ъямхре, онвелс юкцнпхрл~R бяе пюбмн пюанрюер. [\emph{Сйюгюмхе.} Асдер кх пюанрюрэ юкцнпхрл~R, еякх лмнфеярбс~$\set{|LOSER|(|LOC| (X[0])),~\ldots, |LOSER|(|LOC| (X[P-1]))}$ опхябюхбюеряъ мю ьюце~R1 \emph{опнхгбнкэмюъ} оепеярюмнбйю лмнфеярбю~$\set{|LOC|(X[0]),~\ldots, |LOC|(X[P-1])}$?] \ex[Л25] Бепмн кх, врн дкъ яксвюимшу хяундмшу дюммшу бепнърмнярэ рнцн, врн~$|KEY|(|Q|)<|LASTKEY|$ мю ьюце~R4, опхакхфеммн пюбмю~1/2? \ex[M46] Опнбедхре дерюкэмне хяякеднбюмхе рнцн, яйнкэйн пюг бшонкмъеряъ йюфдюъ вюярэ юкцнпхрлю~R; мюопхлеп, йюй вюярн бшонкмъеряъ оепеярюмнбйю мю ьюце~R6? %%315 \ex[13] Онвелс брнпни нрпегнй, онксвеммши опх бшанпе я гюлеыемхел, нашвмн дкхммее оепбнцн? \rex[БЛ25] Хяонкэгсире юмюкнцхч ян ямецннвхярхрекел, врнаш нжемхрэ япедмчч дкхмс дбсу \emph{онякедмху} нрпегйнб, онксвеммшу опх бшанпе я гюлеыемхел, опхлемеммнл й дкхммни онякеднбюрекэмнярх хяундмшу дюммшу. \ex[20] Бепмн кх, врн онякедмхи нрпегнй, онксвеммши опх бшанпе я гюлеыемхел, мхйнцдю ме яндепфхр анкее $P$~гюохяеи? Наясдхре бюь нрбер. \ex[Л26] Мюидхре "опнярне" менаундхлне х днярюрнвмне сякнбхе рнцн, врн тюик~$R_1$~$R_2$~\dots{} $R_N$ асдер онкмнярэч сонпъднвем гю ндхм опнунд $P\hbox{-осребнцн}$ бшанпю я гюлеыемхел. Йюйнбю бепнърмнярэ щрнцн янашрхъ йюй тсмйжхъ~$P$ х~$N$, еякх хяундмшлх дюммшлх яксфхр яксвюимюъ оепеярюмнбйю лмнфеярбю~$\set{1, 2,~\ldots, N}$? \ex[20] Врн онксвюеряъ б пегскэрюре пюанрш юкцнпхрлю~R, йнцдю хяундмше йкчвх опедярюбкъчр янани мебнгпюярючысч онякеднбюрекэмнярэ~$K_1\ge K_2\ge\ldots\ge K_N$? \rex[22] Врн опнхгнидер, еякх бмнбэ опхлемхрэ юкцнпхрл~R й тюикс, онксвеммнлс б пегскэрюре пюанрш юкцнпхрлю~R? \ex[БЛ22] Хяонкэгсире юмюкнцхч ян ямецннвхярхрекел, врнаш днйюгюрэ, врн оепбши нрпегнй, онксвеммши опх бшанпе я гюлеыемхел, хлеер дкхмс опхлепмн $(e-1)P$~гюохяеи. \ex[БЛ24] Йюйсч опхлепмн дкхмс хлеер оепбши нрпегнй, онксвеммши опх мюрспюкэмнл бшанпе, йнцдю~$P=P'$? \rex[БЛ23] Нопедекхре опхакхгхрекэмсч дкхмс нрпегйнб, онксвеммшу оняпедярбнл мюрспюкэмнцн бшанпю опх~$P'P$. Осярэ~$\kappa=k+\theta$---деиярбхрекэмне вхякн~$\ge 1$, цде~$k=\floor{\kappa}$, ю~$\theta=\kappa \bmod 1$, х пюяялнрпхл тсмйжхч~$F(\kappa)=F_k(\theta)$, цде~$F_k(\theta)$---онкхмнлш, нопедекъелше опнхгбндъыеи тсмйжхеи $$ \sum_{k\ge0} F_k(\theta)z^k=e^{-\theta z}/(1-z e^{1-z}). $$ Рюйхл напюгнл, $F_0(\theta)=1$, $F_1(\theta)=e-\theta$, $F_2(\theta)=e^2-e-e\theta+{1\over2}\theta^2$ х~р.~д. Опедонкнфхл, врн б лнлемр~$t=0$ ямецннвхярхрекэ мювхмюер лндекхпнбюрэ опнжеяя мюрспюкэмнцн бшанпю, х дносярхл, врн гю $T$~едхмхж бпелемх онгюдх мецн союдср пнбмн $P$~ямефхмнй. Б щрнр лнлемр брнпни ямецннвхярхрекэ мювхмюер рнр фе осрэ, гюмхлюъ б лнлемр бпелемх~$t+T$ рн фе онкнфемхе, врн гюмхлюк оепбши ямецннвхярхрекэ б лнлемр~$t$. Б йнмже йнмжнб, й лнлемрс~$\kappa T$ онгюдх оепбнцн ямецннвхярхрекъ союдср пнбмн $P'$~ямефхмнй; нм лцмнбеммн нвхыюер нярюрнй днпнцх х хявегюер. Хяонкэгсъ щрс лндекэ дкъ хмрепоперюжхх мюрспюкэмнцн бшанпю, онйюфхре, врн дкхмю нрпегйю~$e^\theta F(\kappa) P$ онксвюеряъ опх $$ P'/P=k+1+e^\theta\left(\kappa F(\kappa)-\sum_{0\le j \le \kappa}F(\kappa-j)\right). $$ \ex[БЛ35] Опедшдсыее сопюфмемхе юмюкхгхпсер мюрспюкэмши бшанп б рнл яксвюе, йнцдю гюохях хг пегепбсюпю бяецдю вхрючряъ б рнл фе онпъдйе, б йнрнпнл нмх гюохяшбюкхяэ: "оепбшл бйкчвюеряъ---оепбшл хяйкчвюеряъ". Нжемхре дкхмс нрпегйнб, йнрнпюъ онксвхкюяэ аш, еякх аш яндепфхлне пегепбсюпю, нярюбьееяъ нр опедшдсыецн нрпегйю, вхрюкняэ б янбепьеммн \emph{яксвюимнл} онпъдйе, йюй еякх аш гюохях б пегепбсюпе рыюрекэмн оепелеьхбюкхяэ лефдс нрпегйюлх. \ex[БЛ39] Жекэ щрнцн сопюфмемхъ---юмюкхг онякедярбхи, бшгбюммшу яксвюимшл хглемемхел мюопюбкемхъ сонпъднвемхъ нрпегйнб б бшанпе я гюлеыемхел. %%316 \medskip \item{a)}~Осярэ~$g_P(z_1, z_2,~\ldots, z_k)$---рю фе опнхгбндъыюъ тсмйжхъ, врн х б ренпеле~K, мн дкъ йюфднцн хг $k$~нрпегйнб нопедекемн, ъбкъеряъ кх нм бнгпюярючыхл хкх сашбючыхл. Мюопхлеп, лш лнфел явхрюрэ, врн бяе нрпегйх я мевермшлх мнлепюлх бнгпюярючыхе, ю я вермшлх сашбючыхе Онйюфхре, врн ренпелю~K яопюбедкхбю дкъ йюфдни хг $2^k$~опнхгбндъыху тсмйжхи рюйнцн бхдю. \item{b)}~Б яхкс~(a) лнфмн явхрюрэ~$P=1$. Лнфмн рюйфе опедонкнфхрэ, врн хяундмни ъбкъеряъ пюбмнлепмн пюяопедекеммюъ онякеднбюрекэмнярэ мегюбхяхлшу яксвюимшу бекхвхм, гюйкчвеммшу лефдс~0 х~1 Осярэ $$ a(x,y)=\cases{ e^{1-x}-e^{y-x}, & еякх~$x\le y$;\cr e^{1-x}, & еякх~$x>y$.\cr } $$ Осярэ~$f(x)\,dx$---бепнърмнярэ рнцн, врн нопедекеммши бнгпюярючыхи нрпегнй мювхмюеряъ я~$x$. Днйюфхре, врн~$\left(\int_0^1a(x,y) f(x)\,dx\right)\,dy$ еярэ бепнърмнярэ рнцн, врн якедсчыхи нрпегнй мювхмюеряъ я~$y$. [\emph{Сйюгюмхе:} пюяялнрпхре дкъ йюфднцн~$n\ge0$ бепнърмнярэ рнцн, врн~$x\le X_1\le\ldots\le X_n >y$ опх дюммшу~$x$ х~$y$.] \item{c)}~Пюяялнрпхре нрпегйх, лемъчыхе мюопюбкемхе сонпъднвемхъ я бепнърмнярэч~$p$, дпсцхлх якнбюлх, мюопюбкемхе йюфднцн нрпегйю, йпнле оепбнцн, янбоюдюер я мюопюбкемхел опедшдсыецн нрпегйю я бепнърмнярэч~$q=1-p$ х опнрхбнонкнфмн елс я бепнърмнярэч~$p$. (Рюйхл напюгнл, еякх~$p=0$, рн бяе нрпегйх хлечр ндхмюйнбне мюопюбкемхе; еякх~$p=1$, мюопюбкемхе нрпегйнб вепедсеряъ, ю опх~$p=1/2$ нрпегйх яксвюимше х мегюбхяхлше) Осярэ $$ f_1(x)=1,\quad f_{n+1}(y)=p\int_0^1a(x,y)f_n(1-x)\,dx+q\int_0^1a(x,y)f_n(x)\,dx. $$ Онйюфхре, врн бепнърмнярэ рнцн, врн $n\hbox{-и}$~нрпегнй мювхмюеряъ я~$x$, еярэ~$f_n(x)\,dx$, еякх $(n-1)\hbox{-и}$~нрпегнй бнгпюярючыхи, х~$f_n(1-x)\,dx$, еякх $(n-1)\hbox{-и}$~нрпегнй сашбючыхи. \item{d)}~Мюидхре пеьемхе~$f$ дкъ спюбмемхъ "сярюмнбхбьецняъ пефхлю" $$ f(y)=p\int_0^1a(x,y)f(1-x)\,dx+q\int_0^1a(x,y)f(x)\,dx,\quad \int_0^1f(x)\,dx=1. $$ [\emph{Сйюгюмхе:} онйюфхре, врн~$f''(x)$ ме гюбхяхр нр~$x$.] \item{e)}~Онйюфхре, врн онякеднбюрекэмнярэ~$f''(x)$ вюярх~(c) беяэлю ашярпн яундхряъ й тсмйжхх~$f(x)$ вюярх~(d). \item{f)}~Онйюфхре, врн япедмъъ дкхмю бнгпюярючыецн нрпегйю, мювхмючыецняъ я~$x$, пюбмю~$e^{1-x}$. \item{g)}~Мюйнмеж, на╝едхмхре бяе опедшдсыхе пегскэрюрш х днйюфхре якедсчысч ренпелс. \dfn{Еякх мюопюбкемхъ онякеднбюрекэмшу нрпегйнб опх бшанпе я гюлеыемхел мегюбхяхлн хглемъчряъ мю опнрхбнонкнфмше я бепнърмнярэч~$p$, рн япедмъъ дкхмю нрпегйю ярпелхряъ й~$(6/(3+p))P$.} (Щрю ренпелю опх~$p=1$ боепбше ашкю днйюгюмю Ймсрнл [{\sl CACM,\/} {\bf 6} (1963), 685--688]; опх~$p=1/2$ ее днйюгюк Щ.~Ц.~Йнмуеил б~1978~ц.) \ex[БЛ40]Пюяялнрпхре якедсчысч опнжедспс. {\medskip\narrower %!!! нопедекхрэ ярхкэ, ябъгюммши я юкцнпхрлнл \item{N1.}~Опнвхрюрэ гюохяэ, онлеярхб ее б пегепбсюп елйнярэч б ндмн якнбн. Гюрел опнвхрюрэ якедсчысч гюохяэ~|R|, х осярэ~|K| асдер ее йкчвнл. % \item{N2.} Бшбеярх яндепфхлне пегепбсюпю, сярюмнбхрэ~|LASTKEY| пюбмшл ецн йкчвс х носярньхрэ пегепбсюп. % \item{N3.}~Еякх~$|K|<|LASTKEY|$, рн бшбеярх~|R|, сярюмнбхрэ~$|LASTKEY|\asg |K|$ х оепеирх й~N5. %%317 \item{N4.}~Еякх пегепбсюп ме осяр, бепмсрэяъ й~N2; б опнрхбмнл яксвюе онлеярхрэ~|R| б пегепбсюп. % \item{N5.}~Опнвхрюрэ мнбсч гюохяэ~|R| х сярюмнбхрэ~|K| пюбмшл ее йкчвс. Оепеирх й~N3. \endmark\medskip} Щрю опнжедспю, б ясымнярх, щйбхбюкемрмю мюрспюкэмнлс бшанпс я~$P=1$ х~$P'=1$ хкх~$P'=2$ (б гюбхяхлнярх нр рнцн, б йюйни лнлемр лш носярньюел пегепбсюп---йюй рнкэйн нм гюонкмхряъ хкх йнцдю мюл мюдн асдер гюохяюрэ. б гюонкмеммши пегепбсюп мнбши щкелемр, оепеонкмъчыхи ецн), гю хяйкчвемхел рнцн, врн щрю опнжедспю онпнфдюер \emph{сашбючыхе} нрпегйх х мхйнцдю ме нярюмюбкхбюеряъ. Щрх нрйкнмемхъ ме опхмняър бпедю, нмх сднамш дкъ мюьеи жекх. Деиярбсъ, йюй б соп.~24, нангмювхл вепег~$f_n(x, y)\,dy\,dx$ бепнърмнярэ рнцн, врн $(x, y)$~ясрэ гмювемхъ~$(|LASTKEY|,|K|)$ яннрберярбеммн япюгс фе оняке $n\hbox{-цн}$~бшонкмемхъ ьюцю~N2. Днйюфхре, врн ясыеярбсер тсмйжхъ~$g_n(x)$ нр ндмни оепелеммни, рюйюъ, врн~$f_n(x, y)=g_n(x)$, еякх~$xy$. Тсмйжхъ~$g_n(x)$ нопедекъеряъ яннрмньемхълх~$g_1(x)=1$, $$ g_{n+1}(x)=\int_0^x e^ug_n(u)\,du+\int_0^x dv\,(v+1) \int_v^1du\, ((e^v-1)g_n(u)+g_n(v))+ +x\int_x^1dv\,\int_v^1 du\,((e^v-1)g_n(u)+g_n(v)). $$ Онйюфхре дюкее, врн нфхдюелюъ дкхмю $n\hbox{-цн}$~нрпегйю пюбмю $$ \int_0^1\,dx\int_0^x\,dy(g_n(x)(e^y-1)+g_n(y))\left(2-{1\over2}y^2\right) +\int_0^1dx\,(1-x)g_n(x)e^x. $$ [\emph{Гюлевюмхе.} Пеьемхе щрнцн спюбмемхъ б сярюмнбхбьеляъ пефхле нйюгшбюеряъ нвемэ якнфмшл; нмн ашкн вхякеммн мюидемн Дф.~Люй-Йеммни. Нм онйюгюк, врн дкхмю нрпегйю ярпелхряъ й опедекэмнлс гмювемхч~2.61307209. Ренпелю~K ме опхлемхлю й мюрспюкэмнлс бшанпс, рюй врн яксвюи~$P=1$ мекэгъ пюяопнярпюмхрэ мю дпсцхе~$P$.] \ex[Л33] Пюяялюрпхбюъ юкцнпхрл соп.~25 йюй нопедекемхе мюрспюкэмнцн бшанпю дкъ~$P'=1$, мюидхре япедмчч дкхмс \emph{оепбнцн} нрпегйю дкъ~$P'=r$ опх кчанл~$r\ge0$ он якедсчыеи яуеле: \medskip \item{a)}~Онйюфхре, врн оепбши нрпегнй хлеер дкхмс~$n$ я бепнърмнярэч $$ (n+r)\stir{n+r}{n}\Big/(n+r+1)!. $$ \item{b)}~Нопедекхл "вхякю Ярхпкхмцю брнпнцн онпъдйю"~$\Stir{n}{m}$ опюбхкюлх $$ \Stir{0}{m}=\delta_{m0},\quad \Stir{n}{m}=(n+m-1)\left(\Stir{n-1}{m}+\Stir{n-1}{m-1}\right)\rem{опх $n>0$.} $$ Днйюфхре, врн $$ \stir{n+r}{n}=\sum_{0\le k \le r}\perm{n+r}{k+r}\Stir{r}{k}. $$ %%318 \item{c)}~Днйюфхре, врн япедмъъ дкхмю оепбнцн нрпегйю асдер, якеднбюрекэмн, $c_re-r-1$, цде $$ c_r=\sum_{0\le k \le r}\left[\left[{r\atop k}\right]\right] (r+k+1)/(r+k)!. $$ \ex[25] Б рейяре пюяялюрпхбюеряъ рнкэйн яксвюи янпрхпнбйх гюохяеи тхйяхпнбюммнцн пюглепю. Йюй пюгслмшл напюгнл опхяонянахрэ бшанп я гюлеыемхел й гюохяъл \emph{оепелеммни дкхмш?} \subsubchap{Лмнцнтюгмне якхъмхе} %5.4.2 Реоепэ, оняке рнцн йюй лш бшъямхкх, йюй лнфмн напюгнбюрэ мювюкэмше нрпегйх, пюяялнрпхл пюгкхвмше лерндш пюяопедекемхъ нрпегйнб он кемрюл х якхъмхъ ху дн реу онп, онйю ме онксвхряъ едхмярбеммши нрпегнй. Опедонкнфхл ямювюкю, врн б мюьел пюяонпъфемхх хлечряъ рпх кемрнвмшу сярпниярбю: $T1$, $T2$ х~$T3$; лнфмн бняонкэгнбюрэяъ яаюкюмяхпнбюммшл якхъмхел, нохяюммшл б мювюке~\S~5.4, дкъ~$P=2$ х~$T=3$. Нмн опхмхлюер якедсчыхи бхд: %% !!! нопедекхрэ ярхкэ, ябъгюммши я юкцнпхрлнл {\medskip\narrower \item{B1.}~Пюяопедекхрэ мювюкэмше нрпегйх оноепелеммн мю кемрш~$T1$ х~$T2$. \item{B2.}~Якхрэ нрпегйх я кемр~$T1$ х~$T2$ мю~$T3$; гюрел нярюмнбхрэяъ, еякх~$T3$ яндепфхр рнкэйн ндхм нрпегнй. \item{B3.}~Яйнохпнбюрэ нрпегйх я~$T3$ оноепелеммн мю~$T1$ х~$T2$, гюрел бепмсрэяъ й ьюцс~B2.\endmark \medskip\noindent} Еякх мювюкэмне пюяопедекемхе дюкн 5~нрпегйнб, рн оепбши опнунд якхъмхъ опхбедер й $\ceil{S/2}$~нрпегйюл мю~$T3$, брнпни---й~$\ceil{S/4}$ х~р.~д. Рюйхл напюгнл, еякх, яйюфел, $17\le S \le 32$, рн опнхгнидер 1~опнунд пюяопедекемхъ, 5~опнунднб якхъмхъ х 4~опнундю йнохпнбюмхъ; б наыел яксвюе опх~$S>1$ вхякн опнунднб он бяел дюммшл асдер пюбмн~$2 \ceil{\log_2 S}$. Опнундш йнохпнбюмхъ б щрни опнжедспе мефекюрекэмш, рюй йюй нмх ме слемэьючр вхякю нрпегйнб. Лнфмн нанирхяэ онкнбхмни йнохпнбюмхи, еякх хяонкэгнбюрэ \emph{дбсутюгмсч} опнжедспс: %% !!! нопедекхрэ ярхкэ, ябъгюммши я юкцнпхрлнл {\medskip\narrower \item{A1.}~Пюяопедекхрэ мювюкэмше нрпегйх оноепелеммн мю кемрш~$T1$ х~$T2$. \item{A2.}~Якхрэ нрпегйх я кемр~$T1$ х~$T2$ мю~$T3$; нярюмнбхрэяъ, еякх $T3$~яндепфхр рнкэйн ндхм нрпегнй. \item{A3.}~Яйнохпнбюрэ \emph{онкнбхмс} нрпегйнб я~$T3$ мю~$T1$. \item{A4.}~Якхрэ нрпегйх я кемр~$T1$ х~$T3$ мю~$T2$; нярюмнбхрэяъ, еякх $T2$~яндепфхр рнкэйн ндхм нрпегнй. \item{A5.}~Яйнохпнбюрэ \emph{онкнбхмс} нрпегйнб я~$T2$ мю~$T1$. Бепмсрэяъ й ьюцс~A2. \endmark \medskip\noindent} Вхякн опнунднб он бяел дюммшл янйпюрхкняэ дн~${3\over2}\ceil{\log_2 S}+{1\over2}$, %%319 \bye