\input style \chapno=5\subchno=2\chapnotrue \subchap{НОРХЛЮКЭМЮЪ ЯНПРХПНБЙЮ} % 5.3 Реоепэ, йнцдю лш опнюмюкхгхпнбюкх рюйне лмнфеярбн лернднб бмсрпеммеи янпрхпнбйх, опхькн бпелъ напюрхрэяъ й анкее наыелс бнопняс: \emph{йюйни лернд бмсрпеммеи янпрхпнбйх мюхксвьхи?} Ясыеярбсер кх рюйни бепумхи опедек яйнпнярх янпрхпнбйх, йнрнпнцн аш ме лнц днярхвэ мх ндхм опнцпюллхяр, йюй аш хяйсяем нм мх ашк? Пюгслееряъ, мюхксвьецн бнглнфмнцн яонянаю янпрхпнбйх \emph{мер}; лш днкфмш рнвмн нопедекхрэ, врн онмхлюрэ онд якнбнл "мюхксвьхи", мн ме ясыеярбсер мюхксвьецн бнглнфмнцн яонянаю нопедекхрэ якнбн "мюхксвьхи". Юмюкнцхвмше бнопняш на норхлюкэмнярх юкцнпхрлнб лш наясфдюкх б о.~4.3.3, 4.6.3 х~4.6.4, цде пюяялюрпхбюкняэ слмнфемхе я бшянйни рнвмнярэч х бшвхякемхе онкхмнлнб. Б йюфднл яксвюе, дкъ рнцн врнаш бшонкмъкхяэ сякнбхъ "днярюрнвмнярх", р.~е.\ врнаш гюдювю ярюкю пюгпеьхлни, менаундхлн ашкн ятнплскхпнбюрэ днбнкэмн опнярне нопедекемхе юкцнпхрлю, "мюхксвьецн хг бнглнфмшу". Х б йюфднл яксвюе оепед мюлх бярюбюкх хмрепеямеиьхе гюдювх, мюярнкэйн якнфмше, врн нмх дн яху онп онкмнярэч ме пеьемш. Рюй фе наярнхр декн х я янпрхпнбйни: ашкх онксвемш мейнрнпше хмрепеямше пегскэрюрш, мн нярюкняэ еые лмнцн хмрпхцсчыху бнопнянб, мю йнрнпше дн яху онп мер нрбернб. Хгсвемхе бмсрпеммецн леуюмхглю лернднб янпрхпнбйх нашвмн ашкн мюопюбкемн мю лхмхлхгюжхч вхякю япюбмемхи йкчвеи опх янпрхпнбйе $n$~щкелемрнб, хкх якхъмхх $m$~щкелемрнб я $n$~щкелемрюлх, хкх бшанпе $t\hbox{-цo}$~мюханкэьецн щкелемрю хг месонпъднвеммнцн мюанпю $n$~щкелемрнб. Б о.~5.3.1, 5.3.2 х~5.3.3 щрх бнопняш наясфдючряъ б наыел яксвюе; б о.~5.3.4 пюяялюрпхбючряъ юмюкнцхвмше бнопняш я хмрепеямшл нцпюмхвемхел: онякеднбюрекэмнярэ япюбмемхи днкфмю ашрэ, он ясыеярбс, гюпюмее тхйяхпнбюмю. Мейнрнпше дпсцхе рхош хмрепеямшу ренперхвеяйху бнопнянб, ябъгюммшу я норхлюкэмни янпрхпнбйни, лнфмн мюирх б сопюфмемхъу й о.~5.3.4 х б наясфдемхх бмеьмеи янпрхпнбйх б о.~5.4.4. %% 219 \subsubchap{Янпрхпнбйю я лхмхлюкэмшл вхякнл япюбмемхи} % 5.3.1 Нвебхдмн, лхмхлюкэмне вхякн япюбмемхи йкчвеи, менаундхлне дкъ янпрхпнбйх $n$~щкелемрнб, пюбмн~\emph{мскч,} оняйнкэйс, йюй лш бхдекх, ясыеярбсчр лерндш онпюгпъдмни янпрхпнбйх, б йнрнпшу бннаые ме бшонкмъеряъ япюбмемхи. Б яюлнл деке, лнфмн мюохяюрэ \MIX-опнцпюллш, яонянамше янпрхпнбюрэ х ме яндепфюыхе рел ме лемее мх ндмни йнлюмдш сякнбмнцн оепеундю! (Ял.~соп.~5-6 б мювюке щрни цкюбш.) Лш рюйфе бярпевюкхяэ я меяйнкэйхлх лерндюлх янпрхпнбйх, йнрнпше, он ясыеярбс, ашкх нямнбюмш мю япюбмемхх йкчвеи, мн бпелъ пюанрш йнрнпшу мю деке нопедекъкняэ дпсцхлх тюйрнпюлх, рюйхлх, йюй оепелеыемхе дюммшу, бяонлнцюрекэмше ноепюжхх х~р.~д. Онщрнлс ъямн, врн ондявер вхякю япюбмемхи---ме едхмярбеммши яоняна хглепхрэ щттейрхбмнярэ лерндю янпрхпнбйх. Ндмюйн б кчанл яксвюе меаегшмрепеямн опнбеярх рыюрекэмне хяякеднбюмхе вхякю япюбмемхи, оняйнкэйс ренперхвеяйне хгсвемхе щрнцн бнопняю онгбнкхр мюл я онкэгни дкъ декю опнмхймсрэ бн бмсрпеммчч опхпндс опнжеяянб янпрхпнбйх, ю рюйфе онлнфер нррнвхрэ люярепярбн дкъ пеьемхъ анкее опюйрхвеяйху гюдюв, йнрнпше лнцср бярюрэ оепед мюлх б асдсыел. Врнаш хяйкчвхрэ онпюгпъдмсч янпрхпнбйс, цде янбяел ме бшонкмъеряъ япюбмемхи, нцпюмхвхляъ наясфдемхел лернднб янпрхпнбйх, нямнбюммшу рнкэйн мю юаярпюйрмнл кхмеимнл нрмньемхх онпъдйю "$<$" лефдс йкчвюлх, пюяялнрпеммнл б мювюке щрни цкюбш. Дкъ опнярнрш лш рюйфе нцпюмхвхл ябне наясфдемхе яксвюел \emph{пюгкхвмшу} йкчвеи, ю щрн гмювхр, врн опх кчанл япюбмемхх йкчвеи~$K_i$ х~$K_j$ бнглнфмш кхьэ дбю хяундю: кхан~$K_iK_j$. (Пюяопнярпюмемхе щрни ренпхх мю наыхи яксвюи, йнцдю дносяйючряъ пюбмше йкчвх, ял.~б соп.~нр~3 дн~12.) Гюдювс янпрхпнбйх оняпедярбнл япюбмемхи лнфмн ятнплскхпнбюрэ рюйфе дпсцхлх щйбхбюкемрмшлх яонянаюлх. Еякх еярэ $n$~цпсгнб х беяш я дбслъ вюьюлх, рн йюйнбн лхмхлюкэмне вхякн бгбеьхбюмхи, менаундхлне дкъ рнцн, врнаш пюяонкнфхрэ цпсгш он онпъдйс б яннрберярбхх я беянл, еякх б йюфдни вюье беянб онлеыюеряъ рнкэйн ндхм цпсг? Хкх фе, еякх б мейнрнпнл рспмхпе свюярбсчр $n$~хцпнйнб, рн йюйнбн мюхлемэьее вхякн хцп, днярюрнвмне дкъ рнцн, врнаш пюяопедекхрэ леярю лефдс янпебмсчыхлхяъ б опедонкнфемхх, врн яхкш хцпнйнб лнфмн кхмеимн сонпъднвхрэ (мхвеимше пегскэрюрш ме дносяйючряъ). Лерндш янпрхпнбйх $n$~щкелемрнб, сднбкербнпъчыхе сйюгюммшл нцпюмхвемхъл, лнфмн опедярюбхрэ оняпедярбнл ярпсйрспш пюяьхпеммнцн ахмюпмнцн депебю, рюйнцн, йюй онйюгюмн мю пхя.~34. Йюфдши \emph{бмсрпеммхи сгек} (хгнапюфеммши б бхде йпсфнвйю) яндепфхр %%220 дбю хмдейяю "$i:j$" х нгмювюер япюбмемхе йкчвеи~$K_i$ х~$K_j$. Кебне онддепебн щрнцн сгкю яннрберярбсер онякедсчыхл япюбмемхъл, йнрнпше менаундхлн бшонкмхрэ, еякх~$K_iK_j$. Йюфдши \emph{бмеьмхи сгек} депебю (хгнапюфеммши б бхде опълнсцнкэмхйю) яндепфхр оепеярюмнбйс $a_1$ $a_2$~\dots $a_n$ \picture{Пхя.~34. Депебн япюбмемхи дкъ янпрхпнбйх рпеу щкелемрнб.} лмнфеярбю~$\set{1, 2,~\ldots, n}$, нангмювючысч рнр тюйр, врн ашкн сярюмнбкемн сонпъднвемхе $$ K_{a_1}K_2$, рн опнднкфюрэ (дбхцюъяэ он опюбнлс онддепебс) япюбмхбюрэ~$K_2$ я~$K_3$, ю гюрел, еякх~$K_2K_3$, ярюмнбхряъ ъямн, врн~$K_2\ceil{n/2}$, бярюбхрэ ахмюпмшлх бярюбйюлх б цкюбмсч жеонвйс нярюкэмше щкелемрш~$b$ б якедсчыел онпъдйе: $$ b_3, b_2; b_5, b_4; b_{11}, b_{10},~\dots, b_6; b_{t_k}, b_{t_k-1},~\ldots, b_{t_{k-1}+1};~\ldots\,. \eqno(11) $$ Мюл унрекняэ аш нопедекхрэ онякеднбюрекэмнярэ~$(t_1, t_2, t_3, t_4,~\ldots)=(1, 3, 5, 11,~\ldots)$, свюярбсчысч б~(11), рюйхл напюгнл, врнаш йюфдши хг щкелемрнб~$b_{t_k}$, $b_{t_k-1}$,~\dots, $b_{t_{k-1}+1}$ лнфмн ашкн бярюбхрэ б цкюбмсч жеонвйс ме анкее, вел гю $k$~япюбмемхи. Нанаыюъ~(7), (8) х~(9), онксвхл дхюцпюллс \picture{224.2} %%225 цде цкюбмюъ жеонвйю дн~$a_{t_k-1}$~бйкчвхрекэмн яндепфхр $2t_{k-1}+(t_k-t_{k-1}-1)$~щкелемрнб. Щрн вхякн днкфмн ашрэ лемэье~$2^k$; дкъ мюя ксвье бяецн онкнфхрэ ецн пюбмшл~$2^k-1$, х рнцдю $$ t_{k-1}+t_k=2^k. \eqno(12) $$ Оняйнкэйс~$t_1=1$, рн дкъ сднаярбю лнфмн онкнфхрэ~$t_0=1$; рнцдю, ясллхпсъ ценлерпхвеяйсч опнцпеяяхч, мюидел $$ \eqalignno{ t_k=2^k-t_{k-1}&=2^k-2^{k-1}+t_{k-2}=\ldots\cr \ldots&= 2^k-2^{k-1}+\cdots+(-1)^k2^0=(2^{k+1}+(-1)^k)/3. & (13)\cr } $$ (Кчаношрмн, врн рнвмн рюйюъ фе онякеднбюрекэмнярэ бнгмхйкю опх хгсвемхх юкцнпхрлю бшвхякемхъ мюханкэьецн наыецн декхрекъ дбсу жекшу вхяек; яп.~я~соп.~4.5.2-27.) Осярэ $F(n)$---вхякн япюбмемхи, менаундхлшу дкъ янпрхпнбйх о щкелемрнб бярюбйюлх х якхъмхел. Ъямн, врн $$ F(n)=\floor{n/2}+F(\floor{n/2})+G(\ceil{n/2}), \eqno(14) $$ цде тсмйжхъ~$G$ нохяшбюер йнкхвеярбн пюанрш, бшонкмъелни б ьюце~(iii). Еякх~$t_{k-1}\le m \le t_k$, рн, ясллхпсъ он вюяръл, онксвюел $$ \eqalignno{ G(m)&=\sum_{1\le j K_j$. Ъямн, врн $$ T(G)=T(G_1)+T(G_2). $$ Еякх~$T(G_1)\ge T(G_2)$, рн хлеел $$ \eqalignno{ T(G)&\le 2T(G_1),\cr E(G_1)={n!\over 2^{k+1}T(G_1)} &={E(G)T(G)\over 2T(G_1)}\le E(G).&(23)\cr } $$ Якеднбюрекэмн, йюфдне япюбмемхе опхбндхр й цпютс лемэьеи хкх пюбмни щттейрхбмнярх; мекэгъ сбекхвхрэ щттейрхбмнярэ гю явер днонкмхрекэмшу япюбмемхи. Гюлерхл, врн еякх~$G$ янбяел ме яндепфхр дсц, рн~$k=0$ х~$T(G)=n!$, р.~е.~мювюкэмюъ щттейрхбмнярэ пюбмю~1. Еякх фе цпют~$G$ опедярюбкъер нйнмвюрекэмши пегскэрюр янпрхпнбйх, рн $G$~бшцкъдхр йюй нрпегнй опълни, х~$T(G)=1$. Рюй, мюопхлеп, еякх мюл мсфмн онярпнхрэ опнжедспс янпрхпнбйх, йнрнпюъ аш янпрхпнбюкю оърэ щкелемрнб гю яелэ хкх лемее япюбмемхи, рн менаундхлн онксвхрэ кхмеимши цпют \picture{228.1} щттейрхбмнярэ йнрнпнцн пюбмю~$5!/(2^7\times1)=120/128=15/16$. Нрячдю якедсер, врн бяе цпютш, бнгмхйючыхе б опнжеяяе янпрхпнбйх, днкфмш хлерэ щттейрхбмнярэ~$\ge{15\over16}$; еякх аш онъбхкяъ йюйни-мхасдэ цпют лемэьеи щттейрхбмнярх, рн он йпюимеи лепе ндхм хг ецн онрнлйнб рнфе хлек аш лемэьсч щттейрхбмнярэ, х лш аш б йнмже йнмжнб опхькх й кхмеимнлс цпютс я щттейрхбмнярэч~$<{15\over16}$. Б наыел яксвюе щрн пюяясфдемхе онйюгшбюер, врн бяе цпютш, яннрберярбсчыхе сгкюл депебю дкъ мейнрнпни опнжедспш янпрхпнбйх $n$~щкелемрнб, днкфмш хлерэ щттейрхбмнярэ~$\ge n!/2^l$, цде $l+1$---вхякн спнбмеи б депебе. Щрн еые ндхм яоняна днйюгюрекэярбю мепюбемярбю~$S(n)\ge \ceil{\log_2 n!}$, унръ рюйне пюяясфдемхе мю яюлнл деке ме яхкэмн нркхвюеряъ нр опхбедеммнцн бшье. Цпют~(21) хлеер щттейрхбмнярэ~1, оняйнкэйс~$T(G)=15$ х цпют~$G$ ашк онксвем гю рпх япюбмемхъ. Врнаш бшъямхрэ, йюйхе бепьхмш днкфмш свюярбнбюрэ б якедсчыел япюбмемхх, лнфмн %%229 онярпнхрэ \dfn{люрпхжс япюбмемхи} $$ C(G)=\bordermatrix{ & a & b & c & d & e \cr a&0& 15 & 10 & 15 & 11 \cr b & 0 & 0 & 5 & 15 & 7 \cr c & 5 & 10 & 0 & 15 & 9 \cr d & 0 & 0 & 0 & 0 & 3 \cr e & 4 & 8 & 6 & 12 & 0 \cr }, \eqno(24) $$ цде~$C_{ij}$ еярэ~$T(G_1)$ дкъ цпютю~$G_1$, онксвеммнцн хг~$G$ осрел днаюбкемхъ дсцх~$i\to j$. Еякх лш, мюопхлеп, япюбмхл~$K_c$ я~$K_e$, рн 15~оепеярюмнбнй, янцкюясчыхуяъ я~$G$, пюяоюдсряъ мю дбе цпсоош: $C_{ec}=6$, б йнрнпшу $K_ey_2$. (Б яхкс яхллерпхх, он ясыеярбс, й рел фе пегскэрюрюл опхбекх аш япюбмемхъ~$x_3$ я~$y_2$, $x_5$ я~$y_3$ хкх~$x_7$ я~$y_3$.) Щттейрхбмнярэ онксвеммнцн цпютю дкъ~$x_129$. } хкх лемее бепьхм х накюдюкх щттейрхбмнярэч $\ge 12!/2^{29}\approx0.89221$. Бяъйхи пюг, йюй щрн нйюгшбюеряъ бнглнфмшл, лш бшахпюел цпют я лемэьеи щттейрхбмнярэч х днаюбкъел ецн й мюьелс лмнфеярбс, еякх рнкэйн нм ме ъбкъеряъ хгнлнптмшл ндмнлс хг сфе бйкчвеммшу б лмнфеярбн цпютнб (хкх дбниярбеммшл й мелс, р.~е.~онксвюеряъ напюыемхел нрмньемхъ онпъдйю). Еякх наю онксвеммшу цпютю хлечр ндхмюйнбсч щттейрхбмнярэ, рн опнхгбнкэмшл напюгнл бшахпюеряъ ндхм хг мху. Оепбше 24~цпютю, онксвеммше рюйхл яонянанл, хгнапюфемш мю пхя.~36, цде опхбедемш рюйфе ху щттейрхбмнярх. Опх онлных бшвхякхрекэмни люьхмш ашкн онярпнемн пнбмн 1594~цпютю, опефде вел щрнр опнжеяя гюбепьхкяъ. Оняйнкэйс цпют %%233 ме ашк онксвем, лнфмн ядекюрэ бшбнд н рнл, врн~$S(12)>29$. Беяэлю опюбднонднамн, врн х дкъ днйюгюрекэярбю мепюбемярбю~$S(22)>70$ лнфмн опнхгбеярх юмюкнцхвмши щйяоепхлемр гю бонкме пюгслмне бпелъ, оняйнкэйс $22!/2^{70}\approx 0.952$---щрн впегбшвюимн бшянйюъ щттейрхбмнярэ дкъ янпрхпнбйх гю 70~ьюцнб. (Хг 1594~мюидеммшу цпютнб я~12 хкх лемее бепьхмюлх бяецн 92~хлечр ярнкэ бшянйсч щттейрхбмнярэ.) Опнлефсрнвмше пегскэрюрш дючр беяйхе нямнбюмхъ опедонкнфхрэ, врн~$S(13)=33$, х, якеднбюрекэмн, янпрхпнбйю бярюбйюлх х якхъмхел ме норхлюкэмю опх~$n=13$. Мн дн яху онп мхйнлс ме сдюкняэ намюпсфхрэ \emph{мх ндмнцн} рюйнцн гмювемхъ~$n$, врн~$S(n)0} \perm{n}{k} P_{n-k} \rem{опх $n>0$.} $$ \ex[БЛ27] (Н.~Ю.~Цпняя.) Мюидхре опедек онякеднбюрекэмнярх вхяек~$P_n$ хг соп.~3 опх~$n\to\infty$. [\emph{Бнглнфмне сйюгюмхе:} пюяялнрпхре вюярхвмне пюгкнфемхе б дпнаэ~$\ctg z$.] \ex[16] Еякх дносяйючряъ пюбмше йкчвх, рн йюфдне япюбмемхе лнфер хлерэ ме дбю, ю рпх пегскэрюрю: $K_iK_j$. Б щрни наыеи яхрсюжхх юкцнпхрлш янпрхпнбйх лнфмн опедярюбкърэ б бхде пюяьхпеммшу \emph{репмюпмшу} депебэеб, б йнрнпшу йюфдши бмсрпеммхи сгек~$i:j$ хлеер рпх онддепебю: кебне, япедмее х опюбне, яннрберярбсчыхе рпел бнглнфмшл хяундюл япюбмемхъ. Мюпхясире пюяьхпеммне репмюпмне депебн, нопедекъчыее юкцнпхрл янпрхпнбйх дкъ~$n=3$, еякх дносяйючряъ пюбмше йкчвх. Б бюьел депебе днкфмн ашрэ 13~бмеьмху сгкнб, яннрберярбсчыху 13~бнглнфмшл хяундюл, оепевхякеммшл б соп.~3. \rex[Л22] Осярэ~$S'(n)$---лхмхлюкэмне вхякн япюбмемхи, менаундхлшу дкъ янпрхпнбйх $n$~щкелемрнб х бшъбкемхъ бяеу пюбемярб лефдс йкчвюлх, еякх йюфдне япюбмемхе хлеер рпх бнглнфмшу пегскэрюрю, йюй б соп.~5. Мерпсдмн нанаыхрэ "ренперхйн-хмтнплюжхнммне" пюяясфдемхе, опхбедеммне б рейяре, %%236 х онйюгюрэ, врн~$S'(n)\ge \ceil{\log_3 P_n}$, цде~$P_n$---тсмйжхъ, хгсвеммюъ б соп.~3 х~4; днйюфхре, врн мю яюлнл деке~$S'(n)=S(n)$. \ex[20] Мюпхясире пюяьхпеммне репмюпмне депебн б ялшяке соп.~5 дкъ янпрхпнбйх вершпеу щкелемрнб, еякх хгбеярмн, врн бяе йкчвх пюбмш кхан~0, кхан~1. (Рюй, мюопхлеп, еякх~$K_1 \ceil{\log_2 n!}$. \ex[Л20] Днйюфхре рнфдеярбн~(29). \ex[20] Еякх аш опнжедспю, мювюкн йнрнпни хгнапюфемн мю пхя.~36, онпндхкю цпют \picture{p.236} я щттейрхбмнярэч~$12!/2^{29}$, рн ашкн кх аш рел яюлшл днйюгюмн, врн~$S(12) =29$? \ex[40] Опнбедхре щйяоепхлемрш ян якедсчыхл щбпхярхвеяйхл опюбхкнл пеьемхъ нрмняхрекэмн рнцн, йюйсч оюпс йкчвеи япюбмхбюрэ якедсчыеи опх йнмярпсхпнбюмхх депебю япюбмемхи. Осярэ мю йюфдни ярюдхх янпрхпнбйх йкчвеи~$\set{K_1,~\ldots, K_n}$ вхякн йкчвеи, н йнрнпшу мю нямнбюмхх бшонкмеммшу дн яху онп япюбмемхи хгбеярмн, врн нмх~$\le K_i$, нангмювюеряъ вепег~$u_i$, ю вхякн йкчвеи, н йнрнпшу хгбеярмн, врн нмх~$\ge K_i$, нангмювюеряъ вепег~$v_i$, $1\le i\le n$. %%237 Оепемслепсел йкчвх рюй, врнаш онякеднбюрекэмнярэ~$u_i/v_i$ ярюкю бнгпюярючыеи: $u1/v_1 \le u_2/v_2 \le \ldots \le u_n/v_n$. Реоепэ япюбмхл~$K_i:K_{i+1}$, цде~$i$---хмдейя, лхмхлхгхпсчыхи бшпюфемхе~$\abs{u_iv_{i+1}-u_{i+1}v_i}$. (Унръ щрнр лернд хяонкэгсер цнпюгдн лемэье хмтнплюжхх, вел яндепфхряъ б онкмни люрпхже япюбмемхи, онднамни~(24), нм, йюй нйюгшбюеряъ, бн лмнцху яксвюъу дюер норхлюкэмше пегскэрюрш.) \rex[Л26] Днйюфхре, врн пюяьхпеммне ахмюпмне депебн хлеер лхмхлюкэмсч дкхмс бмеьмецн осрх рнцдю х рнкэйн рнцдю, йнцдю ясыеярбсер рюйне вхякн~$l$, врн бяе бмеьмхе сгкш мюундъряъ мю спнбмъу~$l$ х~$l+1$ (хкх, ашрэ лнфер, рнкэйн мю спнбме~$l$). \edef\exref{\the\excerno} \ex[Л21] \dfn{Бшянрни} пюяьхпеммнцн ахмюпмнцн депебю мюгшбюеряъ люйяхлюкэмши мнлеп спнбмъ, мю йнрнпнл еярэ бмеьмхе сгкш. Осярэ~$x$---бмсрпеммхи сгек пюяьхпеммнцн ахмюпмнцн депебю; нангмювхл вепег~$t(x)$ вхякн бмеьмху сгкнб-онрнлйнб сгкю~$x$, ю вепег~$l(x)$ йнпемэ кебнцн онддепебю сгкю~$x$. Еякх $x$---бмеьмхи сгек, рн онкнфхл~$t(x)=1$. Днйюфхре, врн пюяьхпеммне ахмюпмне депебн хлеер лхмхлюкэмсч бшянрс япедх бяеу ахмюпмшу депебэеб я рел фе вхякнл сгкнб рнцдю х рнкэйн рнцдю, йнцдю дкъ бяеу ецн бмсрпеммху сгкнб~$x$ бшонкмъеряъ мепюбемярбн $$ \abs{t(x)-2t(l(x))}\le2^{\ceil{\log_2 t(x)}}-t(x). $$ \ex[Л24] Опнднкфемхе соп.~\exref. Днйюфхре, врн ахмюпмне депебн хлеер лхмхлюкэмсч дкхмс бмеьмецн осрх япедх бяеу ахмюпмшу депебэеб я рел фе вхякнл сгкнб рнцдю х рнкэйн рнцдю, йнцдю дкъ бяеу ецн бмсрпеммху сгкнб~$x$ бшонкмъчряъ мепюбемярбю $$ \abs{t(x)-2t(l(x))}\le 2^{\ceil{\log_2 t(x)}}-t(x) \hbox{ х } \abs{t(x)-2t(l(x))}\le t(x)-2^{\floor{\log_2 t(x)}}. $$ [Рюй, мюопхлеп, еякх~$t(x)=67$, рн днкфмн ашрэ~$t(l(x))=32$, 33, 34 хкх~35. Еякх мсфмн опнярн лхмхлхгхпнбюрэ бшянрс депебю, рн, янцкюямн опедшдсыелс сопюфмемхч, днярюрнвмн, врнаш~$3\le t(l(x))\le 64$.] \ex[10] Б рейяре днйюгюмн [ял.~тнплскс~(34)], врн япедмее вхякн япюбмемхи, бшонкмъелшу кчашл лернднл янпрхпнбйх $n$~щкелемрнб, ме лнфер ашрэ лемэье~$\ceil{\log_2 n!}\approx n\log_2 n$. Ндмюйн опх янпрхпнбйе бярюбйюлх б меяйнкэйн яохяйнб (юкцнпхрл~5.2.1Л) гюрпювхбюеряъ б япедмел бяецн $O(n)$~едхмхж бпелемх. Вел щрн на╝ъямъеряъ? \ex[27] (Й. Охйюп.) Онярпнире рюйне депебн янпрхпнбйх дкъ ьеярх щкелемрнб, врнаш бяе ецн бмеьмхе сгкш пюяонкюцюкхяэ мю спнбмъу~10 х~11. \ex[11] Еякх аш ясыеярбнбюкю опнжедспю янпрхпнбйх яелх щкелемрнб, мю йнрнпни днярхцюкяъ лхмхлсл япедмецн вхякю япюбмемхи, бшвхякъелши опх онлных тнплскш~(34), рн яйнкэйн бмеьмху сгкнб ашкн аш мю спнбме~13 яннрберярбсчыецн депебю? \ex[Л42] Мюидхре опнжедспс янпрхпнбйх дкъ яелх щкелемрнб, лхмхлхгхпсчысч япедмее вхякн бшонкмъелшу япюбмемхи. \rex[20] Осярэ хгбеярмн, врн йнмтхцспюжхх ($K_1K_j$, рн онлемърэ леярюлх гюохях~$i$ х~$j$ х опндбхмсрэяъ он опюбни бербх депебю" Он днярхфемхх бмеьмецн сгкю днкфмш бшонкмърэяъ сякнбхъ~$K_1\le K_2\le \ldots\le K_n$. Рюйхл напюгнл, депебн япюбмемхи-налемнб нркхвюеряъ нр депебю япюбмемхи рел, врн нмн нохяшбюер ме рнкэйн ноепюжхх япюбмемхъ, мн х ноепюжхх оепелеыемхъ дюммшу. Нангмювхл вепег~$S_e(n)$ лхмхлюкэмне вхякн япюбмемхи-налемнб, менаундхлшу б мюхусдьел яксвюе дкъ янпрхпнбйх щкелемрнб опх онлных депебю япюбмемхи-налемнб. Днйюфхре, врн~$S_e(n)\le S(n)+n-1$. \ex[Л38] Опнднкфемхе соп.~30. Днйюфхре, врн~$S_e(5)=8$. \ex[Л42] Опнднкфемхе соп.~31. Хяякедсире гмювемхъ тсмйжхх~$S_e(n)$ опх люкшу~$n>5$. \ex[M30] (Р.~М.~Ухааюпд.) \dfn{Беыеярбеммнгмювмшл депебнл онхяйю} онпъдйю~$x$ я пюгпеьемхел~$\delta$ мюгшбюеряъ пюяьхпеммне ахмюпмне депебн, йюфдши сгек йнрнпнцн яндепфхр менрпхжюрекэмне деиярбхрекэмне гмювемхе, рюйне, врн (i)~гмювемхе б кчанл бмеьмел сгке~$\le \delta$; (ii)~гмювемхе б кчанл бмсрпеммел сгке~$\le $ ясллш гмювемхи дбсу ецн яшмнбеи; (iii)~гмювемхе б йнпме пюбмн~$x$. \dfn{Дкхмю бгбеьеммнцн осрх} рюйнцн депебю нопедекъеряъ йюй ясллю он бяел бмеьмхл сгкюл мнлепнб спнбмеи щрху сгкнб, слмнфеммшу мю яндепфюыхеяъ б мху гмювемхъ. Днйюфхре, врн беыеярбеммнгмювмне депебн онхяйю онпъдйю~$x$ я пюгпеьемхел~1 хлеер лхмхлюкэмсч япедх бяеу рюйху депебэеб рнцн фе онпъдйю х я рел фе пюгпеьемхел дкхмс бгбеьеммнцн осрх рнцдю х рнкэйн рнцдю, йнцдю б~(ii) хлеер леярн пюбемярбн х дкъ бяеу оюп гмювемхи~$x_0$ х~$x_1$, опхмюдкефюыху сгкюл-апюрэъл, бшонкмъчряъ якедсчыхе сякнбхъ: (iv)~ме ясыеярбсер жекнцн вхякю~$k\ge 0$, рюйнцн, врн~$x_0<2^kB_j$, еякх~$i\ge j$. Якхъмхе днкфмн гюбепьхрэяъ %%240 йнмтхцспюжхеи $$ B_1B_1$). \smallskip } \noindent Опюбше нцпюмхвемхъ нангмювючряъ яхлбнкюлх {\narrower \item{$\cdot$}~(мер нцпюмхвемхъ яопюбю), \item{$\backslash$}~(пегскэрюрш бяеу япюбмемхи ме днкфмш опнрхбнпевхрэ сякнбхч~$A_mB_n$). \medskip } \noindent Ясыеярбсер дебърэ рхонб дэъбнкнб, нангмювюелшу яхлбнкюлх~$\nabla M\phi$, цде~$\nabla$---кебне нцпюмхвемхе, ю~$\phi$---опюбне. Мюопхлеп, дэъбнк~"$\backslash M \backslash$" днкфем цнбнпхрэ, врн~$A_1B_q$, еякх~$p>k$ х~$qk$ х~$q\ge l$. {\sl Ярпюрецхъ~$B(k, l)$ дкъ~$i\le k \le m$ х~$1\le l < j$\/}. Нрберхрэ, врн~$A_iB_q$, еякх~$p>k$ х~$q\le l$; нмх асдср сопюбкърэяъ дэъбнкнл~$(k, l, \nabla, \backslash)$, еякх~$p\le k$ х~$q\le l$, х дэъбнкнл~$(m-k, n+1-l, /, \phi)$, еякх~$p>k$ х~$q\le l$. {\sl Ярпюрецхъ~$C(k, l)$ дкъ~$iB_j$, х онрпеанбюрэ, врнаш онякедсчыхе ноепюжхх нясыеярбкъкх якхъмхъ~$\set{A_1,~\ldots, A_{k-1}}$ я~$\set{B_1,~\ldots, B_l}$ х~$\set{A_k,~\ldots, A_m}$ я~$\set{B_{l+1},~\ldots, B_n}$. (Юмюкнцхвмн ярпюрецхх~A.) {\sl Ярпюрецхъ~$B'(k, l)$ дкъ~$1\le k \le i$ х~$jB_j$, х онрпеанбюрэ, врнаш онякедсчыхе ноепюжхх нясыеярбкъкх якхъмхъ~$\set{A_1,~\ldots, A_{k-1}}$ я~$\set{B_1,~\ldots, B_l}$ х~$\set{A_k,~\ldots, A_m}$ я~$\set{B_l,~\ldots, B_n}$ опх сякнбхх~$A_{k-1}B_j$, х онрпеанбюрэ, врнаш онякедсчыхе ноепюжхх нясыеярбкъкх якхъмхъ~$\set{A_1,~\ldots, A_k}$ я~$\set{B_1,~\ldots, B_l}$ х~$\set{A_k, ~\ldots, A_m}$ я~$\set{B_{l+1},~\ldots, B_n}$ опх сякнбхх~$B_lB_2$, рн мсфмн еые $M(m, n-2)$~япюбмемхи, еякх фе~$A_1i$, рн бняонкэгселяъ ярпюрецхеи~$A(i, i+1)$; опхлемхб хмдсйжхч он~$m$, онксвхл $$ .M.(m,m+d)\ge 1+.M.(i, i)+.M.(m-i, m+d-i)=2m+d-1. $$ \proofend % йнмжебни люпйеп ме мю леяре Оепбше дбю србепфдемхъ ренпелш~K онксвхкх Т.~Усюм х~Ь.~Кхмэ б~1969~ц. Щрн днйюгюрекэярбн дюер нямнбюмхъ опедонкнфхрэ, %%246 врн $M(m, m+d)=2m+d-1$ опх бяеу днярюрнвмн анкэьху~$m$, цде~$d$ тхйяхпнбюмн. (Яп.~я~соп.~6.) \section Бепумхе нжемйх. Пюяялнрпхл реоепэ \emph{бепумхе} нжемйх тсмйжхх~$M(m, n)$; унпньхе бепумхе нжемйх яннрберярбсчр щттейрхбмшл юкцнпхрлюл якхъмхъ. Опх~$m=1$ гюдювю якхъмхъ щйбхбюкемрмю гюдюве бярюбйх, йнцдю хлееряъ $n+1$~леяр лефдс щкелемрюлх~$B_1$,~\dots,$B_n$, йсдю лнфер оноюярэ щкелемр~$A_1$. Б щрнл яксвюе мерпсдмн бхдерэ, врн \emph{кчане} пюяьхпеммне ахмюпмне депебн я $n+1$~бмеьмхлх сгкюлх еярэ депебн дкъ мейнрнпнцн лерндю якхъмхъ! (Ял.~соп.~2.) Якеднбюрекэмн, лнфмн бшапюрэ норхлюкэмне ахмюпмне депебн, пеюкхгнбюб ренперхйн-хмтнплюжхнммсч мхфмчч нжемйс $$ 1+\floor{\log_2 n}=M(1, n)=\ceil{\log_2(n+1)}. \eqno(15) $$ Пюгслееряъ, ахмюпмши онхяй~(о.~6.2.1)---опняреиьхи яоняна. онгбнкъчыхи днярхвэ щрнцн гмювемхъ. Яксвюи~$m=2$ впегбшвюимн хмрепеяем, мн нм цнпюгдн якнфмее. Ецн онкмнярэч хяякеднбюкх П.~К.~Цпщуел, Т.~Й.~Усюм х~Ь.~Кхмэ (ял.~соп.~11, 12, 13); хлеел $$ M(2, n)=\ceil{\log_2{7\over12}(n+1)}+\ceil{\log_2{14\over17}(n+1)}. \eqno(16) $$ Лш бхдекх, врн опх~$m=n$ норхлюкэмю нашвмюъ опнжедспю якхъмхъ, ю опх~$m=1$ норхлюкэмю днбнкэмн яхкэмн нркхвючыюъяъ нр мее опнжедспю ахмюпмнцн онхяйю. Мюл фе мсфем мейнрнпши опнлефсрнвмши лернд, на╝едхмъчыхи б яеае ксвьхе вепрш юкцнпхрлнб нашвмнцн якхъмхъ х ахмюпмнцн онхяйю. Тнплскю~(14) мюбндхр мю лшякэ н якедсчыел юкцнпхрле, йнрнпшл лш наъгюмш Т.~Й.~Усюмс х~Ь.~Кхмч [{\sl SIAM J.~Computing,\/} {\bf 1} (1972), 31--39]. \alg М.(Ахмюпмне якхъмхе.) \st Еякх~$m$ хкх~$n$ пюбмн~0, рн нярюмнбхрэяъ. Еякх~$m\le n$, рн сярюмнбхрэ~$t\asg\floor{\log_2 (n/m)}$. Еякх~$m>n$, сярюмнбхрэ~$t\asg\floor{\log_2 (m/n)}$ х оепеирх й~\stp{4}. \st Япюбмхрэ~$A_m:B_{n+1-2^t}$. Еякх $A_m$~лемэье, рн сярюмнбхрэ~$n\asg n-2^t$ х бнгбпюрхрэяъ й ьюцс~\stp{1}. \st Бняонкэгнбюбьхяэ лернднл ахмюпмнцн онхяйю (йнрнпши рпеасер еые пнбмн $t$~япюбмемхи), бярюбхрэ~$A_m$ б яннрберярбсчыее леярн япедх~$\set{B_{n+1-2^t},~\ldots, B_n}$. Еякх~$k$---люйяхлюкэмши хмдейя, рюйни, врн~$B_k X_{n-j}. $$ [Сякнбхе~$\alpha< X_{i+1}$ хкх~$\beta>X_{n-j}$ репъер ялшяк, еякх~$i\ge n$ хкх~$j\ge n$. Онщрнлс~$R_n(n,n)=M(2, n)$.] Ъямн, врн~$R_n(0, 0) = 0$. Днйюфхре, врн $$ R_n(i,j)=1+\min\left(\min_{1\le k \le i} \max(R_n(k-1, j), R_{n-k}(i-k, j)), \min_{1\le k \le j} \max(R_n(i, k-1), R_{n-k}(i, j-k))\right) $$ опх $0\le i \le n$, $0\le j \le n$, $i+j>0$. \ex[M42] (P.~К.~Цпщуел). Онйюфхре, врн пеьемхе пейсппемрмнцн яннрмньемхъ хг соп.~12 лнфмн бшпюгхрэ якедсчыхл напюгнл. Нопедекхл тсмйжхч~$G(x)$ опх~$0{6\over7}2^{r-2}\hbox{ х } i-2^r\ge v \right)$,} \cr } $$ цде~$u=2^pG(t/2^p)$ х~$v=2^{r-2}G(t/2^{r-2})$. %%250 (Щрн, ашрэ лнфер, яюлне якнфмне пейсппемрмне яннрмньемхе хг бяеу, йнрнпше йнцдю-кхан асдср пеьемш!) \ex[46] (Усюм х~Кхмэ.) Осярэ~$h_{3k}=2^k+2^{k-1}-1$, $h_{3k+1}=g_{2k}+g_{2k-3}+2^{k-2}$, $h_{3k+2}=2g_{2k}$ опх~$k\ge 2$, гю хяйкчвемхел~$h_8=9$, х мювюкэмше гмювемхъ онднапюмш рюй, врн~$(h_0, h_1, h_2,~\ldots)=(1, 1, 2, 2, 3, 4, 5, 7, 9, 11, 14, 18, 23, 29, 38, 47, 59, 76,~\ldots)$. Гдеяэ~$g_k$---тсмйжхъ, йнрнпюъ ашкю нопедекемю б соп.~11. Днйюфхре (хкх нопнбепцмхре), врн~$M(3, h_t)>t$, $M(3, h_t-1)\le t$ опх бяеу~$t$. \ex[12] Б ьюце~H1 юкцнпхрлю ахмюпмнцн якхъмхъ лнфер онрпеанбюрэяъ бшвхякемхе гмювемхъ~$\floor{\log_2 (n/m)}$. Йюй лнфмн кецйн бшвхякхрэ щрн гмювемхе, ме опхлемъъ ноепюжхи декемхъ х бгърхъ кнцюпхтлю? \picture{Пхя.~38. Тсмйжхъ Цпщуелю (ял.~соп.~13).} \ex[18] Опх йюйху~$m$ х~$n$, $1\le m \le n \le 10$, норхлюкем юкцнпхрл ахмюпмнцн якхъмхъ Усюмю х Кхмъ? \ex[Л25] Днйюфхре мепюбемярбн~(21). [\emph{Сйюгюмхе:} щрн мепюбемярбн ме нвемэ феярйне.] \ex[Л40] Хяякедсире \emph{япедмее} вхякн япюбмемхи, бшонкмъелшу юкцнпхрлнл ахмюпмнцн якхъмхъ. \rex[23] Днйюфхре, врн тсмйжхъ~$M$ сднбкербнпъер мепюбемярбс~(22). \ex[20] Онйюфхре, врн еякх~$M(m, n+1) \le M(m+1, n)$ опх бяеу~$m\le n$, рн~$M(m, n+1)\le 1+M(m, n)$ опх бяеу~$m\le n$. \ex[Л47] Днйюфхре хкх нопнбепцмхре яннрмньемхъ~(23), (24). \ex[Л50] Хяякедсире лхмхлюкэмне \emph{япедмее} вхякн япюбмемхи, менаундхлшу дкъ якхъмхъ $m$~щкелемрнб я $n$~щкелемрюлх. \ex[БЛ30] (Щ.~Пеимцнкэд.) Осярэ~$\set{A_1,~\ldots, A_n}$ х~$\set{B_1,~\ldots, B_n}$---лмнфеярбю, яндепфюыхе он $n$~щкелемрнб йюфдне. Пюяялнрпхре юкцнпхрл, йнрнпши ошрюеряъ опнбепхрэ мюкхвхе пюбемярбю лефдс лмнфеярбюлх хяйкчвхрекэмн осрел япюбмемхи мю пюбемярбн щкелемрнб щрху лмнфеярб. Рюйхл напюгнл, юкцнпхрл гюдюер бнопняш рхою~"$A_i=B_j$?" опх мейнрнпшу~$i$ х~$j$ х бшахпюер дюкэмеиьхи осрэ бшвхякемхи б гюбхяхлнярх нр рнцн, ашк кх нрбер онкнфхрекэмшл хкх нрпхжюрекэмшл. Нопедекхб ондундъыецн дэъбнкю, днйюфхре, врн кчани рюйни юкцнпхрл б мюхусдьел дкъ яеаъ яксвюе бшмсфдем бшонкмхрэ ме лемее ${1\over2}n (n+1)$~япюбмемхи. %%250 \subsubchap{* Бшанп я лхмхлюкэмшл вхякнл япюбмемхи} % 5.3.3 Опх онхяйе мюхксвьху бнглнфмшу опнжедсп дкъ бшанпю $t\hbox{-цн}$~щкелемрю б онпъдйе сашбюмхъ хг $n$~щкелемрнб лш бярпевюеляъ я йкюяянл гюдюв, онднамшу пюяялнрпеммшл б опедшдсыел осмйре. Хярнпхъ щрнцн бнопняю бняундхр й гюмхлюрекэмнлс (унръ х яепэегмнлс) нвепйс опеонднамнцн В.~К.~Дндфянмю н рспмхпюу он реммхяс, онъбхбьелсяъ б St.~James's Gazette 1~юбцсярю 1883~ц. (ярп.~5--6). Дндфянм, йнрнпши, пюгслееряъ, анкее хгбеярем йюй Кэчхя Йщппнк, пюяялюрпхбюк меяопюбедкхбше опюбхкю, он йнрнпшл опхясфдюкхяэ (х дн яху онп опхясфдючряъ) опхгш б рспмхпюу он реммхяс. Пюяялнрпхл, мюопхлеп, пхя.~39, цде онйюгюм рхохвмши рспмхп "я бшашбюмхел" лефдс 32~хцпнйюлх, онлевеммшлх $01$, $02$,~\dots, $32$. Б тхмюке хцпнй~$01$ ндепфхбюер онаедс мюд хцпнйнл~$05$, онщрнлс ъямн, врн хцпнй~$01$---велохнм х гюяксфхк оепбши опхг. Меяопюбедкхбнярэ опнъбкъеряъ б рнл, врн хцпнй~$05$ нашвмн онксвюер брнпни опхг, унръ нм лнфер х ме ашрэ брнпшл хцпнйнл. Бшхцпюрэ брнпни опхг лнфмн, дюфе еякх хцпюеьэ усфе онкнбхмш хцпнйнб рспмхпю. Б яюлнл деке, йюй гюлерхк Дндфянм, брнпни хцпнй бшхцпшбюер брнпни опхг б рнл х рнкэйн рнл яксвюе, еякх оепбнмювюкэмн нм х велохнм мюундхкхяэ б опнрхбнонкнфмшу онкнбхмюу рспмхпю; дкъ $2^n$~хцпнйнб щрн опнхяундхр я бепнърмнярэч~$2^{n-1}/(2^n-1)$, рюй врн онврх б онкнбхме яксвюеб брнпни опхг онксвюер ме рнр хцпнй! Еякх опнхцпюбьхе б онкстхмюке (хцпнйх~$25$ х~$17$ мю пхя.~39) янпебмсчряъ гю рперхи опхг, рн беяэлю люкнбепнърмн, врн рперхи хцпнй онксвхр рперхи опхг. Онщрнлс Дндфянм пеьхк мюирх рюйни рспмхп, йнрнпши опюбхкэмн нопедекъер брнпнцн х рперэецн хцпнйнб б опедонкнфемхх рпюмгхрхбмнярх. (Хмюве цнбнпъ, еякх хцпнй~$A$ онаефдюер хцпнйю~$B$, ю~$B$ онаефдюер~$C$, рн лнфмн явхрюрэ, врн хцпнй~$A$ онаедхр~$C$). Нм опхдслюк опнжедспс, б йнрнпни опнхцпюбьхл дючр яшцпюрэ еые меяйнкэйн хцп, онйю ме ярюмер нопедекеммн хгбеярмн, врн нмх усфе дпсцху рпеу хцпнйнб. Опхлеп яуелш Дндфянмю опхбндхряъ мю пхя.~40, хгнапюфючыел днонкмхрекэмши рспмхп, йнрнпши якедсер опнбеярх блеяре я рспмхпнл, онйюгюммшл мю пхя.~39. Декюеряъ оношрйю нпцюмхгнбюрэ бярпевх хцпнйнб, с йнрнпшу дн яху онп ашкх пюбмше пегскэрюрш, х хяйкчвхрэ люрвх лефдс хцпнйюлх, онаефдеммшлх ндмхл х рел фе векнбейнл. Мюопхлеп, хцпнй~$16$ опнхцпшбюер~$11$, ю хцпнй~$13$ опнхцпшбюер~$12$ б оепбнл рспе; оняке рнцн йюй хцпнй~$16$ опнхцпшбюер~$13$ бн брнпнл рспе, $16$~хяйкчвюеряъ, рюй йюй реоепэ хгбеярмн, врн нм усфе, вел~$11$, $12$ х~$13$. Б рперэел рспе лш ме онгбнкъел мнлепс~$19$ хцпюрэ я~$21$, рюй йюй нмх наю ашкх онаефдемш %%252 \picture{Пхя. 39. Рспмхп 32~хцпнйнб я бшашбюмхел.} %%253 \picture{Пхя. 40. Реммхямши рспмхп Кэчхяю Йщппнкю (б днонкмемхе й рспмхпс пхя.~39).} %% 254 хцпнйнл~$18$ х лш ме лнцкх аш юбрнлюрхвеяйх хяйкчвхрэ опнхцпюбьецн бн бярпеве~$19$ я~$21$. Ашкн аш опхърмн яннаыхрэ, врн рспмхп Кэчхяю Йщппнкю нйюгюкяъ норхлюкэмшл, мн, й янфюкемхч, щрн ме рюй. Хг гюохях б ецн дмебмхйе нр 23~хчкъ 1883~ц. ъбярбсер, врн нм янярюбхк щрнр нвепй опхлепмн гю ьеярэ вюянб, х всбярбнбюк, врн, "оняйнкэйс реммхямши яегнм опхакхфюеряъ й йнмжс, нвепй якедсер мюохяюрэ онашярпее, ме якхьйнл сбкейюъяэ йювеярбнл". Б ецн опнжедспе декюеряъ анкэье япюбмемхи, вел менаундхлн, х нмю ме ятнплскхпнбюмю днярюрнвмн верйн, врнаш йбюкхтхжхпнбюрэ ее йюй юкцнпхрл. Я дпсцни ярнпнмш, б меи хлечряъ мейнрнпше нвемэ хмрепеямше юяоейрш, еякх ясдхрэ я рнвйх гпемхъ оюпюккекэмшу бшвхякемхи. Нмю рюйфе опедярюбкъеряъ нркхвмшл пюяохяюмхел реммхямнцн рспмхпю, оняйнкэйс Йщппнк бйкчвхк б мее меяйнкэйн дпюлюрхвеяйху щттейрнб; мюопхлеп, нм нопедекхк, врн дбю тхмюкхярю днкфмш опносярхрэ оърши рсп х яшцпюрэ "дкхммши" люрв б рспюу~6 х~7. Ндмюйн нпцюмхгюрнпш рспмхпнб, он-бхдхлнлс, янвкх щрн опедкнфемхе хгкхьме кнцхвмшл, х онрнлс яхярелю Йщппнкю, яйнпее бяецн, мхйнцдю ме хяошршбюкюяэ. Блеярн щрнцн опюйрхйсеряъ лернд "пюяяехбюмхъ" анкее яхкэмшу хцпнйнб, врнаш нмх оноюкх б пюгмше вюярх депебю. Мю люрелюрхвеяйнл яелхмюпе б~1929--1930~ц. Цсцн Ьреимцюсг онярюбхк гюдювс мюунфдемхъ лхмхлюкэмнцн вхякю реммхямшу люрвеи, рпеаселшу дкъ нопедекемхъ оепбнцн х брнпнцн хцпнйнб б рспмхпе, еякх хлееряъ $n >2$~хцпнйнб. Ч.~Ьпеиеп [{\sl Mathesis Polska,\/} {\bf 7} (1932), 154--160] опхбек опнжедспс, рпеасчысч яюлне анкэьее $n-2+\ceil{\log_2 n}$~люрвеи, хяонкэгнбюб, он ясыеярбс, рнр фе лернд, врн х оепбше дбе ярюдхх опнжеяяю, йнрнпши лш мюгбюкх янпрхпнбйни оняпедярбнл бшанпю хг депебю (ял.~о.~5.2.3, пхя.~23), ндмюйн ме бшонкмъъ днонкмхрекэмшу япюбмемхи, яндепфюыху~$-\infty$. Ьпеиеп рюйфе србепфдюк, врн $n-2+\ceil{\log_2 n}$---мюхксвьее бнглнфмне гмювемхе; мн ецн днйюгюрекэярбн ашкн ньханвмшл, йюй х еые ндмю оношрйю днйюгюрекэярбю, опедопхмърюъ Е.~Яксоежйх [{\sl Colloquium Mathematician,\/} {\bf 2} (1951), 286--290]. Опнькн 32~цндю, опефде вел Я.~Я.~Йхякхжшмшл ашкн носакхйнбюмн опюбхкэмне, унръ х нвемэ якнфмне днйюгюрекэярбн [{\sl Яхахпяйхи люрелюрхвеяйхи фспмюк,\/} {\bf 5} (1964), 557--564]. Осярэ~$V_t(n)$ дкъ~$1\le t \le n$ нангмювюер лхмхлюкэмне вхякн япюбмемхи, рпеаселшу дкъ нопедекемхъ $t\hbox{-цн}$ б онпъдйе сашбюмхъ щкелемрю хг $n$~щкелемрнб, х осярэ $W_t(n)$~пюбмн мюхлемэьелс вхякс япюбмемхи, менаундхлшу дкъ нопедекемхъ мюханкэьецн, брнпнцн,~\dots, $t\hbox{-цн}$ щкелемрнб бяеу япюгс. Хг яннапюфемхи яхллерпхх хлеел $$ V_t(n)=V_{n+1-t}(n); \eqno(1) $$ %%255 нвебхдмн рюйфе, врн $$ \eqalignno{ V_1(n)&=W_1(n), & (2) \cr V_t(n)&\le W_t(n), & (3) \cr W_n(n)&=W_{n-1}(n)=S(n). & (4) \cr } $$ Б о.~5.2.3 лш бхдекх, врн $$ V_1(n)=n-1. \eqno(5) $$ Еярэ сдхбхрекэмн опнярне днйюгюрекэярбн щрнцн тюйрю, оняйнкэйс йюфдши свюярмхй рспмхпю, йпнле велохнмю, днкфем опнхцпюрэ он йпюимеи лепе ндмс хцпс! Нанаыюъ щрс хдеч х хяонкэгсъ "дэъбнкю", лш лнфел аег нянанцн рпсдю днйюгюрэ ренпелс Ьпеиепю---Йхякхжшмю. \proclaim Ренпелю~S. Опх~$n\ge 2$ яопюбедкхбн пюбемярбн~$V_2(n)=W_2(n)=n-2+\ceil{\log_2 n}$. \proof Опедонкнфхл, врн б рспмхпе, цде я онлныэч мейнрнпни дюммни опнжедспш днкфем нопедекхрэяъ брнпни хцпнй, свюярбсчр $n$~хцпнйнб, х осярэ~$a_j$---вхякн хцпнйнб, опнхцпюбьху~$j$ хкх анкэье люрвеи. Наыее вхякн яшцпюммшу люрвеи асдер рнцдю пюбмн~$a_1+a_2+a_3+\ldots\,$. Лш ме лнфел нопедекхрэ брнпнцн хцпнйю, ме бшъбхб гюндмн х велохнмю (ял.~соп.~2), онщрнлс хг опедшдсыху пюяясфдемхи~$a_1=n-1$. Дкъ гюбепьемхъ днйюгюрекэярбю онйюфел, врн бяецдю ясыеярбсер онякеднбюрекэмнярэ пегскэрюрнб люрвеи, йнрнпюъ опхбндхр й~$a_2\ge \ceil{\log_2 n}-1$. Опедонкнфхл, врн й йнмжс рспмхпю велохнм яшцпюк $p$~хцп х онаедхк $p$~хцпнйнб; ндмхл хг мху ашк брнпни хцпнй, ю нярюкэмше днкфмш опнхцпюрэ он йпюимеи лепе еые он ндмнлс пюгс, онщрнлс~$a_2\ge p-1$. Хрюй, лш лнфел гюйнмвхрэ днйюгюрекэярбн, онярпнхб дэъбнкю, опеднопедекъчыецн пегскэрюрш хцп рюйхл напюгнл, врнаш велохнмс опхькняэ яшцпюрэ он йпюимеи лепе еые я~$\ceil{\log_2 n}$~дпсцхлх свюярмхйюлх рспмхпю. Осярэ дэъбнк явхрюер, врн хцпнй~$A$ ксвье, вел~$B$, еякх~$A$ пюмее ме опнхцпшбюк, ю~$B$ унръ аш ндмюфдш опнхцпюк, хкх еякх наю ме опнхцпшбюкх, мн $B$~бшхцпюк й щрнлс лнлемрс лемэье люрвеи, вел~$A$. Опх дпсцху наярнърекэярбюу дэъбнк лнфер опхмхлюрэ опнхгбнкэмне пеьемхе, ме опнрхбнпевюыее мейнрнпнлс вюярхвмнлс сонпъднвемхч. Пюяялнрпхл пегскэрюрш гюбепьеммнцн рспмхпю, люрвх йнрнпнцн опеднопедекъкхяэ рюйхл дэъбнкнл. Лш яйюфел, врн "$A$ опебняундхр $B$" рнцдю х рнкэйн рнцдю, йнцдю~$A=B$ хкх $A$~опебняундхр хцпнйю, йнрнпши оепбшл онаедхк~$B$. (Рнкэйн оепбне онпюфемхе хцпнйю ясыеярбеммн б щрнл нрмньемхх, онякедсчыхе ецн хцпш хцмнпхпсчряъ. Б яннрберярбхх я сярпниярбнл дэъбнкю кчани хцпнй, \emph{оепбшл} онаедхбьхи йюйнцн-рн, мх б ндмни хг опедшдсыху бярпев ме днкфем хлерэ онпюфемхи. Нрячдю якедсер, врн %%256 хцпнй, йнрнпши бшхцпюк ябнх оепбше $p$~люрвеи, опебняундхр мю нямнбюмхх щрху $p$~хцп ме анкее $2^p$~хцпнйнб. (Еякх~$p=0$, щрн нвебхдмн, еякх фе $p>0$, рн $p\hbox{-и}$~люрв ашк яшцпюм опнрхб хцпнйю, йнрнпши кхан пюмее онрепоек онпюфемхе, кхан опебняундхр ме анкее~$2^{p-1}$~хцпнйнб.) Велохнм опебняундхр бяеу, онщрнлс нм днкфем ашк яшцпюрэ ме лемее $\ceil{\log_2 n}$~люрвеи. \proofend Рюйхл напюгнл, гюдювю мюунфдемхъ брнпнцн б онпъдйе сашбюмхъ щкелемрю онкмнярэч пеьемю б лхмхлюйямнл ялшяке. Б соп.~6 онйюгюмн, врн лнфмн дюрэ опнярсч тнплскс дкъ лхмхлюкэмнцн вхякю япюбмемхи, менаундхлшу дкъ бшъбкемхъ брнпнцн щкелемрю лмнфеярбю, еякх хгбеярмн опнхгбнкэмне вюярхвмне сонпъднвемхе щкелемрнб. \qsection Ю еякх $t>2$? Б сонлъмсрни ярюрэе Йхякхжшм оньек дюкэье. Нм пюяялнрпек анкэьхе гмювемхъ~$t$, днйюгюб, врн $$ W_t(n)\le n-t+\sum_{n+1-tX_3$, $X_5X_7$, гюрел япюбмхл~$X_2:X_6$; б яхкс яхллерпхх онкнфхл~$X<2n+t-3+\sum_{0\le j\le t-2}\ceil{\log_2((n+2-t)/(t+j))}, \rem{$n\ge 2t-1$.} \eqno(12) $$ Йхпйоюрпхй рнвмн сярюмнбхк онбедемхе тсмйжхх~$V_t(n)$ опх~$t=3$, днйюгюб, врн~$V_3(n)=n+\ceil{\log_2 ((n-1)/2.5)}+\ceil{\log_2((n-1)/4)}$ опх бяеу~$n\ge 50$ (яп.~я~соп.~22). \section Кхмеимши лернд. Еякх $n$~мевермн х~$t=\ceil{n/2}$, рн~$t\hbox{-и}$ б онпъдйе сашбюмхъ (х~$t\hbox{-и}$ б онпъдйе бнгпюярюмхъ) щкелемр мюгшбюеряъ ледхюмни. Б яннрберярбхх я~(11) лш лнфел мюирх ледхюмс~$n$ %%260 {\catcode`\!=\active\def!{\hbox to 0 pt{${}^*$\hss}} \htable{Рюакхжю 1}% {Мюхксвьхе хг хгбеярмшу бепумху нжемнй дкъ $V_t(n)$}% {\strut\bskip\hfill$#$\bskip&&\bskip\hfill$#$\bskip\cr n & V_1(n) & V_2(n) & V_3(n) & V_4(n) & V_5(n) & V_6(n) & V_7(n) & V_8(n) & V_9(n) & V_{10}(n)\cr \noalign{\hrule} 1 & 0 \cr 2 & 1 & 1 \cr 3 & 2 & 3 & 2 \cr 4 & 3 & 4 & 4 & 3 \cr 5 & 4 & 6 & 6 & 6 & 4 \cr 6 & 5 & 7 & 8 & 8 & 7 & 5 \cr 7 & 6 & 8 & 10 & 10!& 10 & 8 & 6\cr 8 & 7 & 9 & 11 & 12 & 12 & 11 & 9 & 7\cr 9 & 8 & 11 & 12 & 14 & 15!& 14 & 12 & 11 & 8\cr 10 & 9 & 12 & 14!& 15 & 17 & 17 & 15 & 14! & 12 & 9 \cr \noalign{\hrule} \multispan{11}\hbox{$*$)~Б щрху яксвюъу соп.~10--12 дючр онярпнемхъ, онгбнкъчыхе сксвьхрэ~(11).}\cr }}% щкелемрнб гю $\approx {1\over2}n\log_2 n$~япюбмемхи, мн щрн кхьэ опхакхгхрекэмн бдбне ашярпее янпрхпнбйх, унръ мюл мсфмю гмювхрекэмн лемэьюъ хмтнплюжхъ. Б ревемхе меяйнкэйху кер на╝едхмеммше сяхкхъ пъдю хяякеднбюрекеи ашкх мюопюбкемш мю сксвьемхе тнплскш~(11) дкъ анкэьху гмювемхи~$t$ х~$n$; мюйнмеж, б 1971~ц. Люмсщкэ Аксл нрйпшк лернд, рпеасчыхи рнкэйн $O(n \log \log n)$~ьюцнб. Ондунд Акслю й щрни гюдюве дюк рнквнй й пюгбхрхч мнбнцн йкюяяю лернднб, йнрнпши опхбек й якедсчыелс онярпнемхч, опхмюдкефюыелс П.~Пюибеярс х~П.~Рюпэъмс. \proclaim Ренпелю~L. Еякх~$n>32$, рн~$V_t(n)\le 15n-163$ опх~$1\le t\le n$. \proof Йнцдю $n$~люкн, ренпелю рпхбхюкэмю, рюй йюй~$V_t(n)\le S(n)\le 10n\le 15n-163$ дкъ~$32r+1$, рн мюл мсфмн мюирх $(t-1-r)\hbox{-и}$~щкелемр б онпъдйе сашбюмхъ хг $n-1-r$~лемэьху щкелемрнб. Ясрэ декю б рнл, врн~$r$ х~$n-1-r$ наю лемэье хкх пюбмш~$10q+3$ (пюглеп накюяреи~Ю х~D окчя~Б хкх~Я). Хмдсйжхеи он~$q$ бшбндхл, врн щрнр ьюц рпеасер ме анкее $15(10q+3)-163$~япюбмемхи. \medskip Наыее вхякн япюбмемхи нйюгшбюеряъ ме анкэье $$ 13(2q+1)+30q-148+4q+15(10q+3)-163=15(14q-6)-163. $$ Рюй йюй лш мювюкх я ме лемее $14q-6$~щкелемрнб, днйюгюрекэярбн гюбепьемн. \proofend Лернд, хяонкэгнбюммши б щрнл днйюгюрекэярбе, ме бонкме янбепьеммши, оняйнкэйс мю ьюце~4 репъеряъ гмювхрекэмюъ хмтнплюжхъ. Рыюрекэмше сксвьемхъ, опндекюммше Б.~Опюррнл, %%262 П.~Пюибеярнл х~П.~Рюпэъмнл, онйюгшбючр, врн йнмярюмрс~15 лнфмн слемэьхрэ дн~$5.43$. \section Япедмее вхякн. Блеярн лхмхлхгюжхх \emph{люйяхлюкэмнцн} вхякю япюбмемхи лнфмн хяйюрэ юкцнпхрл, йнрнпши лхмхлхгхпсер \emph{япедмее} вхякн япюбмемхи, опедонкюцюъ, врн онпъднй яксвюем. Йюй нашвмн, щрю гюдювю гмювхрекэмн рпсдмее, х нмю бяе еые ме пеьемю дюфе б яксвюе~$t=2$. Йкнд Охйюп сонлъмск щрс гюдювс б ябнеи \picture{ Пхя.~42. Опнжедспю, йнрнпюъ бшахпюер брнпни щкелемр хг~$\set{X_1, X_2, X_3, X_4, X_5, X_6}$, хяонкэгсъ б япедмел $6{1\over2}$~япюбмемхи. Йюфдюъ "яхллерпхвмюъ" бербэ хдемрхвмю ябнелс апюрс, ндмюйн хлемю оепеярюбкемш яннрберярбсчыхл напюгнл. Бн бмеьмху сгкюу гюохяюмн~$j\ k$, еякх хгбеярмн, врн $X_j$---брнпни, a $X_k$---мюханкэьхи щкелемр; вхякн оепеярюмнбнй, опхбндъыху й щрнлс сгкс, гюохяюмн меоняпедярбеммн онд мхл. } ймхце Th\'eorie des Questionnaires (1965), ьхпнйне хяякеднбюмхе ашкн опедопхмърн Лхкрнмнл Янаекел [Univ.~of Minnesota, Dept.~of Statistics, report~113 (November, 1968)]. Янаекэ онярпнхк опнжедспс, хгнапюфеммсч мю пхя.~42, йнрнпюъ мюундхр брнпни б онпъдйе сашбюмхъ щкелемр хг ьеярх щкелемрнб, б япедмел хяонкэгсъ рнкэйн $6{1\over2}$~япюбмемхи. Б усдьел %%263 яксвюе рпеасеряъ 8~япюбмемхи, х щрн усфе, вел~$V_2(6)=7$; мн бяе хгбеярмше опнжедспш дкъ щрни гюдювх, рпеасчыхе ме анкее 7~япюбмемхи, хяонкэгсчр б япедмел он йпюимеи лепе $6{2\over3}$~япюбмемхи. Рюйхл напюгнл, бепнърмн, мхйюйюъ опнжедспю мюунфдемхъ брнпнцн хг ьеярх щкелемрнб ме асдер норхлюкэмни ндмнбпелеммн х йюй лхмхлюйямюъ, х йюй лхмхлхгхпсчыюъ япедмее вхякн япюбмемхи. Осярэ $\bar V(n)$~нангмювюер лхмхлюкэмне япедмее вхякн япюбмемхи, менаундхлшу дкъ нопедекемхъ $t\hbox{-цн}$~щкелемрю б онпъдйе сашбюмхъ хг $n$~щкелемрнб. Б якедсчыеи рюакхже онйюгюмш мюхксвьхе хгбеярмше бепумхе нжемйх дкъ~$\bar V_2(n)$, бшвхякеммше Янаекел: {\catcode`\!=\active\def!#1,#2/#3.{#1{#2\over#2}} $$ \vbox{ \halign{ \hfill$#$\bskip&&\bskip$#$\hfill\bskip\cr n=2& 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \cr \bar V_2(n)\le 1& !2,2/3. & 4 & !5,4/15. & !6,1/2. & !7,17/21. & 9 & !10, 1/15. & !11,4/135.\cr }} \eqno(13) $$ } Янаекэ опедонкнфхк, врн $$ \bar V_2(n)\ge n-2+\floor{2\log_2 n}/2. \eqno(14) $$ П.~С.~Ткнид б 1970~ц.\ намюпсфхк, врн ледхюмю $n$~щкелемрнб б япедмел лнфер ашрэ мюидемю бяецн гю ${3\over2}n+O\left(n^{2\over3}\log n\right)$~япюбмемхи. (Ял.~соп.~13.) Тюйрхвеяйх нм днйюгюк, врн $$ \bar V_t(n)\le n+t+f(n), \rem{цде $\lim_{n\to\infty} f(n)/n=0$.} \eqno(15) $$ Опедонкюцюеряъ, врн щрнр пегскэрюр ъбкъеряъ мюхксвьеи юяхлорнрхвеяйни тнплскни, ндмюйн мхйюйни сднбкербнпхрекэмни мхфмеи нжемйх бяе еые ме мюидемн. \excercises \ex[15] Онвелс б рспмхпе Кэчхяю Йщппнкю (пхя.~39 х~40) хцпнй~$13$ бшашбюер, меялнрпъ мю рн врн нм бшхцпюк ябни люрв б рперэел рспе? \rex[Л25] Днйюфхре, врн оняке рнцн, йюй лш мюькх я онлныэч онякеднбюрекэмнярх япюбмемхи $t\hbox{-и}$ щкелемр б онпъдйе сашбюмхъ хг $n$~щкелемрнб, лш рюйфе гмюел, йюйхе $t-1$~щкелемрнб анкэье мецн х йюйхе $n-t$~щкелемрнб лемэье. \ex[M21] Днйюфхре, врн~$V_t(n)\ge V_t(n-1)+1$ опх~$1\le t \le n$. \ex[Л20] Днйюфхре, врн~$W_t(n)\ge\ceil{\log_2 n^{t\atop -}}$, цде~$n^{t\atop -}=n(n-1) \ldots (n+1-t)$. \ex[10] Днйюфхре, врн~$W_3(n)\le V_3(n)+1$. \rex[Л26] (П.~С.~Ткнид.) Дюмн $n$~пюгкхвмшу щкелемрнб~$\set{X_1,~\ldots, X_n}$ х нрмньемхъ~$X_iK_j$, ндмюйн~$i$ х~$j$ лемъчряъ пнкълх. Мю пхя.~43(ю) хгнапюфемн депебн япюбмемхи, б йнрнпнл щрн сякнбхе бшонкмемн. (Гюлерхл, врн мю йюфднл спнбме опнхгбндхряъ ндхмюйнбне вхякн япюбмемхи, онщрнлс оняке $m$~япюбмемхи хлееряъ $2^m$~пегскэрюрнб; рюй йюй~$n!$ ме ъбкъеряъ яреоемэч~2, рн мейнрнпше япюбмемхъ асдср хгкхьмхлх б рнл ялшяке, врн ндмн хг ху онддепебэеб мхйнцдю ме бярпевюеряъ мю опюйрхйе. Хмшлх якнбюлх, мю мейнрнпшу бербъу депебю опхундхряъ бшонкмърэ анкэье япюбмемхи, вел менаундхлн, врнаш янпрхпнбйю ашкю опюбхкэмни мю бяеу яннрберярбсчыху бербъу.) Рюй йюй йюфдши осрэ рюйнцн депебю ябепус днмхгс нопедекъер бяе депебн, рн онднамсч яуелс янпрхпнбйх опные хгнапюфюрэ б бхде \dfn{яерх,} йюй мю пхя.~43(b). Опълнсцнкэмхйх б рюйни яерх опедярюбкъчр "йнлоюпюрнпмше лндскх", хлечыхе дбю бундю (хгнапюфеммше кхмхълх, бундъыхлх б лндскэ ябепус) %%266 \picture{Пхя. 43. Депебн япюбмемхи, б йнрнпнл ме свхршбюеряъ опедшярнпхъ, (a) х яннрберярбсчыюъ яерэ~(b).} %%267 х дбю бшундю (хгнапюфеммше кхмхълх, бшундъыхлх бмхг); кебши бшунд еярэ лемэьхи хг дбсу бунднб, ю опюбши бшунд---анкэьхи хг мху. Щкелемр~$K'_1$ б мхфмеи вюярх яерх еярэ мюхлемэьхи хг~$\set{K_1, K_2, K_3, K_4}$, $K'_2$---брнпни б онпъдйе бнгпюярюмхъ х~р.~д. Мерпсдмн днйюгюрэ, врн кчаюъ яерэ янпрхпнбйх яннрберярбсер депебс япюбмемхи, накюдючыелс ябниярбнл мегюбхяхлнярх нр опедшярнпхх (б сйюгюммнл бшье ялшяке), х врн кчане рюйне депебн яннрберярбсер яерх йнлоюпюрнпмшу лндскеи. Лефдс опнвхл гюлерхл, врн я хмфемепмни рнвйх гпемхъ йнлоюпюрнпмши лндскэ днбнкэмн кецйн хгцнрнбхрэ. Опедонкнфхл, мюопхлеп, врн он кхмхъл ябъгх б лндскэ онярсоючр дбнхвмше вхякю он ндмнлс ахрс б едхмхжс бпелемх, мювхмюъ ян ярюпьецн. Йюфдши йнлоюпюрнпмши лндскэ хлеер рпх янярнъмхъ х тсмйжхнмхпсер якедсчыхл напюгнл: $$ \matrix{ \multispan{3}\hfill\hbox{Лнлемр $t$}\hfill &\multispan{3}\hfill \hbox{Лнлемр $(t+1)$}\hfill\cr \hbox{Янярнъмхе} & \hbox{Бундш}\hfill\span & \hbox{Янярнъмхе} &\hbox{Бшундш}\hfill\span\cr 0 & 0 & 0 & 0 & 0 & 0\cr 0 & 0 & 1 & 1 & 0 & 1\cr 0 & 1 & 0 & 2 & 0 & 1\cr 0 & 1 & 1 & 0 & 1 & 1\cr 1 & x & y & 1 & x & y\cr 2 & x & y & 2 & y & x\cr } $$ Оепбнмювюкэмн бяе лндскх мюундъряъ б янярнъмхх~0 х бшдючр~$00$. Лндскэ оепеундхр б янярнъмхе~1 хкх~2, йюй рнкэйн ецн бундш ярюмср пюгкхвмшлх. Вхякю, йнрнпше б лнлемр бпелемх~$t$ мювюкх онярсоюрэ ябепус б яерэ, яннрберярбсчысч пхя.~43(b), мювмср б лнлемр~$t+3$ бшбндхрэяъ ямхгс б нрянпрхпнбюммнл \picture{Пхя.~44. Еые ндхм яоняна опедярюбкемхъ янпрхпнбйх онякеднбюрекэмнярх $\langle 4, 1, 3, 2\rangle$ оняпедярбнл яерх, хгнапюфеммни мю пхя.~43.} онпъдйе, еякх бйкчвхрэ яннрберярбсчыхи гюдепфхбючыхи щкелемр б кхмхъу~$K'_1$ х~$K'_4$. Дкъ пюгпюанрйх ренпхх яереи янпрхпнбйх сднамн хгнапюфюрэ ху меяйнкэйн хмшл яонянанл (пхя.~44). Мю щрнл пхясмйе вхякю онярсоючр якебю, ю йнлоюпюрнпмше лндскх хгнапюфемш бепрхйюкэмшлх янедхмемхълх лефдс дбслъ опълшлх; йюфдши %%268 йнлоюпюрнп бшгшбюер, еякх менаундхлн, оепеярюмнбйс ябнху бунднб рюйхл напюгнл, врн оняке опнунфдемхъ йнлоюпюрнпю анкэьее вхякн нйюгшбюеряъ мю мхфмеи кхмхх. Б опюбни вюярх дхюцпюллш бяе вхякю сонпъднвемш ябепус бмхг. Пюмее, хгсвюъ норхлюкэмсч янпрхпнбйс, лш сдекъкх нямнбмне бмхлюмхе лхмхлхгюжхх вхякю япюбмемхи, онврх (хкх янбяел) \picture{Пхя.~45. Онксвемхе $(n+1)$-щкелемрмнцн янпрхпнбыхйю хг $n$-щкелемрмнцн: (a)---бярюбйю; (b)---бшанп.} ме свхршбюъ оепелеыемхе дюммшу хкх якнфмнярэ ярпсйрспш пеьемхи лерндю янпрхпнбйх. Б щрнл нрмньемхх яерх янпрхпнбйх хлечр мейнрнпне опехлсыеярбн, рюй йюй дюммше лнцср упюмхрэяъ б $n$~ъвеийюу, ю ярпсйрспю пеьемхи "опълнкхмеимю"; мер менаундхлнярх гюонлхмюрэ пегскэрюрш опедшдсыху япюбмемхи---окюм мехглемем х тхйяхпнбюм гюпюмее. Еые ндмхл бюфмшл \picture{Пхя.~46. Яеребше юмюкнцх щкелемрюпмшу яуел бмсрпеммеи янпрхпнбйх, онксвеммше лмнцнйпюрмшл опхлемемхел ноепюжхх, опедярюбкеммни мю пхя.~45: (a)---опнярюъ бярюбйю; (b)---лернд осгшпэйю.} опехлсыеярбнл яереи янпрхпнбйх ъбкъеряъ рн, врн вюярэ ноепюжхи лнфмн янблеярхрэ, еякх бшонкмърэ ху ндмнбпелеммн (мю ондундъыеи люьхме). Мюопхлеп, оърэ ьюцнб мю пхя.~43 х~44 янйпюыючряъ дн рпеу, еякх дносярхрэ ндмнбпелеммше меоепейпшбючыхеяъ япюбмемхъ, рюй йюй лнфмн на╝едхмхрэ оепбше дбю х якедсчыхе дбю ьюцю; онгдмее б дюммнл осмйре лш хяонкэгсел %%269 щрн ябниярбн яереи янпрхпнбйх. Рюйхл напюгнл, яерх янпрхпнбйх лнцср ашрэ нвемэ онкегмш, унръ бнглнфмнярэ онярпнемхъ щттейрхбмни яерх янпрхпнбйх $n$~щкелемрнб опх анкэьху~$n$ бнбяе ме нвебхдмю; бнглнфмн, лш намюпсфхл, врн дкъ онддепфюмхъ ндмнпндмни ярпсйрспш пеьемхи рпеасеряъ лмнцн днонкмхрекэмшу япюбмемхи. Хлееряъ дбю опняршу яонянаю онярпнемхъ яерх янпрхпнбйх. дкъ $n+1$~щкелемрнб, еякх дюмю яерэ дкъ $n$~щкелемрнб: я хяонкэгнбюмхел кхан опхмжхою \emph{бярюбйх,} кхан опхмжхою \emph{бшанпю.} Мю \picture{Пхя.~47. Опх оюпюккекэмнл бшонкмемхх ноепюжхи опнярюъ бярюбйю янбоюдюер я лернднл осгшпэйю!} пхя.~45(a) онйюгюмн, йюй $(n+1)\hbox{-и}$~щкелемр лнфер ашрэ бярюбкем мю мсфмне леярн оняке рнцн, йюй оепбше $n$~щкелемрнб нрянпрхпнбюмш, ю мю пхя.~45(b) онйюгюмн, йюй лнфмн бшапюрэ мюханкэьхи щкелемр, опефде вел оепеирх й янпрхпнбйе нярюкэмшу. Лмнцнйпюрмне опхлемемхе пхя.~45(a) дюер яеребни юмюкнц опняршу бярюбнй (юкцнпхрл~5.2.1S), ю лмнцнйпюрмне опхлемемхе пхя.~45(b) опхбндхр й яеребнлс юмюкнцс лерндю осгшпэйю (юкцнпхрл~5.2.2B). Мю пхя.~46 хгнапюфемш яннрберярбсчыхе яерх дкъ ьеярх щкелемрнб. Хмрепеямн гюлерхрэ, врн еякх яфюрэ йюфдсч яерэ, врнаш наеяоевхрэ ндмнбпелеммше ноепюжхх, рн наю лерндю ябедсряъ й ндмни х рни фе "рпесцнкэмни" опнжедспе я $(2n-3)$~ярюдхълх (пхя.~47). Кецйн днйюгюрэ, врн яерх, опедярюбкеммше мю пхя.~43 х~44, асдср янпрхпнбюрэ кчане лмнфеярбн хг вершпеу вхяек, оняйнкэйс оепбше вершпе йнлоюпюрнпю мюопюбкъчр мюхлемэьхи х мюханкэьхи щкелемрш мю онкнфеммше хл леярю, ю онякедмхи йнлоюпюрнп пюяонкюцюер б рпеаселнл онпъдйе нярюкэмше дбю щкелемрю. Ндмюйн ме бяецдю рюй кецйн яйюгюрэ, асдер кх дюммюъ яерэ янпрхпнбюрэ бяе бнглнфмше бундмше онякеднбюрекэмнярх; мюопхлеп, яерх \picture{p.269} ъбкъчряъ опюбхкэмшлх вершпеущкелемрхшлх яерълх янпрхпнбйх, мн днйюгюрекэярбн ху опюбхкэмнярх мерпхбхюкэмн. Ашкн аш %%270 днярюрнвмн опнбепхрэ йюфдсч $n$-щкелемрмсч яерэ мю бяеу $n!$~оепеярюмнбйюу $n$~пюгкхвмшу вхяек, мн тюйрхвеяйх лш лнфел нанирхяэ гмювхрекэмн лемэьхл йнкхвеярбнл опнбепнй. \proclaim Ренпелю~Z. (Опхмжхо мскеи х едхмхж.) Еякх яерэ я $n$~бундюлх янпрхпсер б месашбючыел онпъдйе бяе $2^n$~онякеднбюрекэмняреи хг~0 х~1, рн нмю асдер янпрхпнбюрэ б месашбючыел онпъдйе кчасч онякеднбюрекэмнярэ $n$~вхяек. \proof (Щрн вюярмши яксвюи ренпелш Аспхяхсяю, соп.~5.3.1-12.) Еякх~$f(x)$---кчаюъ лнмнрнммюъ тсмйжхъ, дкъ йнрнпни~$f(x)\le f(y)$ опх~$x\le y$, х еякх дюммюъ яерэ опенапюгсер~$\< x_1,~\ldots, x_n>$ б~$\$, рн, йюй мерпсдмн бхдерэ, щрю яерэ опенапюгсер~$\$ б~$\$. Еякх~$y_i>y_{i+1}$ опх мейнрнпнл~$i$, рн пюяялнрпхл лнмнрнммсч тсмйжхч~$f$, йнрнпюъ дкъ бяеу вхяек $$, йнрнпюъ ме янпрхпсеряъ дюммни яерэч. Якеднбюрекэмн, еякх бяе онякеднбюрекэмнярх~0 х~1 онддючряъ янпрхпнбйе, рн асдел хлерэ~$y_i\le y_{i+1}$ дкъ бяеу~$1\le i < n$. \proofend Опхмжхо мскеи х едхмхж днбнкэмн онкегем дкъ онярпнемхъ яереи янпрхпнбйх. Б йювеярбе мерпхбхюкэмнцн опхлепю онксвхл нанаыеммши бюпхюмр "налеммни янпрхпнбйх ян якхъмхел" Ащрвепю (юкцнпхрл~5.2.2Л). Хдеъ янярнхр б рнл, врнаш янпрхпнбюрэ $m+n$~щкелемрнб, "янпрхпсъ оепбше~$m$ х онякедмхе~$n$ щкелемрнб мегюбхяхлн х гюрел опхлемъъ й пегскэрюрс \dfn{$(m, n)$-яерэ якхъмхъ.} Онярпнхрэ $(m, n)$-яерэ якхъмхъ лнфмн он хмдсйжхх: {\medskip\narrower \item{a)}~Еякх~$m=0$ хкх~$n=0$, рн яерэ осярюъ. Еякх~$m=n=1$, рн яерэ янярнхр хг едхмярбеммнцн йнлоюпюрнпмнцн лндскъ. \item{b)}~Еякх~$mn>1$, рн нангмювхл якхбюелше онякеднбюрекэмнярх $\$ х~$\$. Янкэел "мевермше онякеднбюрекэмнярх"~$\$ х~$\$ х онксвхл нрянпрхпнбюммши пегскэрюр~$\$; янкэел "вермше онякеднбюрекэмнярх"~$\$ х~$\$ х онксвхл нрянпрхпнбюммши пегскэрюр~$\$. Х мюйнмеж, опхлемхл ноепюжхх япюбмемхъ-налемю $$ w_1:v_2, w_2:v_3, w_3:v_4, w_{\floor{m/2}+\floor{n/2}}:v^* \eqno(1) $$ й онякеднбюрекэмнярх $$ \; \eqno(2) $$ пегскэрюр асдер нрянпрхпнбюм. (!) (Гдеяэ~$v^*=v_{\floor{m/2}+\floor{n/2}+1}$ ме ясыеярбсер, еякх~$m$ х~$n$ наю вермше, х~$v^{**}=v_{\floor{m/2}+\floor{n/2}+2}$ %% 271 ясыеярбсер, кхьэ еякх~$m$ х~$n$ наю мевермше; наыее вхякн йнлоюпюрнпмшу лндскеи, сйюгюммшу б~(1), пюбмн~$\floor{(m+n)-1)/2}$.) \medskip} \noindent Мюгнбел $(m, n)$-яерэ якхъмхъ Ащрвепю \dfn{вермн-мевермшл якхъмхел.} Онярпнеммне б яннрберярбхх я щрхлх опхмжхоюлх $(4, 7)$-якхъмхе онйюгюмн мю пхя.~48. \picture{Пхя. 48. Вермн-мевермне якхъмхе дкъ~$m=4$ х~$n=7$.} Врнаш днйюгюрэ, врн щрю нвемэ ярпюммюъ опнжедспю деиярбхрекэмн пюанрюер опх~$mn>1$, бняонкэгселяъ опхмжхонл мскеи х едхмхж х опнбепхл ее мю бяеу онякеднбюрекэмняръу~0 х~1. Оняке мювюкэмшу $m$-янпрхпнбйх х $n$-янпрхпнбйх онякеднбюрекэмнярэ~$\$ асдер янярнърэ хг $k$~мскеи, гю йнрнпшлх якедсчр $m-k$~едхмхж, ю онякеднбюрекэмнярэ~$\$---хг $l$~мскеи я онякедсчыхлх $n-l$~едхмхжюлх опх мейнрнпшу~$k$ х~$l$. Якеднбюрекэмн, онякеднбюрекэмнярэ~$\$ асдер янярнърэ хг~$\ceil{k/2}+\ceil{l/2}$~мскеи я онякедсчыхлх едхмхжюлх, ю $\$---хг $\floor{k/2}+\floor{l/2}$~мскеи я онякедсчыхлх едхмхжюлх. Пеьючыхл лнлемрнл днйюгюрекэярбю ъбкъеряъ рн, врн $$ (\ceil{k/2}+\ceil{l/2})-(\floor{k/2}+\floor{l/2})=0, 1 \hbox{ хкх } 2. \eqno(3) $$ Еякх щрю пюгмнярэ пюбмю~0 хкх~1, рн онякеднбюрекэмнярэ~(2) сфе сонпъднвемю, ю еякх нмю пюбмю~2, рн ндмю хг ноепюжхи япюбмемхъ-налемю б~(1) ярюбхр бяе мю ябнх леярю. Днйюгюрекэярбн гюбепьемн. (Гюлерхл, врн опхмжхо мскеи х едхмхж ябндхр $\perm{m+n}{m}$~яксвюеб б гюдюве якхъмхъ бяецн кхьэ й~$(m+1)(n+1)$, йюфдши хг йнрнпшу хгнапюфюеряъ дбслъ оюпюлерпюлх~$k$ х~$l$.) Осярэ~$C(m, n)$---вхякн йнлоюпюрнпмшу лндскеи, хяонкэгселшу опх вермн-мевермнл якхъмхх $m$ х $n$~щкелемрнб, ме явхрюъ %%272 мювюкэмшу $m$- х~$n$-янпрхпнбнй; хлеел $$ C(m,n)=\cases{ mn, & еякх $mn\le 1$;\cr C(\ceil{m/2}, \ceil{n/2})+C(\floor{m/2}, \floor{n/2})+ \floor{(m+n-1)/2}, & еякх $mn>1$.\cr } \eqno(4) $$ Б наыел яксвюе щрн ме якхьйнл опнярюъ тсмйжхъ нр~$m$ х~$n$, ндмюйн, гюлерхб, врн~$C(1, n)=n$ х врн $$ C(m+1, n+1)-C(m,n)= =1+C(\floor{m/2}+1, \floor{n/2}+1)-C(\floor{m/2}, \floor{n/2}), \rem{еякх $mn\ge 1$}, $$ лш лнфел бшбеярх яннрмньемхе $$ C(m+1, n+1)-C(m,n)=t+2+\floor{n/2^{t+1}}, \rem{еякх~$n\ge m \ge 1$ х~$t=\floor{\log_2 m}$.} \eqno(5) $$ Якеднбюрекэмн, $$ C(m, m+r)=B(m)+m+R_m(r) \rem{опх $m\ge0$, $r\ge0$,} \eqno (6) $$ цде $B(m)$~еярэ тсмйжхъ "ахмюпмни бярюбйх"~$\sum_{1\le k\le m}\ceil{\log_2 k}$ хг яннрмньемхъ~(5.3.1-3), ю $R_m(r)$~нангмювюер ясллс оепбшу нр вкемнб пъдю $$ \floor{{r+0\over1}}+\floor{{r+1\over2}}+\floor{{r+2\over4}}+ \floor{{r+3\over4}}+\floor{{r+4\over8}}+\cdots+ \floor{{r+j\over2^{\floor{\log_2 j}+1}}}+\ldots\,. \eqno(7) $$ Еякх фе~$r=0$, онксвюел бюфмши вюярмши яксвюи $$ C(m,m)=B(m)+m. \eqno(8) $$ Йпнле рнцн, еякх~$t=\ceil{\log_2 m}$, рн $$ \eqalign{ R_m(r+2^t) &= R_m(r)+1\cdot 2^{t-1}+2\cdot 2^{t-2}+\cdots+2^{t-1}\cdot2^0+m=\cr &= R_m(r)+m+t\cdot 2^{t-1}. } $$ Якеднбюрекэмн, $C(m, n+2^t)-C(m, n)$~хлеер опнярни бхд х $$ C(m, n)=\left({t\over2}+{m\over 2^t}\right) n+O(1)\rem{ опх тхйяхпнбюммнл~$m$, $n\to\infty$, $t=\ceil{\log_2 m}$;} \eqno (9) $$ вкем~$O(1)$ ярюмнбхряъ б йнмже йнмжнб оепхндхвеяйни тсмйжхеи нр~$n$ я дкхмни оепхндю~$2^t$. Юяхлорнрхвеяйх опх~$n\to\infty$ бекхвхмю~$C(n, n)$ пюбмю~$n \log_2 n$ хг~(8) х соп.~5.3.1-15. \section Яерх я лхмхлюкэмшл вхякнл япюбмемхи. Осярэ~$\hat S(n)$---лхмхлюкэмне вхякн япюбмемхи, рпеаселшу б яерх янпрхпнбйх дкъ $n$~щкелемрнб; ъямн, врн~$\hat S(n)\ge S(n)$, цде~$S(n)$---лхмхлюкэмне вхякн япюбмемхи, %%273 менаундхлне дкъ янпрхпнбйх аег бяъйху нцпюмхвемхи (ял.~о.~5.3.1). Лш бхдекх, врн~$\hat S(4)=5=S(4)$, онщрнлс мнбне нцпюмхвемхе ме бшгшбюер онрепх щттейрхбмнярх опх~$n=4$; мн сфе опх~$n=5$ нйюгшбюеряъ, врн~$\hat S(5)=9$, б рн бпелъ йюй~$S(5)=7$. Гюдювю нопедекемхъ~$\hat S(n)$ йюферяъ еые анкее рпсдмни, вел гюдювю нопедекемхъ~$S(n)$; дн яху онп мехгбеярмн дюфе юяхлорнрхвеяйне онбедемхе~$\hat S(n)$. Хмрепеямн опнякедхрэ хярнпхч щрни гюдювх, рюй йюй мю йюфдши мнбши ьюц опхундхкняэ гюрпювхбюрэ нопедекеммше сяхкхъ. Яерх янпрхпнбйх ашкх боепбше хяякеднбюмш О.~М.~Юплярпнмцнл, П.~Дф.~Мекэянмнл х Д.~Дф.~Н'Йнммнпнл нйнкн 1954~ц. [ял.~U.~S.~Patent 3029413]; нмх онйюгюкх, врн~$\hat S(n+1)\le \hat S(n)+n$. Йюй яйюгюмн б ху оюремрмни гюъбйе, "опхкнфхб ярюпюмхъ, лнфмн яйнмярпсхпнбюрэ щйнмнлхвмше $n$-бундмше янпрхпсчыхе оепейкчвюрекх, хяонкэгсъ слемэьеммне вхякн дбсубундмшу янпрхпсчыху оепейкчвюрекеи"; нмх опхбекх опхлепш йнмярпсйжхи дкъ~$4\le n \le 8$, хяонкэгнбюб яннрберярбеммн 5, 9, 12, 18 х 19~йнлоюпюрнпнб. Пюанрюъ дюкее мюд щрни гюдювеи, Мекэянм янблеярмн я П.~В.~Анге еые дн~1960~ц. пюгпюанрюкх наысч опнжедспс дкъ онярпнемхъ яереи янпрхпнбйх, онйюгшбючысч, врн~$\hat S(2^n)\le3^n-2^n$ опх бяеу~$n$, онщрнлс~$\hat S(n)=O(n^{\log_2 3})=O(n^{1.585})$. Анге х~Мекэянм носакхйнбюкх ябни хмрепеямши лернд б {\sl JACM,\/} {\bf 9} (1962), 282--296, бшяйюгюб опедонкнфемхе, врн щрн мюхксвьхи бнглнфмши пегскэрюр; Р.~М.~Ухааюпд [{\sl JACM,\/} {\bf 10} (1963), 142--150] мюьек юмюкнцхвмши, мн меяйнкэйн анкее опнярни лернд, б йнрнпнл хяонкэгсеряъ рюйне фе вхякн япюбмемхи, ондйпеохб рел яюлшл щрн опедонкнфемхе. Б 1964~ц.\ П.~С.~Ткнид х~Д.~Щ.~Ймср хяонкэгнбюкх мнбши ондунд й щрни гюдюве, опхбедьхи ху й юяхлорнрхвеяйни нжемйе бхдю~$\hat S(n)=O(n^{1+c/\sqrt{\log n}})$. Пюанрюъ мегюбхяхлн, Й.~Щ.~Ащрвеп нрйпшк нохяюммсч бшье наысч ярпюрецхч якхъмхъ; хяонкэгсъ вхякн йнлоюпюрнпнб, нопедекъелне йюй $$ c(1)=0, c(n)=c(\ceil{n/2})+c(\floor{n/2})+C(\ceil{n/2}, \floor{n/2}) \rem{опх $n\ge2$,} \eqno (10) $$ нм днйюгюк, врн (ял.~соп.~5.2.2-14) $$ c(2^t)=(t^2-t+4)2^{t-2}-1, $$ х нрячдю бшбек, врн~$\hat S(n)=O(n(\log n)^2)$. Йюй Ащрвеп, рюй х Ткнид я Ймсрнл носакхйнбюкх ябнх йнмярпсйжхх кхьэ вепег мейнрнпне бпелъ [{\sl Notices of the Amer.\ Math.\ Soc.,\/} {\bf 14} (1967), 283; Proc.\ AFIPS Spring Joint Computer Conference, {\bf 32} (1968), 307--314]. %%274 Йне-йнлс сдюкняэ янйпюрхрэ вхякн йнлоюпюрнпнб, хяонкэгселшу б йнмярпсйжхх якхъмхъ я налемюлх, опедкнфеммни Ащрвепнл; б якедсчыеи рюакхже онйюгюмш дюхксвьхе хг хгбеярмшу б мюярнъыее бпелъ бепумху нжемнй дкъ~$\hat S(n)$: $$ \matrix{ \hfill n=1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 \cr \hfill c(n)=0 & 1 & 3 & 5 & 9 & 12 & 16 & 19 & 26 & 31 & 37 & 41 & 48 & 53 & 59 & 63 \cr \hfill \hat S(n)\le 0 & 1 & 3 & 5 & 9 & 12 & 16 & 19 & 25 & 29 & 35 & 39 & 46 & 51 & 56 & 60\cr } \eqno(11) $$ Рюй йюй~$\hat S(n)8$. Еякх~$n\le 8$, рн рюйюъ янпрхпнбйю щйбхбюкемрмю он йнкхвеярбс йнлоюпюрнпнб йнмярпсйжхх Анге х~Мекэянмю. Ткнид х~Ймср днйюгюкх б 1964--1966~цц., врн сйюгюммше гмювемхъ~$\hat S(n)$ \emph{рнвмш} опх~$n<8$ [ял.\ A Survey of Combinatorial Theory (North-Holland, 1973), 163--172]; гмювемхъ~$\hat S(n)$ опх~$n>8$ дн яху онп мехгбеярмш. Йнмярпсйжхх, опхбндъыхе й сйюгюммшл бшье гмювемхъл дкъ~$\hat S(n)$, хгнапюфемш мю пхя.~49. Яерэ опх~$n=9$, нямнбюммюъ мю хмрепеямнл рпеуосребнл якхъмхх, ашкю мюидемю П.~С.~Ткниднл б 1964~ц.; сярюмнбхрэ ее яопюбедкхбнярэ лнфмн опх онлных наыецн опхмжхою, нохяюммнцн б соп.~27. Яерэ опх~$n=10$ б~1969~ц.\ онярпнхк Ю.~Бюйялюм; нм пюяялюрпхбюк бундш йюй оепеярюмнбйх лмнфеярбю~$\set{1, 2,~\ldots, 10}$ х ошрюкяъ, янупюмъъ мейнрнпсч яхллерпхч, мюяйнкэйн бнглнфмн слемэьхрэ вхякн гмювемхи, йнрнпше лнцср онъбкърэяъ б йюфдни ярпнйе мю дюммни ярюдхх. Б 1969~ц. Ц.~Ьюохпн мюьек яерэ янпрхпнбйх 16~щкелемрнб я 62~йнлоюпюрнпюлх, х щрн ашкн беяэлю менфхдюммн, оняйнкэйс лернд Ащрвепю (63~япюбмемхъ), йюгюкняэ, хяонкэгсер бяе бнглнфмнярх, еякх $n$~ъбкъеряъ яреоемэч~2. Л.~С.~Цпхм бяйнпе оняке рнцн, йюй нм нгмюйнлхкяъ я йнмярпсйжхеи Ьюохпн, онбепц бяеу б еые анкэьее хгслкемхе, мюидъ янпрхпнбйс я 60~япюбмемхълх, онйюгюммсч мю пхя.~49. Оепбюъ вюярэ йнмярпсйжхх Цпхмю днбнкэмн опнярю дкъ онмхлюмхъ; оняке рнцн йюй бшонкмемш 32~ноепюжхх япюбмемхъ-налемю якебю нр осмйрхпмни кхмхх, бяе опълше лнфмн рюй онлерхрэ 16~ондлмнфеярбюлх~$\set{a, b, c, d}$, врнаш опн опълсч, онлевеммсч~$s$, ашкн хгбеярмн, врн нмю яндепфхр вхякю, лемэьхе хкх пюбмше яндепфхлнлс опълни, онлевеммни~$t$, бяъйхи пюг, йнцдю $s$~еярэ ондлмнфеярбн~$t$. Янярнъмхе янпрхпнбйх б щрнр лнлемр наясфдюеряъ анкее ондпнамн б соп.~32. Ндмюйн япюбмемхъ, бшонкмъелше мю онякедсчыху спнбмъу, ярюмнбъряъ янбепьеммн гюцюднвмшлх, х дн яху онп мхйрн ме гмюер, йюй нанаыхрэ щрс йнмярпсйжхч, врнаш онксвхрэ ярнкэ фе щттейрхбмше яерх дкъ анкэьху гмювемхи~$n$. %%275 Ьюохпн х Цпхм нрйпшкх рюйфе хгнапюфеммсч мю пхя.~49 яерэ дкъ~$n=12$. Унпньхе яерх дкъ~$n=11$, 13, 14 х~15 лнфмн онксвхрэ, сдюкхб мхфмчч опълсч яерх дкъ~$n+1$ блеяре ян бяелх йнлоюпюрнпюлх, ондянедхмеммшлх й щрни кхмхх. \picture{Пхя. 49. Щттейрхбмше яерх янпрхпнбйх.} Мюхксвьхе хгбеярмше й мюярнъыелс лнлемрс яерх дкъ~$n\to\infty$ ял.~б днйрнпяйни дхяяепрюжхх Д.~Бюм~Бнпхяю (Stanford University, 1971); ецн яерх рпеасчр юяхлорнрхвеяйх %% 276 ${1\over 4}n(\log_2 n)^2-\alpha n \log_2 n$~йнлоюпюрнпнб, цде~$\alpha={1\over4}+{1\over6}\sum_{k\ge0}2^{-2^k-k}\approx0.356~852$. \section Яерх я лхмхлюкэмшл бпелемел. Б тхгхвеяйху пеюкхгюжхъу яереи янпрхпнбйх х мю оюпюккекэмшу ЩБЛ лнфмн бшонкмърэ меоепеяейючыхеяъ ноепюжхх япюбмемхъ-налемю ндмнбпелеммн, онщрнлс йюферяъ еяреярбеммшл оношрюрэяъ лхмхлхгхпнбюрэ бпелъ гюдепфйх. Он мейнрнпнл пюглшькемхх гюйкчвюел, врн бпелъ гюдепфйх яерх янпрхпнбйх пюбмн люйяхлюкэмнлс вхякс йнлоюпюрнпнб, опхкецючыху й йюйнлс-кхан "осрх" вепег яерэ, еякх нопедекхрэ осрэ йюй рпюейрнпхч кчанцн дбхфемхъ якебю мюопюбн, \picture{Пхя.~50. Бшонкмемхе йюфднцн япюбмемхъ б мюханкее пюммхи хг бнглнфмшу лнлемрнб.} бнглнфмн, я оепеунднл я ндмни опълни мю дпсцсч вепег йнлоюпюрнпш. С йюфднцн йнлоюпюрнпю лш лнфел онярюбхрэ онпъдйнбши мнлеп, сйюгшбючыхи яюлши пюммхи лнлемр, йнцдю лнфер ашрэ бшонкмемн япюбмемхе; щрнр мнлеп мю едхмхжс анкэье, вел люйяхлюкэмши мнлеп с йнлоюпюрнпнб, опедьеярбсчыху дюммнлс. (Ял.~пхя.~50(a); б вюярх~(b) щрнцн пхясмйю онйюгюмю рю фе яерэ, оепепхянбюммюъ рюй, врнаш йюфдне япюбмемхе бшонкмъкняэ б мюханкее пюммхи бнглнфмши лнлемр.) Б нохяюммни бшье яерх Ащрвепю дкъ вермн-мевермнцн якхъмхъ гюрпювхбюеряъ $T_b(m,n)$~едхмхж бпелемх, цде~$T_b(m,0)=T_b(0, n)=0$, $T_B(1,1)=1$ х $$ T_B(m, n)=1+\max(T_B(\floor{m/2}, \floor{n/2}), T_B(\ceil{m/2}, \ceil{n/2})) \rem{дкъ~$mn\ge 2$.} $$ Хяонкэгсъ щрх яннрмньемхъ, лнфмн днйюгюрэ он хмдсйжхх, врн~$T_B(m, n+1)\ge T_B(m,n)$; якеднбюрекэмн, $T_B(m, n)=1+T_B(\ceil{m/2}, \ceil{n/2})$ дкъ~$mn\ge2$, ю нрячдю гюйкчвюел, врн $$ T_B(m,n)=1+\ceil{\log_2 \max (m,n)} \rem{дкъ $mn\ge1$.} \eqno (12) $$ Рюйхл напюгнл, йюй онйюгюмн б соп.~5, лернд янпрхпнбйх Ащрвепю хлеер бпелъ гюдепфйх $$ \perm{1+\ceil{\log_2 n}}{2}. \eqno(13) $$ %%277 Осярэ $\hat T(n)$---лхмхлюкэмне бпелъ гюдепфйх, днярхфхлне б кчани яерх янпрхпнбйх $n$~щкелемрнб. Мейнрнпше хг нохяюммшу бшье яереи лнфмн сксвьхрэ, ме хяонкэгнбюб днонкмхрекэмшу йнлоюпюрнпнб, рюй, врнаш нмх хлекх лемэьее бпелъ гюдепфйх, йюй \picture{Пхя.~51. Яерх янпрхпнбйх, йнрнпше менашймнбеммн ашярпш, еякх япюбмемхъ бшонкмъчряъ оюпюккекэмн.} онйюгюмн мю пхя.~51 дкъ~$n=6$ х~$n=9$, ю б соп.~7---дкъ~$n=10$. Лнфмн онксвхрэ еые лемэьее бпелъ гюдепфйх, еякх днаюбхрэ ндхм хкх дбю днонкмхрекэмшу лндскъ, йюй онйюгшбючр яерх дкъ~$n=10$, 12 х~16 мю пхя.~51. Щрх онярпнемхъ опхбндър й якедсч- %%378 ыхл бепумхл нжемйюл дкъ~$T(n)$ опх слепеммшу гмювемхъу~$n$: $$ \matrix{ \hfill n=1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16\cr \hfill \hat T(n)\le 0 & 1 & 3 & 3 & 5 & 5 & 6 & 6 & 7 & 7 & 8 & 8 & 9 & 9 & 9 & 9\cr } \eqno(14) $$ Хгбеярмн, врн опхбедеммше гдеяэ гмювемхъ рнвмш опх~$n\le 8$ (ял.~соп.~4). Яерх мю пхя.~51 гюяксфхбючр рыюрекэмнцн хгсвемхъ, оняйнкэйс бнбяе ме нвебхдмн, врн нмх цндъряъ дкъ янпрхпнбйх; щрх яерх ашкх нрйпшрш б~1969--1971~цц. Ц.~Ьюохпн ($n=6$, 9, 12) х~Д.~Бюм~Бнпхянл ($n=10$, 16). \section Яерх якхъмхъ. Осярэ $\hat M(m, n)$~нангмювюер лхмхлюкэмне вхякн йнлоюпюрнпнб, менаундхлшу дкъ яерх, йнрнпюъ якхбюер $m$~щкелемрнб~$x_1~\le~\ldots \le x_m$ я~$n$~щкелемрюлх~$y_1\le\ldots \le y_n$, напюгсъ нрянпрхпнбюммсч онякеднбюрекэмнярэ~$z_1\le \ldots \le z_{m+n}$. Й мюярнъыелс бпелемх ме нрйпшрн мх ндмни яерх якхъмхъ, йнрнпюъ ашкю аш ксвье вермн-мевермнцн якхъмхъ, нохяюммнцн бшье; якеднбюрекэмн, тсмйжхъ~$C(m, n)$ б~(6) опедярюбкъер мюхксвьсч хгбеярмсч бепумчч нжемйс дкъ~$\hat M(m, n)$. П.~С.~Ткнид намюпсфхк хмрепеямши яоняна, онгбнкъчыхи нопедекхрэ \emph{мхфмхе} нжемйх б щрни гюдюве якхъмхъ. \proclaim Ренпелю~F. Опх бяеу~$n\ge 1$ яопюбедкхбн мепюбемярбн~$\hat M (2n, 2n)\ge 2\hat M(n, n)+n$. \proof Пюяялнрпхл яерэ я~$\hat M(2n, 2n)$~йнлоюпюрнпмшлх лндскълх, яонянамсч янпрхпнбюрэ бяе бундмше онякеднбюрекэмнярх~$\$, рюйхе, врн~$z_1\le z_3\le\ldots \le z_{4n-1}$ х~$z_2\le z_4\le\ldots\le z_{4n}$. Лш лнфел явхрюрэ, врн йюфдши лндскэ гюлемъер~$(z_i, z_j)$ мю~$(\min(z_i, z_j, \max(z_i, z_j))$ опх мейнрнпшу~$i2n$ х~$j>2n$; \item{c)}~$i\le 2n$ х~$j>2n$. \medskip} Йкюяя~(a) днкфем яндепфюрэ он йпюимеи лепе $\hat M(n, n)$~йнлоюпюрнпнб, рюй йюй $z_{2n+1}$, $z_{2n+2}$,~\dots, $z_{4n}$ лнцср сфе мюундхрэяъ мю ябнху леярюу, йнцдю якхъмхе мювхмюеряъ; юмюкнцхвмн б йкюяяе~(b) днкфмн ашрэ он йпюимеи лепе $\hat M(n, n)$~йнлоюпюрнпнб. Йпнле рнцн, йюй онйюгшбюер бундмюъ онякеднбюрекэмнярэ~$\<0, 1, 0, 1,~\ldots, 0, 1>$, йкюяя~(c) яндепфхр ме лемее $n$~йнлоюпюрнпнб, рюй йюй $n$~мскеи днкфмш оепелеярхрэяъ хг~$\set{z_{2n+1},~\ldots, z_{4n}}$ б~$\set{z_1,~\ldots, z_{2n}}$. \proofend Лмнцнйпюрмне опхлемемхе ренпелш~F днйюгшбюер, врн~$\hat M(2^m, 2^m)\ge{1\over2}(m+2) 2^m$; якеднбюрекэмн, $\hat M(n, n) \ge {1\over2}n \log_2 n+O(n)$. %%279 Якхъмхе \emph{аег} яеребнцн нцпюмхвемхъ рпеасер кхьэ $M(n,n)=2n-1$~япюбмемхи; рюйхл напюгнл, лш днйюгюкх, врн яеребне якхъмхе якнфмее он ясыеярбс, вел якхъмхе бннаые. Вермн-мевермне якхъмхе онйюгшбюер, врн~$\hat M(n,n)\le C(n, n)= n\log_2 n+O(n)$, онщрнлс юяхлорнрхвеяйне онбедемхе~$\hat M(n, n)$ хгбеярмн я рнвмнярэч дн лмнфхрекъ~2. (Рнвмше гмювемхъ~$\hat M(n, n)$ хгбеярмш дкъ~$n\le 5$; ял.~соп.~9.) Ю.~Й.~Ън х~Т.~Т.~Ън днйюгюкх, врн~$\hat M(2,n)=C(2, n)=\ceil{{3\over2}n}$ х~$\hat M(m, n)\ge{1\over2}n\log_2(m+1)$ опх~$m$ хг $p$~вхяек асдел мюгшбюрэ \dfn{ахрнммни,} еякх~$z_1\ge\ldots\ge z_k\le\ldots\le z_p$ дкъ мейнрнпнцн~$k$, $1\le k \le p$ (япюбмхре щрн я нашвмшл нопедекемхел "лнмнрнммшу" онякеднбюрекэмняреи). Ахрнммши янпрхпнбыхй онпъдйю~$p$---щрн йнлоюпюрнпмюъ яерэ, яонянамюъ янпрхпнбюрэ б месашбючыел онпъдйе кчасч ахрнммсч онякеднбюрекэмнярэ дкхмш~$p$. Гюдювю якхъмхъ~$x_1\le\ldots\le x_m$ я~$y_1\le\ldots\le y_n$ ъбкъеряъ вюярмшл яксвюел гюдювх ахрнммни янпрхпнбйх, рюй йюй якхъмхе лнфмн нясыеярбхрэ, опхлемхб й онякеднбюрекэмнярх~$\$ ахрнммши янпрхпнбыхй онпъдйю~$m+n$. Гюлерхл, врн еякх онякеднбюрекэмнярэ~$\$ ахрнммюъ, рн рюйнбшлх фе ъбкъчряъ х бяе ее ондонякеднбюрекэмнярх. Бяйнпе оняке рнцн, йюй Ащрвеп нрйпшк яерх вермн-мевермнцн якхъмхъ, нм намюпсфхк, врн юмюкнцхвмшл напюгнл лнфмн онярпнхрэ ахрнммши янпрхпнбыхй онпъдйю~$p$, ямювюкю мегюбхяхлн янпрхпсъ ахрнммше ондонякеднбюрекэмнярх~$\$ х~$\$, ю гюрел бшонкмъъ япюбмемхъ-налемш~$z_1:z_2$, $z_3:z_4$,~$\ldots\,$. (Днйюгюрекэярбн ял.~б~соп.~10.) Еякх яннрберярбсчыее вхякн йнлоюпюрнпмшу лндскеи нангмювхрэ вепег~$C'(p)$, рн асдел хлерэ $$ C'(p)=C'(\ceil{p/2})+C'(\floor{p/2})+\floor{p/2} \rem{опх $p\ge2$.} \eqno (15) $$ ю бпелъ гюдепфйх, нвебхдмн, пюбмн~$\ceil{\log_2 p}$. Мю~пхя.~52 онйюгюм ахрнммши янпрхпнбыхй онпъдйю~7, онярпнеммши щрхл яонянанл; нм лнфер ашрэ хяонкэгнбюм х йюй~$(3, 4)$, х йюй $(2, 5)\hbox{-яерэ}$ якхъмхъ я гюдепфйни б рпх едхмхжш; вермн-мевермне якхъмхе дкъ~$m=2$ х~$n=5$ хлеер мю ндхм йнлоюпюрнп лемэье, мн мю ндхм спнбемэ гюдепфйх анкэье. %%280 Ахрнммши янпрхпнбыхй Ащрвепю онпъдйю~$2^k$ нянаеммн хмрепеяем; нм янярнхр хг $k$~спнбмеи он $2^{k-1}$~йнлоюпюрнпнб б йюфднл. Гюмслепсел бундмше опълше~$z_0$, $z_1$,~\dots, $z_{2^k-1}$; опх щрнл щкелемр~2, япюбмхбюеряъ я~$z_j$ мю спнбме~$l$ рнцдю х рнкэйн рнцдю, йнцдю дбнхвмше опедярюбкемхъ~$i$ х~$j$ пюгкхвючряъ рнкэйн б $l\hbox{-л}$~ахре якебю. Щрю опнярюъ ярпсйрспю опхбндхр й оюпюккекэмни яерх янпрхпнбйх, йнрнпюъ рюй фе ашярпю, йюй налеммюъ янпрхпнбйю \picture{Пхя.~52. Ахрнммши янпрхпнбыхй Ащрвепю онпъдйю~7.} ян якхъмхел (юкцнпхрл~5.2.2M), мн гмювхрекэмн опные дкъ пеюкхгюжхх. (Ял.~соп.~11 х~13.) Еякх~$m=n$, рн мерпсдмн бхдерэ, врн х вермн-мевермне якхъмхе, х ахрнммши янпрхпнбыхй Ащрвепю наеяоевхбючр юаянкчрмши лхмхлсл бпелемх гюдепфйх, днярхфхлнцн б кчани яерх якхъмхъ. \picture{Пхя.~53. Ндхм щкелемр якхбюеряъ я ьеярэч дпсцхлх я пюгбербкемхел, врнаш днярхвэ лхмхлюкэмн бнглнфмнцн бпелемх гюдепфйх.} Б $(n, n)$-яерх якхъмхъ $n\hbox{-и}$ он бекхвхме бшунд (явхрюъ нр мюхлемэьецн) днкфем гюбхяерэ нр бяеу $2n$~бунднб, х еякх ецн лнфмн бшвхякхрэ гю $l$~ьюцнб, рн нм асдер гюбхяерэ ме анкее, вел нр $2^l$~бунднб; онщрнлс~$2^l\ge 2n$, $l\ge \ceil{\log_2 (2n)}$. Еякх~$m$ х лш унрхл бшапюрэ $t$~мюханкэьху; Б.~Е.~Юкейяееб [{\sl Йхаепмерхйю,\/} {\bf 5}, 5 (1969), 99--103] гюлерхк, врн щрн лнфер ашрэ бшонкмемн, еякх ямювюкю нрянпрхпнбюрэ~$\$ х~$\$, ю гюрел япюбмхрэ х онлемърэ леярюлх $$ x_1:x_{2t}, x_2:x_{2t-1},~\ldots, x_t:x_{t+1}. \eqno(17) $$ Рюй йюй мх б ндмни хг щрху оюп ме лнфер яндепфюрэяъ анкее ндмнцн хг мюханкэьху $t$~щкелемрнб (онвелс?), рн опнжедспю Юкейяеебю днкфмю бшапюрэ $t$~мюханкэьху щкелемрнб. Еякх мюл мсфмн бшапюрэ $t$~мюханкэьху хг $nt$~щкелемрнб, рн лш лнфел опхлемхрэ щрс опнжедспс $n-1$~пюг (хяйкчвюъ йюфдши пюг $t$~щкелемрнб); якеднбюрекэмн, $$ \hat U_t(nt)\le (n-1)(2\hat S(t)+t). \eqno(18) $$ Юкейяееб рюйфе онксвхк хмрепеямсч \emph{мхфмчч} нжемйс дкъ гюдювх бшанпю. %%282 \proclaim Ренпелю~A. $\hat U_t (n) \ge (n-t)\ceil{\log_2 (t+1)}$. \proof Сднамее пюяялюрпхбюрэ щйбхбюкемрмсч гюдювс бшанпю \emph{мюхлемэьху} $t$~щкелемрнб. Нйнкн йюфдни опълни йнлоюпюрнпмни яерх лнфмн бшохяюрэ вхякю~$(l, u)$, йюй онйюгюмн мю пхя.~54, цде~$l$ х~$u$ нангмювючр яннрберярбеммн лхмхлюкэмне х \picture{Пхя.~54. Нрдекемхе вершпеу мюханкэьху нр вершпеу мюхлемэьху. (Вхякю мюд опълшлх хяонкэгсчряъ б днйюгюрекэярбе ренпелш~A.)} люйяхлюкэмне гмювемхъ, йнрнпше лнцср онъбхрэяъ б щрнл леяре, еякх бунднл яксфхр оепеярюмнбйю~$\set{1, 2,~\ldots, n}$. Осярэ~$l_i$ х~$l_j$---мхфмхе нжемйх мю опълшу~$i$ х~$j$ оепед япюбмемхел~$x_i:x_j$, х осярэ~$l'_i$ х~$l'_j$---яннрберярбсчыхе мхфмхе нжемйх оняке щрнцн \picture{Пхя.~55. Хмюъ хмрепоперюжхъ яерх, хгнапюфеммни мю пхя.~54.} япюбмемхъ. Нвебхдмн, врн~$l'_i=\min(l_i, l_j)$, ю б соп.~24 днйюгшбюеряъ (менвебхдмне) яннрмньемхе $$ l'_j\le l_i+l_j. \eqno (19) $$ Реоепэ дюдхл дпсцсч хмрепоперюжхч деиярбхъ яерх (пхя.~55); опедонкнфхл, врн мю бяеу бундмшу опълшу яндепфхряъ мскэ, %%283 ю йюфдши "йнлоюпюрнп" онлеыюер реоепэ мю бепумчч опълсч лемэьхи хг ецн бунднб, ю мю мхфмчч опълсч---анкэьхи бунд \emph{окчя ндхм.} Онксвючыхеяъ вхякю~$\$ накюдючр ябниярбнл $$ 2^{m_i}\ge l_i \eqno(20) $$ б кчанл леяре яерх, рюй йюй щрн ябниярбн оепбнмювюкэмн яопюбедкхбн х янупюмъеряъ йюфдшл йнлоюпюрнпнл б яхкс~(19). Йпнле рнцн, нйнмвюрекэмне гмювемхе $$ m_1+m_2+\cdots+m_n $$ пюбмн наыелс вхякс йнлоюпюрнпнб б яерх, рюй йюй йюфдши йнлоюпюрнп днаюбкъер й щрни яслле едхмхжс. Еякх яерэ бшахпюер мюхлемэьхе $t$~вхяек, рн~$n-t$ хг вхяек~$l_i$ анкэье хкх пюбмш~$t+1$; якеднбюрекэмн, $n-t$ хг вхяек~$m_i$ днкфмш ашрэ~$\ge \ceil{\log_2 (t+1)}$. \proofend Мхфмъъ нжемйю б ренпеле~A нйюгшбюеряъ рнвмни, еякх~$t=1$ хкх~$t=2$ (ял.~соп.~19). Б рюак.~1 дюмш гмювемхъ~$\hat U_t(n)$, $\hat V_t(n)$ х~$\hat W_t(n)$ дкъ меанкэьху~$t$ х~$n$. \htable{Рюакхжю~1}% {Япюбмемхъ, менаундхлше дкъ яереи бшанпю ($\hat U_t(n)$, $\hat V_t(n)$, $\hat W_t(n)$)}% {\strut\hfill$#$\hfill&&\bskip\hfill$#$\hfill\bskip\cr & t=1 & t=2 & t=3 & t=4 & t=5 & t=6 \cr \noalign{\hrule} n=1 & (0,0,0)\cr n=2 & (1,1,1)& (0,1,1)\cr n=3 & (2,2,2)& (2,3,3)& (0,2,3) \cr n=4 & (3,3,3)& (4,5,5)& (3,5,5) & (0,3,5) \cr n=5 & (4,4,4)& (6,7,7)& (6,7,8) & (4,7,9) & (0,4,9) \cr n=6 & (5,5,5)& (8,9,9)& (8,10,10)& (8,10,12) & (5,9,12) & (0,5,12) \cr \noalign{\hrule} } \excercises (ОЕПБЮЪ ВЮЯРЭ) Дюкее б меяйнкэйху сопюфмемхъу дюмн анкее цксанйне пюгбхрхе ренпхх яереи янпрхпнбйх, онщрнлс асдер сднамн ббеярх мейнрнпше нангмювемхъ. Блеярн лндскъ япюбмемхъ-налемю асдел охяюрэ~$[i:j]$. Яерэ я $n$~бундюлх х $r$~йнлоюпюрнпмшлх лндскълх гюохьел йюй~$[i_1:j_1]\,[i_2:j_2]\ldots[i_r:j_r]$, цде бяе~$i$ х~$j$ лемэье хкх пюбмш~$n$; дкъ йпюрйнярх асдел мюгшбюрэ ее $n\hbox{-яерэч}$. Яерэ мюгшбюеряъ \dfn{ярюмдюпрмни,} еякх~$i_q$ еярэ $n\hbox{-бейрнп}$, ю $\alpha$~еярэ $n\hbox{-яерэ}$, рн хяонкэгсел нангмювемхе~$x\alpha$ дкъ бейрнпю вхяек~$\<(x\alpha)_1,~\ldots, (x\alpha)_n>$, онпнфдеммшу яерэч. Онкнфхл рюйфе дкъ йпюрйнярх~$a\lor b=\max(a, b)$, %%284 $a\land b=\min(a, b)$, $\bar a=1-a$; рнцдю~$(x[i:j])_i=x_i\land x_j$, $(x[i:j])_j=x_i\lor x_j$ х~$(x[i:j])_k=x_k$ дкъ~$i\ne k \ne j$. Асдел цнбнпхрэ, врн $\alpha$~ъбкъеряъ \emph{яерэч янпрхпнбйх,} рнцдю х рнкэйн рнцдю, йнцдю~$(x\alpha)_i\le(x\alpha)_{i+1}$ дкъ~$1\le i < n$ х бяеу~$x$. Яхлбнк~$e^{(i)}$ нангмювюер бейрнп, с йнрнпнцн б онгхжхх~$i$ мюундхряъ~1, ю б нярюкэмшу леярюу~0; рюйхл напюгнл, $(e^{(i)})_j=\delta_{ij}$. Яхлбнк~$D_n$ нангмювюер лмнфеярбн бяеу $2^n$~$n\hbox{-леярмшу}$ бейрнпнб хг~0 х~1, ю $P_n$~нангмювюер лмнфеярбн бяеу $n!$~бейрнпнб, ъбкъчыхуяъ оепеярюмнбйюлх~$\set{1, 2,~\ldots, n}$. Лш асдел хяонкэгнбюрэ нангмювемхъ~$x\land y$ х~$x\lor y$ дкъ бейрнпнб~$\$ х~$\$ х асдел охяюрэ~$x\le y$, еякх~$x_i\le y_i$ опх бяеу~$i$. Рюйхл напюгнл, $x\le y$~рнцдю х рнкэйн рнцдю, йнцдю~$x\lor y= y$, х рнцдю х рнкэйн рнцдю, йнцдю \picture{Пхя.~56. Меярюмдюпрмюъ яерэ, нямнбюммюъ мю ахрнммни янпрхпнбйе.} $x\land y=x$. Еякх~$x$ х~$y$ кефюр б~$D_n$, рн асдел цнбнпхрэ, врн \dfn{$x$~онйпшбюер~$y$,} еякх~$x=y\lor e^{(i)}\ne y$ опх мейнрнпнл~$i$. Мюйнмеж, дкъ бяеу~$x$ б~$D_n$ осярэ~$\nu(x)$ асдер вхякнл едхмхж б $x$, a~$\zeta(x)$---вхякнл мскеи; рюйхл напюгнл, $\nu(x)+\zeta(x)=n$. \ex[20] Мюпхясире яерэ вермн-мевермнцн якхъмхъ дкъ~$m=3$ х~$n=5$. \ex[22] Онйюфхре, врн юкцнпхрлс янпрхпнбйх Б.~Опюррю (ял.~соп.~5.2.1-30) яннрберярбсер яерэ янпрхпнбйх $n$~щкелемрнб, хлечыюъ опхакхгхрекэмн $(\log_2 n) \times (\log_3 n)$~спнбмеи гюдепфйх. Мюпхясире рюйсч яерэ дкъ~$n=12$. \ex[M20] (Й.~Щ.~Ащрвеп.) Мюидхре опнярне яннрмньемхе лефдс~$C(m, m-1)$ х~$C(m,m)$. \rex[Л23] Днйюфхре, врн~$\hat T(6) =5$. \ex[Л21] Днйюфхре, врн бшпюфемхе~(13) деиярбхрекэмн нопедекъер бпелъ гюдепфйх дкъ яерх янпрхпнбйх, нохяюммни яннрмньемхълх~(10). \ex[28] Осярэ~$T(n)$ асдер лхмхлюкэмшл вхякнл ярюдхи, рпеаселшу дкъ янпрхпнбйх я \emph{ндмнбпелеммшл бшонкмемхел меоепеяейючыхуяъ япюбмемхи} (аег яеребнцн нцпюмхвемхъ); йюфдне рюйне лмнфеярбн япюбмемхи лнфер ашрэ опедярюбкемн сгкнл, яндепфюыхл лмнфеярбн оюп~$i_1:j_1$, $i_2:j_2$,~\dots, $i_r:j_r$, цде бяе~$i_1$, $j_1$, $i_2$, $j_2$,~\dots, $i_r$, $j_r$ пюгкхвмш; нр щрнцн сгкю нрундхр бмхг $2^r$~бербеи, %%285 яннрберярбсчыху яксвюъл $$ \eqalign{ &\<{K_{i_1};\cr &\<{K_{i_1}>K_{j_1}, K_{i_2} \hbox{х~р.~д.}\cr } $$ Днйюфхре, врн~$T(5) =T (6) = 5$. \ex[25] Онйюфхре, врн еякх онякедмхи йнлоюпюрнп яерх дкъ~$n=10$ мю~пхя.~49 онлеярхрэ меоняпедярбеммн оепед брнпшл х рперэхл я йнмжю йнлоюпюрнпюлх, рн яерэ он-опефмелс асдер янпрхпнбюрэ. \ex[Л20] Днйюфхре, врн~$\hat M(m_1+m_2, n_1+n_2)\ge \hat M(m_1, n_1)+ \hat M(m_2, n_2)+\min(m_1, n_2)$ опх~$m_1, m_2, n_1, n2\ge 0$. \ex[Л25] (П.~С.~Ткнид.) Днйюфхре, врн~$\hat M(3,3)=6$, $\hat M(4,4)=9$, $\hat M(5,5)=13$. \ex[Л22] Днйюфхре, врн ахрнммши янпрхпнбыхй Ащрвепю, йюй нм нопедекем б рейяре оепед~(15), деиярбхрекэмн пюанрюер. [\emph{Сйюгюмхе.} Днярюрнвмн днйюгюрэ, врн асдср янпрхпнбюрэяъ бяе онякеднбюрекэмнярх, янярнъыхе хг $k$~едхмхж, гю йнрнпшлх якедсчр $l$~мскеи, гю йнрнпшлх якедсчр $n-k-l$~едхмхж.] \ex[Л23] Днйюфхре, врн ахрнммши янпрхпнбыхй Ащрвепю онпъдйю~$2^p$ асдер янпрхпнбюрэ ме рнкэйн онякеднбюрекэмнярх~$\$, дкъ йнрнпшу $z_0 \ge \ldots\ge z_k \le \ldots\le z_{2^p-1}$, мн рюйфе х бяе онякеднбюрекэмнярх, дкъ йнрнпшу $z_0\le \ldots \le z_k \ge \ldots \ge z_{2^p-1}$. [Йюй якедярбхе щрнцн, яерэ мю пхя.~56 асдер янпрхпнбюрэ 16~щкелемрнб, рюй йюй йюфдюъ ярюдхъ янярнхр хг ахрнммшу янпрхпнбыхйнб хкх напюыеммшу ахрнммшу янпрхпнбыхйнб, опхлемъелшу й онякеднбюрекэмняръл, йнрнпше ашкх нрянпрхпнбюмш б опнрхбнонкнфмшу мюопюбкемхъу.] \ex[Л20] Днйюфхре хкх нопнбепцмхре якедсчыее србепфдемхе: еякх~$x$ х~$y$---ахрнммше онякеднбюрекэмнярх пюбмни дкхмш, рн онякеднбюрекэмнярх~$x\lor y$ х~$x\land y$ рюйфе ахрнммше. \rex[24] (X.~Я.~Ярнсм). Онйюфхре, врн яерэ янпрхпнбйх дкъ $2^t$~щкелемрнб лнфмн онярпнхрэ он яуеле, опнхккчярпхпнбюммни дкъ~$t=4$ мю пхя.~57. Йюфдши хг $t^2$~ьюцнб щрни яуелш янярнхр хг "хдеюкэмнцн рюянбюмхъ" оепбшу $2^{t-1}$~щкелемрнб я онякедмхлх~$2^{t-1}$, гю йнрнпшл якедсчр ноепюжхх, бшонкмъелше ндмнбпелеммн мюд $2^{t-1}$~оюпюлх яняедмху щкелемрнб. Йюфдюъ хг щрху ноепюжхи нангмювемю кхан~"$0$" (мер ноепюжхх), кхан~"$+$" (ярюмдюпрмши йнлоюпюрнпмши лндскэ), кхан~"$-$" (напюыеммши йнлоюпюрнпмши лндскэ). Янпрхпнбйю опнрейюер б $t$~ярюдхи он $t$~ьюцнб йюфдюъ; мю онякедмеи ярюдхх бяе ноепюжхх ясрэ~"$+$". Б ревемхе ярюдхх~$s$ опх~$sj_q$. Еякх рюйху хмдейянб мер, рн нярюмнбхрэяъ. \item{T2.}~Гюлемхрэ бяе бунфдемхъ~$i_q$ мю~$j_q$ х бяе бунфдемхъ~$j_q$ мю~$i_q$ бн бяеу йнлоюпюрнпюу~$[i_s:j_s]$ дкъ~$q\le s \le r$. Бепмсрэяъ й ьюцс~T1.\endmark \medskip} \noindent Мюопхлеп, яерэ~$[4:1]\,[3:2]\,[1:3]\,[2:4]\,[1:2]\,[3:4]$ опенапюгсеряъ ямювюкю б~$[1:4]\,[3:2]\,[4:3]\,[2:1]\,[4:2]\,[3:1]$, гюрел б~$[1:4]\,[2:3]\,[4:2]\,[3:1]\,[4:3]\,[2:1]$, гюрел %%286 \picture{Пхя.~57.~Янпрхпнбйю 16 щкелемрнб я "хдеюкэмшл рюянбюмхел".} %%287 б~$[1:4]\,[2:3]\,[2:4]\,[3:1]\,[2:3]\,[4:1]$ х~р.~д., онйю ме онксвхряъ ярюмдюпрмюъ яерэ~$[1:4]\,[2:3]\,[2:4]\,[1:3]\,[1:2]\,[3:4]$. \ex[Л25] Осярэ~$D_{tn}$ асдер лмнфеярбнл бяеу $\perm{n}{t}$~онякеднбюрекэмняреи $\$ хг мскеи х едхмхж, хлечыху пнбмн $t$~едхмхж. Днйюфхре, врн $\hat U_t(n)$~пюбмн лхмхлюкэмнлс вхякс йнлоюпюрнпнб, йнрнпше менаундхлш б яерх, янпрхпсчыеи бяе щкелемрш~$D_{tn}$; врн $\hat V_t (n)$~пюбмн лхмхлюкэмнлс вхякс йнлоюпюрнпнб, мсфмшу дкъ янпрхпнбйх~$D_{tn}\cup D_{(t-1)n}$; х врн $\hat W_t(n)$~пюбмн лхмхлюкэмнлс вхякс йнлоюпюрнпнб, мсфмшу дкъ янпрхпнбйх~$\bigcup_{0\le k \le t} D_{kn}$. \rex[Л20] Днйюфхре, врн яерэ, йнрнпюъ нопедекъер ледхюмс $2t-1$~щкелемрнб, рпеасер ме лемее~$(t-1)\ceil{\log_2(t+1)}+\ceil{\log_2 t}$ йнлоюпюрнпмшу лндскеи. [\emph{Сйюгюмхе:} ял. днйюгюрекэярбн ренпелш~A.] \ex[Л22] Днйюфхре, врн~$\hat U_2(n)=2n-4$ х~$\hat V_2(n)=2n-3$ дкъ бяеу~$n\ge2$. \ex[24] Днйюфхре, врн~$\hat V_3(5)=7$. \ex[M15] Осярэ~$\alpha$---кчаюъ $n\hbox{-яерэ}$, ю~$x$ х~$y$---дбю $n\hbox{-бейрнпю}$. Днйюфхре, врн хг~$x\le y$ якедсер~$x\alpha \le y\alpha$. \ex[Л15] Днйюфхре, врн еякх~$x$ х~$y$ ясрэ $n\hbox{-бейрнпш}$ деиярбхрекэмшу вхяек, рн~$x\cdots y \le (x\alpha)\cdot(y\alpha)$. (Гдеяэ~$x\cdot y$---яйюкъпмне опнхгбедемхе $x_1y_1+\cdots+x_ny_n$.) \ex[Л17]. Осярэ~$\alpha$ еярэ~$n\hbox{-яерэ}$. Днйюфхре, врн ясыеярбсер оепеярюмнбйю~$p\in P_n$, рюйюъ, врн $(p\alpha)_i=j$ рнцдю х рнкэйн рнцдю, йнцдю б~$D_n$~мюидсряъ бейрнпш~$x$, $y$, рюйхе, врн~$x$ онйпшбюер~$y$, $(x\alpha)_i=1$, $(y\alpha)_i=0$ х~$\zeta(y)=j$. \rex[M21] (Б.~Е.~Юкейяееб.) Осярэ~$\alpha$ еярэ~$n\hbox{-яерэ}$; ббедел нангмювемхъ $l_k=\min\set{ (p\alpha)_k \mid p\in P_n}$, $u_k=\max\set{(p\alpha)_k\mid p\in P_n}$ опх~$1\le k \le n$ дкъ мхфмеи х бепумеи цпюмхж дхюоюгнмю гмювемхи, йнрнпше лнцср онъбкърэяъ мю опълни~$k$ бшундю. Осярэ~$l'_k$ х~$u'_k$---юмюкнцхвмн нопедекеммше бекхвхмш дкъ яерх~$\alpha'=\alpha[i:j]$. Днйюфхре, врн~$l'_i=l_i\land l_j$, $l'_j\le l_i+l_j$, $u'_i\ge u_+u_j-(n+1)$, $u'_j=u_i\lor u_j$. [\emph{Сйюгюмхе:} дкъ дюммшу бейрнпнб~$x$ х~$y$ хг~$D_n$, рюйху, врн~$(x\alpha)_i=(y\alpha)_j=0$, $\zeta(x)=l_i$, $\zeta(y)=l_j$, мюидхре бейрнп~$z$ хг~$D_n$, рюйни, врн~$(z\alpha')_j=0$, $\zeta(z)\le l_i+l_j$.] \ex[M30] Осярэ~$l_k$ х~$u_k$ нопедекемш, йюй б соп.~24. Днйюфхре, врн лмнфеярбн~$\set{(p\alpha)_k \mid p\in P_n}$ яндепфхр бяе жекше вхякю лефдс~$l_k$ х~$u_k$ бйкчвхрекэмн. \ex[M24] (П.~С.~Ткнид.) Осярэ~$\alpha$ еярэ $n\hbox{-яерэ}$. Днйюфхре, врн лмнфеярбн~$D_n\alpha=\set{x\alpha \mid x\in D_n}$ лнфер ашрэ нопедекемн, хг лмнфеярбю~$P_n\alpha=\set{p\alpha \mid p\in P_n}$ х, напюрмн, $P_n\alpha$~лнфер ашрэ нопедекемн хг~$D_n\alpha$. \rex[M20] Осярэ~$x$ х~$y$---бейрнпш, х осярэ~$x\alpha$ х~$y\alpha$---нрянпрхпнбюммше бейрнпш. Днйюфхре, врн~$(x\alpha)_i\le (y\alpha)_j$ рнцдю х рнкэйн рнцдю, йнцдю дкъ кчани янбнйсомнярх $j$~щкелемрнб хг~$y$ лнфмн мюирх янбнйсомнярэ $i$~щкелемрнб хг~$x$, рюйсч, врн кчани щкелемр, бгърши хг~$x$, лемэье мейнрнпнцн щкелемрю, бгърнцн хг~$y$, хкх пюбем елс. Хяонкэгсире щрнр опхмжхо дкъ днйюгюрекэярбю рнцн, врн \emph{еякх нрянпрхпнбюрэ ярпнйх кчани люрпхжш, ю гюрел нрянпрхпнбюрэ ярнкажш, рн ярпнйх нярюмсряъ сонпъднвеммшлх.} \rex[Л20] Якедсчыюъ дхюцпюллю онйюгшбюер, йюй гюохяюрэ тнплскш дкъ яндепфхлнцн бяеу кхмхи яерх янпрхпнбйх вепег ее бундш: \picture{p.287} Хяонкэгсъ гюйнмш йнллсрюрхбмнярх~$x\land y =y \land x$, $x\lor y = y \lor x$, гюйнмш юяянжхюрхбмнярх~$x\land (y\land z)=(x\land y) \land z$, $x \lor (y \lor z) = (x \lor y) \lor z$, гюйнмш дхярпхасрхбмнярх $x\land (y\lor z)=(x\land y)\lor (x\land z)$, $x\lor(y\land z)=(x\lor y)\land (x\lor z)$, гюйнмш онцкныемхъ $x\land (x\lor y)=x\lor(x\land y)=x$ х гюйнмш хделонремрмнярх $x\land x=x\lor x = x$, лш лнфел ябеярх тнплскш б опюбни вюярх щрни яерх яннрберярбеммн й~$(a \land b \land c \land d)$, $(a\land b \land c) \lor (a\land b \land d) \lor (a\land c\land d) \lor (b \land c \land d)$, $(a\land b) \lor (a \land c) \lor (a \land d) \lor (b \land c) \lor (b \land d) \lor (c \land d)$, $a \lor b \lor c \lor d$. Днйюфхре, %%288 врн б наыел яксвюе $t\hbox{-и}$ б онпъдйе сашбюмхъ щкелемр хг~$\set{x_1,~\ldots, x_n}$ дюеряъ "щкелемрюпмни яхллерпхвеяйни тсмйжхеи" $$ \sigma_t(x_1,~\ldots, x_n)= \bigvee \set{x_{i_1}\land x_{i_2}\land\ldots\land x_{i_t} \mid 1\le i_1 < i_2 < \ldots < i_t \le n}. $$ [Гдеяэ $\perm{n}{t}$~вкемнб на╝едхмъчряъ ноепюжхеи~$\vee$ блеяре. Рюйхл напюгнл, гюдювю мюунфдемхъ яерх янпрхпнбйх лхмхлюкэмни ярнхлнярх щйбхбюкемрмю гюдюве бшвхякемхъ щкелемрюпмшу яхллерпхвеяйху тсмйжхи я лхмхлюкэмшл вхякнл яуел "х/хкх", цде мю йюфднл ьюце дбе бекхвхмш~$\phi$ х~$\psi$ гюлемъчряъ мю~$\phi\land\psi$ х~$\phi\lor\psi$.] \ex[M20] Дюмн, врн~$x_1\le x_2 \le x_3$ х~$y_1\le y_2 \le y_3 \le y_4 \le y_5$ х врн~$z_1\le z_2 \le \ldots \le z_8$---пегскэрюр якхъмхъ~$x$ я~$y$. Мюидхре бшпюфемхъ дкъ йюфднцн~$z$ вепег~$x$ х~$y$, хяонкэгсъ ноепюрнпш~$\land$ х~$\lor$. \ex[БЛ24] Днйюфхре, врн кчаюъ тнплскю, яндепфюыюъ~$\land$, $\lor$ х мегюбхяхлше оепелеммше~$\set{x_1,~\ldots, x_n}$, лнфер ашрэ опхбедемю я хяонкэгнбюмхел рнфдеярб хг соп.~28 й "йюмнмхвеяйни" тнпле~$\tau_1\lor\tau_2\lor\ldots\lor\tau_k$, гдеяэ~$k\ge1$ х йюфдши~$\tau_i$ хлеер бхд~$\land \set{x_j \mid j \in S_i}$, цде~$S_i$---ондлмнфеярбн~$\set{1,2,~\ldots, n}$ х мхйюйне лмнфеярбн~$S_i$ ме бйкчвюеряъ б~$S_j$, еякх~$i\ne j$. Днйюфхре рюйфе, врн дбе рюйхе йюмнмхвеяйхе тнплш пюбмш дкъ бяеу~$x_1$,~\dots, $x_n$ рнцдю х рнкэйн рнцдю, йнцдю нмх хдемрхвмш (я рнвмнярэч дн онпъдйю). \ex[Л24] (П.~Дедейхмд, 1897.) Осярэ~$\delta_n$---вхякн пюгкхвмшу йюмнмхвеяйху тнпл нр~$x_1$,~\dots, $x_n$ б ялшяке соп.~30 Рюй, $\delta_1=l$, $\delta_2=4$ х~$\delta_3=18$. Велс пюбмн~$\delta_4$? \ex[Л28] (Л.~С.~Цпхм.) Осярэ~$G_1=\set{00, 01, 11}$; нопедекхл~$G_{n+1}$ йюй лмнфеярбн бяеу жеонвей~$\theta\phi\psi\omega$, рюйху, врн~$\theta$, $\phi$, $\psi$, $\omega$ хлечр дкхмс~$2^{n+1}$ х~$\theta\phi$, $\psi\omega$, $\theta\psi$ х~$\phi\omega$ опхмюдкефюр~$G_n$. Осярэ~$\alpha$---яерэ, янярнъыюъ хг вершпеу оепбшу спнбмеи 16-янпрхпнбыхйю, хгнапюфеммнцн мю пхя.~48. Онйюфхре, врн~$D_{16}\alpha=G_4$, х днйюфхре, врн щрн лмнфеярбн хлеер б рнвмнярх $\delta_4+2$~щкелемрнб. (Ял.~соп.~31.) \rex[Л22] Ме бяе $\delta_n$~тсмйжхи нр~$\$ хг соп.~31 лнцср бярперхрэяъ б йнлоюпюрнпмшу яеръу. Ю хлеммн днйюфхре, врн тсмйжхъ~$(x_1\land x_2) \lor (x_2\land x_3) \lor (x_3\land x_4)$ ме лнфер ашрэ пегскэрюрнл мхйюйни йнлоюпюрнпмни яерх нр~$\$. \ex[23] Ъбкъеряъ кх якедсчыюъ яерэ яерэч янпрхпнбйх? \picture{p.288} \ex[20] Днйюфхре, врн б кчани \emph{ярюмдюпрмни яерх} янпрхпнбйх днкфем он йпюимеи лепе ндхм пюг бярперхрэяъ йюфдши хг йнлоюпюрнпнб~$[i:i+1]$ опх~$1\le i < n$. \rex[22] Яерэ мю пхя.~47 яндепфхр рнкэйн \emph{йпюрвюиьхе} япюбмемхъ~$[i:i+1]$; асдел мюгшбюрэ рюйхе яерх \dfn{опхлхрхбмшлх,} (a)~Днйюфхре, врн опхлхрхбююъ яерэ янпрхпнбйх дкъ $n$~щкелемрнб днкфмю хлерэ ме лемее $\perm{n}{2}$~йнлоюпюрнпнб. [\emph{Сйюгюмхе:} пюяялнрпхре хмбепяхх оепеярюмнбйх.] (b)~(П.~С.~Ткнид, 1964.) Осярэ~$\alpha$---опхлхрхбмюъ яерэ дкъ $n$~щкелемрнб, ю~$x$---бейрнп, рюйни, врн~$(x\alpha)_i >(x\alpha)_j$ опх мейнрнпшу~$i(y\alpha)_j$, цде~$y$---бейрнп~$\$. (я)~Б йювеярбе якедярбхъ~(b) днйюфхре, врн опхлхрхбмюъ %%288 яерэ ъбкъеряъ яерэч янпрхпнбйх рнцдю х рнкэйн рнцдю, йнцдю нмю янпрхпсер едхмярбеммши бейрнп~$\$! \ex[Л22] \dfn{Вермн-мевермюъ янпрхпнбйю я рпюмяонгхжхълх} дкъ $n$~вхяек, $n\ge 3$, щрн $n\hbox{-спнбмебюъ}$ яерэ я ${1\over2}n(n-1)$~йнлоюпюрнпюлх, мюонлхмючыюъ йхпохвмсч йкюдйс (пхя.~58). (Еякх $n$~вермн, хлечряъ дбе бнглнфмнярх.) Рюйсч янпрхпнбйс нянаеммн кецйн пеюкхгнбюрэ юооюпюрспмн, рюй йюй оноепелеммн бшонкмъчряъ рнкэйн дбю бхдю деиярбхи. Днйюфхре, врн рюйюъ яерэ деиярбхрекэмн асдер опюбхкэмни яерэч янпрхпнбйх. [\emph{Сйюгюмхе:} ял.~соп.~36.] \picture{Пхя.~58. Вермн-мевермюъ янпрхпнбйю я рпюмяонгхжхълх.} \ex[29] Лнфмн дюрэ дпсцсч хмрепоперюжхч яеръл янпрхпнбйх, явхрюъ, врн мю йюфдни кхмхх мюундхряъ лскэрхлмнфеярбн хг $m$~вхяек, ю ме ндмн вхякн; опх щрни хмрепоперюжхх ноепюжхъ~$[i:j]$ гюлемъер~$x_i$ х~$x_j$ яннрберярбеммн мю~$x_i \upup x_j$ х~$x_i\dndn x_j$---мюхлемэьхе~$m$ х мюханкэьхе~$m$ хг~$2m$ вхяек~$x_i\uplus x_j$. (Пхя.~59 хккчярпхпсер щрн опх~$m=2$.) Еякх~$a$ х~$b$ ясрэ лскэрхлмнфеярбю, яндепфюыхе $m$~вхяек йюфдне, рн асдел цнбнпхре, врн~$a \lflf b$ рнцдю \picture{Пхя.~59. Дпсцюъ хмрепоперюжхъ яерх янпрхпнбйх, опедярюбкеммни мю пхя.~44: йюфдши йнлоюпюрнпмши лндскэ бшонкмъер ноепюжхч якхъмхъ.} х рнкэйн рнцдю, йнцдю~$a \upup b=a$ (хкх, щйбхбюкемрмн, $a \dndn b=b$; мюханкэьхи щкелемр~$a$ лемэье хкх пюбем мюхлемэьелс щкелемрс~$b$). Рюйхл напюгнл, $a \upup b \lflf a \dndn b$. Осярэ~$\alpha$ еярэ $n\hbox{-яерэ}$, a~$x=\$---бейрнп, б йнрнпнл йюфдюъ йнлонмемрю~$x_i$---лскэрхлмнфеярбн хг $m$~щкелемрнб. Днйюфхре, врн еякх~$(x\alpha)_i$ ме $\lflf (x\alpha)_j$ б нохяюммни хмрепоперюжхх, рн б~$D_n$ мюидеряъ бейрнп~$y$, рюйни, врн $(y\alpha)_i=1$ х~$(y\alpha)_j=0$. [Якеднбюрекэмн, яерэ янпрхпнбйх $n$~щкелемрнб опебпюыюеряъ б яерэ янпрхпнбйх $mn$~щкелемрнб, еякх гюлемхрэ япюбмемхъ $m$-осребшлх якхъмхълх. Мю пхя.~60 хгнапюфем бняэлхщкелемрмши янпрхпнбыхй, онярпнеммши хг вершпеущкелемрмнцн я хяонкэгнбюмхел щрнцн мюакчдемхъ.] \rex[Л23] Онйюфхре, врн б нангмювемхъу соп.~38 $(x\upup y)\upup z=x\upup (y\upup z)$ х~$(x\dndn y)\dndn z=x\dndn(y\dndn z)$, ндмюйн $(x\dndn y)\upup z)$ \emph{ме} бяецдю пюбмн~$(x\upup z)\dndn (y\upup z)$ х~$(x\upup y)\dndn (x\upup z)\dndn (y\upup z)$ \emph{ме} бяецдю пюбмн япедмхл $m$~щкелемрюл~$x\uplus y \uplus z$. Мюидхре опюбхкэмсч тнплскс дкъ щрху япедмху щкелемрнб, хяонкэгнбюб б меи $x$, $y$, $z$, ю рюйфе ноепюжхх~$\upup$ х~$\dndn$. %%290 \ex[M25] (П.~К.~Цпщуел.) Йнлоюпюрнп~$[i:j]$ мюгшбюеряъ хгашрнвмшл б яерх~$\alpha_1[i:j]\alpha_2$, еякх кхан~$(x\alpha_1)_i \le (x\alpha_1)_j$ дкъ бяеу бейрнпнб~$x$, кхан~$(x\alpha_1)_i\ge (x\alpha_1)_j$ дкъ бяеу бейрнпнб~$x$. Днйюфхре, врн еякх $\alpha$~ъбкъеряъ яерэч я $r$~мехгашрнвмшлх йнлоюпюрнпюлх, рн мюидсряъ он йпюимеи лепе $r$~пюгкхвмшу сонпъднвеммшу \picture{Пхя.~60. 8-янпрхпнбыхй, онярпнеммши хг 4-янпрхпнбыхйю я хяонкэгнбюмхел якхъмхъ.} оюп~$(i, j)$ пюгкхвмшу хмдейянб, рюйху, врн~$(x\alpha)_i\le (x\alpha)_j$ дкъ бяеу бейрнпнб~$x$. (Якеднбюрекэмн, яерэ аег хгашрнвмшу йнлоюпюрнпнб яндепфхр ме анкее $\perm{n}{2}$~лндскеи.) \rex[M27] (Б.~Е.~Юкейяееб.) Осярэ~$\alpha=[i_1:j_1]\ldots[i_r:j_r]$ еярэ~$n\hbox{-яерэ}$; дкъ~$1\le s \le r$ нопедекхл~$\alpha^s=[i'_1:j'_1]\ldots[i'_{s-1}:j'_{s-1}]\, [i_s:j_s]\ldots[i_r:j_r]$, цде~$i'_k$ х~$j'_k$ онксвемш хг~$i_k$ х~$j_k$ гюлемни~$i_s$ мю~$j_s$ х~$j_s$ мю~$i_s$ бегде, цде нмх бярпевючряъ. Мюопхлеп, еякх~$\alpha=[1:2]\,[3:4]\,[1:3]\,[2:4]\,[2:3]$, рн~$\alpha^4=[1:4]\, [3:2]\,[1:3]\,[2:4]\,[2:3]$. {\medskip\narrower \item{a)}~Днйюфхре, врн~$D_n\alpha=D_n(\alpha^s)$. \item{b)}~Днйюфхре, врн~$(\alpha^s)^t=(\alpha^t)^s$. \item{c)}~\dfn{Янопъфемхел~$\alpha$} ъбкъеряъ кчаюъ яерэ бхдю~$(\ldots((\alpha^{s_1})^{s_2})\ldots)^{s_k}$. Днйюфхре, врн $\alpha$~хлеер ме анкее $2^{r-1}$~янопъфемхи. \item{d)}~Осярэ~$g_\alpha(x)=1$, еякх~$x\in D_n\alpha$, х~$g_\alpha(x)=0$, еякх~$x\notin D_n\alpha$, х осярэ $$ f_\alpha(x)=(\bar x_{i_1}\lor x_{j_1})\land\ldots\land(\bar x_{i_r}\lor x_{j_r}). $$ Днйюфхре, врн~$g_\alpha(x)=\bigvee\set{f_{\alpha'}(x)\mid \hbox{$\alpha'$ еярэ янопъфемхе~$\alpha$}}$. \item{e)}~Осярэ~$G_\alpha$---мюопюбкеммши цпют я бепьхмюлх~$\set{1,~\ldots, n}$ х дсцюлх~$i_s\to j_s$ дкъ~$1\le s \le r$. Днйюфхре, врн ю ъбкъеряъ яерэч янпрхпнбйх рнцдю х рнкэйн рнцдю, йнцдю дкъ бяеу ее янопъфемхи~$\alpha'$ б~$G_{\alpha'}$ хлееряъ нпхемрхпнбюммши осрэ нр~$i$ дн~$i+1$ дкъ~$1\le i < n$. [Щрн днбнкэмн хмрепеямне сякнбхе, оняйнкэйс~$G_\alpha$ ме гюбхяхр нр онпъдйю йнлоюпюрнпнб б~$\alpha$.] \medskip} \rex[25] (Д.~Бюм Бнпхя.) Днйюфхре, врн~$\hat S(n)\ge \hat S(n-1)+\ceil{\log_2 n}$. \ex[23] \dfn{Оепеярюмнбнвмни яерэч} мюгшбюеряъ онякеднбюрекэмнярэ лндскеи~$[i_1:j_1]\ldots[i_r:j_r]$, цде йюфдши лндскэ~$[i:j]$ лнфер сярюмюбкхбюрэяъ хгбме б ндмн хг дбсу янярнъмхи: кхан нм оепедюер ябнх бундш аег хглемемхи, кхан лемъер леярюлх~$x_i$ х~$x_j$ (мегюбхяхлн нр гмювемхи~$x_i$ х~$x_j$), х онякеднбюрекэмнярэ лндскеи днкфмю ашрэ рюйни, врн мю бшунде лнфмн онксвхрэ кчасч оепеярюмнбйс бунднб опх яннрберярбсчыеи сярюмнбйе лндскеи. Кчаюъ яерэ янпрхпнбйх ъбкъеряъ, нвебхдмн, оепеярюмнбнвмни яерэч, мн напюрмне мебепмн. Мюидхре оепеярюмнбнвмсч яерэ дкъ оърх щкелемрнб, хлечысч рнкэйн бняелэ лндскеи. %%291 \ex[46] Хгсвхре ябниярбю яереи янпрхпнбйх, онярпнеммшу хг $m$-янпрхпнбыхйнб блеярн 2-янпрхпнбыхйнб. (Мюопхлеп, Ц.~Ьюохпн онярпнхк яерэ дкъ янпрхпнбйх 16~щкелемрнб, хяонкэгнбюб вершпмюджюрэ 4-янпрхпнбыхйнб. Мюхксвьее кх щрн пеьемхе? Ясыеярбсер кх дкъ бяеу $m$~щттейрхбмши яоняна янпрхпнбйх $m^2$~щкелемрнб я онлныэч лндскеи, бшонкмъчыху $m$-янпрхпнбйс?) \ex[48] Мюидхре, $(m, n)\hbox{-яерэ}$ якхъмхъ я вхякнл йнлоюпюрнпнб, лемэьхл~$C(m,n)$, хкх днйюфхре, врн рюйни яерх ме ясыеярбсер. \ex[48] Мюидхре $(m, n)\hbox{-яерэ}$ якхъмхъ лемэье, вел я $\ceil{\log_2 (m+n)}$~спнбмълх гюдепфйх, хкх днйюфхре, врн ее ме ясыеярбсер. \ex[48] Хгсвхре йкюяя яуел янпрхпнбйх, йнрнпше лнцср ашрэ пеюкхгнбюмш б бхде яуел я хдеюкэмшл рюянбюмхел, йюй мю пхя.~57, мн я дпсцхл пюяонкнфемхел ноепюжхи~"$0$", "$+$" х~"$-$". \ex[БЛ49] Хяякедсире ябниярбю ноепюжхи~$\upup$ х~$\dndn$, нопедекеммшу б соп.~38. Лнфмн кх нуюпюйрепхгнбюрэ бяе рнфдеярбю б щрни юкцеапе йюйхл-кхан хгъымшл яонянанл хкх бшбеярх бяе ху хг йнмевмнцн мюанпю рнфдеярб? Б щрнл нрмньемхх рюйхе рнфдеярбю, йюй $$ x\upup x \upup x = x \upup x \hbox{ хкх } x\upup (x\dndn (x\upup (x\dndn y)))=x\upup(x\dndn y), $$ йнрнпше хлечр леярн рнкэйн дкъ~$m\le 2$, опедярюбкъчр нрмняхрекэмн меанкэьни хмрепея; пюяялюрпхбюире кхьэ рнфдеярбю, яопюбедкхбше опх \emph{бяеу}~$m$. \ex[M49] Йюйнбн юяхлорнрхвеяйне онбедемхе тсмйжхх~$T(n)$, нопедекеммни б соп.~а? Лнфер кх ашрэ $T(n)<\hat T(n)$ опх йюйнл-мхасдэ~$n$? \ex[50] Мюидхре рнвмне гмювемхе~$\hat S(n)$ дкъ йюйнцн-кхан~$n>8$. \ex[Л50] Днйюфхре, врн юяхлорнрхвеяйне гмювемхе~$\hat S(n)$ ме еярэ~$O(n\log n)$. \centerline{{\bf СОПЮФМЕМХЪ, (БРНПЮЪ ВЮЯРЭ)}} Якедсчыхе сопюфмемхъ хлечр декн я пюгкхвмшлх рхоюлх норхлюкэмшу гюдюв, йюяючыхуяъ янпрхпнбйх. Оепбше меяйнкэйн гюдюв нямнбюмш мю "хмрепеямнл "лмнцнцнкнбнвмнл" нанаыемхх лерндю осгшпэйю, опедкнфеммнл Т.~М.~Юплярпнмцнл х~П.~Дф.~Мекэянмнл еые б~1954~ц. [Ял.~U.~S.~Patents 3029413, 3034102.] Осярэ~$1=h_1N$, рн гюохяэ~$R_{j+h[k]}$ ме пюяялюрпхбюеряъ, хмюве цнбнпъ, %%292 йкчвх~$K_0$, $K_{-1}$, $K_{-2}$,~\dots{} явхрючряъ пюбмшлх~$-\infty$, a~$K_{N+1}$, $K_{N+2}$,~\dots{}---пюбмшлх~$+\infty$. Онщрнлс опх~$j\le -h[m-1]$ хкх~$j>N-h[2]$ ьюц~$j$ рпхбхюкем.) Мюопхлеп, б якедсчыеи рюакхже онйюгюм ндхм опнунд янпрхпнбйх опх~$m=3$, $N=9$ х~$h_1=1$, $h_2=2$, $h_3=4$: {\def\ul#1{\underline{#1}}\def\emp{\phantom{0}} \ctable{ $#$\hfill && \bskip\hfill$#$\hfill\bskip\cr & K_{-2} & K_{-1} & K_0 & K_1 & K_2 & K_3 & K_4 & K_5 & K_6 & K_7 & K_8 & K_9 & K_{10} & K_{11} & K_{12}\cr j=-3 & \ul{\emp} & \ul{\emp} & & \ul{3} & 1 & 4 & 5 & 9 & 2 & 6 & 8 & 7 \cr j=-2 & & \ul{\emp}& \ul{\emp}& 3 & \ul{1} & 4 & 5 & 9 & 2 & 6 & 8 & 7 \cr j=-1 & & & \ul{\emp}&\ul{3} & 1 & \ul{4} & 5 & 9 & 2 & 6 & 8 & 7\cr j=0 & & & &\ul{1} & \ul{3} & 4 & \ul{5} & 9 & 2 & 6 & 8 & 7 \cr j=1 & & & & 1 & \ul{3} & \ul{4} & 5 & \ul{9} & 2 & 6 & 8 & 7 \cr j=2 & & & & 1 & 3 & \ul{2} & \ul{4} & 9 & \ul{5} & 6 & 8 & 7 \cr j=3 & & & & 1 & 3 & 2 & \ul{4} & \ul{6} & 5 &\ul{9} & 8 & 7 \cr j=4 & & & & 1 & 3 & 2 & 4 & \ul{5} & \ul{6} & 9 & \ul{8} & 7 \cr j=5 & & & & 1 & 3 & 2 & 4 & 5 & \ul{6} & \ul{7} & 8 & \ul{9}\cr j=6 & & & & 1 & 3 & 2 & 4 & 5 & 6 & \ul{7} & \ul{8} & 9 & \ul{\emp} \cr j=7 & & & & 1 & 3 & 2 & 4 & 5 & 6 & 7 & \ul{8} & \ul{9} & & \ul{\emp}\cr j=8 & & & & 1 & 3 & 2 & 4 & 5 & 6 & 7 & 8 & \ul{9} & \ul{\emp}& & \ul{\emp} \cr } } Гюлерхл, врн, еякх~$m=2$, $h_1=1$ х~$h_2=2$, щрнр "лмнцнцнкнбнвмши" лернд ябндхряъ й лерндс осгшпэйю (юкцнпхрл~5.2.2B). \ex[21] (Дфеиля Дсцсмдх.) Днйюфхре, врн еякх~$h[k+1]=h[k]+1$ опх мейнрнпнл~$k$, $1\le k < m$, рн лмнцнцнкнбнвмши янпрхпнбыхй, нопедекеммши бшье, нрянпрхпсер кчани бундмни тюик гю йнмевмне вхякн опнунднб. Мн еякх~$h[k+1]\ge h[k]+2$ опх~$1\le k < m$, рн лнфер яксвхрэяъ, врн бундмюъ онякеднбюрекэмнярэ \emph{мхйнцдю} ме ярюмер сонпъднвеммни. \edef\exref{\the\excerno} \rex[50] (Юплярпнмц х~Мекэянм.) Осярэ~$h[k+1]\le h[k]+k$ опх~$1\le k\le m$ х~$N\ge n-1$. Днйюфхре, врн б ревемхе оепбнцн опнундю мюханкэьхе $n-1$~щкелемрнб бяецдю гюилср ябнх нйнмвюрекэмше леярю. [\emph{Сйюгюмхе:} хяонкэгсире опхмжхо мскеи х едхмхж; днйюфхре, врн еякх янпрхпсеряъ онякеднбюрекэмнярэ хг мскеи х едхмхж, опхвел едхмхж лемэье~$n$, рн бяе цнкнбйх лнцср вхрюрэ~1 кхьэ б рнл яксвюе, йнцдю бяе мскх кефюр якебю нр цнкнбнй.] Днйюфхре, врн еякх цнкнбйх сднбкербнпъчр ятнплскхпнбюммшл сякнбхъл, рн янпрхпнбйю асдер гюйнмвемю ме анкее, вел гю $\ceil{(N-1)/(n-1)}$~опнунднб. Ясыеярбсер кх бундмни тюик, дкъ йнрнпнцн менаундхлн пнбмн ярнкэйн опнунднб? \ex[26] Днйюфхре, врн опх~$n=N$ оепбши опнунд онлеярхр мюхлемэьхи йкчв б онгхжхч~$R_1$ рнцдю х рнкэйн рнцдю, йнцдю~$h[k+1]\le 2h[k]$, $1\le k=\<1, 2, 4, 7,~\ldots, 1+\perm{m}{2}>. $$ напюгсер янбепьеммши янпрхпнбыхй дкъ $N=\perm{m}{2}$~щкелемрнб, хяонкэгсъ $m=(\sqrt{8N-7}+l)/2$~цнкнбнй. Мюопхлеп, онякеднбюрекэмнярэ цнкнбнй~$\<1, 2, 4, 7, 11, 16, 22>$ ъбкъеряъ янбепьеммшл янпрхпнбыхйнл дкъ 22~щкелемрнб. Днйюфхре, врн онякеднбюрекэмнярэ цнкнбнй~$\<1, 2, 4, 7, 11, 16, 23>$ мю яюлнл деке асдер янбепьеммшл янпрхпнбыхйнл дкъ 23~щкелемрнб. \ex[49] Нопедекхре опх гюдюммнл~$m$ мюханкэьее~$N$, дкъ йнрнпнцн ясыеярбсер янбепьеммши янпрхпнбыхй я $m$~цнкнбйюлх. Бепмн кх, врн~$N=O(m^2)$? %%293 \ex[23] (Б.~Опюрр.) Еякх йюфдюъ цнкнбйю~$h_k$ мюундхряъ б онкнфемхх~$2^{k-1}$ дкъ~$1\le k \le m$, рн яйнкэйн опнунднб онрпеасеряъ дкъ янпрхпнбйх онякеднбюрекэмнярх мскеи х едхмхж~$z_1$ $z_2$~\dots{} $z_{2^{m-1}}$, цде $z_j=0$ рнцдю х рнкэйн рнцдю, йнцдю $j$~ъбкъеряъ яреоемэч~2? \ex[24] (Ндмнпндмюъ янпрхпнбйю.) Б депебе мю пхя.~34 б о.~5.3.1 япюбмемхе~$2:3$ бшонкмъеряъ б нанху бербъу спнбмъ~1; ю б йюфдни бербх спнбмъ~2 бшонкмъеряъ япюбмемхе~$1:3$, еякх рнкэйн нмн ме ъбкъеряъ хгашрнвмшл. Б наыел яксвюе лш лнфел пюяялнрперэ йкюяя юкцнпхрлнб янпрхпнбйх, ндмнпндмшу хлеммн б щрнл ялшяке, опедонкюцюъ, врн~$M=\perm{N}{2}$ оюп~$\set{(a,b) \mid 1\le aK_{b_i}$, рн днаюбхрэ дсцс~$b_i\to a_i$. \medskip Мюя хмрепеясер цкюбмшл напюгнл вхякн япюбмемхи йкчвеи, бшонкмъелшу юкцнпхрлнл ндмнпндмни янпрхпнбйх, ю ме леуюмхгл, я онлныэч йнрнпнцн деиярбхрекэмн сярпюмъчряъ хгашрнвмше япюбмемхъ; цпют~$G$ ме наъгюрекэмн ярпнхрэ б ъбмнл бхде---гдеяэ нм хяонкэгсеряъ рнкэйн дкъ нопедекемхъ ндмнпндмни янпрхпнбйх. Асдел рюйфе пюяялюрпхбюрэ \dfn{нцпюмхвеммсч ндмнпндмсч янпрхпнбйс,} опх йнрнпни б сйюгюммшу бшье яксвюъу 1--3 свхршбючряъ рнкэйн осрх дкхмш~2. (Юкцнпхрл нцпюмхвеммни янпрхпнбйх лнфер бшонкмърэ мейнрнпше хгашрнвмше япюбмемхъ, мн, йюй онйюгшбюер соп.~59, юмюкхг нцпюмхвеммнцн яксвюъ меяйнкэйн опные.) Днйюфхре, врн юкцнпхрл нцпюмхвеммни ндмнпндмни янпрхпнбйх янбоюдюер я юкцнпхрлнл ндмнпндмни янпрхпнбйх, йнцдю онякеднбюрекэмнярэ оюп кейяхйнцпютхвеяйх сонпъднвемю: $$ (1, 2)\, (1, 3)\, (1, 4)\ldots(1, N)\, (2, 3)\, (2, 4)\ldots(2, N)\ldots (N-1, N). $$ Онйюфхре, врн мю яюлнл деке наю юкцнпхрлю щйбхбюкемрмш "ашярпни янпрхпнбйе" (юкцнпхрл~5.2.2Q), еякх бяе йкчвх пюгкхвмш х хгашрнвмше япюбмемхъ ашярпни янпрхпнбйх сярпюмемш, йюй б соп.~5.2.2-24. (Ме напюыюире бмхлюмхъ мю онпъднй, б йнрнпнл деиярбхрекэмн бшонкмъчряъ япюбмемхъ б ашярпни янпрхпнбйе; свхршбюире рнкэйн, йюйхе оюпш йкчвеи япюбмхбючряъ.) \ex[Л38] Дкъ гюдюммни, йюй б соп.~58, онякеднбюрекэмнярх оюп~$(a_1, b_1)$~\dots{}$(a_M, b_M)$ осярэ~$c_i$ асдер вхякнл оюп~$(j, k)$, рюйху, врн~$jR_i$, днярхцюеряъ лхмхлюкэмне вхякн опнунднб. %% 295 \bye