\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