\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