\input style \chapnotrue\chapno=5\subchno=4\subsubchno=2 рюй йюй б ьюцюу~A3 х~A5 бшонкмъеряъ рнкэйн "онкнбхмю опнундю", р.~е.\ ящйнмнлкемн нйнкн 25\% бпелемх. Б деиярбхрекэмнярх лнфмн дюфе онкмнярэч сярпюмхрэ йнохпнбюмхе, еякх мювюрэ я $F_n$~нрпегйнб мю кемре~T1 х я $F_{n-1}$~нрпегйнб мю~T2, цде~$F_n$ х~$F_{n-1}$---онякеднбюрекэмше вхякю Тханмюввх. Пюяялнрпхл, мюопхлеп, яксвюи~$n=7$, $S=F_n+F_{n-1}=13+8=21$: {\def\cm{\hfil$-$\hfil}\def\hd#1{\multispan{3}\hfil#1\hfil}\let\f=\hfil\ctable{ #\bskip& #&#&#\bskip&\bskip#&#&#\bskip&\bskip#&#&#&#\hfil\cr &\hd{Яндепфхлне~Р1} & \hd{Яндепфхлне~Р2} & \hd{Яндепфхлне~T3} & Опхлевюмхъ \cr Тюгю~1.& 1, 1, 1, 1, &1, 1, 1, 1, &1, 1, 1, 1, 1& 1, 1, &1, 1, 1, 1, & 1, 1 & & & & Мювюкэмне пюяопедекемхе\cr Тюгю~2.& & &1, 1, 1, 1, 1& &\cm & & 2, 2, 2, & 2,2, & 2,2,2 & Якхъмхе 8~нрпегйнб мю~T3\cr Тюгю~3.& &\cm & & &3, 3, 3, 3, & 3 & & & 2,2,2 & Якхъмхе 5~нрпегйнб мю~T3\cr Тюгю~4.& &\f 5, 5, 5 & & &\f 3, & 3 & & \cm & & Якхъмхе 3~нрпегйнб мю~T1\cr Тюгю~5.& &\f 5 & & &\cm & & &\f 8,8 & & Якхъмхе 2~нрпегйнб мю~T3\cr Тюгю~6.& &\cm & & &\f 13 \f & & &\f 8 & & Якхъмхе 1~нрпегйю мю~T2\cr Тюгю~7.& &\f 21 \f & & &\cm & & &\cm & & Якхъмхе 1~нрпегйю мю~T1\cr }}% Гдеяэ "2, 2, 2, 2, 2, 2, 2, 2", мюопхлеп, нангмювюер бняелэ нрпегйнб нрмняхрекэмни дкхмш~2, еякх явхрюрэ нрмняхрекэмсч дкхмс йюфднцн мювюкэмнцн нрпегйю пюбмни~1. Бячдс б щрни рюакхже вхякю Тханмюввх! Онкмши опнунд он дюммшл нясыеярбкъчр рнкэйн тюгш~1 х~7; тюгю~2 напюаюршбюер кхьэ $16/21$~наыецн вхякю мювюкэмшу нрпегйнб, тюгю~3---кхьэ~$15/21$ х~р. д.; рюйхл напюгнл, ясллюпмне вхякн "опнунднб" пюбмн~$(21+16+15+15+16+13+21)/21=5{4\over7}$, еякх опедонкнфхрэ, врн мювюкэмше нрпегйх хлечр опхлепмн пюбмсч дкхмс. Дкъ япюбмемхъ гюлерхл, врн пюяялнрпеммюъ бшье дбсутюгмюъ опнжедспю гюрпюрхкю аш 8~опнунднб мю янпрхпнбйс щрху фе мювюкэмшу нрпегйнб. Лш сбхдхл, врн б наыел яксвюе щрю яуелю Тханмюввх рпеасер опхакхгхрекэмн $1.04\log_2 S+0.99$~опнунднб, врн декюер ее япюбмхлни я \emph{вершпеукемрнвмшл} яаюкюмяхпнбюммшл якхъмхел, унръ нмю хяонкэгсер рнкэйн рпх кемрш. Щрс хдеч лнфмн нанаыхрэ мю яксвюи $T$~кемр опх кчанл~$T\ge 3$, хяонкэгсъ $(T-1)\hbox{-осребне}$~якхъмхе. Лш сбхдхл, мюопхлеп, врн б яксвюе вершпеу кемр рпеасеряъ рнкэйн нйнкн $0.703\log_2 S+0.96$~опнунднб он дюммшл. Нанаыеммюъ яуелю хяонкэгсер нанаыеммше вхякю Тханмюввх. Пюяялнрпхл якедсчыхи опхлеп я ьеярэч кемрюлх: \ctable{ #\hfil\bskip&$#$\hfil\bskip&$#$\hfil\bskip&$#$\hfil\bskip&$#$\hfil\bskip&$#$\hfil\bskip&$#$\hfil\bskip&\hfil$#$&\hfil$\hbox{}#$\cr & & & & & & & \hbox{Вхякн напюаюршбюелшу мювюкэмшу нрпегйнб}\cr & T1 & T2 & T3 & T4 & T5 & T6 & \cr Тюгю~1.& 1^{31}& 1^{30}& 1^{28}& 1^{24}& 1^{16}& - & 31+30+28+24+16 =&129\cr Тюгю~2.& 1^{15}& 1^{14}& 1^{12}& 1^8 & - & 5^{16}& 16\times 5 =& 80\cr Тюгю~3.& 1^7 & 1^6 & 1^4 & - & 9^8 & 5^8 & 8\times 9 =& 72\cr Тюгю~4.& 1^3 & 1^2 & - & 17^4 & 9^4 & 5^4 & 4\times 17 =& 68\cr Тюгю~5.& 1^1 & - & 33^2 & 17^2 & 9^2 & 5^2 & 2\times 33 =& 66\cr Тюгю~6.& - & 65^1 & 33^1 & 17^1 & 9^1 & 5^1 & 1\times 65 =& 65\cr Тюгю~7.& 129^1 & - & - & - & - & - & 1\times 129=&129\cr } %%320 Гдеяэ $1^{31}$~нангмювюер 31~нрпегнй нрмняхрекэмни дкхмш~1 х~р.д.; бегде хяонкэгсеряъ оърхосребне якхъмхе. Щрю наыюъ яуелю ашкю пюгпюанрюмю П.~К.~Цхкярщднл [Proc.\ AFIPS Eastern Jt.\ Computer Conf., 18 (1960), 143--148], йнрнпши мюгбюк ее лмнцнтюгмшл якхъмхел. Яксвюи рпеу кемр ашк пюмее нрйпшр А.~Й.~Аержел [меносакхйнбюммюъ гюлерйю, Minneapolis-Honeywell Regulator Co.\ (1956)]. Врнаш гюярюбхрэ лмнцнтюгмне якхъмхе пюанрюрэ, йюй б опедшдсыел опхлепе, менаундхлн оняке йюфдни тюгш хлерэ "рнвмне тханмюввхебн пюяопедекемхе" нрпегйнб он кемрюл. Вхрюъ опхбедеммсч бшье рюакхжс ямхгс ббепу, лнфмн гюлерхрэ, врн оепбше яелэ рнвмшу тханмюввхебшу пюяопедекемхи опх~$T=6$ ясрэ $\set{1, 0, 0, 0, 0}$, $\set{1, 1, 1, 1, 1}$, $\set{2, 2, 2, 2, 1}$, $\set{4, 4, 4, 3, 2}$, $\set{8, 8, 7, 6, 4}$, $\set{16, 15, 14, 12, 8}$ х~$\set{31, 30, 28, 24, 16}$. Реоепэ оепед мюлх ярнър якедсчыхе бюфмше бнопняш: \enumerate \li Йюйне опюбхкн яйпшрн гю щрхлх рнвмшлх тханмюввхебшлх пюяопедекемхълх? \li Врн декюрэ, еякх~$S$ ме яннрберярбсер рнвмнлс тханмюввхебнлс пюяопедекемхч? \li Йюй онярпнхрэ мювюкэмши опнунд пюяопедекемхъ, врнаш нм онпнфдюк мсфмне пюяонкнфемхе нрпегйнб мю кемрюу? \li Яйнкэйн "опнунднб" он дюммшл онрпеасер $T\hbox{-кемрнвмне}$ лмнцнтюгмне якхъмхе (йюй тсмйжхъ нр~$S$---вхякю мювюкэмшу нрпегйнб)? \enumend Лш наясдхл щрх вершпе бнопняю он нвепедх, опх щрнл ямювюкю дюдхл "опнярше нрберш", ю гюрел гюилеляъ анкее цксанйхл юмюкхгнл. Рнвмше тханмюввхебш пюяопедекемхъ лнфмн онксвхрэ, "опнйпсвхбюъ" пюяялнрпеммсч яуелс б напюрмсч ярнпнмс, жхйкхвеяйх оепеярюбкъъ яндепфхлне кемр. Мюопхлеп, опх~$T=6$ хлеел якедсчыее пюяопедекемхе нрпегйнб: $$ \vcenter{\halign{ \hfil # \hfil &\bskip\hfil$#$\bskip&\bskip\hfil$#$\bskip&\bskip\hfil$#$\bskip&\bskip\hfil$#$\bskip&\bskip\hfil$#$\bskip&\bskip\hfil$#$\bskip&\hfil$#$\hfil\cr Спнбемэ & T1 & T2 & T3 & T4& T5 & \hbox{Ясллю} & \hbox{Кемрю я нйнмвюрекэмшл пегскэрюрнл}\cr 0 & 1 & 0& 0& 0 & 0& 1& T1\cr 1 & 1 & 1& 1& 1 & 1& 5& T6\cr 2 & 2 & 2& 2& 2 & 1& 9& T5\cr 3 & 4 & 4& 4& 3 & 2& 17& T4\cr 4 & 8 & 8& 7& 6 & 4& 33& T3\cr 5 & 16 & 15& 14& 12 & 8& 65& T2\cr 6 & 31 & 30& 28& 24 & 16& 129& T1\cr 7 & 61 & 59& 55& 47 & 31& 253& T6\cr 8 & 120 & 116& 108& 92 & 61& 497& T5\cr \multispan{8}\dotfill\cr n & a_n & b_n & c_n & d_n & e_n & t_n & T(k) \cr n+1 & a_n+b_n & a_n+c_n & a_n+d_n & a_n+e_n & a_n & t_n+4a_n & T(k-1)\cr \multispan{8}\dotfill\cr }} \eqno(1) $$ %%321 (Оняке мювюкэмнцн пюяопедекемхъ кемрю~T6 бяецдю асдер осярни.) Хг опюбхкю оепеундю нр спнбмъ~$n$ й спнбмч~$n+1$ ъямн, врн сякнбхъ $$ a_n \ge b_n \ge c_n \ge d_n \ge e_n \eqno (2) $$ бшонкмъчряъ мю кчанл спнбме. Б яюлнл деке, кецйн бхдерэ хг~(1), врн $$ \eqalign{ e_n &= a_{n-1},\cr d_n &= a_{n-1}+e_{n-1}=a_{n-1}+a_{n-2},\cr c_n &= a_{n-1}+d_{n-1}=a_{n-1}+a_{n-2}+a_{n-3},\cr b_n &= a_{n-1}+c_{n-1}=a_{n-1}+a_{n-2}+a_{n-3}+a_{n-4},\cr a_n &= a_{n-1}+b_{n-1}=a_{n-1}+a_{n-2}+a_{n-3}+a_{n-4}+a_{n-5},\cr } \eqno (3) $$ цде~$a_0=1$ х цде лш онкюцюел~$a_n=0$ опх~$n=-1$, $-2$, $-3$, $-4$. \def\Fib#1,#2.{F^{(#1)}_{#2}} \dfn{Вхякю Тханмюввх $p\hbox{-цн}$~онпъдйю~$\Fib p, n.$} нопедекъчряъ опюбхкюлх $$ \eqalign{ \Fib p, n. &=\Fib p, n-1.+\Fib p, n-2.+\cdots+\Fib p, n-p. \rem{опх $n\ge p$;}\cr \Fib p, n. &=0 \rem{опх $0\le n \le p-2$;}\cr \Fib p, p-1. &=1.\cr } \eqno (4) $$ Дпсцхлх якнбюлх, лш мювхмюел я $p-1$~мскеи, гюрел охьел~1, ю йюфдне якедсчыее вхякн ъбкъеряъ ясллни $p$~опедшдсыху вхяек. Опх~$p=2$ щрн нашвмюъ онякеднбюрекэмнярэ Тханмюввх; дкъ анкэьху гмювемхи~$p$ щрс онякеднбюрекэмнярэ боепбше хгсвхк, он-бхдхлнлс, Б.~Ькецекэ б [{\sl El Progreso Matematico,\/} {\bf 4} (1894), 173--174]. Ькецекэ бшбек опнхгбндъысч тсмйжхч $$ \sum_{n\ge 0}\Fib p, n. z^n= {z^{p-1}\over 1-z-z^2-\cdots-z^p}= {z^{p-1}-z^p \over 1-2z+z^{p+1}}. \eqno (5) $$ Тнплскю~(3) онйюгшбюер, врн вхякн нрпегйнб мю~T1 б опнжеяяе ьеярхкемрнвмнцн лмнцнтюгмнцн якхъмхъ ъбкъеряъ вхякнл Тханмюввх оърнцн онпъдйю~$a_n=\Fib 5, n+4.$. Б наыел яксвюе, еякх онкнфхрэ~$P=T-1$, пюяопедекемхъ б лмнцнтюгмнл якхъмхх дкъ $T$~кемр асдср юмюкнцхвмшл напюгнл яннрберярбнбюрэ вхякюл Тханмюввх $P\hbox{-цн}$~онпъдйю. Б рнвмнл пюяопедекемхх $n\hbox{-цн}$~спнбмъ мю $k\hbox{-и}$~кемре асдер $$ \Fib P, n+P-2. + \Fib P, n+P-3. +\cdots+ \Fib P, n+k-2. $$ %% 322 мювюкэмшу нрпегйнб дкъ~$1\le k \le P$, ю наыее йнкхвеярбн мювюкэмшу нрпегйнб мю бяеу кемрюу асдер, якеднбюрекэмн, пюбмн $$ t_n=P\Fib P, n+P-2. + (P-1)\Fib P, n+P-3. + \cdots + \Fib P, n-1. . \eqno(6) $$ Щрн пеьюер бнопня н "рнвмнл тханмюввхебнл пюяопедекемхх". Мн врн лш днкфмш декюрэ, еякх~$S$ ме пюбмн б рнвмнярх~$t_n$ мх опх йюйнл~$n$? Йюй оепбнмювюкэмн онлеярхрэ нрпегйх мю кемрш? Еякх~$S$ ме ъбкъеряъ рнвмшл вхякнл Тханмюввх (ю вхяек Тханмюввх ме рюй сф лмнцн), рн лнфмн деиярбнбюрэ, йюй б яаюкюмяхпнбюммнл $P\hbox{-осребнл}$ якхъмхх, днаюбкъъ "тхйрхбмше \picture{Пхя.~68. Янпрхпнбйю лмнцнтюгмшл якхъмхел.} нрпегйх"; онщрнлс лнфмн явхрюрэ, врн~$S$, б йнмже йнмжнб, асдер рнвмшл. Еярэ меяйнкэйн яонянанб днаюбкемхъ тхйрхбмшу нрпегйнб; лш еые ме гмюел, йюй щрн ядекюрэ "мюхксвьхл" яонянанл. Б оепбсч нвепедэ пюяялнрпхл лернд пюяопедекемхъ нрпегйнб х опхохяшбюмхъ тхйрхбмшу нрпегйнб, йнрнпши унръ х ме яюлши норхлюкэмши, мн гюрн днярюрнвмн опнярни х, он-бхдхлнлс, ксвье бяеу дпсцху лернднб рюйни фе яреоемх якнфмнярх. \alg D.(Янпрхпнбйю лмнцнтюгмшл якхъмхел я хяонкэгнбюмхел "цнпхгнмрюкэмнцн" пюяопедекемхъ.) Щрнр юкцнпхрл аепер мювюкэмше нрпегйх х пюяопедекъер ху ндхм гю дпсцхл он кемрюл, онйю гюоюя мювюкэмшу нрпегйнб ме хявепоюеряъ. Гюрел нм нопедекъер, йюй мюдн якхбюрэ кемрш, хяонкэгсъ $P\hbox{-осребне}$ якхъмхе, б опедонкнфемхх, врн хлечряъ $T=P+1\ge 3$~кемрнопнръфмшу сярпниярб. Кемрс~$T$ лнфмн хяонкэгнбюрэ дкъ упюмемхъ ббндю, рюй йюй мю мее ме гюохяшбюеряъ мх ндмнцн мювюкэмнцн нрпегйю. Б оюлърх упюмъряъ якедсчыхе рюакхжш: %%323 \descrtable{ $|A|[j]$, $1 \le j \le T$: & Рнвмне тханмюввхебне пюяопедекемхе, й йнрнпнлс лш ярпелхляъ. \cr $|D|[j]$, $1 \le j \le T$: & Вхякн тхйрхбмшу нрпегйнб, йнрнпше явхрючряъ опхясрярбсчыхлх б мювюке кемрш мю кнцхвеяйнл сярпниярбе я мнлепнл~$j$.\cr $|TAPE|[j]$, $1 \le j \le T$: & Мнлеп тхгхвеяйнцн кемрнопнръфмнцн сярпниярбю, яннрберярбсчыецн кнцхвеяйнлс сярпниярбс я мнлепнл~$j$.\cr } (Нйюгюкняэ, врн сднамн пюанрюрэ я "мнлепюлх кнцхвеяйху кемрнопнръфмшу сярпниярб", яннрберярбхе йнрнпшу тхгхвеяйхл сярпниярбюл лемъеряъ б опнжеяяе бшонкмемхъ юкцнпхрлю.) \st[Мювюкэмюъ сярюмнбйю.] Сярюмнбхрэ~$|A|[j]\asg |D|[j]\asg 1$ х~$|TAPE|[j]\asg j$ опх~$1\le j < T$. Сярюмнбхрэ~$|A|[T]\asg |D|[T]\asg 0$ х~$|TAPE|[T]\asg T$. Гюрел сярюмнбхрэ~$l\asg 1$, $j\asg 1$. \st[Ббнд мю кемрс~$j$.] Гюохяюрэ ндхм нрпегнй мю кемрс~$j$ х слемэьхрэ~$|D|[j]$ мю~1. Гюрел, еякх ббнд хявепоюм, оепелнрюрэ бяе кемрш х оепеирх й ьюцс~\stp{5}. \st[Опндбхфемхе~$j$.] Еякх~$|D|[j]<|D|[j+1]$, рн сбекхвхрэ~$j$ мю~1 х бепмсрэяъ й ьюцс~\stp{2}. Б опнрхбмнл яксвюе, еякх~$|D|[j]=0$, оепеирх й ьюцс~\stp{4}, ю еякх~$|D|[j]\ne 0$, сярюмнбхрэ~$j\asg 1$ х бепмсрэяъ й ьюцс~\stp{2}. \st[Ондмърэяъ мю ндхм спнбемэ.] Сярюмнбхрэ~$l\asg l+1$, $a\asg |A|[1]$, гюрел дкъ~$j=1$, 2,~\dots, $P$ (хлеммн б щрнл онпъдйе) сярюмнбхрэ~$|D|[j]\asg a+|A|[j+1]-|A|[j]$ х~$|A|[j]\asg a+|A|[j+1]$. (Ял.~(1). Нрлерхл, врн~$|A|[P+1]$ бяецдю~0. Б щрнл леяре асдел хлерэ~$|D|[1]>|D|[2]>\ldots>|D|[T]$.) Реоепэ сярюмнбхрэ~$j\asg 1$ х бепмсрэяъ й ьюцс~\stp{2}. \st[Якхъмхе.] Еякх~$l=0$, рн янпрхпнбйю гюбепьемю, пегскэрюр мюундхряъ мю~$|TAPE|[1]$. Б опнрхбмнл яксвюе якхбюрэ нрпегйх я кемр~$|TAPE|[1]$,~\dots, $|TAPE|[P]$ мю~$|TAPE|[T]$ дн реу онп, онйю~$|TAPE|[P]$ ме ярюмер осярни х~$|D|[P]$ ме напюрхряъ б~$0$. Опнжеяя якхъмхъ дкъ йюфднцн якхбюелнцн нрпегйю днкфем опнрейюрэ якедсчыхл напюгнл. Еякх~$|D|[j]>0$ дкъ бяеу~$j$, $1\le j \le P$, рн сбекхвхрэ~$|D|[T]$ мю~1 х слемэьхрэ йюфдне~$|D|[j]$ мю~1 дкъ~$1\le j \le P$; б опнрхбмнл яксвюе якхбюрэ он ндмнлс нрпегйс я йюфдни кемрш~$|TAPE|[j]$, рюйни, врн~$|D|[j]=0$, х слемэьхрэ~$|D|[j]$ мю~1 дкъ нярюкэмшу~$j$. (Рюйхл напюгнл, явхрюеряъ, врн тхйрхбмше нрпегйх мюундъряъ б \emph{мювюке} кемрш, ю ме б йнмже.) \st[Носярхрэяъ мю ндхм спнбемэ.] Сярюмнбхрэ~$l\asg l-1$. Оепелнрюрэ кемрш~$|TAPE|[P]$ х~$|TAPE|[T]$. (Б деиярбхрекэмнярх оепелнрйю~$|TAPE|[P]$ лнцкю ашрэ мювюрю мю ьюце~\stp{5} оняке ббндю я мее онякедмецн акнйю.) Гюрел сярюмнбхрэ~$(|TAPE|[1], %%324 |TAPE|[2],~\ldots, |TAPE|[T])\asg (|TAPE|[T], |TAPE|[1],~\ldots, |TAPE|[T-1])$, $(|D|[1], |D|[2],~\ldots, |D|[T])\asg(|D|[T], |D|[1],~\ldots, |D|[T-1])$ х бепмсрэяъ й ьюцс~\stp{5}. \algend Опюбхкн пюяопедекемхъ, йнрнпне рюй кюйнмхвмн ятнплскхпнбюмн б ьюце~D3 щрнцн юкцнпхрлю, ярпелхряъ он бнглнфмнярх спюбмърэ вхякю тхйрхбмшу нрпегйнб мю йюфдни кемре. Пхясмнй~69 хккчярпхпсер онпъднй пюяопедекемхъ, йнцдю лш оепеундхл нр спнбмъ~4 (33~нрпегйю) й спнбмч~5 (65~нрпегйнб) б янпрхпнбйе я ьеярэч кемрюлх; еякх ашкн аш, яйюфел, рнкэйн 53~мювюкэмшу \picture{ Пхя.~69. Онпъднй, б йнрнпнл нрпегйх я~34-цн он~65-и пюяопедекъчряъ мю кемрш опх оепеунде я спнбмъ~4 мю спнбемэ~5. (Ял.~рюакхжс рнвмшу пюяопедекемхи мю ярп.~320.) Гюьрпхунбюммше накюярх яннрберярбсчр оепбшл 33~нрпегйюл, йнрнпше ашкх пюяопедекемш й лнлемрс днярхфемхъ спнбмъ~4. } нрпегйю, рн бяе нрпегйх я мнлепюлх~54 х бшье пюяялюрпхбюкхяэ аш йюй тхйрхбмше. (Мю яюлнл деке нрпегйх гюохяшбючряъ б йнмеж кемрш, мн сднамее явхрюрэ, врн нмх гюохяшбючряъ б мювюкн, рюй йюй опедонкюцюеряъ, врн тхйрхбмше нрпегйх мюундъряъ б мювюке кемрш.) Лш сфе пюяялнрпекх оепбше рпх хг онярюбкеммшу бшье бнопнянб, нярюкняэ бшъямхрэ вхякн "опнунднб" он дюммшл. Япюбмхбюъ мюь ьеярхкемрнвмши опхлеп я рюакхжеи~(1), лш бхдхл, врн ясллюпмне йнкхвеярбн напюанрюммшу мювюкэмшу нрпегйнб опх~$S=t_6$ еярэ~$a_5t_1+a_4t_2+a_3t_3+a_2t_4+a_1t_5+a_0t_6$, еякх хяйкчвхрэ мювюкэмши опнунд пюяопедекемхъ. Б соп.~4 бшбндъряъ %%325 опнхгбндъыхе тсмйжхх $$ \eqalign{ a(z)&=\sum_{n\ge0}a_nz^n={1\over 1-z-z^2-z^3-z^4-z^5},\cr t(z)&=\sum_{n\ge1} t_nz^n={5z+4z^2+3z^3+2z^4+z^5\over 1-z-z^2-z^3-z^4-z^5}.\cr } \eqno(7) $$ Нрячдю якедсер, врн б наыел яксвюе вхякн напюаюршбюелшу мювюкэмшу нрпегйнб опх~$S=t_n$ пюбмн йнщттхжхемрс опх~$z^n$ б опнхгбедемхх~$a(z)\cdot t(z)$ окчя~$t_n$ (щрн дюер мювюкэмши опнунд пюяопедекемхъ). Реоепэ лш лнфел бшвхякхрэ юяхлорнрхвеяйне онбедемхе лмнцнтюгмнцн якхъмхъ, йюй онйюгюмн б соп.~5--7, х онксвюел пегскэрюрш, опхбедеммше б рюак.~1. Б рюак.~1 "нрмньемхе пнярю" еярэ опедек~$\lim_{n\to\infty} t_{n+1}t_n$, онйюгшбючыхи, бн яйнкэйн опхакхгхрекэмн пюг бнгпюярюер вхякн \htable{Рюакхжю~1}% {Юоопнйяхлюжхъ онбедемхъ янпрхпнбйх лмнцнтюгмшл якхъмхел}% {\hfill$#$\bskip&&\bskip\hfill$#$\hfill\bskip\cr \hbox{Кемрш} & \hbox{Тюгш} & \hbox{Опнундш} & \hbox{Опнундш/тюгш,} & \hbox{Нрмньемхе}\cr & & & & \hbox{б опнжемрюу пнярю}\cr \noalign{\hrule} 3 & 2.078 \ln S+0.678 & 1.504 \ln S+0.992 & 72 & 1.6180340\cr 4 & 1.641 \ln S+0.364 & 1.015 \ln S+0.965 & 62 & 1.8392868\cr 5 & 1.524 \ln S+0.078 & 0.863 \ln S+0.921 & 57 & 1.9275620\cr 6 & 1.479 \ln S-0.185 & 0.795 \ln S+0.864 & 54 & 1.9659482\cr 7 & 1.460 \ln S-0.424 & 0.762 \ln S+0.797 & 52 & 1.9835826\cr 8 & 1.451 \ln S-0.642 & 0.744 \ln S+0.723 & 51 & 1.9919642\cr 9 & 1.447 \ln S-0.838 & 0.734 \ln S+0.646 & 51 & 1.9960312\cr 10 & 1.445 \ln S-1.017 & 0.728 \ln S+0.568 & 50 & 1.9980295\cr 20 & 1.443 \ln S-2.170 & 0.721 \ln S-0.030 & 50 & 1.9999981\cr \noalign{\hrule} } нрпегйнб мю йюфднл спнбме. "Опнундш" нангмювючр япедмее йнкхвеярбн напюанрнй йюфдни гюохях, ю хлеммн~$(1/S)$, слмнфеммне мю наыее вхякн мювюкэмшу нрпегйнб, напюаюршбюелшу б ревемхе тюг пюяопедекемхъ х якхъмхъ. Сярюмнбкеммше вхякю опнунднб х тюг яопюбедкхбш б йюфднл яксвюе я рнвмнярэч дн~$O(S^{-\varepsilon})$ опх мейнрнпнл~$\varepsilon>0$ дкъ рнвмнцн пюяопедекемхъ опх~$S\to\infty$. Мю пхя.~70 хгнапюфемш б бхде тсмйжхи нр~$S$ япедмхе йнкхвеярбю якхъмхи йюфдни гюохях опх хяонкэгнбюмхх юкцнпхрлю~D б яксвюе мернвмшу вхяек. Гюлерхл, врн опх хяонкэгнбюмхх рпеу кемр йюй пюг оняке рнвмшу пюяопедекемхи онъбкъчряъ "охйх" нрмняхрекэмни мещттейрхбмнярх, мн щрн ъбкемхе б гмювхрекэмни яреоемх хявегюер опх вершпеу хкх анкэьел вхяке кемр. Хяонкэгнбюмхе %%326 бняэлх хкх анкее кемр дюер япюбмхрекэмн люкне сксвьемхе он япюбмемхч я ьеярэч хкх яелэч кемрюлх. \section *Анкее дерюкэмне пюяялнрпемхе. Б яаюкюмяхпнбюммнл якхъмхх, рпеасчыел $k$~опнунднб, йюфдюъ гюохяэ напюаюршбюеряъ б унде янпрхпнбйх пнбмн $k$~пюг. Мн лмнцнтюгмюъ опнжедспю ме ъбкъеряъ рюйни аеяопхярпюярмни: мейнрнпше гюохях лнцср напюаюршбюрэяъ \picture{Пхя.~70. Щттейрхбмнярэ лмнцнтюгмнцн якхъмхъ, хяонкэгсчыецн юкцнпхрл~D.} лмнцн анкэьее вхякн пюг, вел дпсцхе, х лш лнфел сбекхвхрэ яйнпнярэ, еякх сякнбхляъ онлеыюрэ тхйрхбмше нрпегйх б вюярн напюаюршбюелше онгхжхх. Он щрни опхвхме хгсвхл анкее ондпнамн лмнцнтюгмне пюяопедекемхе. Блеярн рнцн врнаш хмрепеянбюрэяъ рнкэйн вхякнл нрпегйнб мю йюфдни кемре, йюй б~(1), опхохьел йюфднлс нрпегйс ецн \emph{вхякн якхъмхи}---яйнкэйн пюг нм напюаюршбюеряъ б ревемхе бяецн опнжеяяю янпрхпнбйх. Блеярн~(1) онксвхл якедсчысч рюакхжс: %%327 $$ \matrix{ \hbox{Спнбемэ} & T1 & T2 & T3 & T4 & T5 \cr 0 & 0 & - & - & - & - \cr 1 & 1 & 1 & 1 & 1 & 1 \cr 2 & 21 & 21 & 21 & 21 & 2\cr 3 & 3221 & 3221 & 3221 & 322 & 32 \cr 4 & 43323221 & 43323221 & 4332322 & 433232 & 4332 \cr 5 & 5443433243323221 & 544343324332322 & 54434332433232 & 544343324332 & 54434332 \cr \multispan{6}{\dotfill}\cr n & A_n & B_n & C_n & D_n & E_n \cr n+1& (A_n+1)B_n & (A_n+1)C_n & (A_n+1)D_n & (A_n+1)E_n & A_n+1\cr \multispan{6}{\dotfill}\cr } \eqno(8) $$ Гдеяэ $A_n$~еярэ жеонвйю хг $a_n$~гмювемхи, опедярюбкъчыху вхякю якхъмхи йюфднцн нрпегйю мю~$T1$, еякх лш мювхмюел я пюяопедекемхъ $n\hbox{-цн}$~спнбмъ; $B_n$~еярэ яннрберярбсчыюъ жеонвйю дкъ~T2 х~р.~д.\ Нангмювемхе~"$(A_n+1)B_n$" вхрюеряъ: "$A_n$, бяе гмювемхъ йнрнпни сбекхвемш мю~1, ю гю меч~$B_n$". Пхясмнй~71~(ю), мю йнрнпнл "ямхгс ббепу" хгнапюфемш~$A_5$, $B_5$, $C_5$, $D_5$, $E_5$, делнмярпхпсер, йюйхл напюгнл вхякю якхъмхи дкъ йюфднцн нрпегйю онъбкъчряъ мю кемре; гюлерхл, врн нрпегнй б мювюке кчани кемрш асдер напюаюршбюрэяъ 5~пюг, б рн бпелъ йюй нрпегнй б йнмже~T1 асдер напюаюршбюрэяъ кхьэ ндмюфдш. \picture{Пхя.~71. Юмюкхг лмнцнтюгмнцн пюяопедекемхъ оърнцн спнбмъ мю ьеярх кемрюу: (a)---вхякю якхъмхи; (b)---норхлюкэмши онпъднй пюяопедекемхъ.} Щрю "дхяйпхлхмюжхъ" опх лмнцнтюгмнл якхъмхх опхбндхр й рнлс, врн тхйрхбмше нрпегйх ксвье онлеыюрэ б мювюкн кемрш, ю ме б йнмеж. Мю пхя.~71~(b) опедярюбкем норхлюкэмши онпъднй пюяопедекемхъ нрпегйнб дкъ яксвюъ оърхспнбмебнцн лмнцнтюгмнцн якхъмхъ; йюфдши мнбши нрпегнй онлеыюеряъ б онгхжхч я мюхлемэьхл хг нярюбьхуяъ вхякнл якхъмхи. Гюлерхл, врн юкцнпхрл~D %%328 (пхя.~69) меяйнкэйн усфе, рюй йюй нм гюонкмъер мейнрнпше онгхжхх~"4" дн рнцн, йюй гюонкмемш бяе онгхжхх~"3". Пейсппемрмше яннрмньемхъ~(8) онйюгшбючр, врн бяе~$B_n$, $C_n$, $D_n$, $E_n$ ъбкъчряъ мювюкэмшлх онджеонвйюлх~$A_n$. Б деиярбхрекэмнярх, хяонкэгсъ~(8), лнфмн бшбеярх тнплскш $$ \eqalign{ E_n&=(A_{n-1})+1,\cr D_n&=(A_{n-1}A_{n-2})+1,\cr C_n&=(A_{n-1}A_{n-2}A_{n-3})+1,\cr B_n&=(A_{n-1}A_{n-2}A_{n-3}A_{n-4})+1,\cr A_n&=(A_{n-1}A_{n-2}A_{n-3}A_{n-4}A_{n-5})+1,\cr } \eqno(9) $$ нанаыючыхе яннрмньемхъ~(3), йнрнпше хлечр декн рнкэйн я дкхмюлх щрху жеонвей. Йпнле рнцн, хг опюбхк, нопедекъчыху жеонвйх~$A$, якедсер, врн ярпсйрспю б мювюке йюфднцн спнбмъ, б ясымнярх, ндмю х рю фе; хлеел $$ A_n=n-Q_n, \eqno(10) $$ цде $Q_n$~еярэ жеонвйю хг $a_n$~гмювемхи, нопедекъелюъ гюйнмнл $$ \displaynarrow{ Q_n=Q_{n-1}(Q_{n-2}+1)(Q_{n-3}+2)(Q_{n-4}+3)(Q_{n-5}+4) \rem{опх $n\ge 1$},\cr Q_0=\hbox{'0'}; Q_n=\hbox{(осярн)} \rem{опх $n<0$.}\cr } \eqno(11) $$ Рюй йюй~$Q_n$ мювхмюеряъ я~$Q_{n-1}$, рн лнфмн пюяялнрперэ \emph{аеяйнмевмсч} жеонвйс~$Q_\infty$, оепбше $a_n$~щкелемрнб йнрнпни янбоюдючр я~$Q_n$; щрю жеонвйю, он ясыеярбс, нохяшбюер бяе вхякю якхъмхи б лмнцнтюгмнл пюяопедекемхх. Б яксвюе ьеярх кемр хлеел $$ Q_\infty=011212231223233412232334233434412232334233434452334344534454512232\ldots\,. \eqno (12) $$ Б соп.~11 яндепфхряъ хмрепеямюъ хмрепоперюжхъ щрни жеонвйх. Опх сякнбхх врн~$A_n$ еярэ жеонвйю~$m_1m_2\ldots m_{a_n}$, нангмювхл вепег~$A_n(x)=x^{m_1}+x^{m_2}+\cdots+x^{m_{a_n}}$ яннрберярбсчысч опнхгбндъысч тсмйжхч, нохяшбючысч, яйнкэйн пюг онъбкъеряъ йюфдне вхякн якхъмхи; юмюкнцхвмн ббедел~$B_n(x)$, $C_n(x)$, $D_n(x)$, $E_n(x)$. Мюопхлеп, $A_4(x)=x^4+x^3+x^3+x^2+x^3+x^2+x^2+x=x^4+3x^3+3x^2+x$. Б яхкс яннрмньемхи~(9) хлеел опх~$n\ge1$ $$ \eqalign{ E_n(x)&=x(A_{n-1}(x)),\cr D_n(x)&=x(A_{n-1}(x)+A_{n-2}(x)),\cr C_n(x)&=x(A_{n-1}(x)+A_{n-2}(x)+A_{n-3}(x)),\cr B_n(x)&=x(A_{n-1}(x)+A_{n-2}(x)+A_{n-3}(x)+A_{n-4}(x)),\cr A_n(x)&=x(A_{n-1}(x)+A_{n-2}(x)+A_{n-3}(x)+A_{n-4}(x)+A_{n-5}(x)),\cr } \eqno(13) $$ %%329 цде~$A_0(x)=1$ х~$A_n(x)=0$ опх~$n=-1$, $-2$, $-3$, $-4$. Якеднбюрекэмн, $$ \sum_{n\ge 0} A_n(x)z^n={1\over 1-x(z+z^2+z^3+z^4+z^5)}= \sum_{k\ge 0} x^k(z+z^2+z^3+z^4+z^5)^k. \eqno(14) $$ Пюяялюрпхбюъ нрпегйх мю бяеу кемрюу, онкнфхл $$ T_n(x)=A_n(x)+B_n(x)+C_n(x)+D_n(x)+E_n(x), \qquad n\ge 1; \eqno (15) $$ хг~(13) меледкеммн онксвюел $$ T_n(x)=5A_{n-1}(x)+4A_{n-2}(x)+3A_{n-3}(x)+2A_{n-4}(x)+A_{n-5}(x), $$ ю гмювхр, х $$ \sum_{n\ge 1} T_n(x)z^n= {x(5z+4z^2+3z^3+2z^4+z^5)\over 1-x(z+z^2+z^3+z^4+z^5)}. \eqno(16) $$ Яннрмньемхе~(16) онйюгшбюер, врн кецйн бшвхякхрэ йнщттхжхемрш~$T_n(x)$: $$ \matrix{ & z &z^2 & z^3 & z^4 & z^5 & z^6 & z^7 & z^8 & z^9 & z^{10} & z^{11} & z^{12} & z^{13} & z^{14} \cr x & 5 & 4 & 3 & 2 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \cr x^2 & 0 & 5 & 9 & 12 & 14 & 15 & 10 & 6 & 3 & 1 & 0 & 0 & 0 & 0 \cr x^3 & 0 & 0 & 5 & 14 & 26 & 40 & 55 & 60 & 57 & 48 & 35 & 20 & 10 & 4 \cr x^4 & 0 & 0 & 0 & 5 & 19 & 45 & 85 & 140 & 195 & 238 & 260 & 255 & 220 & 170\cr x^5 & 0 & 0 & 0 & 0 & 5 & 24 & 69 & 154 & 294 & 484 & 703 & 918 & 1088 & 1168 \cr } \eqno(17) $$ Ярнкажш щрни рюакхжш дючр~$T_n(x)$; мюопхлеп, $T_4(x)=2x+12x^2+14x^3+5x^4$. Йюфдши щкелемр щрни рюакхжш (йпнле щкелемрнб оепбни ярпнйх) ъбкъеряъ ясллни оърх щкелемрнб, пюяонкнфеммшу б опедшдсыеи ярпнйе меоняпедярбеммн кебее мецн. Вхякн нрпегйнб б рнвмнл пюяопедекемхх $n\hbox{-цн}$~спнбмъ пюбмн~$T_n(1)$, ю наыее йнкхвеярбн напюаюршбюелшу нрпегйнб б опнжеяяе ху якхъмхъ пюбмн опнхгбндмни~$T'_n(1)$. Дюкее, $$ \sum_{n\ge 1} T'_n(x)z^n= {5z+4z^2+3z^3+2z^4+z^5\over (1-x(z+z^2+z^3+z^4+z^5))^2}; \eqno(18) $$ онкюцюъ~$x=1$ б~(16) х~(18), онксвюел, врн вхякн якхъмхи дкъ рнвмнцн пюяопедекемхъ о-цн спнбмъ еярэ йнщттхжхемр опх~$z^n$ б~$a(z)t(z)$ [яп.~(7)]. Щрн янцкюясеряъ я мюьхлх опедшдсыхлх пюяясфдемхълх. Тсмйжхх~$T_n(x)$ лнфмн хяонкэгнбюрэ дкъ нопедекемхъ янбепьюелни пюанрш, йнцдю тхйрхбмше нрпегйх днаюбкъчряъ норхлюкэмшл напюгнл. Осярэ~$\sum_n (m)$ еярэ ясллю мюхлемэьху $m$~вхяек якхъмхи б пюяопедекемхх $n\hbox{-цн}$~спнбмъ. Онялнрпеб мю ярнкажш~(17), %%330 лш аег рпсдю бшвхякхл щрх ясллш~$\sum_n(m)$: {\let\i=\infty $$\vcenter{\halign{ $#$\bskip&&\bskip\hfill$#$\bskip\cr \span m=1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 \cr n=1 & 1 & 2 & 3 & 4 & 5 & \i & \i & \i & \i & \i & \i & \i & \i & \i & \i& \i & \i & \i & \i & \i & \i \cr n=2 & 1 & 2 & 3 & 4 & а & 8 & 10 & 12 & 14 & \i & \i & \i & \i & \i & \i & \i & \i & \i & \i & \i & \i \cr n=3 & 1 & 2 & 3 & 5 & 7 & 9 & 11 & 13 & 15 & 17 & 19 & 21 & 24 & 27 & 30 &33 & 36 & \i & \i & \i & \i \cr n=4 & 1 & 2 & 4 & 6 & 8 & 10 & 12 & 14 & 16 & 18 & 20 & 22 & 24 & 26 & 29& 32 & 35 & 38 & 41 & 44 & 47 \cr n=5 & 1 & 3 & 5 & 7 & 9 & 11 & 13 & 15 & 17 & 19 & 21 & 23 & 25 & 27 & 29& 32 & 35 & 38 & 41 & 44 & 47 \cr n=6 & 2 & 4 & 6 & 8 & 10 & 12 & 14 & 16 & 18 & 20 & 22 & 24 & 26 & 28 & 30 & 33 & 36 & 38 & 42 & 45 & 48 \cr n=7 & 2 & 4 & 6 & 8 & 10 & 12 & 14 & 16 & 18 & 20 & 23 & 26 & 29 & 32 & 35 & 38 & 41 & 44 & 47 & 50 & 53 \cr }} \eqno(19) $$}% Мюопхлеп, еякх лш унрхл нрянпрхпнбюрэ 17~нрпегйнб, хяонкэгсъ пюяопедекемхе 3-цн~спнбмъ, рн наыее йнкхвеярбн ноепюжхи еярэ~$\sum_3 (17)=36$, мн еякх хяонкэгнбюрэ пюяопедекемхе~4-цн хкх 5-цн~спнбмъ, рн наыее йнкхвеярбн ноепюжхи б опнжеяяе якхъмхъ асдер рнкэйн~$\sum_4(17)=\sum_5 (17)=35$. Бшцндмее хяонкэгнбюрэ спнбемэ~4, унръ вхякн~17 яннрберярбсер рнвмнлс пюяопедекемхч 3-цн~спнбмъ! Б яюлнл деке, он. лепе бнгпюярюмхъ~$S$ норхлюкэмши мнлеп спнбмъ нйюгшбюеряъ гмювхрекэмн анкэье, вел хяонкэгселши б юкцнпхрле~D. Сопюфмемхе~14 онйюгшбюер, врн ясыеярбсер месашбючыюъ онякеднбюрекэмнярэ вхяек~$M_n$, рюйюъ, врн спнбемэ~$n$ норхлюкем дкъ~$M_n\le S < M_{n+1}$, мн ме дкъ~$S\ge M_{n+1}$. Б яксвюе ьеярх кемр рнкэйн врн бшвхякеммюъ рюакхжю~$\sum_n (m)$ дюер $$ M_0=0,\quad M_1=2,\quad M_2=6,\quad M_3=10,\quad M_4=14. $$ Бшье лш хлекх декн рнкэйн ян яксвюел ьеярх кемр, ндмюйн ъямн, врн ре фе хдех опхлемхлш й лмнцнтюгмни янпрхпнбйе я~$T$~кемрюлх дкъ кчанцн~$T\ge3$; опнярн б яннрберярбсчыху леярюу мюдн гюлемхрэ~5 мю~$P=T-1$. Б рюак.~2 хгнапюфемш онякеднбюрекэмнярх~$M_n$, онксвеммше дкъ пюгкхвмшу гмювемхи~$T$. Рюакхжю~3 х пхя.~72 дючр опедярюбкемхе на наыел йнкхвеярбе напюаюршбюелшу мювюкэмшу нрпегйнб оняке бшонкмемхъ норхлюкэмнцн пюяопедекемхъ тхйрхбмшу нрпегйнб. (Тнплскш бмхгс рюак.~3 якедсер опхмхлюрэ я нярнпнфмнярэч, рюй йюй щрн опхакхфемхе он лерндс мюхлемэьху йбюдпюрнб мю накюярх~$1\le S \le 5000$ ($1\le S \le 10\, 000$ опх~$T=3$), врн опхбндхр й мейнрнпнлс нрйкнмемхч, оняйнкэйс дюммюъ накюярэ гмювемхи~$S$ ме ъбкъеряъ ндхмюйнбн ондундъыеи дкъ бяеу~$T$. Опх~$S\to\infty$ вхякн напюаюршбюелшу мювюкэмшу нрпегйнб оняке норхлюкэмнцн лмнцнтюгмнцн пюяопедекемхъ юяхлорнрхвеяйх пюбмн~$S\log_p S$, мн яундхлнярэ й щрнлс юяхлорнрхвеяйнлс опедекс йпюиме ледкеммюъ.) Опх онлных рюак.~4 лнфмн япюбмхрэ лернд пюяопедекемхъ юкцнпхрлю~D я пегскэрюрюлх норхлюкэмнцн пюяопедекемхъ, опхбедеммшлх б рюак.~3. Ъямн, врн юкцнпхрл~D ме нвемэ акхгнй й норхлюкэмнлс опх анкэьху~$S$ х~$T$; ндмюйн меонмърмн, лнфмн кх онярсохрэ б щрху яксвюъу ясыеярбеммн ксвье юкцнпхрлю~D, ме опхаецюъ й гмювхрекэмшл сякнфмемхъл, нянаеммн еякх лш ме %%331 гмюел~$S$ гюпюмее. Й явюярэч, гюанрхрэяъ н анкэьху~$S$ опхундхряъ днбнкэмн педйн (ял.~о.~5.4.6), рюй врн юкцнпхрл~D мю опюйрхйе ме рюй сф окну, мю яюлнл деке---дюфе беяэлю меокну. Люрелюрхвеяйх лмнцнтюгмюъ янпрхпнбйю боепбше ашкю опнюмюкхгхпнбюмю С.~Й.~Йюпрепнл [Пцня.\ IFIP Congress (1962), 62--66]. \picture{Пхя.~72. Щттейрхбмнярэ лмнцнтюгмнцн якхъмхъ я норхлюкэмшл мювюкэмшл пюяопедекемхел (яп.~я~пхя.~70).} Лмнцхе хг опхбедеммшу пегскэрюрнб нрмняхрекэмн норхлюкэмнцн пюглеыемхъ тхйрхбмшу нрпегйнб опхмюдкефюр А.~Ящйлюмс х~Р.~Яхмцкепс [A vector model for merge sort analisis, меносакхйнбюммши днйкюд, опедярюбкеммши мю яхлонгхсл~ACM он янпрхпнбйе (мнъапэ 1962), ярп.~21]. Онгдмее Ящйлюм опедкнфхк цнпхгнмрюкэмши лернд пюяопедекемхъ, хяонкэгселши б юкцнпхрле~D; Днмюкэд Ьекк [{\sl CACM,\/} {\bf 14} (1971), 713--719; {\bf 15} (1972), 28], мегюбхяхлн пюгбхб щрс ренпхч, сйюгюк мю яннрмньемхе~(10) х ондпнамн хгсвхк меяйнкэйн пюгкхвмшу юкцнпхрлнб пюяопедекемхъ. Дюкэмеиьхе онкегмше сянбепьемярбнбюмхъ х сопныемхъ ашкх онксвемш Депейнл~Щ.~Гщибнл [{\sl JACM,\/} асдер носакхйнбюмн]. %%332 \htable{Рюакхжю 2}% {Вхякн нрпегйнб, опх йнрнпнл дюммши спнбемэ норхлюкем} { \hfill$#$\bskip&\hfill\bskip$#$\bskip&\hfill\bskip$#$\bskip&\hfill\bskip$#$\bskip&\hfill\bskip$#$\bskip&\hfill\bskip$#$\bskip&\hfill\bskip$#$\bskip&\hfill\bskip$#$\bskip&\hfill\bskip$#$\bskip&\bskip$#$\hfill\cr \hbox{Спнбемэ}& T=3 & T=4 & T=5 & T=6 & T=7 & T=8 & T=9 & T=10\cr \noalign{\hrule} 1 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & M_1 \cr 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & M_2 \cr 3 & 4 & 6 & 8 & 10 & 12 & 14 & 16 & 18 & M_3 \cr 4 & 6 & 10 & 14 & 14 & 17 & 20 & 23 & 26 & M_4 \cr 5 & 9 & 18 & 23 & 29 & 20 & 24 & 28 & 32 & M_5 \cr 6 & 14 & 32 & 35 & 43 & 53 & 27 & 32 & 37 & M_6 \cr 7 & 22 & 55 & 76 & 61 & 73 & 88 & 35 & 41 & M_7 \cr 8 & 35 & 96 &109 &194 & 98 &115 &136 & 44 & M_8 \cr 9 & 56 &173 &244 &216 &283 &148 &171 &199 & M_9 \cr 10 & 90 &280 &359 &269 &386 &168 &213 &243 & M_{10}\cr 11 &145 &535 &456 &779 &481 &640 &240 &295 & M_{11}\cr 12 &234 &820 &1197&1034&555 &792 &1002&330 & M_{12}\cr 13 &378 &1635&1563&1249&1996&922 &1228&1499& M_{13}\cr 14 &611 &2401&4034&3910&2486&1017&1432&1818& M_{14}\cr 15 &988 &4959&5379&4970&2901&4397&1598&2116& M_{15}\cr 16 &1598&7029&6456&5841&10578&5251&1713&2374&M_{16}\cr 17 &2574&14953&18561&19409&13097&5979&8683&2576&M_{17}\cr 18 &3955&20583&22876&23918&15336&6499&10069&2709&M_{18}\cr 19 &6528&44899&64189&27557&17029&30164&11259&15787& M_{19}\cr \noalign{\hrule} } {\def\m#1#2{\matrix{\hfill #1\cr\hfill #2\cr}} \htable{Рюакхжю~3}% {Вхякн мювюкэмшу нрпегйнб, напюаюршбюелшу опх норхлюкэмнл \nl лмнцнтюгмнл якхъмхх}% {\hfill$#$\bskip&&\hfill\bskip$#$\bskip\cr S& T=3 & T=4 & T=5 & T=6 & T=7 & T=8 & T=9 & T=10\cr \noalign{\hrule} 10& 36& 24& 19& 17& 15& 14& 13& 12\cr 20& 90& 60& 49& 44& 38& 36& 34& 33\cr 50& 294& 194& 158& 135& 128& 121& 113& 104\cr 100& 702& 454& 362& 325& 285& 271& 263& 254\cr 1000& 10371& 6680& 5430& 4672& 4347& 3872& 3739& 3632\cr 5000& 63578& 41286& 32905& 28620& 26426& 23880& 23114& 22073\cr \multispan{2} \hfil$ \displaystyle S\left\{\matrix{ \hfill (1.51\cr \hfill +(-.11\cr }\right. $ & \m{0.951}{+.14} & \m{0.761}{+.16} & \m{0.656}{+.19} & \m{0.589}{+.21} & \m{0.548}{+.20} & \m{0.539}{+.02} & \multispan{2} \hfill\bskip$\displaystyle\vcenter{\halign{\hfil$#$&$\hbox{}#$\hfil\cr 0.488)&\cdot S \ln S \cr +.18)&\cdot S \cr }}$ \cr \noalign{\hrule} }} Опнхгбндъыюъ тсмйжхъ~(16) ашкю боепбше хяякеднбюмю С.~Аспфел [Пцня. IFIP Congress (1971), I, 454--459]. \qsection Ю йюй наярнхр декн я бпелемел оепелнрйх? Дн яху онп лш хяонкэгнбюкх "напюаюршбюелше мювюкэмше нрпегйх" йюй едхмярбеммсч лепс щттейрхбмнярх дкъ япюбмемхъ ярпюрецхи кемрнвмнцн якхъмхъ. Мн оняке йюфдни хг тюг~2--6 б опхлепюу б мювюке щрнцн осмйрю ЩБЛ днкфмю нфхдюрэ оепелнрйх дбсу кемр; йюй опедшдсыюъ бшбндмюъ кемрю, рюй х мнбюъ рейсыюъ бшбндмюъ %%333 \htable{Рюакхжю~4}% {Вхякн мювюкэмшу нрпегйнб, напюаюршбюелшу опх ярюмдюпрмнл \nl лмнцнтюгмнл якхъмхх}% {\hfill$#$\bskip&&\hfill\bskip$#$\bskip\cr S& T=3 & T=4 & T=5 & T=6 & T=7 & T=8 & T=9 & T=10\cr \noalign{\hrule} 10& 36& 24& 19& 17& 15& 14& 13& 12\cr 20& 90& 62& 49& 44& 41& 37& 34& 33\cr 50& 294& 194& 167& 143& 134& 131& 120& 114\cr 100& 714& 459& 393& 339& 319& 312& 292& 277\cr 1000& 10730& 6920& 5774& 5370& 4913& 4716& 4597& 4552\cr 5000& 64740& 43210& 36497& 32781& 31442& 29533& 28817& 28080\cr \noalign{\hrule} } кемрю днкфмш ашрэ оепелнрюмш б мювюкн, опефде вел ялнфер бшонкмърэяъ якедсчыюъ тюгю. Щрн лнфер бшгбюрэ ясыеярбеммсч гюдепфйс, рюй йюй б наыел яксвюе опедшдсыюъ бшбндмюъ кемрю яндепфхр гмювхрекэмши опнжемр янпрхпселшу гюохяеи (ял. ярнкаеж "опнундш/тюгш" б рюак.~1). Дняюдмн, йнцдю ЩБЛ опнярюхбюер бн бпелъ ноепюжхи оепелнрйх, рнцдю йюй лнфмн ашкн аш, хяонкэгсъ хмсч яуелс якхъмхъ, бшонкмхрэ онкегмсч пюанрс я нярюкэмшлх кемрюлх. Щрс гюдювс пеьюер опнярюъ лндхтхйюжхъ лмнцнтюгмни опнжедспш, унръ нмю рпеасер ме лемее оърх кемр [ял.~дхяяепрюжхч Х.~Яегюпх (Univ.~of~Paris (1968), 25--27), цде щрю хдеъ опхохяшбюеряъ Дф.~Йщипнмс]. Йюфдюъ тюгю яуелш Йщипнмю якхбюер нрпегйх я $(T-3)$~кемр мю мейнрнпсч дпсцсч кемрс, б рн бпелъ йюй нярючыхеяъ дбе кемрш оепелюршбючряъ. Пюяялнрпхл, мюопхлеп, яксвюи ьеярх кемр х 49~мювюкэмшу нрпегйнб. Б якедсчыеи рюакхже асйбни~$R$ онлевемш кемрш, оепелюршбючыхеяъ бн бпелъ дюммни тюгш; опедонкюцюеряъ, врн $T5$~яндепфхр оепбнмювюкэмше нрпегйх: \ctable{ \hfill$#$\bskip&&\bskip\hfill$#$\hfill\bskip\cr \omit\hfill Тюгю\hfill & T1 & T2 & T3 & T4 & T5 & T6 & \omit\hfill Бпелъ гюохях \hfill & \omit\hfill Бпелъ оепелнрйх \hfill \cr 1&1^{11}&1^{17}&1^{13}& 1^8& - & (R) & 49 & 17\cr 2& (R)& 1^9& 1^5& -& R & 3^8 & 8\times 3=24& 49-17=32\cr 3& 1^6& 1^4& - & R& 3^5 & R & 5\times 3=15& \max(8,24)\cr 4& 1^2& -& R & 5^4& R & 3^4 & 4\times 5=20& \max(13,15)\cr 5& - & R& 7^2& R& 3^3 & 3^2 & 2\times 7=14& \max(17,20)\cr 6& R & 11^2& R& 5^2& 3^1 & - & 2\times 11=22& \max(11,14)\cr 7& 15^1& R& 7^1& 5^1& - & R & 1\times 15=15& \max(22,24)\cr 8& R & 11^1& 7^0& -& R & 23^1 & 1\times 23=23& \max(15,16)\cr 9& 15^1 & 11^1& -& R& 33^0& R & 0\times 33= 0& \max(20,23)\cr 10&(15^0)& -& R&49^1& (R) & (23^0)& 1\times 49=49& 14\cr } Гдеяэ бяе оепелнрйх, он ясыеярбс, янблеыемш; гю хяйкчвемхел тюгш~9 ("тхйрхбмюъ тюгю", йнрнпюъ ондцнрюбкхбюер нйнмвюрекэмне якхъмхе) х оепелнрйх оняке мювюкэмни тюгш пюяопедекемхъ (йнцдю оепелюршбючряъ бяе кемрш). Еякх $t$~еярэ бпелъ, менаундхлне %%334 дкъ якхъмхъ рюйнцн йнкхвеярбю гюохяеи, йюйне яндепфхряъ б ндмнл мювюкэмнл нрпегйе, ю $r$---бпелъ оепелнрйх мю ндхм мювюкэмши нрпегнй, рн щрнр опнжеяя рпюрхр нйнкн~$182t+40r$ окчя бпелъ мювюкэмнцн пюяопедекемхъ х гюбепьючыеи оепелнрйх. Яннрберярбсчыхе бшпюфемхъ дкъ ярюмдюпрмнцн лмнцнтюгмнцн лерндю, хяонкэгсчыецн юкцнпхрл~D, еярэ~$140t+104r$, врн меяйнкэйн усфе, еякх~$r={3\over 4}t$, х меяйнкэйн ксвье, еякх~$r={1\over2}t$. Бяе яйюгюммне н ярюмдюпрмнл лмнцнтюгмнл лернде опхкнфхлн й лмнцнтюгмнлс лерндс Йщипнмю; мюопхлеп, онякеднбюрекэмнярэ~$a_n$ реоепэ сднбкербнпъер пейсппемрмнлс яннрмньемхч $$ a_n=a_{n-2}+a_{n-3}+a_{n-4} \eqno (20) $$ блеярн~(3). Вхрюрекч асдер онкегмн опнюмюкхгхпнбюрэ щрнр лернд рюйхл фе напюгнл, йюй лш юмюкхгхпнбюкх ярюмдюпрмши лмнцнтюгмши, рюй йюй щрн сксвьхр онмхлюмхе нанху лернднб (ял., мюопхлеп, соп.~19 х~20). Б рюак.~5 ябедемш тюйрш н лмнцнтюгмнл лернде Йщипнмю, юмюкнцхвмше тюйрюл на нашвмнл лмнцнтюгмнл лернде, опхбедеммшл б рюак.~1. Гюлерхл, врн. мю яюлнл деке опх бняэлх х анкее. кемрюу лернд Йщипнмю ярюмнбхряъ \emph{ксвье} лмнцнтюгмнцн йюй он вхякс напюаюршбюелшу нрпегйнб, рюй х он бпелемх оепелнрйх, меялнрпъ мю рн врн нм бшонкмъер $(T-3)\hbox{-осребне}$ якхъмхе блеярн $(T-1)\hbox{-осребнцн}$! Щрн лнфер йюгюрэяъ, оюпюднйяюкэмшл, онйю лш ме онилел, врн \emph{бшянйхи онпъднй якхъмхъ ме наъгюрекэмн нгмювюер щттейрхбмсч янпрхпнбйс.} Б йювеярбе йпюимецн пюяялнрпхл яксвюи, йнцдю мю кемрс~T1 онлеыюеряъ 1~нрпегнй х $n$~нрпегйнб---мю~T2, T3, \htable{Рюакхжю 5}% {Опхакхгхрекэмне онбедемхе лмнцнтюгмнцн якхъмхъ Йщипнмю}% { \hfill$#$\bskip&&\bskip\hfill$#$\hfill\bskip\cr \hbox{Кемрш} & \hbox{Тюгш} & \hbox{Опнундш} & \hbox{Опнундш/тюгш,} & \hbox{Нрмньемхе}\cr & & & \hbox{б опнжемрюу} & \hbox{пнярю} \cr \noalign{\hrule} 5& 3.566 \ln S +0.158 & 1.463 \ln S + 1.016 & 41 & 1.3247180\cr 6& 2.616 \ln S -0.166 & 0.951 \ln S + 1.014 & 36 & 1.4655712\cr 7& 2.337 \ln S -0.472 & 0.781 \ln S + 1.001 & 33 & 1.5341577\cr 8& 2.216 \ln S -0.762 & 0.699 \ln S + 0.980 & 32 & 1.5701473\cr 9& 2.156 \ln S -1.034 & 0.654 \ln S + 0.954 & 30 & 1.5900054\cr 10& 2.124 \ln S -1.290 & 0.626 \ln S + 0.922 & 29 & 1.6013473\cr 20& 2.078 \ln S -3.093 & 0.575 \ln S + 0.524 & 28 & 1.6179086\cr \noalign{\hrule} } T4, T5; еякх лш асдел оннвепедмн бшонкмърэ якхъмхъ мю~T6 х~T1, онйю T2, T3, T4, T5 ме ярюмср осяршлх, рн бпелъ напюанрйх асдер пюбмн $(2n^2+3n)$~дкхмюл мювюкэмшу нрпегйнб, р.~е., он ясыеярбс, опнонпжхнмюкэмн~$S^2$, ю ме~$S\log S$, унръ бяе бпелъ опнхгбндхряъ оърхосребне якхъмхе. %%335 \section Пюяыеокемхе кемр. Щттейрхбмне янблеыемхе бпелемх оепелнрйх ъбкъеряъ опнакелни, бнгмхйючыеи бн лмнцху опхкнфемхъу, ю ме рнкэйн б янпрхпнбйе; ясыеярбсер наыхи ондунд, йнрнпши вюярн лнфер ашрэ хяонкэгнбюм. Пюяялнрпхл хрепюрхбмши опнжеяя, йнрнпши хяонкэгсер кемрш якедсчыхл напюгнл: \ctable{ #\bskip\hfill&&\bskip#\bskip\hfill\cr &\omit\hfill T1 \hfill&\omit\hfill T2 \hfill\cr Тюгю~1& Бшбнд~1 & \omit\hfill $-$ \hfill \cr & Оепелнрйю & \omit\hfill $-$ \hfill \cr Тюгю~2& Ббнд~1 & Бшбнд~2\cr & Оепелнрйю & Оепелнрйю\cr Тюгю~3& Бшбнд~3 & Ббнд~2\cr & Оепелнрйю & Оепелнрйю\cr Тюгю~4& Ббнд~3 & Бшбнд~4\cr & Оепелнрйю & Оепелнрйю\cr } х р. д., цде "бшбнд~$k$" нгмювюер гюохяэ б $k$-и бшбндмни тюик, ю "ббнд~$k$" нгмювюер ецн времхе. Лнфмн сярпюмхрэ бпелъ оепелнрйх, еякх хяонкэгнбюрэ рпх кемрш, йюй ашкн опедкнфемн Й.~Беияепрнл [{\sl CACM,\/} {\bf 5} (1962), 102]: \ctable{ #\bskip\hfill&&\bskip#\bskip\hfill\cr &\omit\hfill T1 \hfill&\omit\hfill T2 \hfill& \omit\hfill T3 \hfill\cr Тюгю~1 & Бшбнд~1.1 & \omit\hfill $-$ \hfill & \omit\hfill $-$ \hfill\cr & Бшбнд~1.2 & \omit\hfill $-$ \hfill & \omit\hfill $-$ \hfill\cr & Оепелнрйю & Бшбнд~1.3 & \omit\hfill $-$ \hfill\cr Тюгю~2 & Ббнд~1.1 & Бшбнд~2.1 & \omit\hfill $-$ \hfill\cr & Ббнд~1.2 & Оепелнрйю & Бшбнд~2.2\cr & Оепелнрйю & Ббнд~1.3 & Бшбнд~2.3\cr Тюгю~3 & Бшбнд~3.1 & Ббнд~2.1 & Оепелнрйю\cr & Бшбнд~3.2 & Оепелнрйю & Ббнд~2.2\cr & Оепелнрйю & Бшбнд~3.3 & Ббнд~2.3\cr Тюгю~4 & Ббнд~3.1 & Бшбнд~4.1 & Оепелнрйю\cr & Ббнд~3.2 & Оепелнрйю & Бшбнд~4.2\cr & Оепелнрйю & Ббнд~3.3 & Бшбнд~4.3\cr } х~р.~д. Гдеяэ "бшбнд~$k.j$" нгмювюер гюохяэ $j\hbox{-и}$~рперх $k\hbox{-цн}$~бшбндмнцн тюикю, ю "ббнд~$k.j$" нгмювюер ее времхе. Б йнмже йнмжнб асдер хяйкчвемн бяе бпелъ оепелнрйх, еякх оепелнрйю он йпюимеи лепе бдбне ашярпее времхъ/гюохях. Онднамюъ опнжедспю, б йнрнпни бшбнд б йюфдни тюге пюгдекъеряъ лефдс кемрюлх, мюгшбюеряъ "пюяыеокемхел кемр". К.~Люй-Юккеяреп [{\sl CACM\/}, {\bf 7} (1964), 158--159] онйюгюк, врн пюяыеокемхе кемр опхбндхр й щттейрхбмнлс лерндс янблеыемхъ бпелемх оепелнрйх б лмнцнтюгмнл якхъмхх. Ецн лернд лнфмн хяонкэгнбюрэ я вершпэлъ хкх анкэьхл йнкхвеярбнл кемр, х нм нясыеярбкъер $(T-2)\hbox{-осребне}$~якхъмхе. %%336 Опедонкнфхл ямнбю, врн с мюя еярэ ьеярэ кемр х оношрюеляъ онярпнхрэ яуелс якхъмхъ, йнрнпюъ пюанрюер якедсчыхл напюгнл, пюяыеокъъ бшбнд мю йюфднл спнбме (асйбш~I, Н х~R нангмювючр яннрберярбеммн ббнд, бшбнд х оепелнрйс): $$ \vcenter{\halign{ \hfil$#$\hfil&\bskip\hfill # \hfill\bskip&\bskip\hfill # \hfill\bskip&\bskip\hfill # \hfill\bskip&\bskip\hfill # \hfill\bskip&\bskip\hfill # \hfill\bskip&\bskip\hfill # \hfill\bskip&\bskip\hfill$#$\hfill\bskip\cr & & & & & & & \hbox{Вхякн бшбндхлшу}\cr Спнбемэ & T1 & T2 & T3 & T4 & T5 & T6 & \hbox{нрпегйнб}\cr 7 & I & I & I & I & R & O & u_7 \cr & I & I & I & I & O & R & v_7 \cr 6 & I & I & I & R & O & I & u_6 \cr & I & I & I & O & R & I & v_6 \cr 5 & I & I & R & O & I & I & u_5 \cr & I & I & O & R & I & I & v_5 \cr 4 & I & R & O & I & I & I & u_4 \cr & I & O & R & I & I & I & v_4 \cr 3 & R & O & I & I & I & I & u_3 \cr & O & R & I & I & I & I & v_3 \cr 2 & O & I & I & I & I & R & u_2 \cr & R & I & I & I & I & O & v_2 \cr 1 & I & I & I & I & R & O & u_1 \cr & I & I & I & I & O & R & v_1 \cr 0 & I & I & I & R & O & I & u_0 \cr & I & I & I & O & R & I & \cr }} \eqno (21) $$ Врнаш гюйнмвхрэ пюанрс я ндмхл нрпегйнл мю Р4 х осяршлх нярюкэмшлх кемрюлх, лш днкфмш хлерэ $$ \eqalign{ v_0 &= 1,\cr u_0+v_1&= 0,\cr u_1+v_2 &= u_0+v_0,\cr u_2+v_3 &= u_1+v_1+u_0+v_0,\cr u_3+v_4 &= u_2+v_2+u_1+v_1+u_0+v_0,\cr u_4+v_5 &= u_3+v_3+u_2+v_2+u_1+v_1+u_0+v_0,\cr u_5+v_6 &= u_4+v_4u_3+v_3+u_2+v_2+u_1+v_1,\cr } $$ х~р.~д.; б наыел яксвюе рпеасеряъ, врнаш $$ u _n+v_{n+1}=u_{n-1}+v_{n-1}+u_{n-2}+v_{n-2}+u_{n-3}+v_{n-3}+u_{n-4}+v_{n-4} \eqno (22) $$ опх бяеу~$n\ge 0$, еякх явхрюрэ~$u_j=v_j=0$ опх бяеу~$j<0$. С щрху спюбмемхи мер едхмярбеммнцн пеьемхъ; б яюлнл деке, еякх онкнфхрэ бяе~$u$ пюбмшлх мскч, рн онксвхл нашвмне лмнцнтюгмне, якхъмхе, опхвел ндмю кемрю асдер кхьмеи! Мн еякх %%337 бшапюрэ~$u_n\approx v_{n+1}$, рн бпелъ оепелнрйх асдер сднбкербнпхрекэмн янблеыемн. Люй-Юккеяреп опедкнфхк бгърэ~$u_n=v_{n-1}+v_{n-2}+v_{n-3}+v_{n-4}$, $v_{n+1}=u_{n-1}+u_{n-2}+u_{n-3}+u_{n-4}$, рюй врн онякеднбюрекэмнярэ $$ \ = \ $$ сднбкербнпъер ндмнпндмнлс пейсппемрмнлс яннрмньемхч $$ x_n=x_{n-3}+x_{n-5}+x_{n-7}+x_{n-9}. $$ Нйюгюкняэ, ндмюйн, врн ксвье онкнфхрэ $$ \eqalign{ v_{n+1} &= u_{n-1}+v_{n-1}+u_{n-2}+v_{n-2},\cr u_n &= u_{n-3}+v_{n-3}+u_{n-4}+v_{n-4}.\cr } $$ Щрю онякеднбюрекэмнярэ ме рнкэйн мелмнцн ксвье он бпелемх якхъмхъ, ее анкэьне опехлсыеярбн б рнл, врн яннрберярбсчыее бпелъ якхъмхъ лнфмн опнюмюкхгхпнбюрэ люрелюрхвеяйх. [Бюпхюмр Люй-Юккеярепю дкъ юмюкхгю йпюиме рпсдем, онрнлс врн б ндмни тюге лнцср бярпевюрэяъ нрпегйх пюгмни дкхмш; лш сбхдхл, врн рюйнцн ме лнфер яксвхрэяъ опх~(23).] Лнфмн бшбеярх вхякн нрпегйнб мю йюфдни кемре мю йюфднл спнбме, дбхцюъяэ мюгюд он яуеле~(21); лш онксвюел якедсчысч яуелс янпрхпнбйх: {\def\m#1{\displaystyle\matrix{#1}}\ctable{ \hfil#\hfil&\bskip\hfil$#$\hfil\bskip&\bskip\hfil$#$\hfil\bskip&\bskip\hfil$#$\hfil\bskip&\bskip\hfil$#$\hfil\bskip&\bskip\hfil$#$\hfil\bskip&\bskip\hfil$#$\hfil\bskip&\bskip$#$\hfil\bskip&\bskip\hfil$#$\hfil\bskip\cr Спнбемэ & T1 & T2 & T3 & T4 & T5 & T6 & \hbox{Бпелъ гюохях} & \hbox{Бпелъ оепелнрйх}\cr & 1^{23} & 1^{21} & 1^{17} & 1^{10} & - & 1^{11} & 82 & 23\cr 7 & 1^{19} & 1^{17} & 1^{13} & 1^6 & R & 1^{11}4^4 & 4\times 4=16 & 82-23\cr & 1^{13} & 1^{11} & 1^7 & - & 4^6& R & 6\times 4=24 & 25 \cr 6 & 1^{10} & 1^8 & 1^4 & R & 4^9& 1^84^4 & 3\times 4=12 & 10 \cr & 1^6 & 1^4 & - & 4^4 & R & 1^44^4 & 4\times 4=16 & 36 \cr 5 & 1^5 & 1^3 & R & 4^47^1 & 4^8& 1^34^4 & 1\times 7=7 & 17 \cr & 1^2 & - & 7^3 & R & 4^5& 4^4 & 3\times 7=21 & 23 \cr 4 & 1^1 & R &7^3 13^1& 4^37^1 & 4^4& 4^3 & 1\times 13=13 & 21 \cr & - & 13^1 & R & 4^27^1 & 4^3& 4^2 & 1\times 13=13 & 34 \cr 3 & R & 13^1 19^1& 7^2 13^1 & 4^1 7^1 & 4^2 & 4^1 & 1\times 19=19 & 23 \cr & 19^1 & R & 7^1 13^1 & 7^1 & 4^1& - & 1\times 19=19 & 32 \cr 2 & 19^1 31^0& 13^1 19^1 & 7^1 13^1 & 7^1 & 4^1 & R & 0\times 31=0 & 25 \cr & R & 19^1 & 13^1 & 7^0 & - & 31^1 & 1\times 31=31 & 19 \cr $\m{ 1\cr \cr 0\cr}$ & \m{ 19^1 31^0 \cr 19^1 31^0 \cr 19^1 31^0 \cr}& \m{ 19^1 \cr 19^1 \cr 19^1 \cr } & \m{13^1 \cr 13^1 \cr 13^1 \cr } & \m{ 7^0 \cr - \cr R \cr } & \m{ R \cr 52^0 \cr 52^0 82^0 \cr } & \m{ 31^1 52^0 \cr R \cr 31^1 52^0 \cr } & \left.\m{ 0\times 52 = 0 \cr 0\times 52 = 0 \cr 0\times 82 = 0 \cr } \right\} \max(36, 31, 23)\span\cr & (31^0) & (19^0) & - & 82^1 & (R) & (52^0) & 1\times 82 = 82 & 0\cr }} Меянблеыеммюъ оепелнрйю бярпевюеряъ рнкэйн опх оепелнрйе ббндмни кемрш~T5 (82~едхмхжш), б ревемхе оепбни онкнбхмш тюгш брнпнцн спнбмъ (25~едхмхж) х б ревемхе нйнмвюрекэмшу тюг "тхйрхбмнцн якхъмхъ" мю спнбмъу~1 х~0 (36 едхмхж). Рюйхл %% 338 напюгнл, бпелъ пюанрш лнфмн нжемхрэ бекхвхмни~$273t+143r$; дкъ юкцнпхрлю~D яннрберярбсчыюъ бекхвхмю~$268t+208r$ онврх бяецдю усфе. Мерпсдмн бхдерэ (ял.~соп.~23), врн дкхмш нрпегйнб, бшбндхлшу бн бпелъ йюфдни тюгш, ясрэ онякеднбюрекэмн $$ 4, 4, 7, 13, 19, 31, 52, 82, 133, \ldots \eqno(24) $$ опх щрнл онякеднбюрекэмнярэ~$\< t_1, t_2, t_3,~\ldots>$ сднбкербнпъер гюйнмс $$ t_n=t_{n-2}+2t_{n-3}+t_{n-4}, \eqno(25) $$ еякх явхрюрэ~$t_n=1$ опх~$n \le 0$. Лнфмн рюйфе опнюмюкхгхпнбюрэ норхлюкэмне пюглеыемхе тхйрхбмшу нрпегйнб, пюяялнрпеб ярпнйх вхяек якхъмхи, йюй лш декюкх дкъ ярюмдюпрмнцн лмнцнтюгмнцн лерндю [яп.~я~(8)]: $$ \vcenter{\halign{ \hfill$#$\hfill&&\bskip\hfill$#$\hfill\bskip\cr & & & & & & \hbox{Нйнмвюрекэмши} \cr \hbox{Спнбемэ} & T1 & T2 & T3 & T4 & T6 & \hbox{бшбнд мю кемре}\cr 1 & 1 & 1 & 1 & 1 & - & T5 \cr 2 & 1 & 1 & 1 & - & 1 & T4 \cr 3 & 21 & 21 & 2 & 2 & 1 & T3 \cr 4 & 2221 & 222 & 222 & 22 & 2 & T2 \cr 5 & 23222 & 23222 & 2322 & 23 & 222 & T1 \cr 6 & 333323222 & 33332322 & 333323 & 3333 & 2322 & T6 \cr \multispan{7}\dotfill\cr n & A_n & B_n & C_n & D_n & E_n & T(k) \cr n+1 & (A''_n E_n+1)B_n & (A''_nE_n+1)C_n & (A''_n E_n+1)D_n & A''_nE_n+1 & A'_n & T(k-1)\cr \multispan{7}\dotfill\cr }} \eqno(26) $$ цде~$A_n=A'nA''_n$ х~$A''_n$ янярнхр хг онякедмху $u_n$~вхяек якхъмхи~$A_n$. Опхбедеммне бшье опюбхкн оепеундю я спнбмъ~$n$ мю спнбемэ~$n+1$ яопюбедкхбн дкъ \emph{кчани} яуелш, сднбкербнпъчыеи~(22). Еякх лш нопедекъел~$u$ х~$v$ оняпедярбнл~(23), рн ярпнйх~$A_n$,~\dots, $E_n$ лнфмн бшпюгхрэ б якедсчыел, днбнкэмн опнярнл бхде [яп.~я~(9)]: $$ \eqalign{ A_n &= (W_{n-1}W_{n-2}W_{n-3}W_{n-4})+1,\cr B_n &= (W_{n-1}W_{n-2}W_{n-3})+1,\cr C_n &= (W_{n-1}W_{n-2})+1,\cr D_n &= (W_{n-1})+1,\cr E_n &= (W_{n-2}W_{n-3})+1,\cr } \eqno(27) $$ цде $$ \eqalign{ W_n &= (W_{n-3}W_{n-4}W_{n-2}W_{n-3})+1 \rem{опх $n>0$;}\cr W_0 &=\hbox{'0'}\hbox{ х } W_n = \hbox{(осярн)} \rem{ опх $n<0$.}\cr } \eqno(28) $$ %%339 Хяундъ хг щрху яннрмньемхи, кецйн ондпнамн опнюмюкхгхпнбюрэ яксвюи ьеярх кемр. Б наыел яксвюе, еякх хлееряъ $T\ge 5$~кемр, рн онкнфхл~$P=T-2$ х нопедекхл онякеднбюрекэмнярх~$\$, $\$ он опюбхкюл $$ \eqalign{ v_{n+1}&= u_{n-1}+v_{n-1}+\cdots+u_{n-r}+v_{n-r};\cr u_n &= u_{n-r-1}+v_{n-r-1}+\cdots+u_{n-P}+v_{n-P} \rem{опх $n\ge 0$,}\cr } \eqno(29) $$ цде~$r=\floor{P/2}$, $v_0=1$ х~$u_n=v_n=0$ опх~$n<0$. Еякх~$w_n=u_n+v_n$, рн хлеел $$ \eqalign{ w_n &= w_{n-2}+\cdots+w_{n-r}+2w_{n-r-1}+w_{n-r-2}+\cdots+w_{n-P}, \rem{$n>0$,}\cr w_0&=1 \hbox{ х } w_n=0 \rem{опх $n<0$.}\cr } \eqno(30) $$ Опх мювюкэмнл пюяопедекемхх дкъ спнбмъ~$n+1$ мю кемрс~$k$ онлеыюеряъ $w_n+w_{n-1}+\cdots+w_{n-P+k}$~нрпегйнб опх~$1\le k \le P$ х~$w_{n-1}+\cdots+w_{n-r}$--- мю кемрс~$T$; кемрю~$T-1$ хяонкэгсеряъ дкъ ббндю. Гюрел $u_n$~нрпегйнб якхбючряъ мю кемрс~$T$, б рн бпелъ йюй кемрю~$T-1$ оепелюршбюеряъ; $v_n$~нрпегйнб якхбючряъ мю~$T-1$, онйю~$T$ оепелюршбюеряъ; $u_{n-1}$~нрпегйнб---мю~$T-1$, онйю $T-2$~оепелюршбюеряъ, х~р.~д. \htable{Рюакхжю~6} {Опхакхгхрекэмне онбедемхе лмнцнтюгмнцн якхъмхъ я пюяыеокемхел кемр}% {\hfill$#$\hfill&&\hfill\bskip$#$\bskip\hfill\cr \hbox{Кемрш} & \hbox{тюгш} & \hbox{Опнундш} & \hbox{Опнундш/тюгш} & \hbox{Нрмньемхе}\cr & & & \hbox{б опнжемрюу} & \hbox{пнярю}\cr \noalign{\hrule} 4 & 2.885\ln S+0.000 & 1.443\ln S+1.000 & 50 & 1.4142136\cr 5 & 2.078\ln S+0.232 & 0.929\ln S+1.022 & 45 & 1.6180340\cr 6 & 2.078\ln S-0.170 & 0.752\ln S+1.024 & 34 & 1.6180340\cr 7 & 1.958\ln S-0.408 & 0.670\ln S+1.007 & 34 & 1.6663019\cr 8 & 2.008\ln S-0.762 & 0.624\ln S+0.994 & 31 & 1.6454116\cr 9 & 1.972\ln S-0.987 & 0.595\ln S+0.967 & 30 & 1.6604077\cr 10 & 2.013\ln S-1.300 & 0.580\ln S+0.94l & 29 & 1.6433803\cr 20 & 2.069\ln S-3.164 & 0.566\ln S+0.536 & 27 & 1.6214947\cr \noalign{\hrule} } Рюакхжю~6 онйюгшбюер опхакхгхрекэмне онбедемхе щрни опнжедспш, йнцдю~$S$ ме якхьйнл люкн. Ярнкаеж "опнундш/тюгш" опхлепмн сйюгшбюер, йюйюъ вюярэ бяецн тюикю оепелюршбюеряъ бн бпелъ йюфдни онкнбхмш тюгш х йюйюъ вюярэ тюикю гюохяшбюеряъ гю бпелъ йюфдни онкмни тюгш. \emph{Лернд пюяыеокемхъ кемр опебняундхр ярюмдюпрмши лмнцнтюгмши мю ьеярх хкх анкее кемрюу} х, бепнърмн; рюйфе мю оърх кемрюу, он йпюимеи лепе дкъ анкэьху~$S$. Еякх~$T=4$, рн сйюгюммюъ опнжедспю ярюкю аш, он ясыеярбс, щйбхбюкемрмни яаюкюмяхпнбюммнлс дбсуосребнлс якхъмхч \emph{аег} янблеыемхъ бпелемх оепелнрйх, рюй йюй~$w_{2n+1}$ ашкн аш пюбмн~$0$ %$390 опх бяеу~$n$. Онщрнлс щкелемрш рюак.~6 опх~$T=4$ ашкх онксвемш оняпедярбнл меанкэьни лндхтхйюжхх, янярнъыеи б рнл, врн онкюцюкняэ $$ \displaylines{ v_2=0, u_1=1, v_1=0, u_0=0, v_0=1\hbox{ х } v_{n+1}=u_{n-1}+v_{n-1},\cr u_n=u_{n-2}+v_{n-2}\rem{опх $n \ge 2$.}\cr } $$ Щрн опхбндхр й нвемэ хмрепеямни яуеле янпрхпнбйх (ял.~соп.~25 х~26). \excercises \ex[16] Мю пхя.~69 сйюгюм онпъднй, б йнрнпнл юкцнпхрл~D пюяопедекъер он оърх кемрюл нрпегйх я~34-цн он~65-и; б йюйнл онпъдйе пюяопедекъчряъ нрпегйх я~1-цн он~33-и? \rex[21] Бепмн кх, врн оняке дбсу тюг якхъмхъ б юкцнпхрле~D, р.~е.~йнцдю лш бн брнпни пюг днярхцмел ьюцю~D6, бяе тхйрхбмше нрпегйх хявегючр? \rex[22] Днйюфхре, врн он нйнмвюмхх ьюцю~D4 бяецдю бшонкмемн сякнбхе $|D|[1]\ge |D|[2] \ge \ldots \ge |D|[T]$. На╝ъямхре, бюфмнярэ щрнцн сякнбхъ дкъ опюбхкэмни пюанрш леуюмхглю ьюцнб~D2 х~D3. \ex[Л20] Бшбедхре опнхгбндъыхе тсмйжхх~(7). \ex[БЛ26] (Щ.~О.~Люикя~лк., 1960.) Днйюфхре, врн опх бяеу~$p\ge 2$ лмнцнвкем~$f_p(z)=z^p-z^{p-1}-\cdots-z-1$ хлеер $p$~пюгкхвмшу йнпмеи, хг йнрнпшу пнбмн ндхм опебняундхр~1 он юаянкчрмни бекхвхме. [\emph{Сйюгюмхе:} пюяялнрпхре лмнцнвкем~$z^{p+1}-2z^p+1$.] \ex[БЛ24] Жекэ щрнцн сопюфмемхъ---пюяялнрперэ яоняна янярюбкемхъ рюак.~1, 5 х~6. Опедонкнфхл, врн хлееряъ яуелю якхъмхъ, ябниярбю йнрнпни якедсчыхл напюгнл уюпюйрепхгсчряъ лмнцнвкемюлх~$p(z)$ х~$q(z)$: (1)~Вхякн мювюкэмшу нрпегйнб б "рнвмнл пюяопедекемхх", рпеасчыел $n$~тюг якхъмхъ, пюбмн йнщттхжхемрс опх~$z^n$ б~$p(z)/q(z)$. (2)~Вхякн мювюкэмшу нрпегйнб, напюаюршбюелшу б ревемхе щрху $n$~тюг якхъмхъ, пюбмн йнщттхжхемрс опх~$z^n$ б~$p(z)/q(z)^2$. (3)~С лмнцнвкемю~$q(z^{-1})$ еярэ "цкюбмши йнпемэ"~$\alpha$, рюйни, врн~$q(\alpha^{-1})=0$, $q'(\alpha^{-1}) \ne 0$, $p(\alpha^{-1})\ne 0$, х хг~$q(\beta^{-1})=0$ якедсер, врн~$\beta=\alpha$ хкх~$\abs{\beta}<\abs{\alpha}$. Днйюфхре, врн ясыеярбсер~$\varepsilon > 0$, рюйне, врн еякх $S$~пюбмн вхякс нрпегйнб б рнвмнл пюяопедекемхх, рпеасчыел $n$~тюг якхъмхъ, ю бн бпелъ щрху тюг напюаюршбюеряъ $\rho S$~нрпегйнб, рн~$n=a\ln S+b+O(S^\varepsilon)$, $\rho=c\ln S+d+O(S^{-\varepsilon})$, цде $$ \displaylines{ a=(\ln \alpha)^{-1},\quad b= -a\ln\left({p(\alpha^{-1})\over -q'(\alpha^{-1})}\right)-1, \quad c=a{\alpha\over -q'(\alpha^{-1})},\cr d={(b+1)\alpha-p'(\alpha^{-1})/p(\alpha^{-1})+q''(\alpha^{-1})/q'\alpha^{-1} \over -q'(\alpha^{-1})}.\cr } $$ \ex[БЛ22] Осярэ~$\alpha_p$---цкюбмши йнпемэ лмнцнвкемю~$f_p(z)$ хг соп.~5. Йюйнбн юяхлорнрхвеяйне онбедемхе~$\alpha_p$ опх~$p\to\infty$? \ex[Л20] (Щ.~Меррн, 1901.) Осярэ~$N^{(p)}_m$ еярэ вхякн яонянанб бшпюгхрэ~$m$ б бхде сонпъднвеммни ясллш жекшу вхяек~$\set{1, 2,~\ldots, p}$. Мюопхлеп, еякх~$p=3$ х~$m=5$, рн хлееряъ 13~яонянанб: $1+1+1+1+1=1+1+1+2=1+1+2+1=1+1+3=1+2+1+1 =1+2+2= 1+3+1=2+1+1+1=2+1+2=2+2+1=2+3=3+1+1=3+2$. Онйюфхре, врн $N^{(p)}_m$~ъбкъчряъ нанаыеммшлх вхякюлх Тханмюввх. \ex[Л20] Осярэ~$K^{(p)}_m$---вхякн онякеднбюрекэмняреи хг мскеи х едхмхж, рюйху, врн б мху мер $p$~онякеднбюрекэмшу едхмхж. Мюопхлеп, еякх~$p=3$ х~$m=5$, хлееряъ 24~бюпхюмрю: $00000$, $00001$, $00010$, $00011$, $00100$, $00101$, $00110$, $01000$, $01001$,~\dots, $11011$. Онйюфхре, врн $K^{(p)}_m$~ъбкъчряъ нанаыеммшлх вхякюлх Тханмюввх. %%341 \ex[Л27]\exhead(Яхярелю явхякемхъ я нанаыеммшлх вхякюлх Тханмюввх.) Днйюфхре, врн йюфдне менрпхжюрекэмне жекне~$n$ хлеер едхмярбеммне опедярюбкемхе б бхде ясллш пюгкхвмшу вхяек Тханмюввх $p\hbox{-цн}$~онпъдйю~$F^{(p)}_j$ опх~$j\ge p$, сднбкербнпъчыее сякнбхч, врн ме хяонкэгсчряъ мхйюйхе $p$~онякеднбюрекэмше вхякю Тханмюввх. \ex[Л24] Днйюфхре, врн $n\hbox{-и}$~щкелемр жеонвйх~$Q_\infty$ б~(12) пюбем йнкхвеярбс пюгкхвмшу вхяек Тханмюввх б опедярюбкемхх щкелемрю $n-1$~вхякюлх Тханмюввх оърнцн онпъдйю (ял.~соп.~10). \rex[M20] Мюидхре гюбхяхлнярэ лефдс яреоемълх люрпхжш $$ \pmatrix{ 0 & 1 & 0 & 0 & 0 \cr 0 & 0 & 1 & 0 & 0 \cr 0 & 0 & 0 & 1 & 0 \cr 0 & 0 & 0 & 0 & 1 \cr 1 & 1 & 1 & 1 & 1 \cr } $$ х рнвмшл тханмюввхебшл пюяопедекемхел б~(1). \rex[22] Днйюфхре якедсчыее хмрепеямне ябниярбн рнвмшу тханмюввхебшу пюяопедекемхи: еякх нйнмвюрекэмши бшбнд нйюгшбюеряъ мю кемре мнлеп~$T$, рн вхякн нрпегйнб мю бяеу дпсцху кемрюу \emph{мевермне,} еякх нйнмвюрекэмши бшбнд нйюгшбюеряъ мю мейнрнпни кемре, нркхвмни нр~$T$, рн вхякн нрпегйнб асдер \emph{мевермшл} мю щрни кемре х \emph{вермшл} мю нярюкэмшу [ял.~(1)]. \ex[Л35] Осярэ~$T_n(x)=\sum_{k\ge0} T_{nk}x^k$, цде $T_n(x)$---лмнцнвкемш, нопедекеммше б~(16). (a)~Онйюфхре, врн дкъ йюфднцн~$k$ ясыеярбсер вхякн~$n(k)$, рюйне, врн~$T_{1k}\le T_{2k} \le \ldots \le T_{n(k)k} > T_{n(k)+1,k}\ge\ldots\,$.. (b)~Опх сякнбхх врн~$T_{n'k'}$, рюйюъ, врн~$\sum_n(S) =\min_{j\ge 1} \sum_j (S)$ опх~$M_n\le S < M_{n+1}$, мн~$\sum_n(S)>\min_{j\ge 1}\sum_j(S)$ опх~$S\ge M_{n+1}$. [Ял.~(19).] \ex[Л43] Бепмн кх, врн~$\sum_{n-1}(m) < \sum_n (m)$ бкевер~$\sum_n(m)\le\sum_{n+1}(m)\le \sum_{n+2}(m) \le \ldots?$ (Рюйни пегскэрюр яхкэмн сопнярхк аш бшвхякемхе рюак.~2.) \ex[M43] Нопедекхре юяхлорнрхвеяйне онбедемхе лмнцнтюгмнцн якхъмхъ я норхлюкэмшл пюяопедекемхел тхйрхбмшу нрпегйнб. \ex[32] Бепмн кх, врн нрпегйх дкъ норхлюкэмнцн лмнцнтюгмнцн пюяопедекемхъ лнфмн пюглеярхрэ рюйхл напюгнл, врн пюяопедекемхе $S+1$~мювюкэмшу нрпегйнб онксвюеряъ осрел днаюбкемхъ ндмнцн нрпегйю (мю яннрберярбсчысч кемрс) й пюяопедекемхч $S$~мювюкэмшу нрпегйнб? \ex[30] Бепмн кх, врн норхлюкэмне лмнцнтюгмне пюяопедекемхе дюер мюхксвьсч бнглнфмсч яуелс якхъмхъ б рнл ялшяке, врн ясллюпмне йнкхвеярбн напюаюршбюелшу мювюкэмшу нрпегйнб лхмхлюкэмн, еякх рпеасеряъ, врнаш мювюкэмше нрпегйх пюглеыюкхяэ ме анкее, вел мю $T-1$~кемрюу? (Бпелемел оепелнрйх опемеапевэ.) \ex[21] Янярюбэре рюакхжс, юмюкнцхвмсч~(1), дкъ лмнцнтюгмнцн лерндю янпрхпнбйх Йщипнмю дкъ ьеярх кемр. \ex[Л24] Йюйюъ опнхгбндъыюъ тсмйжхъ дкъ йщипнмнбяйни лмнцнтюгмни янпрхпнбйх мю ьеярх кемрюу яннрберярбсер~(7) х~(16)? Йюйхе яннрмньемхъ, юмюкнцхвмше~(9) х~(27), нопедекъчр ярпнйх вхяек якхъмхи? \ex[11] Врн днкфмн онъбхрэяъ мю спнбме~7 б~(26)? \ex[M21] Йюфдши вкем онякеднбюрекэмнярх~(24) опхакхгхрекэмн пюбем яслле дбсу опедшдсыху. Мюакчдюеряъ кх щрн ъбкемхе дкъ нярюкэмшу вкемнб онякеднбюрекэмнярх? Ятнплскхпсире х днйюфхре ренпелс н~$t_n-t_{n-1}-t_{n-2}$. \rex[29] Йюйхе хглемемхъ мюдн ашкн аш ядекюрэ б~(25), (27) х (28), еякх аш (23)~гюлемхкняэ мю~$v_{n+1}=u_{n-1}+v_{n-1}+u_{n-2}$, $u_n=v_{n-2}+u_{n-3}+v_{n-3}+u_{n-4}+v_{n-4}$? %%342 \ex[БЛ41] Бшвхякхре юяхлорнрхвеяйне онбедемхе лмнцнтюгмни опнжедспш я пюяыеокемхел кемр, еякх щкелемр~$v_{n+1}$ нопедекем йюй ясллю оепбшу$q$ вкемнб~$u_{n-1}+v_{n-1}+\cdots+u_{n-P}+v_{n-P}$ опх пюгкхвмшу~$P=T-2$ х~$0\le q \le 2P$. (Б рейяре пюяялюрпхбюеряъ рнкэйн яксвюи~$q=2\floor{P/2}$; яп.~я~соп.~23.) \ex[19] Опнделнмярпхпсире, йюй лмнцнтюгмне якхъмхе я пюяыеокемхел кемр, сонлъмсрне б йнмже щрнцн осмйрю, янпрхпнбюкн аш 32~мювюкэмшу нрпегйю. (Дюире юмюкхг тюгю гю тюгни, йюй щрн ядекюмн б рейяре б опхлепе я 82~нрпегйюлх х 6~кемрюлх.) \ex[Л21] Опнюмюкхгхпсире онбедемхе лмнцнтюгмнцн якхъмхъ я пюяыеокемхел кемр мю вершпеу кемрюу опх~$S=2^n$ х опх~$S=2^n+2^{n-1}$ (ял.~соп.~25). \ex[23] Еякх мювюкэмше нрпегйх пюяопедекемш мю кемрюу б яннрберярбхх я рнвмшл пюяопедекемхел, рн лмнцнтюгмюъ ярпюрецхъ опебпюыюеряъ опнярн б "якхбюрэ дн носярньемхъ". Лш якхбюел нрпегйх ян бяеу меосяршу бундмшу кемр, онйю ндмю хг мху ме ярюмер осярни, гюрел лш хяонкэгсел щрс кемрс йюй якедсчысч бшбндмсч, ю опедшдсысч бшбндмсч кемрс хяонкэгсел йюй ббндмсч. Бепмн кх, врн щрю ярпюрецхъ "якхбюрэ дн носярньемхъ" бяецдю бшонкмъер янпрхпнбйс мегюбхяхлн нр рнцн, йюй пюяопедекемш мювюкэмше нрпегйх, опх сякнбхх врн лш пюяопедекъел ху он йпюимеи лепе мю дбе кемрш (ндмю кемрю, йнмевмн, асдер нярюбкемю осярни, врнаш нмю лнцкю яксфхрэ оепбни бшбндмни кемрни). \edef\exref{\the\excerno} \ex[Л26] Опедшдсыее сопюфмемхе нопедекъер беяэлю анкэьне яелеиярбю яуел якхъмхъ. Онйюфхре, врн лмнцнтюгмюъ яуелю \emph{мюхксвьюъ} хг мху б якедсчыел ялшяке: еякх хлееряъ ьеярэ кемр х лш пюяялюрпхбюел йкюяя бяеу мювюкэмшу пюяопедекемхи~$(a, b, c, d, e)$, рюйху, врн ярпюрецхъ "якхбюрэ дн носярньемхъ" рпеасер~$n$ хкх лемэье тюг дкъ янпрхпнбйх, рн~$a+b+c+d+e\le t_n$, цде~$t_n$---яннрберярбсчыее вхякн дкъ лмнцнтюгмни янпрхпнбйх~(1). \ex[Л47] Соп.~\exref{} онйюгшбюер, врн лмнцнтюгмне пюяопедекемхе норхлюкэмн япедх бяеу яуел "якхбюрэ дн носярньемхъ" б ялшяке лхмхлюкэмнярх вхякю тюг. Мн ъбкъеряъ кх нмн норхлюкэмшл рюйфе б ялшяке лхмхлюкэмнярх вхякю опнунднб? Осярэ вхякю~$a$ х~$b$ бгюхлмн опнярше, х опедонкнфхл, врн $a+b$~еярэ вхякн Тханмюввх~$F_n$. Бепмн кх якедсчыее опедонкнфемхе, бшяйюгюммне П.~Л.~Йюпонл: вхякн мювюкэмшу нрпегйнб, напюаюршбюелшу яуелни "якхбюрэ дн носярньемхъ", мювхмючыеияъ я пюяопедекемхъ~$(a, b)$, анкэье хкх пюбмн~$((n-5)F_{n+1}+(2n+2)F_n)/5$? (Сйюгюммне гмювемхе днярхцюеряъ, йнцдю~$a=F_{n+1}$, $b=F_{n-2}$.) \ex[42] Янярюбэре рюакхжс, юмюкнцхвмсч рюак.~2, дкъ лмнцнтюгмнцн якхъмхъ я пюяыеокемхел кемр. \subsubchap{Йюяйюдмне якхъмхе}%5.4.3 Дпсцюъ нямнбмюъ яуелю, мюгшбюелюъ "йюяйюдмшл якхъмхел", мю яюлнл деке ашкю нрйпшрю пюмэье лмнцнтюгмни [А.~Й.~Аерж х~С.~Й.~Йюпреп, ACM Nat'1 Conference, {\bf 14} (1959), Paper~14]. Мхфе б рюакхже щрнр ондунд хккчярпхпсеряъ дкъ 6~кемр х~190~мювюкэмшу нрпегйнб я хяонкэгнбюмхел нангмювемхи хг о.~5.4.2: \ctable{ #\hfil\bskip&\bskip\hfil$#$\bskip\hfil&\bskip\hfil$#$\bskip\hfil &\bskip\hfil$#$\bskip\hfil&\bskip\hfil$#$\bskip\hfil &\bskip\hfil$#$\bskip\hfil&\bskip\hfil$#$\bskip\hfil&#\hfil\cr & T1 & T2 & T3 & T4 & T5 & T6 & Йнкхвеярбн напюанрюммшу мювюкэмшу нрпегйнб\cr Опнунд~1. & 1^{55} & 1^{50} & 1^{41} & 1^{29} & 1^{15} & - & 190 \cr Опнунд~2. & - & {1^5}_* & 2^9 & 3^{12} & 4^{14} & 5^{15}& 190 \cr Опнунд~3. & 15^5 & 14^4 & 12^3 & 9^2 & {5^1}_*& - & 190 \cr Опнунд~4. & - & {15^1}_*& 29^1 & 41^1 & 50^1 & 55^1 & 190 \cr Опнунд~5. & 190^1 & - & - & - & - & - & 190 \cr } %%343 \bye