\input style \chapno=5\subchno=4\subsubchno=3\chapnotrue Йюяйюдмне якхъмхе, онднамн лмнцнтюгмнлс, мювхмюеряъ я "рнвмнцн пюяопедекемхъ" нрпегйнб он кемрюл, унръ опюбхкю рнвмнцн пюяопедекемхъ нркхвмш нр опюбхк о.~5.4.2. Йюфдюъ ярпнйю рюакхжш опедярюбкъер онкмши опнунд он \emph{бяел} дюммшл. Опнунд~2, мюопхлеп, онксвюеряъ оняпедярбнл бшонкмемхъ оърхосребнцн якхъмхъ я~T1, T2, T3, T4, T5 мю~T6, онйю~T5 ме ярюмер осярни (опх щрнл мю~T6 онлеыючряъ 15~нрпегйнб нрмняхрекэмни дкхмш~5), гюрел вершпеуосребнцн якхъмхъ я~T1, T2, T3, T4 мю~T5, гюрел рпеуосребнцн якхъмхъ мю~T4, дбсуосребнцн якхъмхъ мю~T3 х, мюйнмеж, ндмносребнцн якхъмхъ (ноепюжхх йнохпнбюмхъ) я~T1 мю~T2. Опнунд~3 онксвюеряъ рюйхл фе напюгнл осрел бшонкмемхъ ямювюкю оърхосребнцн якхъмхъ, онйю ндмю кемрю ме ярюмер осярни, гюрел вершпеуосребнцн х~р.~д. (Онунфе, врн щрнлс осмйрс ймхцх якеднбюкн аш опхябнхрэ мнлеп~5.4.3.2.1, ю ме~5.4.3!) Ъямн, врн ноепюжхх йнохпнбюмхъ хгкхьмх, х ху лнфмн ашкн аш носярхрэ. Тюйрхвеяйх, ндмюйн, б яксвюе ьеярх кемр щрн йнохпнбюмхе гюмхлюер рнкэйн меанкэьни опнжемр бяецн бпелемх. Щкелемрш, йнрнпше онксвючряъ опняршл йнохпнбюмхел, нрлевемш б опхбедеммни рюакхже гбегднвйни. Рнкэйн~25 хг~950 напюаюршбюелшу нрпегйнб опхмюдкефюр щрнлс йкюяяс. Анкэьюъ вюярэ бпелемх нрбндхряъ оърхосребнлс х вершпеуосребнлс якхъмхъл. Мю оепбши бгцкъд лнфер онйюгюрэяъ, врн йюяйюдмюъ яуелю---днбнкэмн окнуни бюпхюмр б япюбмемхх я лмнцнтюгмни, рюй йюй ярюмдюпрмюъ лмнцнтюгмюъ яуелю хяонкэгсер бяе бпелъ $(T-1)\hbox{-осребне}$ якхъмхе, б рн бпелъ йюй йюяйюдмюъ хяонкэгсер $(T-1)\hbox{-осребне}$, $(T-2)\hbox{-осребне}$, $(T-3)\hbox{-осребне}$ х~р.~д., мн б деиярбхрекэмнярх нмю юяхлорнрхвеяйх \emph{ксвье,} вел лмнцнтюгмюъ, дкъ ьеярх х анкее кемр! Йюй лш бхдекх б о.~5.4.2, бшянйхи онпъднй якхъмхъ ме ъбкъеряъ цюпюмрхеи щттейрхбмнярх. Б рюак.~1 онйюгюмш уюпюйрепхярхйх бшонкмемхъ йюяйюдмнцн якхъмхъ он юмюкнцхх я онднамни рюакхжеи о.~5.4.2. Мерпсдмн бшбеярх "рнвмше пюяопедекемхъ" дкъ йюяйюдмнцн якхъмхъ. Дкъ ьеярх кемр хлеел $$ \matrix{ \hbox{Спнбемэ} & T1 & T2 & T3 & T4 & T5 \cr 0 & 1 & 0 & 0 & 0 & 0 \cr 1 & 1 & 1 & 1 & 1 & 1 \cr 2 & 5 & 4 & 3 & 2 & 1 \cr 3 & 15 & 14 & 12 & 9 & 6 \cr 4 & 55 & 50 & 41 & 29 & 15 \cr 5 & 190 & 175 & 146 & 105 & 55 \cr \multispan{6}\dotfill\cr n & a_n & b_n & c_n & d_n & e_n \cr n+1 & a_n+b_n+c_n+d_n+e_n & a_n+b_n+c_n+d_n & a_n+b_n+c_n & a_n+b_n & a_n \cr } \eqno(1) $$ %%344 \htable{Рюакхжю 1}% {Уюпюйреп онбедемхъ йюяйюдмнцн якхъмхъ}% {\strut\hfill # && \bskip\hfill$#$\hfill\bskip\cr Кемрш & \hbox{Опнундш} & \hbox{Опнундш} & \hbox{Нрмньемхе}\cr & \hbox{(я йнохпнбюмхел)} & \hbox{(аег йнохпнбюмхъ)} &\hbox{пнярю}\cr \noalign{\hrule} 3 & 2.078\ln S+0.672 & 1.504\ln S+0.992 & 1.6180340\cr 4 & 1.235\ln S+0.754 & 1.102\ln S+0.820 & 2.2469796\cr 5 & 0.946\ln S+0.796 & 0.897\ln S+0.800 & 2.8793852\cr 6 & 0.796\ln S+0.821 & 0.773\ln S+0.808 & 3.5133371\cr 7 & 0.703\ln S+0.839 & 0.691\ln S+0.822 & 4.1481149\cr 8 & 0.639\ln S+0.852 & 0.632\ln S+0.834 & 4.7833861\cr 9 & 0.592\ln S+0.861 & 0.587\ln S+0.845 & 5.4189757\cr 10 & 0.555\ln S+0.869 & 0.552\ln S+0.854 & 6.0547828\cr 20 & 0.397\ln S+0.905 & 0.397\ln S+0.901 & 12.4174426\cr \noalign{\hrule} } Нрлерхл хмрепеямне ябниярбн щрху вхяек---ху нрмняхрекэмше бекхвхмш ъбкъчряъ рюйфе х дкхмюлх дхюцнмюкеи опюбхкэмнцн $(2T-1)\hbox{-сцнкэмхйю}$. Мюопхлеп, оърэ дхюцнмюкеи ндхммюджюрхсцнкэмхйю мю пхя.~73 хлечр нрмняхрекэмше дкхмш, нвемэ акхгйхе й~190, 175, 146, 105 х~55! Лш днйюфел щрнр гюлевюрекэмши тюйр \picture{Пхя.~73. Ценлерпхвеяйюъ хмрепоперюжхъ йюяйюдмшу вхяек.} онгдмее б щрнл осмйре, ю рюйфе сбхдхл, врн нрмняхрекэмше бпелемю, гюрпювхбюелше мю $(T-1)\hbox{-осребне}$ якхъмхе, $(T-2)\hbox{-осребне}$ якхъмхе,~\dots, ндмносребне якхъмхе, опхакхгхрекэмн опнонпжхнмюкэмш \emph{йбюдпюрюл} дкхм щрху дхюцнмюкеи. \section *Мювюкэмне пюяопедекемхе нрпегйнб. Еякх вхякн мювюкэмшу нрпегйнб б деиярбхрекэмнярх ме еярэ вхякн Тханмюввх, лш лнфел, йюй нашвмн, бярюбхрэ тхйрхбмше нрпегйх. Онбепумнярмши юмюкхг яхрсюжхх онйюгшбюер, врн лернд опхохяшбюмхъ тхйрхбмшу нрпегйнб меясыеярбем, рюй йюй йюяйюдмне якхъмхе бяецдю нясыеярбкъер %%345 онкмше опнундш; еякх хлееряъ 190~мювюкэмшу нрпегйнб, рн йюфдюъ гюохяэ напюаюршбюеряъ оърэ пюг, йюй б опхбедеммнл бшье опхлепе, мн еякх хлееряъ 191~нрпегнй, рн, нвебхдмн, якедсер сбекхвхрэ спнбемэ, х реоепэ йюфдюъ гюохяэ асдер напюаюршбюрэяъ ьеярэ пюг. Й явюярэч, б деиярбхрекэмнярх лнфмн хгаефюрэ рюйнцн пегйнцн яйювйю. Дщбхд~Щ.~Тепцчянм мюьек яоняна рюй пюяопедекхрэ мювюкэмше нрпегйх, врн лмнцхе ноепюжхх бн бпелъ оепбни \picture{ Пхя.~74. Щттейрхбмнярэ йюяйюдмнцн якхъмхъ я пюяопедекемхел он юкцнпхрлс~D. } тюгш якхъмхъ ябндъряъ й йнохпнбюмхч яндепфхлнцн кемрш. Еякх нанирх рюйхе йнохпнбюмхъ (опнярн хглемхб "кнцхвеяйхе" мнлепю кемрнвмшу сярпниярб он нрмньемхч й "тхгхвеяйхл" мнлепюл, йюй б юкцнпхрле~5.4.2D), рн онксвхл нрмняхрекэмн окюбмши оепеунд я спнбмъ мю спнбемэ, йюй хгнапюфемн мю пхя.~74. Опедонкнфхл, врн $(a, b, c, d, e)$, цде~$a\ge b \ge c \ge d \ge e$---рнвмне пюяопедекемхе. Оепенопедекхб яннрберярбхе лефдс кнцхвеяйхлх х тхгхвеяйхлх кемрнвмшлх сярпниярбюлх, лш лнфел опедярюбхрэ, врн пеюкэмне пюяопедекемхе---щрн~$(e, d, c, b, a)$, %%346 р.~е.~$a$~нрпегйнб мю~T5, $b$~мю~Р4 х~р.~д. Якедсчыее рнвмне пюяопедекемхе---щрн $(a+b+c+d+e, a+b+c+d, a+b+c, a+b, a)$; х еякх ббнд хявепошбюеряъ опефде, вел лш днярхцюел щрнцн якедсчыецн спнбмъ, рн асдел явхрюрэ, врн кемрш яндепфюр яннрберярбеммн~$(D_1, D_2, D_3, D_4, D_5)$ тхйрхбмшу нрпегйнб, цде $$ \displaynarrow{ D_1 \le a+b+c+d,\quad D_1 \le a+b+c,\quad D_3\le a+b,\cr D_4 \le a,\quad D_5=0;\qquad D_1\ge D_2 \ge D_3 \ge D_4 \ge D_5.\cr } \eqno(2) $$ Лш бнкэмш опедярюбкърэ яеае, врн щрх тхйрхбмше нрпегйх онъбкъчряъ мю кемрюу б кчанл сднамнл леяре. Опедонкюцюеряъ, врн оепбши опнунд якхъмхъ дюяр $a$~нрпегйнб оняпедярбнл оърхосребнцн якхъмхъ, гюрел $b$~нрпегйнб оняпедярбнл вершпеуосребнцн х~р.~д. Мюью жекэ янярнхр б пюяонкнфемхх тхйрхбмшу нрпегйнб рюйхл напюгнл, врнаш гюлемхрэ якхъмхе йнохпнбюмхел. Сднамн бшонкмърэ оепбши опнунд якхъмхъ якедсчыхл напюгнл: 1.~Еякх~$D_4=a$, рн бшвеярэ~$a$ хг бяеу~$D_1$, $D_2$, $D_3$, $D_4$ х гюъбхрэ, врн~T5---пегскэрюр якхъмхъ. Еякх~$D_40$, бепмсрэяъ й ьюцс~\stp{5}. Б опнрхбмнл яксвюе слемэьхрэ~$k$ мю~1; еякх~$k>0$, сярюмнбхрэ~$m\asg |A|[T-j-1]-|A|[T-j]$ х бепмсрэяъ й~\stp{5}, еякх~$m>0$. Б опнрхбмнл яксвюе слемэьхрэ~$j$ мю~1; еякх~$j>0$, оепеирх й ьюцс~\stp{4}. Б опнрхбмнл яксвюе сбекхвхрэ~$i$ мю~1; еякх~$i|M|[j]$, х онлеярхрэ бшбндмни нрпегнй мю~$|TAPE|[p+1]$. Опнднкфюрэ пюанрс, онйю $|TAPE|[p]$ ме ярюмер осярни. Гюрел оепелнрюрэ~$|TAPE|[p]$ х~$|TAPE|[p+1]$. \st[Носярхрэяъ мю ндхм спнбемэ.] Слемэьхрэ~$l$ мю~1, сярюмнбхрэ~$|FIRST|\asg 0$, сярюмнбхрэ $(|TAPE|[1],~\ldots, |TAPE|[T])\asg (|TAPE|[T],~\ldots, |TAPE|[1])$. (Й щрнлс лнлемрс бяе~|D| х~|M|---мскх х рюйнбшлх нярюмсряъ.) Бепмсрэяъ й~\stp{8}. \algend Ьюцх~C1--C6 щрнцн юкцнпхрлю бшонкмъчр пюяопедекемхе, ьюцх~C7--C9 бшонкмъчр якхъмхе; щрх дбе вюярх янбепьеммн мегюбхяхлш ндмю нр дпсцни, х лнфмн ашкн аш упюмхрэ~$|M|[k]$ х~$|AA|[k+1]$ б ндмху х реу фе ъвеийюу оюлърх. \picture{Пхя.~75. Йюяйюдмне якхъмхе ян яоежхюкэмшл пюяопедекемхел.} \section *Юмюкхг йюяйюдмнцн якхъмхъ. Йюяйюдмне якхъмхе онддюеряъ юмюкхгс я анкэьхл рпсднл, вел лмнцнтюгмне. Мн щрнр юмюкхг нянаеммн хмрепеяем, оняйнкэйс яндепфхр лмнцн гюлевюрекэмшу тнплск. Мюярнърекэмн пейнлемдсел вхрюрекъл, хмрепеясчыхляъ дхяйпермни люрелюрхйни, яюлнярнърекэмн опнюмюкхгхпнбюрэ йюяйюдмне пюяопедекемхе, опефде вел вхрюрэ дюкэье, бедэ вхякю %%350 хлечр рюй лмнцн менашвмшу ябниярб, нрйпшбюрэ йнрнпше---ндмн сднбнкэярбхе! Лш наясдхл гдеяэ кхьэ ндхм хг лмнцху ондунднб, напюыюъ нянане бмхлюмхе мю лерндш онксвемхъ пегскэрюрнб. Дкъ сднаярбю пюяялнрпхл яксвюи ьеярх кемр. Опх щрнл асдел ярюпюрэяъ онксвхрэ тнплскш, йнрнпше нанаыючряъ мю яксвюи кчанцн~$T$. Яннрмньемхъ~(1) опхбндър й оепбни нямнбмни яхяреле: $$ \eqalignter{ a_n &= a_n &=\perm{0}{0}a_n,\cr b_n &= a_n-e_{n-1}=a_n-a_{n-2} &=\perm{1}{0}a_n-\perm{2}{2}a_{n-2},\cr c_n &= b_n-d_{n-1}=b_n-a_{n-2}-b_{n-2} &=\perm{2}{0}a_n-\perm{3}{2}a_{n-2}+\perm{4}{4}a_{n-4},\cr d_n &= c_n-c_{n-1}=c_n-a_{n-2}-b_{n-2}-c_{n-2} &=\perm{3}{0}a_n-\perm{4}{2}a_{n-2}+\perm{5}{4}a_{n-4}-\perm{6}{6}a_{n-6},\cr e_n &= d_n-b_{n-1}=d_n-a_{n-2}-b_{n-2}-c_{n-2}-d_{n-2} &=\perm{4}{0}a_n-\perm{5}{2}a_{n-2}+\perm{6}{4}a_{n-4}-\perm{7}{6}a_{n-6}+\perm{8}{8}a_{n-8}.\cr } \eqno(4) $$ Нангмювхл~$A(z)=\sum_{n\ge0} a_n z^n$,~\dots, $E(z)=\sum_{n\ge0}e_n z^n$ х нопедекхл лмнцнвкемш $$ \eqalignno{ q_m(z)&=\perm{m}{0}-\perm{m+1}{2}z^2+\perm{m+2}{4}z^4-\cdots=\cr &=\sum_{k\ge 0}\perm{m+k}{2k}(-1)^k z^{2k} = \sum_{0\le k \le m}\perm{2m-k}{k}(-1)^{m-k} z^{2m-2k}. & (5)\cr } $$ Пегскэрюр~(4) йпюрйн лнфмн хярнкйнбюрэ рюй, врн~$B(z)-q_1(z)\times A(z)$,~\dots, $E(z)-q_4(z)A(z)$ ябндъряъ й йнмевмшл ясллюл, яннрберярбсчыхл цпюмхвмшл сякнбхъл, ю хлеммн гмювемхъл~$a_{-1}$, $a_{-2}$, $a_{-3}$,~\dots, йнрнпше онъбкъчряъ б~(4) (опх меанкэьху~$n$), мн ме б~$A(z)$. Врнаш онксвхрэ ондундъыхе цпюмхвмше сякнбхъ, опхлемхл пейсппемрмне яннрмньемхе б напюрмсч ярнпнмс дкъ нрпхжюрекэмшу спнбмеи дн спнбмъ~$-8$: \ctable{ \hfill$#$\bskip&&\hfill\bskip$#$\bskip\cr \hfill n & \hfill a_n & \hfill b_n & \hfill c_n & \hfill d_n & \hfill e_n \cr 0 & 1 & 0 & 0 & 0 & 0\cr -1 & 0 & 0 & 0 & 0 & 1\cr -2 & 1 & -1 & 0 & 0 & 0\cr -3 & 0 & 0 & 0 & -1 & 2\cr -4 & 2 & -3 & 1 & 0 & 0\cr -5 & 0 & 0 & 1 & -4 & 5\cr -6 & 5 & -9 & 5 & -1 & 0\cr -7 & 0 & -1 & 6 & -14 & 14\cr -8 & 14 & -28 & 20 & -7 & 1\cr } (Дкъ яелх кемр рюакхжю ашкю аш юмюкнцхвмни, ндмюйн ярпнйх я мевермшлх~$n$ ашкх аш ядбхмсрш бопюбн мю ндхм щкелемр.) Рюимю онякеднбюрекэмнярх~$a_0$, $a_{-2}$, $a_{-4},~\ldots=1, 1, 2, 5, 14,~\ldots$ лцмнбеммн пюяйпшбюеряъ яоежхюкхярнл он хмтнплюрхйе, рюй йюй %%351 щрю онякеднбюрекэмнярэ бярпевюеряъ б ябъгх я нвемэ лмнцхлх пейсппемрмшлх юкцнпхрлюлх (мюопхлеп, б соп.~2.2.1-4 х тнплске~2.3.4.4-13)). Хрюй, лш опедонкюцюел, врн б яксвюе $T$~кемр $$ \eqalignrem{ a_{-2n}&=\perm{2n}{n}{1\over n+1} & опх $0\le n \le T-2$; \cr a_{-2n-1}&=0 & опх $0\le n \le T-3$.\cr } \eqno(6) $$ Врнаш опнбепхрэ опюбхкэмнярэ щрнцн опедонкнфемхъ, днярюрнвмн онйюгюрэ, врн~(6) х~(4) опхбндър й опюбхкэмшл пегскэрюрюл дкъ спнбмеи~0 х~1. Дкъ спнбмъ~1 щрн нвебхдмн, ю дкъ спнбмъ~0 мюл мюдн опнбепхрэ, врн $$ \perm{m}{0}a_0-\perm{m+1}{2}a_{-2}+\perm{m+2}{4}a_{-4}-\perm{m+3}{6}a_{-6}+\cdots =\sum_{k\ge0}\perm{m+k}{2k}\perm{2k}{k}{(-1)^k\over k+1} =\delta_{m0} \eqno(7) $$ дкъ~$0\le m \le T-2$. Й явюярэч, щрс ясллс лнфмн бшвхякхрэ ярюмдюпрмшлх лерндюлх (щрн "гюдювю~2", ндхм хг нямнбмшу опхлепнб б рейяре о.~4.2.6). Реоепэ лнфмн бшвхякхрэ йнщттхжхемрш~$B(z)-q_1(z)A(z)$ х~р.~д. Пюяялнрпхл, мюопхлеп, йнщттхжхемр опх~$z^{2m}$ б~$D(z)-q_3(z)A(z)$. Нм пюбем $$ \eqalign{ \sum_{k\ge0}\perm{3+m+k}{2m+2k}(-1)^{m+k}a_{-2k} &=\sum_{k\ge0}\perm{3+m+k}{2m+2k}\perm{2k}{k}{(-1)^{m+k}\over k+1}=\cr &=(-1)^m\left(\perm{2+m}{2m-1}-\perm{3+m}{2m}\right)=\cr &=(-1)^{m+1}\perm{2+m}{2m}\cr } $$ хг пегскэрюрю "гюдювх~3" б~о.~1.2.6. Рюйхл напюгнл, лш бшбекх тнплскш $$ \eqalign{ A(z) &=q_0(z)A(z);\cr B(z) &=q_1(z)A(z)-q_0(z);\cr C(z) &=q_2(z)A(z)-q_1(z);\cr D(z) &=q_3(z)A(z)-q_2(z);\cr E(z) &=q_4(z)A(z)-q_3(z).\cr } \eqno (8) $$ Йпнле рнцн, хлеел~$e_{n+1}=a_n$; якеднбюрекэмн, $zA(z)=E(z)$ х $$ A(z)=q_3(z)/(q_4(z)-z). \eqno (9) $$ Опнхгбндъыхе тсмйжхх ашкх бшпюфемш опх онлных $q\hbox{-лмнцнвкемнб}$, онщрнлс лш унрхл ксвье хгсвхрэ~$q$. Б щрнл нрмньемхх онкегмн соп.~1.2.9-15, рюй йюй нмн дюер бшпюфемхе б гюлймсрнл %%352 бхде, йнрнпне лнфер ашрэ гюохяюмн йюй $$ q_m(z)={((\sqrt{4-z^2}+iz)/2)^{2m+1}+((\sqrt{4-z^2}-iz)/2)^{2m+1} \over \sqrt{4-z^2}} \eqno(10) $$ Бяе сопныюеряъ, еякх реоепэ онкнфхрэ~$z=2 \sin\theta$: $$ \eqalignno{ q_m(2\sin\theta)=& {(\cos\theta+i\sin\theta)^{2m+1}+(\cos\theta-i\sin\theta)^{2m+1}\over 2\cos\theta}=\cr &={\cos(2m+1)\theta\over \cos\theta}. & (11)\cr } $$ (Щрн янбоюдемхе гюярюбкъер дслюрэ, врн лмнцнвкемш~$q_m(z)$ унпньн хгбеярмш б люрелюрхйе; х деиярбхрекэмн, бгцкъмсб б яннрберярбсчыхе рюакхжш, бхдхл, врн~$q_m(z)$, он ясыеярбс, лмнцнвкем Веашь╦бю брнпнцн пндю, ю хлеммн~$(-1)^m U_{2m}(z/2)$ б нашвмшу нангмювемхъу.) Реоепэ лнфмн нопедекхрэ йнпмх гмюлемюрекъ б~(9): $q_4(2\sin\theta)=2\sin\theta$ ябндхряъ й $$ \cos 9\theta = 2 \sin \theta \cos \theta = \sin 2\theta. $$ Пеьемхъ щрнцн яннрмньемхъ онксвюел, еякх рнкэйн~$\pm9\theta=2\theta+\left(2n-{1\over2}\right)\pi$; бяе рюйхе~$\theta$ дючр йнпмх гмюлемюрекъ б~(9) опх сякнбхх, врн~$\cos\theta\ne 0$. (Еякх~$\cos\theta=0$, рн~$q_m(\pm2)=\pm(2m+1)$, мхйнцдю ме пюбмн~$\pm2$.) Якеднбюрекэмн, онксвюел 8~пюгкхвмшу йнпмеи: $$ \displaylines{ q_4(z)-z=0 \qquad \hbox{ опх } z=2\sin{-5\over 14}\pi,\quad 2\sin{-1 \over 14}\pi,\quad 2\sin{3 \over 14}\pi, \cr 2\sin{-7 \over 22}\pi,\quad 2\sin{-3 \over 22}\pi,\quad 2\sin{1 \over 22}\pi, \quad 2\sin{5 \over 22}\pi,\quad 2\sin{9 \over 22}\pi.\cr } $$ Рюй йюй~$q_4(z)$---лмнцнвкем яреоемх~8, лш свкх бяе йнпмх. Оепбше рпх хг щрху гмювемхи дючр~$q_3(z)=0$, рюй врн~$q_3(z)$ х~$q_4(z)-z$ хлечр наыхл декхрекел лмнцнвкем рперэеи яреоемх. Нярюкэмше оърэ йнпмеи сопюбкъчр юяхлорнрхвеяйхл онбедемхел йнщттхжхемрнб~$A(z)$, еякх пюгкнфхрэ~(9) б щкелемрюпмше дпнах. Оепеидъ й пюяялнрпемхч наыецн яксвюъ $T$~кемр, онкнфхл~$\theta_k=(4k+1)\pi/(4T-2)$. Опнхгбндъыюъ тсмйжхъ~$A(z)$ дкъ $T\hbox{-кемрнвмшу}$ йюяйюдмшу вхяек опхмхлюер бхд $$ {4\over 2T-1}\sum_{-T/2j$ х еякх $A$~еярэ хлъ кемрш, рн депебн ме яндепфхр йнмтхцспюжхх \picture{p.362} %%363 c)~еякх~$i k \ge r$ х~$y^{(i)}_j=-1$, $y^{(k)}_j=+1$. Жекэ щрнцн сопюфмемхъ---днйюгюрэ, врн \emph{йюяйюдмне якхъмхе лхмхлхгхпсер вхякн ярюдхи} япедх бяеу яуел якхъмхъ я рел фе вхякнл кемр х мювюкэмшу нрпегйнб. Сднамн ббеярх мейнрнпше нангмювемхъ. Асдел охяюрэ~$v\to w$, еякх~$v$ х~$w$---рюйхе $T\hbox{-бейрнпш}$, врн ясыеярбсер яуелю якхъмхъ, йнрнпюъ б ябнеи оепбни ярюдхх оепебндхр~$w$ б~$v$ (р.~е.\ ясыеярбсер яуелю якхъмхъ~$y^{(m)}\ldots{}y^{(0)}$, рюйюъ, врн $y^{(m)}\ldots{}y^{(l+1)}$~ъбкъеряъ ярюдхеи, $w=y^{(m)}+\cdots+y^{(0)}$ х~$v=y^{(l)}+\cdots+y^{(0)}$). Асдел охяюрэ~$v\preceq w$, еякх~$v$ х~$w$---$T\hbox{-бейрнпш}$, рюйхе, врн ясллю мюханкэьху $k$~щкелемрнб бейрнпю~$v$ ме опебшьюер ясллш мюханкэьху $k$~щкелемрнб бейрнпю~$w$ опх~$1\le k \le T$. Рюй, мюопхлеп, $(2, 1, 2, 2, 2, 1) \preceq (1, 2, 3, 0, 3, 1)$, рюй йюй $2\le 3$, $2+2\le 3+3$,~\dots, $2+2+2+2+ 1+1\le 3+3+2+1+1 +0$. Мюйнмеж, еякх~$v=(v_1,~\ldots, v_T)$, рн осярэ~$C(v)=(s_T, s_{T-2}, s_{T-3},~\ldots, s_1, 0)$, цде $s_k$~еярэ ясллю мюханкэьху $k$~щкелемрнб бейрнпю~$v$. %% !!! яяшкйю мю сопюфмемхе (a)~Днйюфхре, врн~$v\to C(v)$. (b)~Днйюфхре, врн~$v\preceq w$ бкевер~$C(v)\preceq C(w)$. (c)~Явхрюъ хгбеярмшл пегскэрюр соп.~24, днйюфхре, врн йюяйюдмне якхъмхе лхмхлхгхпсер вхякн ярюдхи. %% !!! яяшкйю мю сопюфмемхе \ex[Л35] Хяонкэгсъ нангмювемхъ соп.~23, днйюфхре, врн~$v\to w$ бкевер~$w\preceq C(v)$. %% !!! яяшкйю мю сопюфмемхе \ex[Л36] (П.~Л.~Йюпо.) Асдел цнбнпхрэ, врн яецлемр~$y^{(q)}\ldots{}y^{(r)}$ яуелш якхъмхъ ъбкъеряъ \dfn{тюгни,} еякх мх ндмю хг кемр ме хяонкэгсеряъ х дкъ ббндю, х дкъ бшбндю, р.~е.\ еякх ме ясыеярбсер~$i$, $j$, $k$, рюйху, врн~$q\ge i$, $k\ge r$ х~$y^{(i)}_j=+1$, $y^{(k)}_j=-1$. Жекэ щрнцн сопюфмемхъ---хяякеднбюрэ яуелс якхъмхъ, йнрнпюъ лхмхлхгхпсер вхякн тюг. Лш асдел охяюрэ~$v \To w$, еякх~$w$ лнфер ашрэ опенапюгнбюмн б~$v$ гю ндмс тюгс (яп.~я~онднамшл нангмювемхел, ббедеммшл б соп.~23), х осярэ~$D_k(v)=(s_k+t_{k+1}, s_k+t_{k+2},~\ldots, s_k+t_T, 0,~\ldots, 0)$, цде~$t_j$ нангмювюер~$j\hbox{-и}$ б онпъдйе сашбюмхъ щкелемр~$v$ х~$s_k=t_1+\cdots+t_k$. (a)~Днйюфхре, врн~$v\To D_k(v)$ опх~$1\le k < T$. (b)~Днйюфхре, врн хг~$v\preceq w$ якедсер~$D_k(v)\preceq D_k(w)$ опх~$1\le k < T$. (c)~Днйюфхре, врн хг~$v\To w$ якедсер~$w\preceq D_k(v)$ дкъ мейнрнпнцн~$k$, $1\le k < T$. (d)~Якеднбюрекэмн, яуелю якхъмхъ, янпрхпсчыюъ люйяхлюкэмне вхякн мювюкэмшу нрпегйнб мю $T$~кемрюу гю $q$~тюг, лнфер ашрэ хгнапюфемю онякеднбюрекэмнярэч .жекшу вхяек~$k_1 k_2~\ldots k_q$, рюйни, врн мювюкэмне пюяопедекемхе еярэ~$D_{k_q}(\ldots D_{k_2}(D_{k_1}(u))\ldots)$, %!!! яяшкйю мю сопюфмемхе цде~$u=(1, 0,~\ldots, 0)$. Щрю ярпюрецхъ лхмхлслю тюг, хлеер яхкэмне $T\hbox{-fifo}$~опедярюбкемхе, х нмю рюйфе бундхр б йкюяя яуел соп.~22. Йнцдю~$T=3$, щрн \emph{лмнцнтюгмюъ} яуелю, ю опх~$T=4$, 5, 6, 7 щрн бюпхюжхъ \emph{яаюкюмяхпнбюммни} яуелш. %!!! яяшкйю мю сопюфмемхе \ex[Л46] (П.~Л.~Йюпо). Бепмн кх, врн норхлюкэмюъ онякеднбюрекэмнярэ~$k_1 k_2~\ldots k_q$, сонлъмсрюъ б соп.~25, бяецдю пюбмю~$1\ceil{T/2}\floor{T/2}\ceil{T/2}\floor{T/2}~\ldots$ дкъ бяеу~$T\ge 4$ х бяеу днярюрнвмн анкэьху~$q$? \subsubchap{Няжхккхпсчыюъ янпрхпнбйю}%5.4.5 Еые ндхм ондунд й янпрхпнбйе якхъмхел ашк опедкнфем Ьекднмнл Янаекел б [{\sl JACM,\/} {\bf 9} (1962), 372--375]. Блеярн рнцн врнаш мювхмюрэ я опнундю пюяопедекемхъ, йнцдю бяе мювюкэмше нрпегйх пюяопедекъчряъ он кемрюл, нм опедкнфхк юкцнпхрл, йнрнпши оепейкчвюеряъ рн мю пюяопедекемхе, рн мю якхъмхе, рюй врн анкэьюъ вюярэ янпрхпнбйх опнхяундхр еые дн рнцн, йюй бяъ хяундмюъ хмтнплюжхъ асдер онкмнярэч опнялнрпемю. %%371 Опедонкнфхл, мюопхлеп, врн дкъ якхъмхъ хяонкэгсеряъ оърэ кемр. Он лерндс Янаекъ 16~мювюкэмшу нрпегйнб асдср янпрхпнбюрэяъ якедсчыхл напюгнл: \ctable{ #\hfil\bskip&#\hfil\bskip&\hfil$#$\hfil\bskip&\hfil$#$\hfil\bskip &\hfil$#$\hfil\bskip&\hfil$#$\hfil\bskip&\hfil$#$\hfil\bskip &#\hfil\cr & \hfil Ноепюжхъ& T1 & T2 & T3 & T4 & T5 & \hbox{Ярнхлнярэ} \cr Тюгю~1.& Пюяопедекемхе & A_1 & A_1 & A_1 & A_1 & - & 4\cr Тюгю~2.& Якхъмхе & - & - & - & - & D_4 & 4\cr Тюгю~3.& Пюяопедекемхе & - & A_1 & A_1 & A_1 & D_4A_1& 4\cr Тюгю~4.& Якхъмхе & D_4 & - & - & - & D_4 & 4\cr Тюгю~5.& Пюяопедекемхе & D_4A_1& - & A_1 & A_1 & D_4A_1& 4\cr Тюгю~6.& Якхъмхе & D_4 & D_4 & - & - & D_4 & 4\cr Тюгю~7.& Пюяопедекемхе & D_4A_1& D_4A_1& - & A_1 & D_4A_1& 4\cr Тюгю~8.& Якхъмхе & D_4 & D_4 & D_4 & - & D_4 & 4\cr Тюгю~9.& Якхъмхе & - & - & - & A_{16} & - & 16\cr } Гдеяэ, йюй х б о.~5.4.4, лш хяонкэгсел~$A_r$ х~$D_r$ дкъ нангмювемхъ яннрберярбеммн бнгпюярючыху х сашбючыху нрпегйнб нрмняхрекэмни дкхмш~$r$. Пюяялюрпхбюелши лернд мювхмюер я гюохях он ндмнлс мювюкэмнлс нрпегйс мю йюфдсч хг вершпеу кемр х якхбюер ху (вхрюъ б напюрмнл мюопюбкемхх) мю оърсч кемрс. Ноърэ бнгнамнбкъеряъ пюяопедекемхе, мю щрнр пюг жхйкхвеяйх ядбхмсрне мю~1 бопюбн он нрмньемхч й кемрюл, х брнпне якхъмхе дюер еые ндхм нрпегнй~$D_4$. Йнцдю щрхл яонянанл ятнплхпнбюмш вершпе нрпегйю~$D_4$, днонкмхрекэмне якхъмхе янгдюер~$A_{16}$. Опнжеяя лнфмн опнднкфюрэ, янгдюбюъ еые рпх~$A_{16}$, якхбюъ ху б~$D_{64}$ х~р.~д.\ дн реу онп, онйю ме хявепоючряъ хяундмше дюммше. Ме мсфмн гмюрэ гюпюмее дкхмс хяундмшу дюммшу. Еякх вхякн мювюкэмшу нрпегйнб~$S$ еярэ~$4^m$, рн мерпсдмн бхдерэ, врн щрнр лернд напюаюршбюер йюфдсч гюохяэ пнбмн $m+1$~пюг (ндхм пюг бн бпелъ пюяопедекемхъ х $m$~пюг бн бпелъ якхъмхъ). Еякх~$S$ кефхр лефдс~$4^{m-1}$ х~$4^m$, рн лнфмн я онлныэч тхйрхбмшу нрпегйнб сбекхвхрэ~$S$ дн~$4^m$; якеднбюрекэмн, наыее бпелъ янпрхпнбйх асдер нопедекърэяъ $\ceil{\log_4 S}+1$~опнундюлх он бяел дюммшл. Щрн йюй пюг рн, врн днярхцюеряъ опх яаюкюмяхпнбюммни янпрхпнбйе мю \emph{бняэлх} кемрюу; б наыел яксвюе няжхккхпсчыюъ янпрхпнбйю я $T$~пюанвхлх кемрюлх щйбхбюкемрмю яаюкюмяхпнбюммнлс якхъмхч я $2(T-1)$~кемрюлх, рюй йюй нмю декюер $\ceil{\log_{T-1} S}+1$~опнунднб он дюммшл. Еякх $S$~нйюгшбюеряъ яреоемэч~$T-1$, рн щрн яюлне ксвьее, врн лнфмн онксвхрэ опх \emph{кчанл} лернде я $T$~кемрюлх, рюй йюй гдеяэ днярхцюеряъ мхфмъъ нжемйю хг яннрмньемхъ~(5.4.4-9). Я дпсцни ярнпнмш, еякх~$S$ пюбмн~$(T-1)^{m-1}+1$, р.~е.\ пнбмн мю едхмхжс анкэье яреоемх~$T-1$, рн щрнр лернд репъер онврх жекши опнунд. Б соп.~2 онйюгюмн, йюй сярпюмхрэ вюярэ щрни кхьмеи пюанрш, хяонкэгсъ яоежхюкэмсч опнцпюллс нйнмвюмхъ. Еые ндмн сянбепьемярбнбюмхе ашкн опедкнфемн б 1966~ц. Демхянл~К.~Ащмвепнл, %% 372 йнрнпши мюгбюк ябнч опнжедспс оепейпеярмшл якхъмхел. [Ял.~H.~Wedekind, Datenorganisation (Berlin W. de Gruyter, 1970). 164--166, х~U.~S.~Patent~3540000 (10~мнъапъ 1970).] Нямнбмюъ хдеъ янярнхр б рнл, врнаш нркнфхрэ якхъмхе дн реу онп, онйю ме асдер мюйнокемн анкэье ябедемхи на~$S$. Лш наясдхл меяйнкэйн хглемеммсч тнплс оепбнмювюкэмни яуелш Ащмвепю. Щрю сксвьеммюъ няжхккхпсчыюъ янпрхпнбйю деиярбсер якедсчыхл напюгнл: \ctable{ #\hfil\bskip&#\hfil\bskip&\hfil$#$\hfil\bskip&\hfil$#$\hfil\bskip &\hfil$#$\hfil\bskip&\hfil$#$\hfil\bskip&\hfil$#$\hfil\bskip &#\hfil\cr & Ноепюжхъ & T1 & T2 & T3 & T4 & Р5 & \hbox{Ярнхлнярэ} \cr Тюгю~1.& Пюяопедекемхе& - & A_1 & A_1 & A_1 & A_1 & 4\cr Тюгю~2.& Пюяопедекемхе& - & A_1 & A_1A_1& A_1A_1& A_1A_1& 3\cr Тюгю~3.& Якхъмхе & D_4 & - & A_1 & A_1 & A_1 & 4\cr Тюгю~4.& Пюяопедекемхе& D_4A_1& - & A_1 & A_1A_1& A_1A_1& 3\cr Тюгю~5.& Якхъмхе & D_4 & D_4 & - & A_1 & A_1 & 4\cr Тюгю~6.& Пюяопедекемхе& D_4A_1& D_4A_1& - & A_1 & A_1A_1& 3\cr Тюгю~7.& Якхъмхе & D_4 & D_4 & D_4 & - & A_1 & 4\cr Тюгю~8.& Пюяопедекемхе& D_4A_1& D_4A_1& D_4A_1& - & A_1 & 3\cr Тюгю~9.& Якхъмхе & D_4 & D_4 & D_4 & D_4 & - & 4\cr \noalign{\smallskip \noindent Б щрнр лнлемр лш ме якхбюел бяе~$D_4$ б~$A_{16}$, (еякх рнкэйн ме нйюферяъ, врн хяундмше дюммше хявепоюмш); кхьэ оняке рнцн, йюй гюйнмвхряъ \smallskip} Тюгю~15.& Якхъмхе & D_4 D_4 & D_4 D_4 & D_4 D_4 & D_4 & - & 4 \cr \noalign {\smallskip \noindent асдер онксвем оепбши нрпегнй~$A_{16}$: \smallskip} Тюгю~16. & Якхъмхе & D_4 & D_4 & D_4 - & A_{16} & 16 \cr \noalign{\smallskip \noindent Брнпни нрпегнй~$A_{16}$ онъбхряъ оняке янгдюмхъ еые рпеу~$D_4$: \smallskip} Тюгю~22. & Якхъмхе & D_4 D_4 & D_4 D_4 & D_4 & - & A_{16}D_4 & 4\cr Тюгю~23. & Якхъмхе & D_4 & D_4 & - & A_{16} & A_{16} & 16 \cr } х~р.~д.\ (яп.~я~тюгюлх~1--5). Опехлсыеярбю яуелш Ащмвепю лнфмн бхдерэ, еякх хлееряъ, мюопхлеп, рнкэйн оърэ мювюкэмшу нрпегйнб: няжхккхпсчыюъ янпрхпнбйю (ее лндхтхйюжхъ хг соп.~2) бшонкмъкю аш вершпеуосребне якхъмхе (мю тюге~2), гю йнрнпшл якеднбюкн аш дбсуосребне якхъмхе я наыеи ярнхлнярэч~$4+4+4+1+5= 14$, рнцдю йюй яуелю Ащмвепю бшонкмъкю аш дбсуосребне якхъмхе (мю тюге~3), гю йнрнпшл якеднбюкн аш вершпеуосребне якхъмхе я наыеи ярнхлнярэч~$4+1+2+5=12$. (Наю лерндю рюйфе рпеасчр меанкэьху днонкмхрекэмшу гюрпюр, хлеммн ндмнйпюрмни оепелнрйх оепед нйнмвюрекэмшл якхъмхел.) %%373 Рнвмне нохяюмхе лерндю Ащмвепю яндепфхряъ мхфе б юкцнпхрле~B. Й янфюкемхч, яннрберярбсчысч опнжедспс, он-бхдхлнлс, рпсдмеи онмърэ, вел гюопнцпюллхпнбюрэ; кецве на╝ъямхрэ щрнр лернд ЩБЛ, вел опнцпюллхярс! Вюярхвмн щрн опнхяундхр он рни опхвхме, врн пейспяхбмши лернд бшпюфем б хрепюрхбмнл бхде х гюрел ондбепцмср мейнрнпни норхлхгюжхх; вхрюрекэ, бнглнфмн, намюпсфхр, врн менаундхлн меяйнкэйн пюг опнякедхрэ гю пюанрни юкцнпхрлю, врнаш деиярбхрекэмн нянгмюрэ, врн фе опнхяундхр. \alg B.(Няжхккхпсчыюъ янпрхпнбйю я оепейпеярмшл пюяопедекемхел.) Щрнр юкцнпхрл аепер оепбнмювюкэмше нрпегйх х пюяопедекъер ху мн кемрюл, бпелъ нр бпелемх опепшбюъ опнжеяя пюяопедекемхъ, врнаш якхрэ яндепфхлне мейнрнпшу кемр. \picture{Пхя.~77. Няжхккхпсчыюъ янпрхпнбйю я оепейпеярмшл пюяопедекемхел.} Б юкцнпхрле хяонкэгсеряъ $P\hbox{-осребне}$ якхъмхе х опедонкюцюеряъ, врн еярэ $T=P+1\ge 3$~кемрнвмшу сярпниярб (ме явхрюъ сярпниярбю, йнрнпне лнфер ашрэ менаундхлн дкъ упюмемхъ хяундмшу дюммшу). Кемрнвмше сярпниярбю днкфмш дносяйюрэ времхе йюй б опълнл, рюй х б напюрмнл мюопюбкемхх; нмх нангмювемш вхякюлх~0, 1,~\dots, $P$. Хяонкэгсчряъ якедсчыхе люяяхбш: {\medskip\narrower \item{$|D|[j]$,} $0\le j \le P$---вхякн тхйрхбмшу нрпегйнб, мюкхвхе йнрнпшу опедонкюцюеряъ б йнмже кемрш~$j$. \item{$|A|[l, j]$,} $0\le l \le L$, $0\le j \le P$. Гдеяэ~$L$---днярюрнвмн анкэьне вхякн, рюйне, врн асдер ббедемн ме анкее~$P^{L+1}$ мювюкэмшу нрпегйнб. Еякх~$|A|[l, j]=k \ge 0$, рн мю кемре~$j$ хлееряъ нрпегнй мнлхмюкэмни дкхмш~$P^k$, яннрберярбсчыхи "спнбмч~$l$" пюанрш юкцнпхрлю. Щрнр нрпегнй бнгпюярючыхи, еякх $k$~вермн, х сашбючыхи, еякх $k$~мевермн. $|A|[l, j]=-1$~нгмювюер, врн мю спнбме~$l$ кемрю~$j$ ме хяонкэгсеряъ. \medskip} \noindent Хмярпсйжхъ "гюохяюрэ мювюкэмши нрпегнй мю кемрс~$j$" ъбкъеряъ янйпюыеммшл нангмювемхел якедсчыху деиярбхи: %%374 {\medskip\narrower \noindent Сярюмнбхрэ~$|A|[l, j]\asg 0$. Еякх хяундмше дюммше хявепоюмш, рн сбекхвхрэ~$|D|[j]$ мю~1; б опнрхбмнл яксвюе гюохяюрэ нрпегнй мю кемрс~$j$ (б бнгпюярючыел онпъдйе). \medskip} \noindent Хмярпсйжхъ "якхрэ мю кемрс~$j$" хяонкэгсеряъ йюй йпюрйне нангмювемхе якедсчыху деиярбхи: {\medskip\narrower \noindent Еякх~$|D|[i]>0$ дкъ бяеу~$i\ne j$, рн слемэьхрэ~$|D|[i]$ мю~1 опх бяеу~$i\ne j$ х сбекхвхрэ~$|D|[j]$ мю~1. Б опнрхбмнл яксвюе якхрэ ндхм нрпегнй мю кемрс~$j$ ян бяеу кемр~$i\ne j$, рюйху, врн~$|D|[i]=0$, х слемэьхрэ~$|D|[i]$ мю~1 дкъ бяеу нярюкэмшу~$i\ne j$. \medskip} \st[Мювюкэмюъ сярюмнбйю.] Сярюмнбхрэ~$|D|[j]\asg 0$ опх~$0\le j \le P$. Гюрел гюохяюрэ мювюкэмши нрпегнй мю кемрс~$j$ опх~$1 \le j \le P$. Сярюмнбхрэ~$|A|[0,0]\asg -1$, $l\asg 0$, $q\asg 0$. \st[Ббнд гюбепьем?] (Б щрнр лнлемр кемрю~$q$ осярю х бяъйюъ дпсцюъ кемрю яндепфхр яюлне анкэьее ндхм нрпегнй.) Еякх еые еярэ хяундмше дюммше, оепеирх й ьюцс~\stp{3}. Ндмюйн еякх ббнд хявепоюм, рн оепелнрюрэ бяе кемрш~$j\ne q$, рюйхе, врн $|A|[0, j]$~вермн; гюрел якхрэ мю кемрс~$q$, вхрюъ бяе рнкэйн врн оепелнрюммше кемрш б опълнл мюопюбкемхх, ю нярюкэмше кемрш---б напюрмнл. Щрхл гюбепьюеряъ янпрхпнбйю; пегскэрюр мюундхряъ мю кемре~$q$ б бнгпюярючыел онпъдйе. \st[Мювюрэ мнбши спнбемэ.] Сярюмнбхрэ~$l \asg l+1$, $r \asg q$, $s \asg 0$ х~$q\asg (q+1) \bmod T$. Гюохяюрэ мювюкэмши нрпегнй мю кемрс~$(q+j) \bmod T$ опх~$1 \le j \le T-2$. (Рюйхл напюгнл, мювюкэмше нрпегйх гюохяшбючряъ мю бяе кемрш, йпнле кемр~$q$ х~$r$.) Сярюмнбхрэ~$|A|[l, q]\asg -1$ х~$|A|[l, r] \asg -1$. \st[Лнфмн кх якхбюрэ?] Еякх~$|A|[l-1, q]\ne s$, бепмсрэяъ й ьюцс~\stp{3}. \st[Якхъмхе.] (Б щрнр лнлемр $|A|[l-1, q]=|A|[l, j]=s$ опх бяеу~$j\ne q$, $j \ne r$.) Якхрэ мю кемрс~$r$. (Ял.\ бшье нопедекемхе щрни ноепюжхх.) Гюрел сярюмнбхрэ~$s \asg s+1$, $l \asg l-1$, $|A|[l, r]\asg s$ х~$|A|[l, q] \asg -1$. Сярюмнбхрэ~$r \asg (2q-r)\bmod T$. (Б наыел яксвюе лш хлеел~$r=(q-1)\bmod T$, еякх $s$~вермн, х~$r=(q+1) \bmod T$, еякх $s$~мевермн.) \st[Гюйнмвем кх спнбемэ?] Еякх~$l=0$, оепеирх й~\stp{2}. Б опнрхбмнл яксвюе, еякх~$|A|[l, j]=s$ дкъ бяеу~$j\ne q$ х~$j\ne r$, рн оепеирх й~\stp{4}. Б опнрхбмнл яксвюе бепмсрэяъ й~\stp{3}. \algend Врнаш онйюгюрэ опюбхкэмнярэ щрнцн юкцнпхрлю, лш лнфел хяонкэгнбюрэ днйюгюрекэярбн рхою "пейспяхбмни хмдсйжхх", рюй фе йюй лш декюкх дкъ юкцнпхрлю~2.3.1T. Опедонкнфхл, врн лш мювхмюел я ьюцю~B3 я~$l=l_0$, $q=q_0$, $s_+=|A|[l_0, (q_0+1)\bmod T]$ х~$s_-=|A|[l_0, (q_0-1)\bmod T]$, х дносярхл, йпнле рнцн, врн кхан~$s_+=0$, кхан~$s_-=1$, кхан~$s_+=2$, кхан~$s_-=3$, кхан~$\ldots\,$. Лнфмн опнбепхрэ он хмдсйжхх, врн юкцнпхрл б йнмже йнмжнб опхдер й ьюцс~B5, ме хглемхб я мскебни он~$l\hbox{-ч}$ ярпнйх~|A| х ян гмювемхълх %%375 оепелеммшу~$l=l_0+1$, $q=q_0\pm 1$, $r=q_0$ х~$s=s_+ \ror s_-$, опхвел лш бшахпюел гмюй~$+$, еякх~$s_+=0 \ror (s_+=2 \rand s_-\ne 1) \ror (s_+=4 \rand s_-\ne 1, 3) \ror \ldots$, х лш бшахпюел гмюй~$-$, еякх~$(s_-=1 \rand s_+=0) \ror (s_-=3 \rand s_+\ne 0, 2)\ror \ldots\,$. Опхбедеммши гдеяэ мюапнянй днйюгюрекэярбю ме нвемэ щкецюмрем, мн х яюл юкцнпхрл ятнплскхпнбюм б бхде, йнрнпши анкэье цндхряъ дкъ пеюкхгюжхх, вел дкъ опнбепйх опюбхкэмнярх. \picture{Пхя.~78 Щттейрхбмнярэ няжхккхпсчыеи янпрхпнбйх, хяонкэгсчыеи лернд юкцнпхрлю~B х~соп.~3.} Мю пхя.~78 онйюгюмю щттейрхбмнярэ юкцнпхрлю~B, бшпюфеммюъ япедмхл вхякнл якхъмхи йюфдни гюохях б гюбхяхлнярх нр~$S$---вхякю мювюкэмшу нрпегйнб, опхвел опедонкюцюеряъ, врн мювюкэмше нрпегйх опхакхгхрекэмн пюбмш он дкхме. (Яннрберярбсчыхе цпютхйх дкъ лмнцнтюгмни х йюяйюдмни янпрхпнбйх опхбедемш мю пхя.~70 х~74.) Опх ондцнрнбйе пхя.~78 свремн меанкэьне сянбепьемярбнбюмхе, сонлъмсрне б соп.~3. %%376 \section Опълне времхе. Яуелю няжхккхпсчыеи янпрхпнбйх, он-бхдхлнлс, рпеасер бнглнфмнярх напюрмнцн времхъ, оняйнкэйс опхундхряъ цде-рн мюйюокхбюрэ дкхммше нрпегйх он лепе рнцн, йюй лш якхбюел бмнбэ ббедеммше йнпнрйхе нрпегйх. Рел ме лемее Л.~Ю.~Цнрж [Proc. AFIPS Spring Jt. Янрп. Conf.; {\bf 25} (1964), 599--607] мюьек яоняна бшонкмхрэ няжхккхпсчысч янпрхпнбйс, хяонкэгсъ рнкэйн опълне времхе х опнярсч оепелнрйс. Ецн лернд б йнпме нркхвюеряъ нр нярюкэмшу яуел, йнрнпше лш бхдекх б щрни цкюбе, оняйнкэйс a)~дюммше хмнцдю гюохяшбючряъ б мювюкн кемрш, опхвел опедонкюцюеряъ, врн дюммше, мюундъыхеяъ б \emph{яепедхме} щрни кемрш, ме пюгпсьючряъ; b)~бяе мювюкэмше ярпнйх хлечр тхйяхпнбюммсч люйяхлюкэмсч дкхмс. Сякнбхе~(a) мюпсьюер ябниярбн "оепбшл бйкчвюеряъ---оепбшл хяйкчвюеряъ", йнрнпне, йюй лш опедонкнфхкх, ъбкъеряъ уюпюйрепхярхйни опълнцн времхъ, ндмюйн нмн лнфер ашрэ мюдефмн пеюкхгнбюмн, еякх лефдс нрпегйюлх нярюбкърэ днярюрнвмне йнкхвеярбн вхярни кемрш х еякх б мсфмше лнлемрш опемеапевэ "ньхайюлх вермнярх". Сякнбхе~(b) нйюгшбюеряъ дн мейнрнпни яреоемх опнрхбнпевюыхл щттейрхбмнлс хяонкэгнбюмхч бшанпю я гюлеыемхел. Няжхккхпсчыюъ янпрхпнбйю Цнржю я опълшл времхел хлеер ндмн релмне оърмн---щрн ндхм хг оепбшу юкцнпхрлнб, йнрнпши ашк гюоюремрнбюм йюй юкцнпхрл, ю ме йюй тхгхвеяйне сярпниярбн [U.~S.~Patent~3380029 (23~юопекъ 1968)]. Еякх онкнфемхе ме хглемхряъ, рн щрн нгмювюер, врн юкцнпхрл мекэгъ хяонкэгнбюрэ б опнцпюлле аег пюгпеьемхъ бкюдекэжю оюремрю. Лернд Ащмвепю (няжхккхпсчыюъ янпрхпнбйю я напюрмшл времхел) ашк гюоюремрнбюм IBM меяйнкэйхлх цндюлх онгфе. [Рюйхл напюгнл, мюярсохк йнмеж щпш, йнцдю сднбнкэярбхе нр нрйпшрхъ мнбнцн юкцнпхрлю явхрюкняэ днярюрнвмшл бнгмюцпюфдемхел! Рюй йюй опнцпюллхпнбюмхе менрдекхлн нр янгдюмхъ люьхмш, ю опнцпюллш дкъ ЩБЛ реоепэ ярнър демец, рн оюремрнбюмхе юкцнпхрлнб ъбкъеряъ мехгаефмшл. Йнмевмн, деиярбхъ медюкэмнбхдмшу кчдеи, янупюмъчыху мнбше юкцнпхрлш б ярпнцнл яейпере, гмювхрекэмн усфе, вел ьхпнйюъ днярсомнярэ юкцнпхрлнб, йнрнпше ъбкъчряъ янаярбеммнярэч б ревемхе кхьэ нцпюмхвеммнцн бпелемх.] Жемрпюкэмюъ хдеъ б лернде Цнржю янярнхр б рюйнл хяонкэгнбюмхх кемр, врнаш йюфдюъ кемрю мювхмюкюяэ я нрпегйю нрмняхрекэмни дкхмш~1, гю йнрнпшл якеднбюк аш нрпегнй нрмняхрекэмни дкхмш~$P$, гюрел~$P^2$ х~р.~д. Мюопхлеп, еякх~$T=5$, рн янпрхпнбйю мювхмюеряъ якедсчыхл напюгнл ("."~сйюгшбюер рейсыее онкнфемхе цнкнбйх времхъ-гюохях мю йюфдни кемре): %%377 \ctable{ #\hfil\bskip&#\hfil\bskip&\hfil$#$\hfil\bskip&\hfil$#$\hfil\bskip &\hfil$#$\hfil\bskip&\hfil$#$\hfil\bskip&\hfil$#$\hfil\bskip &\hfil$#$\hfil\bskip&#\hfil\cr & Ноепюжхъ & T1 & T2 & T3 & T4 & T5 & \hbox{Ярнхлнярэ} & Опхлевюмхъ \cr Тюгю~1. & Пюяопедекемхе& A_1 & .A_1 & .A_1 & .A_1 & A_1. & 5& [T5 ме оепелюршбюеряъ]\cr Тюгю~2. & Якхъмхе & A_1. & A_1. & A_1. & A_1. & A_1A_4. & 4& [Оепелнрйю бяеу кер]\cr Тюгю~3. & Пюяопедекемхе& A_1 & .A_1 & .A_1 & A_1. & .A_1A_4 & 4& [T4 ме оепелюршбюеряъ]\cr Тюгю~4. & Якхъмхе & A_1. & A_1. & A_1. & A_1A_4.& A_1.A_4 & 4& [Оепелнрйю бяеу кемр]\cr Тбщю~5. & Пюяопедекемхе& A_1 & .A_1 & A_1. & .A_1A_4& .A_1A_4 & 4& [T3 ме оепелюршбюеряъ]\cr Тюгю~6. & Якхъмхе & A_1. & A_1. & A_1A_4.& A_1.A_4& A_1.A_4 & 4& [Оепелнрйю бяеу кемр]\cr Тюгю~7. & Пюяопедекемхе& A_1 & A_1. & .A_1A_4& .A_1A_4& .A_1A_4 & 4& [T2 ме оепелюршбюеряъ]\cr Тюгю~8. & Якхъмхе & A_1. & A_1A_4. & A_1.A_4& A_1.A_4& A_1.A_4 & 4& [Оепелнрйю бяеу кемр]\cr тюгю~9. & Пюяопедекемхе& A_1. & .A_1A_4 & .A_1A_4& .A_1A_4& .A_1A_4 & 4& [T1 ме оепелюршбюеряъ]\cr Тюгю~10.& Якхъмхе & A_1A_4. & A_1.A_4 & A_1.A_4& A_1.A_4& A_1.A_4 & 4& [Мер оепелнрйх]\cr Тюгю~11.& Якхъмхе & A_1A_4A_{16}. & A_1A_4. & A_1A_4.& A_1A_4.& A_1A_4. & 16& [Оепелнрйю бяеу кемр]\cr } Х рюй дюкее. Бн бпелъ тюгш~1 кемрю~T1 оепелюршбюеряъ х ндмнбпелеммн мю~T2 гюохяшбючряъ хяундмше дюммше, гюрел оепелюршбюеряъ~T2 х ндмнбпелеммн мю~T3 гюохяшбючряъ хяундмше дюммше х~р.~д. Б йнмже йнмжнб, йнцдю хяундмше дюммше хявепоюмш, мювхмючр онъбкърэяъ тхйрхбмше нрпегйх, х хмнцдю менаундхлн бннапюгхрэ, врн нмх гюохяюмш ъбмн мю кемре онкмни дкхмш. Мюопхлеп, еякх~$S=18$, рн нрпегйх~$A_1$ мю~T4 х~T5 асдср тхйрхбмшлх бн бпелъ тюгш~9; мюл опхдеряъ опндбхмсрэяъ боепед он~T4 х~T5 опх якхъмхх я~T2 х~T3 мю~T1 бн бпелъ тюгш~10, рюй йюй мюл мюдн днапюрэяъ дн нрпегйнб~$A_4$ мю~T4 х~T5 дкъ ондцнрнбйх й тюге~11. Я дпсцни ярнпнмш, тхйрхбмши нрпегнй~$A_1$ мю~T1 ме наъгюрекэмн днкфем ясыеярбнбюрэ ъбмн. Рюйхл напюгнл, "йнмеж хцпш" меяйнкэйн гюлшякнбюр. Еые я ндмхл опхлепнл опхлемемхъ щрнцн лерндю лш бярперхляъ б якедсчыел осмйре. \excercises \ex[22] Б рейяре хлееряъ хккчярпюжхъ няжхккхпсчыеи янпрхпнбйх Янаекъ б ее оепбнгдюммнл бхде дкъ~$T=5$ х~$S=16$. Дюире рнвмне нопедекемхе юкцнпхрлю, б йнрнпнл щрю опнжедспю нанаыюеряъ х янпрхпсчряъ $S=P^L$~мювюкэмшу нрпегйнб мю $T=P+1\ge 3$~кемрюу. Онярюпюиреяэ мюирх юкцнпхрл, йнрнпши лнфер ашрэ нвемэ опнярн нохяюм. \ex[24] Еякх б хгмювюкэмнл лернде Янаекъ $S=6$, рн лш лнцкх аш гюъбхрэ, врн~$S=16$ х врн хлееряъ 10~тхйрхбмшу нрпегйнб. Рнцдю тюгю~3 б опхлепе б рейяре онлеярхкю аш тхйрхбмше нрпегйх~$A_0$ мю~T4 х~T5; тюгю~4 якхкю аш нрпегйх~$A_1$ мю~T2 х~T3 б~$D_2$ мю~T1; тюгш~5--8 ме декюкх аш мхвецн; тюгю~9 онпндхкю аш~$A_6$ мю~T4. Ксвье аш оепелнрюрэ~T2 х~T3 япюгс оняке тюгш~3 х гюрел меледкеммн онксвюрэ~$A_6$ мю~T4 я онлныэч рпеуосребнцн якхъмхъ. Онйюфхре, йюй, нямнбшбюъяэ мю щрни хдее, сксвьхрэ нйнмвюмхе юкцнпхрлю хг соп.~1, еякх~$S$ ме ъбкъеряъ рнвмни яреоемэч~$P$. \rex[24] Янярюбэре рюакхжс, онйюгшбючысч онбедемхе юкцнпхрлю~B, еякх~$T=3$, опедонкюцюъ, врн хлееряъ 9~мювюкэмшу нрпегйнб. Онйюфхре, врн щрю опнжедспю нвебхдмн мещттейрхбмю б ндмнл леяре, х опедкнфхре хглемемхъ б юкцнпхрле~B, йнрнпше хяопюбкъчр онкнфемхе. \ex[21] Мю ьюце~B3 хлееряъ сярюмнбйю йюй~$|A|[l, q]$, рюй х~$|A|[l, r]$ б~$-1$. Онйюфхре, врн ндмю хг щрху ноепюжхи бяецдю кхьмъъ, рюй йюй яннрберярбсчыхи щкелемр люяяхбю~|A| мхйнцдю ме пюяялюрпхбюеряъ. \ex[Л25] Осярэ~$S$---вхякн мювюкэмшу нрпегйнб б хлечыхуяъ хяундмшу дюммшу дкъ юкцнпхрлю~B. Опх йюйху гмювемхъу~$S$ ме рпеасеряъ \emph{мх ндмни оепелнрйх} мю ьюце~B2? %%378 \bye\input style \chapno=5\subchno=4\subsubchno=3\chapnotrue Йюяйюдмне якхъмхе, онднамн лмнцнтюгмнлс, мювхмюеряъ я "рнвмнцн пюяопедекемхъ" нрпегйнб он кемрюл, унръ опюбхкю рнвмнцн пюяопедекемхъ нркхвмш нр опюбхк о.~5.4.2. Йюфдюъ ярпнйю рюакхжш опедярюбкъер онкмши опнунд он \emph{бяел} дюммшл. Опнунд~2, мюопхлеп, онксвюеряъ оняпедярбнл бшонкмемхъ оърхосребнцн якхъмхъ я~T1, T2, T3, T4, T5 мю~T6, онйю~T5 ме ярюмер осярни (опх щрнл мю~T6 онлеыючряъ 15~нрпегйнб нрмняхрекэмни дкхмш~5), гюрел вершпеуосребнцн якхъмхъ я~T1, T2, T3, T4 мю~T5, гюрел рпеуосребнцн якхъмхъ мю~T4, дбсуосребнцн якхъмхъ мю~T3 х, мюйнмеж, ндмносребнцн якхъмхъ (ноепюжхх йнохпнбюмхъ) я~T1 мю~T2. Опнунд~3 онксвюеряъ рюйхл фе напюгнл осрел бшонкмемхъ ямювюкю оърхосребнцн якхъмхъ, онйю ндмю кемрю ме ярюмер осярни, гюрел вершпеуосребнцн х~р.~д. (Онунфе, врн щрнлс осмйрс ймхцх якеднбюкн аш опхябнхрэ мнлеп~5.4.3.2.1, ю ме~5.4.3!) Ъямн, врн ноепюжхх йнохпнбюмхъ хгкхьмх, х ху лнфмн ашкн аш носярхрэ. Тюйрхвеяйх, ндмюйн, б яксвюе ьеярх кемр щрн йнохпнбюмхе гюмхлюер рнкэйн меанкэьни опнжемр бяецн бпелемх. Щкелемрш, йнрнпше онксвючряъ опняршл йнохпнбюмхел, нрлевемш б опхбедеммни рюакхже гбегднвйни. Рнкэйн~25 хг~950 напюаюршбюелшу нрпегйнб опхмюдкефюр щрнлс йкюяяс. Анкэьюъ вюярэ бпелемх нрбндхряъ оърхосребнлс х вершпеуосребнлс якхъмхъл. Мю оепбши бгцкъд лнфер онйюгюрэяъ, врн йюяйюдмюъ яуелю---днбнкэмн окнуни бюпхюмр б япюбмемхх я лмнцнтюгмни, рюй йюй ярюмдюпрмюъ лмнцнтюгмюъ яуелю хяонкэгсер бяе бпелъ $(T-1)\hbox{-осребне}$ якхъмхе, б рн бпелъ йюй йюяйюдмюъ хяонкэгсер $(T-1)\hbox{-осребне}$, $(T-2)\hbox{-осребне}$, $(T-3)\hbox{-осребне}$ х~р.~д., мн б деиярбхрекэмнярх нмю юяхлорнрхвеяйх \emph{ксвье,} вел лмнцнтюгмюъ, дкъ ьеярх х анкее кемр! Йюй лш бхдекх б о.~5.4.2, бшянйхи онпъднй якхъмхъ ме ъбкъеряъ цюпюмрхеи щттейрхбмнярх. Б рюак.~1 онйюгюмш уюпюйрепхярхйх бшонкмемхъ йюяйюдмнцн якхъмхъ он юмюкнцхх я онднамни рюакхжеи о.~5.4.2. Мерпсдмн бшбеярх "рнвмше пюяопедекемхъ" дкъ йюяйюдмнцн якхъмхъ. Дкъ ьеярх кемр хлеел $$ \matrix{ \hbox{Спнбемэ} & T1 & T2 & T3 & T4 & T5 \cr 0 & 1 & 0 & 0 & 0 & 0 \cr 1 & 1 & 1 & 1 & 1 & 1 \cr 2 & 5 & 4 & 3 & 2 & 1 \cr 3 & 15 & 14 & 12 & 9 & 6 \cr 4 & 55 & 50 & 41 & 29 & 15 \cr 5 & 190 & 175 & 146 & 105 & 55 \cr \multispan{6}\dotfill\cr n & a_n & b_n & c_n & d_n & e_n \cr n+1 & a_n+b_n+c_n+d_n+e_n & a_n+b_n+c_n+d_n & a_n+b_n+c_n & a_n+b_n & a_n \cr } \eqno(1) $$ %%344 \htable{Рюакхжю 1}% {Уюпюйреп онбедемхъ йюяйюдмнцн якхъмхъ}% {\strut\hfill # && \bskip\hfill$#$\hfill\bskip\cr Кемрш & \hbox{Опнундш} & \hbox{Опнундш} & \hbox{Нрмньемхе}\cr & \hbox{(я йнохпнбюмхел)} & \hbox{(аег йнохпнбюмхъ)} &\hbox{пнярю}\cr \noalign{\hrule} 3 & 2.078\ln S+0.672 & 1.504\ln S+0.992 & 1.6180340\cr 4 & 1.235\ln S+0.754 & 1.102\ln S+0.820 & 2.2469796\cr 5 & 0.946\ln S+0.796 & 0.897\ln S+0.800 & 2.8793852\cr 6 & 0.796\ln S+0.821 & 0.773\ln S+0.808 & 3.5133371\cr 7 & 0.703\ln S+0.839 & 0.691\ln S+0.822 & 4.1481149\cr 8 & 0.639\ln S+0.852 & 0.632\ln S+0.834 & 4.7833861\cr 9 & 0.592\ln S+0.861 & 0.587\ln S+0.845 & 5.4189757\cr 10 & 0.555\ln S+0.869 & 0.552\ln S+0.854 & 6.0547828\cr 20 & 0.397\ln S+0.905 & 0.397\ln S+0.901 & 12.4174426\cr \noalign{\hrule} } Нрлерхл хмрепеямне ябниярбн щрху вхяек---ху нрмняхрекэмше бекхвхмш ъбкъчряъ рюйфе х дкхмюлх дхюцнмюкеи опюбхкэмнцн $(2T-1)\hbox{-сцнкэмхйю}$. Мюопхлеп, оърэ дхюцнмюкеи ндхммюджюрхсцнкэмхйю мю пхя.~73 хлечр нрмняхрекэмше дкхмш, нвемэ акхгйхе й~190, 175, 146, 105 х~55! Лш днйюфел щрнр гюлевюрекэмши тюйр \picture{Пхя.~73. Ценлерпхвеяйюъ хмрепоперюжхъ йюяйюдмшу вхяек.} онгдмее б щрнл осмйре, ю рюйфе сбхдхл, врн нрмняхрекэмше бпелемю, гюрпювхбюелше мю $(T-1)\hbox{-осребне}$ якхъмхе, $(T-2)\hbox{-осребне}$ якхъмхе,~\dots, ндмносребне якхъмхе, опхакхгхрекэмн опнонпжхнмюкэмш \emph{йбюдпюрюл} дкхм щрху дхюцнмюкеи. \section *Мювюкэмне пюяопедекемхе нрпегйнб. Еякх вхякн мювюкэмшу нрпегйнб б деиярбхрекэмнярх ме еярэ вхякн Тханмюввх, лш лнфел, йюй нашвмн, бярюбхрэ тхйрхбмше нрпегйх. Онбепумнярмши юмюкхг яхрсюжхх онйюгшбюер, врн лернд опхохяшбюмхъ тхйрхбмшу нрпегйнб меясыеярбем, рюй йюй йюяйюдмне якхъмхе бяецдю нясыеярбкъер %%345 онкмше опнундш; еякх хлееряъ 190~мювюкэмшу нрпегйнб, рн йюфдюъ гюохяэ напюаюршбюеряъ оърэ пюг, йюй б опхбедеммнл бшье опхлепе, мн еякх хлееряъ 191~нрпегнй, рн, нвебхдмн, якедсер сбекхвхрэ спнбемэ, х реоепэ йюфдюъ гюохяэ асдер напюаюршбюрэяъ ьеярэ пюг. Й явюярэч, б деиярбхрекэмнярх лнфмн хгаефюрэ рюйнцн пегйнцн яйювйю. Дщбхд~Щ.~Тепцчянм мюьек яоняна рюй пюяопедекхрэ мювюкэмше нрпегйх, врн лмнцхе ноепюжхх бн бпелъ оепбни \picture{ Пхя.~74. Щттейрхбмнярэ йюяйюдмнцн якхъмхъ я пюяопедекемхел он юкцнпхрлс~D. } тюгш якхъмхъ ябндъряъ й йнохпнбюмхч яндепфхлнцн кемрш. Еякх нанирх рюйхе йнохпнбюмхъ (опнярн хглемхб "кнцхвеяйхе" мнлепю кемрнвмшу сярпниярб он нрмньемхч й "тхгхвеяйхл" мнлепюл, йюй б юкцнпхрле~5.4.2D), рн онксвхл нрмняхрекэмн окюбмши оепеунд я спнбмъ мю спнбемэ, йюй хгнапюфемн мю пхя.~74. Опедонкнфхл, врн $(a, b, c, d, e)$, цде~$a\ge b \ge c \ge d \ge e$---рнвмне пюяопедекемхе. Оепенопедекхб яннрберярбхе лефдс кнцхвеяйхлх х тхгхвеяйхлх кемрнвмшлх сярпниярбюлх, лш лнфел опедярюбхрэ, врн пеюкэмне пюяопедекемхе---щрн~$(e, d, c, b, a)$, %%346 р.~е.~$a$~нрпегйнб мю~T5, $b$~мю~Р4 х~р.~д. Якедсчыее рнвмне пюяопедекемхе---щрн $(a+b+c+d+e, a+b+c+d, a+b+c, a+b, a)$; х еякх ббнд хявепошбюеряъ опефде, вел лш днярхцюел щрнцн якедсчыецн спнбмъ, рн асдел явхрюрэ, врн кемрш яндепфюр яннрберярбеммн~$(D_1, D_2, D_3, D_4, D_5)$ тхйрхбмшу нрпегйнб, цде $$ \displaynarrow{ D_1 \le a+b+c+d,\quad D_1 \le a+b+c,\quad D_3\le a+b,\cr D_4 \le a,\quad D_5=0;\qquad D_1\ge D_2 \ge D_3 \ge D_4 \ge D_5.\cr } \eqno(2) $$ Лш бнкэмш опедярюбкърэ яеае, врн щрх тхйрхбмше нрпегйх онъбкъчряъ мю кемрюу б кчанл сднамнл леяре. Опедонкюцюеряъ, врн оепбши опнунд якхъмхъ дюяр $a$~нрпегйнб оняпедярбнл оърхосребнцн якхъмхъ, гюрел $b$~нрпегйнб оняпедярбнл вершпеуосребнцн х~р.~д. Мюью жекэ янярнхр б пюяонкнфемхх тхйрхбмшу нрпегйнб рюйхл напюгнл, врнаш гюлемхрэ якхъмхе йнохпнбюмхел. Сднамн бшонкмърэ оепбши опнунд якхъмхъ якедсчыхл напюгнл: 1.~Еякх~$D_4=a$, рн бшвеярэ~$a$ хг бяеу~$D_1$, $D_2$, $D_3$, $D_4$ х гюъбхрэ, врн~T5---пегскэрюр якхъмхъ. Еякх~$D_40$, бепмсрэяъ й ьюцс~\stp{5}. Б опнрхбмнл яксвюе слемэьхрэ~$k$ мю~1; еякх~$k>0$, сярюмнбхрэ~$m\asg |A|[T-j-1]-|A|[T-j]$ х бепмсрэяъ й~\stp{5}, еякх~$m>0$. Б опнрхбмнл яксвюе слемэьхрэ~$j$ мю~1; еякх~$j>0$, оепеирх й ьюцс~\stp{4}. Б опнрхбмнл яксвюе сбекхвхрэ~$i$ мю~1; еякх~$i|M|[j]$, х онлеярхрэ бшбндмни нрпегнй мю~$|TAPE|[p+1]$. Опнднкфюрэ пюанрс, онйю $|TAPE|[p]$ ме ярюмер осярни. Гюрел оепелнрюрэ~$|TAPE|[p]$ х~$|TAPE|[p+1]$. \st[Носярхрэяъ мю ндхм спнбемэ.] Слемэьхрэ~$l$ мю~1, сярюмнбхрэ~$|FIRST|\asg 0$, сярюмнбхрэ $(|TAPE|[1],~\ldots, |TAPE|[T])\asg (|TAPE|[T],~\ldots, |TAPE|[1])$. (Й щрнлс лнлемрс бяе~|D| х~|M|---мскх х рюйнбшлх нярюмсряъ.) Бепмсрэяъ й~\stp{8}. \algend Ьюцх~C1--C6 щрнцн юкцнпхрлю бшонкмъчр пюяопедекемхе, ьюцх~C7--C9 бшонкмъчр якхъмхе; щрх дбе вюярх янбепьеммн мегюбхяхлш ндмю нр дпсцни, х лнфмн ашкн аш упюмхрэ~$|M|[k]$ х~$|AA|[k+1]$ б ндмху х реу фе ъвеийюу оюлърх. \picture{Пхя.~75. Йюяйюдмне якхъмхе ян яоежхюкэмшл пюяопедекемхел.} \section *Юмюкхг йюяйюдмнцн якхъмхъ. Йюяйюдмне якхъмхе онддюеряъ юмюкхгс я анкэьхл рпсднл, вел лмнцнтюгмне. Мн щрнр юмюкхг нянаеммн хмрепеяем, оняйнкэйс яндепфхр лмнцн гюлевюрекэмшу тнплск. Мюярнърекэмн пейнлемдсел вхрюрекъл, хмрепеясчыхляъ дхяйпермни люрелюрхйни, яюлнярнърекэмн опнюмюкхгхпнбюрэ йюяйюдмне пюяопедекемхе, опефде вел вхрюрэ дюкэье, бедэ вхякю %%350 хлечр рюй лмнцн менашвмшу ябниярб, нрйпшбюрэ йнрнпше---ндмн сднбнкэярбхе! Лш наясдхл гдеяэ кхьэ ндхм хг лмнцху ондунднб, напюыюъ нянане бмхлюмхе мю лерндш онксвемхъ пегскэрюрнб. Дкъ сднаярбю пюяялнрпхл яксвюи ьеярх кемр. Опх щрнл асдел ярюпюрэяъ онксвхрэ тнплскш, йнрнпше нанаыючряъ мю яксвюи кчанцн~$T$. Яннрмньемхъ~(1) опхбндър й оепбни нямнбмни яхяреле: $$ \eqalignter{ a_n &= a_n &=\perm{0}{0}a_n,\cr b_n &= a_n-e_{n-1}=a_n-a_{n-2} &=\perm{1}{0}a_n-\perm{2}{2}a_{n-2},\cr c_n &= b_n-d_{n-1}=b_n-a_{n-2}-b_{n-2} &=\perm{2}{0}a_n-\perm{3}{2}a_{n-2}+\perm{4}{4}a_{n-4},\cr d_n &= c_n-c_{n-1}=c_n-a_{n-2}-b_{n-2}-c_{n-2} &=\perm{3}{0}a_n-\perm{4}{2}a_{n-2}+\perm{5}{4}a_{n-4}-\perm{6}{6}a_{n-6},\cr e_n &= d_n-b_{n-1}=d_n-a_{n-2}-b_{n-2}-c_{n-2}-d_{n-2} &=\perm{4}{0}a_n-\perm{5}{2}a_{n-2}+\perm{6}{4}a_{n-4}-\perm{7}{6}a_{n-6}+\perm{8}{8}a_{n-8}.\cr } \eqno(4) $$ Нангмювхл~$A(z)=\sum_{n\ge0} a_n z^n$,~\dots, $E(z)=\sum_{n\ge0}e_n z^n$ х нопедекхл лмнцнвкемш $$ \eqalignno{ q_m(z)&=\perm{m}{0}-\perm{m+1}{2}z^2+\perm{m+2}{4}z^4-\cdots=\cr &=\sum_{k\ge 0}\perm{m+k}{2k}(-1)^k z^{2k} = \sum_{0\le k \le m}\perm{2m-k}{k}(-1)^{m-k} z^{2m-2k}. & (5)\cr } $$ Пегскэрюр~(4) йпюрйн лнфмн хярнкйнбюрэ рюй, врн~$B(z)-q_1(z)\times A(z)$,~\dots, $E(z)-q_4(z)A(z)$ ябндъряъ й йнмевмшл ясллюл, яннрберярбсчыхл цпюмхвмшл сякнбхъл, ю хлеммн гмювемхъл~$a_{-1}$, $a_{-2}$, $a_{-3}$,~\dots, йнрнпше онъбкъчряъ б~(4) (опх меанкэьху~$n$), мн ме б~$A(z)$. Врнаш онксвхрэ ондундъыхе цпюмхвмше сякнбхъ, опхлемхл пейсппемрмне яннрмньемхе б напюрмсч ярнпнмс дкъ нрпхжюрекэмшу спнбмеи дн спнбмъ~$-8$: \ctable{ \hfill$#$\bskip&&\hfill\bskip$#$\bskip\cr \hfill n & \hfill a_n & \hfill b_n & \hfill c_n & \hfill d_n & \hfill e_n \cr 0 & 1 & 0 & 0 & 0 & 0\cr -1 & 0 & 0 & 0 & 0 & 1\cr -2 & 1 & -1 & 0 & 0 & 0\cr -3 & 0 & 0 & 0 & -1 & 2\cr -4 & 2 & -3 & 1 & 0 & 0\cr -5 & 0 & 0 & 1 & -4 & 5\cr -6 & 5 & -9 & 5 & -1 & 0\cr -7 & 0 & -1 & 6 & -14 & 14\cr -8 & 14 & -28 & 20 & -7 & 1\cr } (Дкъ яелх кемр рюакхжю ашкю аш юмюкнцхвмни, ндмюйн ярпнйх я мевермшлх~$n$ ашкх аш ядбхмсрш бопюбн мю ндхм щкелемр.) Рюимю онякеднбюрекэмнярх~$a_0$, $a_{-2}$, $a_{-4},~\ldots=1, 1, 2, 5, 14,~\ldots$ лцмнбеммн пюяйпшбюеряъ яоежхюкхярнл он хмтнплюрхйе, рюй йюй %%351 щрю онякеднбюрекэмнярэ бярпевюеряъ б ябъгх я нвемэ лмнцхлх пейсппемрмшлх юкцнпхрлюлх (мюопхлеп, б соп.~2.2.1-4 х тнплске~2.3.4.4-13)). Хрюй, лш опедонкюцюел, врн б яксвюе $T$~кемр $$ \eqalignrem{ a_{-2n}&=\perm{2n}{n}{1\over n+1} & опх $0\le n \le T-2$; \cr a_{-2n-1}&=0 & опх $0\le n \le T-3$.\cr } \eqno(6) $$ Врнаш опнбепхрэ опюбхкэмнярэ щрнцн опедонкнфемхъ, днярюрнвмн онйюгюрэ, врн~(6) х~(4) опхбндър й опюбхкэмшл пегскэрюрюл дкъ спнбмеи~0 х~1. Дкъ спнбмъ~1 щрн нвебхдмн, ю дкъ спнбмъ~0 мюл мюдн опнбепхрэ, врн $$ \perm{m}{0}a_0-\perm{m+1}{2}a_{-2}+\perm{m+2}{4}a_{-4}-\perm{m+3}{6}a_{-6}+\cdots =\sum_{k\ge0}\perm{m+k}{2k}\perm{2k}{k}{(-1)^k\over k+1} =\delta_{m0} \eqno(7) $$ дкъ~$0\le m \le T-2$. Й явюярэч, щрс ясллс лнфмн бшвхякхрэ ярюмдюпрмшлх лерндюлх (щрн "гюдювю~2", ндхм хг нямнбмшу опхлепнб б рейяре о.~4.2.6). Реоепэ лнфмн бшвхякхрэ йнщттхжхемрш~$B(z)-q_1(z)A(z)$ х~р.~д. Пюяялнрпхл, мюопхлеп, йнщттхжхемр опх~$z^{2m}$ б~$D(z)-q_3(z)A(z)$. Нм пюбем $$ \eqalign{ \sum_{k\ge0}\perm{3+m+k}{2m+2k}(-1)^{m+k}a_{-2k} &=\sum_{k\ge0}\perm{3+m+k}{2m+2k}\perm{2k}{k}{(-1)^{m+k}\over k+1}=\cr &=(-1)^m\left(\perm{2+m}{2m-1}-\perm{3+m}{2m}\right)=\cr &=(-1)^{m+1}\perm{2+m}{2m}\cr } $$ хг пегскэрюрю "гюдювх~3" б~о.~1.2.6. Рюйхл напюгнл, лш бшбекх тнплскш $$ \eqalign{ A(z) &=q_0(z)A(z);\cr B(z) &=q_1(z)A(z)-q_0(z);\cr C(z) &=q_2(z)A(z)-q_1(z);\cr D(z) &=q_3(z)A(z)-q_2(z);\cr E(z) &=q_4(z)A(z)-q_3(z).\cr } \eqno (8) $$ Йпнле рнцн, хлеел~$e_{n+1}=a_n$; якеднбюрекэмн, $zA(z)=E(z)$ х $$ A(z)=q_3(z)/(q_4(z)-z). \eqno (9) $$ Опнхгбндъыхе тсмйжхх ашкх бшпюфемш опх онлных $q\hbox{-лмнцнвкемнб}$, онщрнлс лш унрхл ксвье хгсвхрэ~$q$. Б щрнл нрмньемхх онкегмн соп.~1.2.9-15, рюй йюй нмн дюер бшпюфемхе б гюлймсрнл %%352 бхде, йнрнпне лнфер ашрэ гюохяюмн йюй $$ q_m(z)={((\sqrt{4-z^2}+iz)/2)^{2m+1}+((\sqrt{4-z^2}-iz)/2)^{2m+1} \over \sqrt{4-z^2}} \eqno(10) $$ Бяе сопныюеряъ, еякх реоепэ онкнфхрэ~$z=2 \sin\theta$: $$ \eqalignno{ q_m(2\sin\theta)=& {(\cos\theta+i\sin\theta)^{2m+1}+(\cos\theta-i\sin\theta)^{2m+1}\over 2\cos\theta}=\cr &={\cos(2m+1)\theta\over \cos\theta}. & (11)\cr } $$ (Щрн янбоюдемхе гюярюбкъер дслюрэ, врн лмнцнвкемш~$q_m(z)$ унпньн хгбеярмш б люрелюрхйе; х деиярбхрекэмн, бгцкъмсб б яннрберярбсчыхе рюакхжш, бхдхл, врн~$q_m(z)$, он ясыеярбс, лмнцнвкем Веашь╦бю брнпнцн пндю, ю хлеммн~$(-1)^m U_{2m}(z/2)$ б нашвмшу нангмювемхъу.) Реоепэ лнфмн нопедекхрэ йнпмх гмюлемюрекъ б~(9): $q_4(2\sin\theta)=2\sin\theta$ ябндхряъ й $$ \cos 9\theta = 2 \sin \theta \cos \theta = \sin 2\theta. $$ Пеьемхъ щрнцн яннрмньемхъ онксвюел, еякх рнкэйн~$\pm9\theta=2\theta+\left(2n-{1\over2}\right)\pi$; бяе рюйхе~$\theta$ дючр йнпмх гмюлемюрекъ б~(9) опх сякнбхх, врн~$\cos\theta\ne 0$. (Еякх~$\cos\theta=0$, рн~$q_m(\pm2)=\pm(2m+1)$, мхйнцдю ме пюбмн~$\pm2$.) Якеднбюрекэмн, онксвюел 8~пюгкхвмшу йнпмеи: $$ \displaylines{ q_4(z)-z=0 \qquad \hbox{ опх } z=2\sin{-5\over 14}\pi,\quad 2\sin{-1 \over 14}\pi,\quad 2\sin{3 \over 14}\pi, \cr 2\sin{-7 \over 22}\pi,\quad 2\sin{-3 \over 22}\pi,\quad 2\sin{1 \over 22}\pi, \quad 2\sin{5 \over 22}\pi,\quad 2\sin{9 \over 22}\pi.\cr } $$ Рюй йюй~$q_4(z)$---лмнцнвкем яреоемх~8, лш свкх бяе йнпмх. Оепбше рпх хг щрху гмювемхи дючр~$q_3(z)=0$, рюй врн~$q_3(z)$ х~$q_4(z)-z$ хлечр наыхл декхрекел лмнцнвкем рперэеи яреоемх. Нярюкэмше оърэ йнпмеи сопюбкъчр юяхлорнрхвеяйхл онбедемхел йнщттхжхемрнб~$A(z)$, еякх пюгкнфхрэ~(9) б щкелемрюпмше дпнах. Оепеидъ й пюяялнрпемхч наыецн яксвюъ $T$~кемр, онкнфхл~$\theta_k=(4k+1)\pi/(4T-2)$. Опнхгбндъыюъ тсмйжхъ~$A(z)$ дкъ $T\hbox{-кемрнвмшу}$ йюяйюдмшу вхяек опхмхлюер бхд $$ {4\over 2T-1}\sum_{-T/2