\input style \chapno=6\subchno=3\chapnotrue %%601 \subchap{ๅฅ่จเฎข ญจฅ} % 6.4 คŽ ‘ˆ• Ž Œ› €‘‘Œ€’ˆ‚€‹ˆ Œ…’Ž„› Žˆ‘Š€, Ž‘Ž‚€›… € ‘€‚…ˆˆ „€ŽƒŽ €ƒ“Œ…’€~$K$ ‘ ˆŒ…ž™ˆŒˆ‘Ÿ ‚ ’€‹ˆ–… Š‹ž—€Œˆ ˆ‹ˆ € ˆ‘Ž‹œ‡Ž‚€ˆˆ …ƒŽ –ˆ” „‹Ÿ “€‚‹…ˆŸ Ž–…‘‘ŽŒ €‡‚…’‚‹…ˆŸ. ญŽ …‘’œ ˆ ’…’ˆ‰ “’œ: … ›‘Š€’œ ‚ŽŠ“ƒ „€ ŽŠŽ‹Ž, € Žˆ‡‚…‘’ˆ €„~$K$ …ŠŽ’ŽŽ… €ˆ”Œ…’ˆ—…‘ŠŽ… ‚›—ˆ‘‹…ˆ… ˆ Ž‹“—ˆ’œ ”“Š–ˆž~$f(K)$, “Š€‡›‚€ž™“ž €„…‘ ‚ ’€‹ˆ–…, ƒ„… •€ˆ’‘Ÿ~$K$ ˆ €‘‘Ž–ˆˆŽ‚€€Ÿ ‘ ˆŒ ˆ”ŽŒ€–ˆŸ. ญ€ˆŒ…, €‘‘ŒŽ’ˆŒ ‚Ž‚œ ŒŽ†…‘’‚Ž ˆ‡ 31~€ƒ‹ˆ‰‘ŠŽƒŽ ‘‹Ž‚€, ŠŽ’ŽŽ… Œ› Ž„‚…ƒ€‹ˆ ‚Ž‡„…‰‘’‚ˆž €‡‹ˆ—›• ‘’€’…ƒˆˆ Žˆ‘Š€ ‚ .~6.2.2 ˆ \S~6.3. โ€‹ˆ–€~1 ‘Ž„…†ˆ’ ŠŽŽ’Š“ž Žƒ€ŒŒ“ „‹Ÿ \MIX, …Ž€‡“ž™“ž Š€†„›‰ ˆ‡ 31~Š‹ž—€ ‚ “ˆŠ€‹œŽ… —ˆ‘‹Ž~$f(K)$ Œ…†„“~$-10$ ˆ~$30$. ฅ‘‹ˆ Œ› ‘€‚ˆŒ ’Ž’ Œ…’Ž„ ‘ \MIX-Žƒ€ŒŒ€Œˆ „‹Ÿ “†… ˆ‡“—…›• €Œˆ Œ…’Ž„Ž‚ (€ˆŒ…, ‘ ˆ€›Œ Žˆ‘ŠŽŒ, Ž’ˆŒ€‹œ›Œ Žˆ‘ŠŽŒ Ž „……‚“, ŽŽ‚Ž‰ €ŒŸ’œž, –ˆ”Ž‚›Œ Žˆ‘ŠŽŒ Ž „……‚“), ’Ž “‚ˆ„ˆŒ, —’Ž Ž ‹“—˜… Š€Š ‘ ’Ž—Šˆ ‡…ˆŸ Ž‘’€‘’‚€, ’€Š ˆ ‘ ’Ž—Šˆ ‡…ˆŸ ‘ŠŽŽ‘’ˆ; ’Ž‹œŠŽ ˆ€›‰ Žˆ‘Š ˆ‘Ž‹œ‡“…’ …‘ŠŽ‹œŠŽ Œ…œ˜… Ž‘’€‘’‚€. ข ‘€ŒŽŒ „…‹…, ˆ ˆ‘Ž‹œ‡Ž‚€ˆˆ Žƒ€ŒŒ› ˆ‡ ’€‹.~1 ‘…„…… ‚…ŒŸ Žˆ‘Š€ ‘Ž‘’€‚‹Ÿ…’ ‹ˆ˜œ ŽŠŽ‹Ž~$17.8u$ („€›… Ž —€‘’Ž’… ‚‡Ÿ’› ˆ‡ ˆ‘.~12), ˆ „‹Ÿ •€…ˆŸ 31~Š‹ž—€ ’…“…’‘Ÿ ’€‹ˆ–€ ‚‘…ƒŽ „‹Ÿ 41~‹…Œ…’€. ช ‘Ž†€‹…ˆž, €•Ž„ˆ’œ Ž„Ž›… ”“Š–ˆˆ~$f(K)$ „Ž‚Ž‹œŽ ‘‹Ž†Ž. แ“™…‘’‚“…’ $41^{31}\approx10^{50}$~€‡‹ˆ—›• Ž’Ž€†…ˆ‰ ŒŽ†…‘’‚€ ˆ‡ 31~‹…Œ…’€ ‚ ŒŽ†…‘’‚Ž ˆ‡ 41~‹…Œ…’€, ˆ ’Ž‹œŠŽ $41\cdot40\cdot\ldots\cdot11=41!/10!\approx10^{43}$ ˆ‡ ˆ• „€ž’ €‡‹ˆ—›… ‡€—…ˆŸ „‹Ÿ Š€†„ŽƒŽ €ƒ“Œ…’€; ’€ŠˆŒ Ž€‡ŽŒ, ‹ˆ˜œ Ž„€ ˆ‡ Š€†„›• 10~Œˆ‹‹ˆŽŽ‚ ”“Š–ˆ‰ ŽŠ€‡›‚€…’‘Ÿ Ž„•Ž„Ÿ™…‰. ไ“Š–ˆˆ, „€ž™ˆ… …Ž‚’ŽŸž™ˆ…‘Ÿ ‡€—…ˆŸ, …Ž†ˆ„€Ž …„Šˆ „€†… ‚ ‘‹“—€… „Ž‚Ž‹œŽ Ž‹œ˜Ž‰ ’€‹ˆ–›. ญ€ˆŒ…, ‡€Œ…ˆ’›‰ €€„ŽŠ‘ „…‰ Ž†„…ˆŸ “’‚…†„€…’, —’Ž, …‘‹ˆ ‚ ŠŽŒ€’… ˆ‘“’‘’‚“…’ … Œ……… 23~—…‹Ž‚…Š, ˆŒ……’‘Ÿ •ŽŽ˜ˆ‰ ˜€‘ € ’Ž, —’Ž “ „‚“• ˆ‡ ˆ• ‘Ž‚€„…’ „…œ Ž†„…ˆŸ! จ›Œˆ ‘‹Ž‚€Œˆ, …‘‹ˆ Œ› ‚›ˆ€…Œ ‘‹“—€‰“ž ”“Š–ˆž, Ž’Ž€†€ž™“ž 23~Š‹ž—€ ‚ 365-‹…Œ…’“ž ’€‹ˆ–“, ’Ž ‘ ‚…ŽŸ’Ž‘’œž~$0.4927$ (Œ……… Ž‹Ž‚ˆ›) ‚‘… Š‹ž—ˆ Ž€„“’ ‚ €‡›… Œ…‘’€. แŠ…’ˆŠˆ, ‘ŽŒ…‚€ž™ˆ…‘Ÿ ‚ ’ŽŒ, ŒŽƒ“’ Ž›’€’œ‘Ÿ €‰’ˆ ‘Ž‚€„…ˆ… „…‰ Ž†„…ˆŸ € ‹ˆ†€‰˜…‰ Ž‹œ˜Ž‰ ‚…—…ˆŠ…. [ฏ€€„ŽŠ‘ „…‰ Ž†„…ˆŸ ‚…‚›… “ŽŒŸ“’ ‚ €Ž’€• ”Ž~ฌˆ‡…‘€ ({\sl Istanbul %%602 \"Universitesi Fen Fak\"ultesi Mecmuasi,\/} {\bf 4} (1939), 145--163) ˆ~ใ.~ไ…‹‹…€ (ข‚…„…ˆ… ‚ ’…Žˆž ‚…ŽŸ’Ž‘’…‰ ˆ …… ˆ‹Ž†…ˆŸ, ฌ., "ฌˆ", 1964, ƒ‹.~2, \S~3).] แ „“ƒŽ‰ ‘’ŽŽ›, Ž„•Ž„, ˆ‘Ž‹œ‡Ž‚€›‰ ‚ ’€‹.~1, „Ž‚Ž‹œŽ ƒˆŠˆ‰ [‘.~‘~ฌ.~ฃ……‚‘Šˆ ˆ~ข.~โ“‘Šˆ, {\sl CACM,\/} {\bf 6} (1963), 322--323], ˆ „‹Ÿ ’€‹ˆ–› ‘…„…ƒŽ €‡Œ…€ Ž„•Ž„Ÿ™“ž ”“Š–ˆž ŒŽ†Ž €‰’ˆ ˆŒ…Ž ‡€ „…œ. ข ‘€ŒŽŒ „…‹…, Ž—…œ ‡€Ÿ’Ž …˜€’œ Ž„Ž›… ƒŽ‹Ž‚Ž‹ŽŒŠˆ. เ€‡“Œ……’‘Ÿ, ’€ŠŽ‰ Œ…’Ž„ ˆŒ……’ ‘“™…‘’‚…›‰ …„Ž‘’€’ŽŠ, ˆŽ ‘Ž„…†ˆŒŽ… ’€‹ˆ–› „Ž‹†Ž ›’œ ˆ‡‚…‘’Ž ‡€€……; „Ž€‚‹…ˆ… •Ž’Ÿ › Ž„ŽƒŽ Š‹ž—€ ŒŽ†…’ ‚‘… ˆ‘Ž’ˆ’œ, ˆ €Œ ˆ„…’‘Ÿ €—ˆ€’œ ”€Š’ˆ—…‘Šˆ € “‘’ŽŒ Œ…‘’…. ฌŽ†Ž Ž‹“—ˆ’œ ƒŽ€‡„Ž Ž‹…… ƒˆŠˆ‰ Œ…’Ž„, …‘‹ˆ Ž’Ž‘ˆ’œ ˆ„…ž Ž„Ž‡€—Ž‘’ˆ, „Ž“‘Š€Ÿ ‘Ž‚€„…ˆŸ ‡€—…ˆ‰~$f(K)$ „‹Ÿ €‡‹ˆ—›• €ƒ“Œ…’Ž‚, ˆ ˆ‘Ž‹œ‡Ž‚€’œ Ž‘Ž›‰ Œ…’Ž„ €‡…˜…ˆŸ …Ž…„…‹…Ž‘’ˆ Ž‘‹… ‚›—ˆ‘‹…ˆŸ~$f(K)$. ญ€˜ˆ €‘‘ŒŽ’…ˆŸ ˆ‚Ž„Ÿ’ Š ˜ˆŽŠŽ ˆ‡‚…‘’ŽŒ“ Š‹€‘‘“ Œ…’Ž„Ž‚, Ž›—Ž €‡›‚€…Œ›• \dfn{•…˜ˆŽ‚€ˆ…Œ} ˆ‹ˆ \dfn{€‘‘…ŸŽ‰ €ŒŸ’œž.}  ƒ‹ˆ‰‘Šˆ‰ ƒ‹€ƒŽ‹ "to hash" ˆŒ……’ ‘Œ›‘‹ €…‡€’œ, €‘ŠŽ˜ˆ’œ —’Ž-‹ˆŽ ˆ‹ˆ ‘„…‹€’œ ˆ‡ ’ŽƒŽ Œ…‘ˆ‚Ž; ˆ„…Ÿ •…˜ˆŽ‚€ˆŸ ‘Ž‘’Žˆ’ ‚ ’ŽŒ, —’Ž› ‚‡Ÿ’œ …ŠŽ’Ž›… •€€Š’…ˆ‘’ˆŠˆ Š‹ž—€ ˆ ˆ‘Ž‹œ‡Ž‚€’œ Ž‹“—…“ž —€‘’ˆ—“ž ˆ”ŽŒ€–ˆž ‚ Š€—…‘’‚… Ž‘Ž‚› Žˆ‘Š€. ฌ› ‚›—ˆ‘‹Ÿ…Œ \dfn{•…˜-”“Š–ˆž $h(K)$} ˆ ……Œ ’Ž ‡€—…ˆ… ‚ Š€—…‘’‚… €„…‘€ €—€‹€ Žˆ‘Š€. ฏ€€„ŽŠ‘ „…‰ Ž†„…ˆŸ ‘‹“†ˆ’ „‹Ÿ €‘ …„Ž‘’……†…ˆ…Œ, —’Ž, ‚…ŽŸ’Ž, €‰„“’‘Ÿ €‡‹ˆ—›… Š‹ž—ˆ~$K_i\ne K_j$, „‹Ÿ ŠŽ’Ž›• %%603 $h(K_i)=h(K_j)$. ฏŽ„ŽŽ… ‘Ž›’ˆ… €‡›‚€…’‘Ÿ \dfn{ŠŽ‹‹ˆ‡ˆ…‰;} „‹Ÿ €‡…˜…ˆŸ ŠŽ‹‹ˆ‡ˆ‰ ›‹ˆ €‡€Ž’€› ˆ’……‘›… Ž„•Ž„›. ็’Ž› ˆ‘Ž‹œ‡Ž‚€’œ €‘‘…Ÿ“ž ’€‹ˆ–“, Žƒ€ŒŒˆ‘’ „Ž‹†… ˆŸ’œ „‚€ Ž—’ˆ …‡€‚ˆ‘ˆŒ›• …˜…ˆŸ: Ž „Ž‹†… ‚›€’œ •…˜-”“Š–ˆž~$h(K)$ ˆ Œ…’Ž„ €‡…˜…ˆŸ ŠŽ‹‹ˆ‡ˆ‰. ํ’ˆ „‚€ €‘…Š’€ ‡€„€—ˆ Žˆ‘Š€ Œ› ˆ €‘‘ŒŽ’ˆŒ Ž Ž—……„ˆ. \section ๅ…˜-”“Š–ˆˆ. ค‹Ÿ Ž…„…‹…Ž‘’ˆ € Ž’Ÿ†…ˆˆ ’ŽƒŽ “Š’€ “„…’ …„Ž‹€ƒ€’œ‘Ÿ, —’Ž •…˜-”“Š–ˆŸ~$h$ ˆŒ……’ … Ž‹…… $M$~€‡‹ˆ—›• ‡€—…ˆ‰ ˆ —’Ž ’ˆ ‡€—…ˆŸ “„Ž‚‹…’‚ŽŸž’ “‘‹Ž‚ˆž $$ 0\le h(K)M$, ’€Š —’Ž ……Ž‹…ˆ… … …„‘’€‚‹Ÿ…’ ‘…œ…‡Ž‰ Ž‹…Œ›. ฅ‘‹ˆ ˆ‘Ž‹œ‡“ž’‘Ÿ €‡„…‹œ›… ‘ˆ‘Šˆ, ”ŽŒ“‹›~(18) ˆ~(19) ‘€‚…„‹ˆ‚› „‹Ÿ~$\alpha>1$. ชŽƒ„€ †… ‘ˆ‘Šˆ ‘€‘’€ž’‘Ÿ, Š€Š ‚ €‹ƒŽˆ’Œ…~C, ŒŽ†Ž ŽŒ…™€’œ ……Ž‹Ÿž™ˆ… ‹…Œ…’› ‚Ž ‚‘ŽŒŽƒ€’…‹œ›‰ “‹ €ŒŸ’ˆ. ช€Š „ŽŠ€‡€‹ ซ.~ฃžˆ€, ‚ ’ŽŒ ‘‹“—€… ‘…„…… —ˆ‘‹Ž Ž ˆ ‚‘’€‚Š… $(M+L+1)\hbox{-ƒŽ}$~‹…Œ…’€ ‘Ž‘’€‚‹Ÿ…’~$\left(L/2M+{1\over4}\right)((1+2/M)^M-1)+{1\over2}$. \section เ€‡…˜…ˆ… ŠŽ‹‹ˆ‡ˆ‰ "Ž’Š›’Ž‰ €„…‘€–ˆ…‰". ค“ƒŽ‰ ‘Ž‘Ž …˜…ˆŸ Ž‹…Œ› ŠŽ‹‹ˆ‡ˆ‰ ‘Ž‘’Žˆ’ ‚ ’ŽŒ, —’Ž› Ž‹Ž‘’œž Ž’Š€‡€’œ‘Ÿ Ž’ ‘‘›‹ŽŠ ˆ Ž‘’Ž Ž‘Œ€’ˆ‚€’œ Ž„ˆ ‡€ „“ƒˆŒ €‡‹ˆ—›… ‹…Œ…’› ’€‹ˆ–›, ŽŠ€ … “„“’ €‰„…› Š‹ž—~$K$ ˆ‹ˆ ‘‚ŽŽ„€Ÿ Ž‡ˆ–ˆŸ. ญ… ‹Ž•Ž ›‹Ž › ˆŒ…’œ €‚ˆ‹Ž, ‘Žƒ‹€‘Ž ŠŽ’ŽŽŒ“ Š€†„›‰ Š‹ž—~$K$ Ž…„…‹Ÿ…’ Ž‘‹…„Ž‚€’…‹œŽ‘’œ %%616 Ž, ’.~….~Ž‘‹…„Ž‚€’…‹œŽ‘’œ Ž‡ˆ–ˆ‰ ‚ ’€‹ˆ–…, ŠŽ’Ž›… “†Ž Ž‘Œ€’ˆ‚€’œ ‚‘ŸŠˆ‰ €‡ ˆ ‚‘’€‚Š… ˆ‹ˆ Žˆ‘Š…~$K$. ฅ‘‹ˆ Œ›, ˆ‘Ž‹œ‡“Ÿ Ž…„…‹Ÿ…Œ“ž~$K$ Ž‘‹…„Ž‚€’…‹œŽ‘’œ Ž, €’Ž‹Š…Œ‘Ÿ € ‘‚ŽŽ„“ž Ž‡ˆ–ˆž, ’Ž ŒŽ†Ž ‘„…‹€’œ ‚›‚Ž„, —’Ž $K$~…’ ‚ ’€‹ˆ–…, ’€Š Š€Š ’€ †… Ž‘‹…„Ž‚€’…‹œŽ‘’œ Ž ‚›Ž‹Ÿ…’‘Ÿ Š€†„›‰ €‡ ˆ Ž€Ž’Š… „€ŽƒŽ Š‹ž—€. ํ’Ž’ Ž™ˆ‰ Š‹€‘‘ Œ…’Ž„Ž‚ ใ.~ฏ…’…‘Ž €‡‚€‹ \dfn{Ž’Š›’Ž‰ €„…‘€–ˆ…‰} [{\sl IBM J.~Research \& Development,\/} {\bf 1} (1957), 130--146]. ฏŽ‘’…‰˜€Ÿ ‘•…Œ€ Ž’Š›’Ž‰ €„…‘€–ˆˆ, ˆ‡‚…‘’€Ÿ Š€Š \dfn{‹ˆ…‰Ž… ŽŽŽ‚€ˆ…,} ˆ‘Ž‹œ‡“…’ –ˆŠ‹ˆ—…‘Š“ž Ž‘‹…„Ž‚€’…‹œŽ‘’œ $$ h(K), h(K)-1, \ldots, 0, M-1, M-2, \ldots, h(K)+1 \eqno(20) $$ ˆ Žˆ‘›‚€…’‘Ÿ ‘‹…„“ž™ˆŒ Ž€‡ŽŒ. \alg L.(ฏŽˆ‘Š ‘ ‚‘’€‚ŠŽ‰ Ž Ž’Š›’Ž‰ €‘‘…ŸŽ‰ ’€‹ˆ–….)  ‹ƒŽˆ’Œ Ž‡‚Ž‹Ÿ…’ €‡›‘Š€’œ „€›‰ Š‹ž—~$K$ ‚ ’€‹ˆ–… ˆ‡ $M$~“‡‹Ž‚. ฅ‘‹ˆ $K$~…’ ‚ ’€‹ˆ–… ˆ Ž€ … Ž‹€, Š‹ž—~$K$ ‚‘’€‚‹Ÿ…’‘Ÿ. ใ‡‹› ’€‹ˆ–› ŽŽ‡€—€ž’‘Ÿ —……‡~$|TABLE|[i]$, $0\le i0$.\cr } \eqno(25) $$ ํ’Ž’ Œ…’Ž„ ›‘’…… Ž‚’ŽŽƒŽ „…‹…ˆŸ, Ž Ž ‚‘… †… ˆ‚Ž„ˆ’ Š \emph{‚’Žˆ—ŽŒ“ ŽŠ“—ˆ‚€ˆž,} ’…“Ÿ …‘ŠŽ‹œŠŽ Ž‹œ˜… Ž ˆ‡-‡€ “‚…‹ˆ—…ˆŸ ‚…ŽŸ’Ž‘’ˆ ’ŽƒŽ, —’Ž „‚€ ˆ‹ˆ Ž‹…… Š‹ž—…‰ Ž‘‹…„“ž’ Ž„ˆŒ ˆ ’…Œ †… “’…Œ. ไŽŒ“‹›, ‚›‚…„…›… ˆ†…, ŒŽ†Ž ˆ‘Ž‹œ‡Ž‚€’œ, —’Ž› Ž…„…‹ˆ’œ, ……‚…˜ˆ‚€…’ ‹ˆ ‚›ˆƒ›˜ ‚Ž ‚…Œ…ˆ •…˜ˆŽ‚€ˆŸ Ž’…ˆ € Ž€•. %% 621  ‹ƒŽˆ’Œ›~L ˆ~D Ž—…œ Ž•Ž†ˆ, Ž ˆŒ…ž’ ˆ „Ž‘’€’Ž—Ž €‡‹ˆ—ˆ‰, Ž’ŽŒ“ Ž‹…‡Ž ‘€‚ˆ’œ ‚…Œ…€ €Ž’› ‘ŽŽ’‚…’‘’‚“ž™ˆ• Žƒ€ŒŒ „‹Ÿ~\MIX. \prog D.(ฎ’Š›’€Ÿ €„…‘€–ˆŸ ‘ „‚Ž‰›Œ •…˜ˆŽ‚€ˆ…Œ.) โ€Š Š€Š ’€ Žƒ€ŒŒ€ ‚…‘œŒ€ €ŽŒˆ€…’ Žƒ€ŒŒ“~L, Ž€ ˆ‚Ž„ˆ’‘Ÿ …‡ ŠŽŒŒ…’€ˆ…‚. ง„…‘œ~$|rI2|\equiv c-1$. \code START&LDX &K &1 &ENTA&0 &1 &DIV &=M= &1 &STX &*+1(0:2) &1 &ENT1&* &1 &LDX &TABLE,1 &1 &แฌเๅ&K &1 &JE &SUCCESS &1 &JXZ &4F &1-S1 &SRAX&5 &A-S1 &DIV &=M-2= &A-S1 &STX &*+1(0:2) &A-S1 &ENT2&* &A-S1 &LDA &K &A-S1 3H &DEC1&1,2 &C-1 &J1NN&*+2 &C-1 &INC1&M &B &CMPA&TABLE,1 &C-1 &JE &SUCCESS &C-1 &LDX &TABLE,1 &C-1-S2 &JXNZ&3B &C-1-S2 4H &LDX &VACANCIES&1-S &JXZ &OVERFLOW &1-S &DECX&1 &1-S &STX &VACANCIES&1-S &LDA &K &1-S &STA &TABLE,1 &1-S \endcode \progend แ—…’—ˆŠˆ —€‘’Ž’~$A$, $C$, $S1$, $S2$ ˆŒ…ž’ ’Ž’ †… ‘Œ›‘‹, —’Ž ˆ ‚ Žƒ€ŒŒ…~C. แ…„…… ‡€—…ˆ… ……Œ…Ž‰~$B$ ˆŒ…Ž €‚Ž~$(C-1)/2$. (ฅ‘‹ˆ ‘“‡ˆ’œ „ˆ€€‡Ž~$h_2(K)$, ‘Š€†…Œ, „Ž~$1\le h_2(K)\le {1\over2} M$, ‡€—…ˆ…~$B$ ‘Ž‘’€‚ˆ‹Ž › ‹ˆ˜œ~$(C-1)/4$, ‚…ŽŸ’Ž, “‚…‹ˆ—…ˆ… —ˆ‘‹€ Ž … ‘‚…„…’ € …’ ’Ž “‚…‹ˆ—…ˆ… ‘ŠŽŽ‘’ˆ.) ฅ‘‹ˆ ‚ ’€‹ˆ–… $N=\alpha M$~Š‹ž—…‰, ‘…„…… ‡€—…ˆ…~$A$, €‡“Œ……’‘Ÿ, €‚Ž~$\alpha$ „‹Ÿ …“„€—ŽƒŽ Žˆ‘Š€ ˆ~1 „‹Ÿ “„€—ŽƒŽ. ช€Š ˆ ‚ €‹ƒŽˆ’Œ…~C, ‘…„…… ‡€—…ˆ…~$S1$ „‹Ÿ …“„€—ŽƒŽ Žˆ‘Š€ ‘Ž‘’€‚‹Ÿ…’~$1-{1\over2}((N-1)/M)\approx 1-{1\over2}\alpha$. โ“„Ž ’Ž—Ž Ž…„…‹ˆ’œ ‘…„…… —ˆ‘‹Ž Ž, Ž„€ŠŽ Œˆˆ—…‘Šˆ… Ž‚…Šˆ ŽŠ€‡›‚€ž’ •ŽŽ˜…… ‘Žƒ‹€‘ˆ… ‘ ‚›‚…„…›Œˆ ˆ†… ”ŽŒ“‹€Œˆ „‹Ÿ "€‚ŽŒ…ŽƒŽ ŽŽŽ‚€ˆŸ": $$ \eqalignno{ C'_N&={M+1\over M+1-N}\approx(1-\alpha)^{-1} \rem{(…“„€—›‰ Žˆ‘Š)};&(26)\cr C_N&={M+1\over N}(H_{M+1}-H_{M+1-N}) \approx-\alpha^{-1}\ln (1-\alpha) \rem{(“„€—›‰ Žˆ‘Š)},&(27)\cr } $$ …‘‹ˆ~$h_1(K)$ ˆ~$h_2(K)$ …‡€‚ˆ‘ˆŒ›. ชŽƒ„€ †… $h_2(K)$~‡€‚ˆ‘ˆ’ Ž’~$h_1(K)$, Š€Š ‚~(25), ‚’Žˆ—Ž… ŽŠ“—ˆ‚€ˆ… ‚›‡›‚€…’ “‚…‹ˆ—…ˆ… ‘…„ˆ• %%622 ‡€—…ˆ‰ „Ž $$ \eqalignno{ C'_N &={M+1\over M+1-N}-{N\over M+1}+H_{M+1}-H_{M+1-N}+O(M)^{-1}\approx\cr &\approx(1-\alpha)^{-1}-\alpha-\ln(1-\alpha);&(28)\cr C_N&=1+H_{M+1}-H_{M+1-N}-{N\over 2(M+1)} -(H_{M+1}-H_{M+1-N})/N+O(N^{-1})\approx\cr &\approx 1-\ln(1-\alpha)-{1\over2}\alpha. &(29) \cr } $$ (แŒ.~“.~44.) ง€Œ…’ˆŒ, —’Ž, ŠŽƒ„€ ’€‹ˆ–€ ‡€Ž‹Ÿ…’‘Ÿ, ’.~….~ŠŽƒ„€ $N $~‘’…Œˆ’‘Ÿ Š~$M$, ‡€—…ˆ…~$C_N$ ˆ‹ˆ†€…’‘Ÿ Š~$H_{M+1}-1$, €~$C'_N$---Š~$H_{M+1}-{1\over2}$; ’Ž ŒŽƒŽ ‹“—˜…, —…Œ ‚ ‘‹“—€… €‹ƒŽˆ’Œ€~L, Ž … ‘’Ž‹œ •ŽŽ˜Ž, Š€Š ‚ Œ…’Ž„€• –…Ž—…Š. ฏŽ‘ŠŽ‹œŠ“ ‚ €‹ƒŽˆ’Œ…~L Ž› ‡€ˆŒ€ž’ …‘ŠŽ‹œŠŽ Œ…œ˜… ‚…Œ…ˆ, „‚Ž‰Ž… •…˜ˆŽ‚€ˆ… …„Ž—’ˆ’…‹œŽ ‹ˆ˜œ ˆ ‡€Ž‹…Ž‰ ’€‹ˆ–…. ญ€ ˆ‘.~42 ‘€‚ˆ‚€ž’‘Ÿ ‘…„ˆ… ‚…Œ…€ €Ž’› Žƒ€ŒŒ~L, D ˆ ŒŽ„ˆ”ˆ–ˆŽ‚€Ž‰ Žƒ€ŒŒ›~D (ˆ—…Œ ’€ ŒŽ„ˆ”ˆŠ€–ˆŸ ‚‹…—…’ ‡€ ‘ŽŽ‰ ‚’Žˆ—Ž… ‘Š“—ˆ‚€ˆ…): Œ› ‡€Œ…Ÿ…Œ „Ž‚Ž‹œŽ Œ…„‹…Ž… ‚›—ˆ‘‹…ˆ…~$h_2(K)$ ‚ ‘’ŽŠ€•~10--13 € ’ˆ ŠŽŒ€„› $$ \mixcode ENN2 & -M-1, 1 & $c\asg M-i$. J1NZ & *+2 ENT2 & 0 & ฅ‘‹ˆ $i=0$, $c\asg 1$. \endmixcode \eqno(30) $$ \picture{เˆ‘. 42. ข…ŒŸ “„€—ŽƒŽ Žˆ‘Š€ „‹Ÿ ’…• ‘•…Œ Ž’Š›’Ž‰ €„…‘€–ˆˆ.} %%623 ข „€ŽŒ ‘‹“—€… ‚’Žˆ—Ž… ‘Š“—ˆ‚€ˆ… ‹“—˜… …‡€‚ˆ‘ˆŒŽƒŽ Ž‚’ŽŽƒŽ •…˜ˆŽ‚€ˆŸ. ญ€ „‚Žˆ—Ž‰ ํขฌ Œ› ŒŽƒ‹ˆ › ˆ›Œ ‘Ž‘ŽŽŒ “‘ŠŽˆ’œ ‚›—ˆ‘‹…ˆ…~$h_2(K)$, ‡€Œ…ˆ‚ ‘’ŽŠˆ~10--13, ‘Š€†…Œ, € $$ \mixcode AND & =511= & $|rA|\asg |rA| \bmod 512$. STA & *+1(0:2) ENT2 & * & $c\asg |rA|+1$. \endmixcode \eqno(31) $$ …‘‹ˆ $M$---Ž‘’Ž… —ˆ‘‹Ž, Ž‹œ˜……~512. ํ’€ ˆ„…Ÿ, …„‹Ž†…€Ÿ ก…‹‹ŽŒ ˆ ช€Œ\'€ [{\sl CACM,\/} {\bf 13} (1970), 675--677], …‡€‚ˆ‘ˆŒŽ ˆ„“Œ€‚˜ˆŒˆ €‹ƒŽˆ’Œ~D, Ž‡‚Ž‹Ÿ…’ ˆ‡…†€’œ ‚’Žˆ—ŽƒŽ ‘Š“—ˆ‚€ˆŸ …‡ ‡€’€’ € Ž‚’ŽŽ… „…‹…ˆ…. ก›‹Ž …„‹Ž†…Ž ŒŽƒŽ „“ƒˆ• Ž‘‹…„Ž‚€’…‹œŽ‘’…‰ Ž ‚ Š€—…‘’‚… “‹“—˜…ˆ‰ €‹ƒŽˆ’Œ€~L, Ž, Ž-‚ˆ„ˆŒŽŒ“, ˆ Ž„€ ˆ‡ ˆ• … ‹“—˜… €‹ƒŽˆ’Œ€~D. (ก›’œ ŒŽ†…’, ˆ‘Š‹ž—…ˆ… ‘Ž‘’€‚‹Ÿ…’ Œ…’Ž„, Žˆ‘€›‰ ‚ “.~20.) \picture{ เˆ‘. 43. แŠŽ‹œŠŽ €‡ ŠŽŒˆ‹Ÿ’Ž ˆ™…’ ˆŒ…€ ……Œ…›• ‚ ’ˆˆ—ŽŒ ‘‹“—€…. จŒ…€ ‚›ˆ‘€› ‘‹…‚€ €€‚Ž ‚ ŽŸ„Š… ˆ• …‚ŽƒŽ ŽŸ‚‹…ˆŸ.} \section จ‡Œ……ˆ…, …„‹Ž†…Ž… ก…’ŽŒ. เˆ—€„ ก…’ €˜…‹ ’€ŠŽ‰ ‘Ž‘Ž ˆ‡Œ……ˆŸ €‹ƒŽˆ’Œ€~D, —’Ž› ‘…„…… ‚…ŒŸ “„€—ŽƒŽ Žˆ‘Š€ Ž‘’€‚€‹Ž‘œ Žƒ€ˆ—…›Œ Ž Œ…… ‡€Ž‹…ˆŸ ’€‹ˆ–›. ฅƒŽ Œ…’Ž„ Ž‘Ž‚€ € ’ŽŒ ”€Š’…, —’Ž ‚Ž ŒŽƒˆ• ˆ‹Ž†…ˆŸ• %%624 “„€—›‰ Žˆ‘Š Žˆ‡‚Ž„ˆ’‘Ÿ ƒŽ€‡„Ž —€™… ‚‘’€‚ŽŠ; Ž’ŽŒ“ Ž …„‹€ƒ€…’ „…‹€’œ Ž‹œ˜… €Ž’› ˆ ‚‘’€‚Š… ‹…Œ…’€, nepeŒ…™€Ÿ ‡€ˆ‘ˆ, —’Ž› “Œ…œ˜ˆ’œ Ž†ˆ„€…ŒŽ… ‚…ŒŸ ‚›ŽŠˆ. [{\sl CACM,\/} {\bf 16} (1973), 105--109.] ญ€ˆŒ…, € ˆ‘.~43 ŽŠ€‡€Ž, ‘ŠŽ‹œŠŽ €‡ ’Ž’ ˆ‹ˆ ˆŽ‰ ˆ„…’ˆ”ˆŠ€’Ž ‚‘’…—€‹‘Ÿ ‚ ’ˆˆ—Ž‰ Ž–…„“… €~PL/1. แ“„Ÿ Ž ’ˆŒ „€›Œ, ŠŽŒˆ‹Ÿ’Ž ‘~PL/1, ˆ‘Ž‹œ‡“ž™ˆ‰ €‘‘…Ÿ“ž ’€‹ˆ–“ „‹Ÿ •€…ˆŸ ˆŒ… ……Œ…›•, “„…’ ˆ‘Š€’œ ŒŽƒˆ… ˆŒ…€ Ÿ’œ ˆ‹ˆ Ž‹…… €‡, € ‚‘’€‚‹Ÿ’œ ˆ• ‹ˆ˜œ Ž„€†„›.  €‹Žƒˆ—Ž ก…‹‹ ˆ~ช€Œ\'€ Ž€“†ˆ‹ˆ, —’Ž ŠŽŒˆ‹Ÿ’Ž ‘~ชŽŽ‹€ ˆ‘Ž‹œ‡Ž‚€‹ ‘‚Ž‰ €‹ƒŽˆ’Œ ’€‹ˆ– ‘ˆŒ‚Ž‹Ž‚ $10988$~€‡ ‚Ž ‚…ŒŸ ŠŽŒˆ‹Ÿ–ˆˆ Žƒ€ŒŒ› ˆ ‘Ž‚…˜ˆ‹ ‹ˆ˜œ $735$~‚‘’€‚ŽŠ, ’.~….~€ Ž„ˆ …“„€—›‰ Žˆ‘Š ˆ•Ž„ˆ‹Ž‘œ ˆŒ…Ž 14~“„€—›•. จŽƒ„€ ’€‹ˆ–€ ‘Ž‡„€…’‘Ÿ ’Ž‹œŠŽ Ž„ˆ €‡ (€ˆŒ…, ’€‹ˆ–€ ‘ˆŒ‚Ž‹ˆ—…‘Šˆ• ŠŽ„Ž‚ Ž…€–ˆ‰ ‚ €‚’ŽŠŽ„…) ˆ ˆ‘Ž‹œ‡“…’‘Ÿ Ž‘‹… ’ŽƒŽ ˆ‘Š‹ž—ˆ’…‹œŽ „‹Ÿ ‚›ŽŠˆ. ก…’ …„‹Ž†ˆ‹ ‘‹…„“ž™ˆŒ Ž€‡ŽŒ ˆ‡Œ…ˆ’œ Ž–…‘‘ ‚‘’€‚Šˆ ‚ €‹ƒŽˆ’Œ…~D. ฏ…„Ž‹Ž†ˆŒ, —’Ž ˆ …“„€—ŽŒ Žˆ‘Š… ›‹ˆ ŽŽŽ‚€› Ÿ—…‰Šˆ $$ p_0, p_1,~\ldots, p_{t-1}, p_t, $$ ƒ„…~$p_j=(h_1(K)-jh_2(K))\bmod M$ ˆ “‡…‹~$|TABLE|[p_t]$ “‘’. ฅ‘‹ˆ~$t\le 1$, Œ›, Š€Š Ž›—Ž, ‚‘’€‚‹Ÿ…Œ~$K$ ‚ Ž‡ˆ–ˆž~$p_t$, Ž …‘‹ˆ~$t\ge2$, ‚›—ˆ‘‹Ÿ…Œ~$c_0=h_2(K_0)$, ƒ„…~$K_0=|KEY|[p_0]$, ˆ ‘ŒŽ’ˆŒ, ‘‚ŽŽ„Ž ‹ˆ ‚~$|TABLE| [(p_0-c_0)\bmod M$]. ฅ‘‹ˆ “‘‹Ž‚ˆ… ‚›Ž‹…Ž, ŽŒ…™€…Œ ‚ „€›‰ “‡…‹ ‘Ž„…†ˆŒŽ… Ÿ—…‰Šˆ~$|TABLE|[p_0]$ ˆ ‚‘’€‚‹Ÿ…Œ~$K$ ‚ Ž‡ˆ–ˆž~$p_0$. ํ’Ž “‚…‹ˆ—ˆ‚€…’ ‚…ŒŸ ‚›ŽŠˆ $K_0$ € Ž„ˆ ˜€ƒ, Ž “Œ…œ˜€…’ ‚…ŒŸ ‚›ŽŠˆ~$K$ € $t\ge2$~˜€ƒŽ‚. ข›ˆƒ›˜ €‹ˆ–Ž.  €‹Žƒˆ—Ž, …‘‹ˆ ‚~$|TABLE|[(p_0-c_0)\bmod M]$ ‡€Ÿ’Ž ˆ~$t\ge3$, Œ› Ž“…Œ Ÿ—…‰Š“~$|TABLE| [(p_0-2c_0)\bmod M]$; …‘‹ˆ ˆ ’€Œ ‡€Ÿ’Ž, ‚›—ˆ‘‹Ÿ…Œ~$c_1=h_2(|KEY|[p_1])$ ˆ Ž“…Œ $|TABLE|[(p_1-c_1)\bmod M]$ ˆ~’.~„. ขŽŽ™…, “‘’œ~$c_j=h_2(|KEY|[p_j])$ ˆ~$p_{j,k}=(p_j-kc_j)\bmod M$; …‘‹ˆ Ž‡ˆ–ˆˆ~$|TABLE|[p_{j,k}]$ ŽŠ€‡€‹ˆ‘œ ‡€Ÿ’›Œˆ ˆ ‚‘…•~$j, k$, ’€Šˆ•, —’Ž~$j+k (M+1)/(M+1-n)$; …‹œ‡Ÿ ‚‘… ‚…ŒŸ Ž…†„€’œ €‚ŽŒ…Ž… •…˜ˆŽ‚€ˆ…. ข „…‰‘’‚ˆ’…‹œŽ‘’ˆ ‚ Š€—…‘’‚… Œ…› ‹“—˜… Ž„•Ž„ˆ’ …~$C'_N$, € —ˆ‘‹Ž Ž ˆ \emph{“„€—ŽŒ} Žˆ‘Š…~$C_N$. ฏ……‘’€Ž‚Šˆ~(52) … „€ž’ “‹“—˜…ˆŸ~$C_N$ ˆ ˆ Š€ŠŽŒ~$N$, ˆ Š€†…’‘Ÿ ‚…‘œŒ€ €‡“Œ›Œ …„Ž‹Ž†ˆ’œ, —’Ž ˆŠ€ŠŽ… ˆˆ‘›‚€ˆ… ……‘’€Ž‚Š€Œ ‚…ŽŸ’Ž‘’…‰ … ŒŽ†…’ ‘„…‹€’œ~$C_N$ Œ…œ˜… "€‚ŽŒ…ŽƒŽ" ‡€—…ˆŸ~$((M+1)/N) (H_{M+1}-H_{M+1-N})$. ช€Š ŽŠ€‡›‚€…’‘Ÿ, ’Ž “’‚…†„…ˆ… Ž—…œ ’“„Ž „ŽŠ€‡€’œ ƒ‹€‚›Œ Ž€‡ŽŒ Ž’ŽŒ“, —’Ž Ž‹“—ˆ’œ ””…Š’ €‚ŽŒ…ŽƒŽ •…˜ˆŽ‚€ˆŸ ŒŽ†Ž ŒŽƒˆŒˆ ‘Ž‘Ž€Œˆ; Œ› … ŽŸ‡€› ˆˆ‘›‚€’œ Š€†„Ž‰ ……‘’€Ž‚Š… ‚…ŽŸ’Ž‘’œ~$1/M!$. ญ€ˆŒ…, ‘‹…„“ž™…… €‘…„…‹…ˆ… ˆ~$M=4$ Š‚ˆ‚€‹…’Ž €‚ŽŒ…ŽŒ“ •…˜ˆŽ‚€ˆž: $$ \matrix{ \hbox{ฏ……‘’€Ž‚Š€} & \hbox{ข…ŽŸ’Ž‘’œ} & \hbox{ฏ……‘’€Ž‚Š€} & \hbox{ข…ŽŸ’Ž‘’œ}\cr 0\ 1\ 2\ 3 & 1/6 &0\ 2\ 1\ 3 & 1/12\cr 1\ 2\ 3\ 0 & 1/6 &1\ 3\ 2\ 0 & 1/12\cr 2\ 3\ 0\ 1 & 1/6 &2\ 0\ 3\ 1 & 1/12\cr } \eqno(53) $$ (Ž‘’€‹œ›Œ 16~……‘’€Ž‚Š€Œ ˆˆ‘›‚€…’‘Ÿ “‹…‚€Ÿ ‚…ŽŸ’Ž‘’œ). แ‹…„“ž™€Ÿ ’…Ž…Œ€ •€€Š’…ˆ‡“…’ \emph{‚‘…} €‘…„…‹…ˆŸ ‚…ŽŸ’Ž‘’…‰, ŠŽ’Ž›… „€ž’ Ž‚…„…ˆ… €‚ŽŒ…ŽƒŽ •…˜ˆŽ‚€ˆŸ: \proclaim โ…Ž…Œ€~U. ฏˆˆ‘›‚€ˆ… ……‘’€Ž‚Š€Œ ‚…ŽŸ’Ž‘’…‰ ‘„…‹€…’ ‚‘… $\perm{M}{N}$~ŠŽ”ˆƒ“€–ˆ‰ ‡€Ÿ’›• ˆ ‘‚ŽŽ„›• Ÿ—……Š Ž‘‹… N~‚‘’€‚ŽŠ €‚Ž‚…ŽŸ’›Œˆ „‹Ÿ~$0{1\over2}$ €˜‹ˆ‘œ \emph{’Ž…,} ˆŒ…ž™ˆ… Ž„ˆ ˆ ’Ž’ †… „…œ Ž†„…ˆŸ? \ex[15] ฌˆ‘’… โ“ˆ–€ ˆ‘€‹ ŠŽŒˆ‹Ÿ’Ž ‘ ไฎเโเ ญ€, ˆ‘Ž‹œ‡“Ÿ „…‘Ÿ’ˆ—“ž Œ€˜ˆ“ \MIX, ˆ ……„ ˆŒ ‚‘’€‹€ ‡€„€—€ ‘Ž‡„€ˆŸ ’€‹ˆ–› ‘ˆŒ‚Ž‹Ž‚ „‹Ÿ •€…ˆŸ ˆŒ… ……Œ…›• ŠŽŒˆ‹ˆ“…ŒŽ‰ Žƒ€ŒŒ›. ค‹ˆ€ ’ˆ• ˆŒ… Žƒ€ˆ—…€ „…‘Ÿ’œž ‹ˆ’…€Œˆ. ฎ …˜ˆ‹ ˆ‘Ž‹œ‡Ž‚€’œ €‘‘…Ÿ“ž ’€‹ˆ–“ ‘~$M=100$ ˆ ›‘’“ž •…˜-”“Š–ˆž~$h(K)=\hbox{Š€‰‰ ‹…‚›‰ €‰’~$K$}$. ๅŽŽ˜Ž ‹ˆ ’Ž? \ex[15] เ€‡“ŒŽ ‹ˆ ‡€Œ…ˆ’œ …‚›… „‚… ˆ‘’“Š–ˆˆ ‚~(3) €~|LDA K|; |ENTX 0|? \ex[ขฌ30] \exhead(ฏŽ‹ˆŽŒˆ€‹œŽ… •…˜ˆŽ‚€ˆ….) ๆ…‹œ €‘’ŽŸ™…ƒŽ “€†…ˆŸ---€‘‘ŒŽ’…’œ Ž‘’Ž…ˆ… ŒŽƒŽ—‹…Ž‚~$P(x)$ ’ˆ€~(10), ŠŽ’Ž›… …Ž€‡“ž’ $n\hbox{-ˆ’Ž‚›…}$ Š‹ž—ˆ ‚ $m\hbox{-ˆ’Ž‚›…}$ €„…‘€ ˆ ˆ ’ŽŒ €‡›… Š‹ž—ˆ, Ž’‹ˆ—€ž™ˆ…‘Ÿ … Ž‹…… —…Œ $t$~ˆ’€Œˆ, Ž‹“—€’ €‡›… €„…‘€. ฏŽ ‡€„€›Œ ‡€—…ˆŸŒ~$n$, $t\le n$, ˆ –…‹ŽŒ“ —ˆ‘‹“~$k$, ’€ŠŽŒ“, —’Ž~$n$ „…‹ˆ’~$2^k-1$, Œ› Ž‘’ŽˆŒ ŒŽƒŽ—‹…, ‘’……œ Ž’ ŠŽ’ŽŽƒŽ Ÿ‚‹Ÿ…’‘Ÿ ”“Š–ˆ…‰~$n$, $t$ ˆ~$k$. (ฎ›—Ž, …‘‹ˆ ’Ž …Ž•Ž„ˆŒŽ, $n$~“‚…‹ˆ—ˆ‚€…’‘Ÿ, Ž’ŽŒ“ $k$~ŒŽ†Ž ‚›€’œ „Ž‘’€’Ž—Ž Œ€‹›Œ.) ฏ“‘’œ $S$---ŒˆˆŒ€‹œŽ… ŒŽ†…‘’‚Ž –…‹›• —ˆ‘…‹, ’€ŠŽ…, —’Ž~$\set{1,2,~\ldots, t}\subseteq S$ ˆ~$(2j) \bmod n \in S$ „‹Ÿ ‚‘…•~$j\in S$. ญ€ˆŒ…, …‘‹ˆ~$n=15$, $k=4$, $t=6$, ˆŒ……Œ~$S=\set{1, 2, 3, 4, 5, 6, 8, 10, 12, 9}$. ฎ…„…‹ˆŒ ’……œ ŒŽƒŽ—‹…~$P(x)= \prod_{j\in S} (x-\alpha^j)$, ƒ„… $\alpha$~…‘’œ ‹…Œ…’ ŽŸ„Š€~$n$ ŠŽ…—ŽƒŽ Ž‹Ÿ~$GF(2^k)$, € ŠŽ””ˆ–ˆ…’›~$P(x)$ ‚›—ˆ‘‹Ÿž’‘Ÿ ‚ ’ŽŒ Ž‹…. แ’……œ~$m$ ŒŽƒŽ—‹…€~$P(x)$ €‚€ —ˆ‘‹“ ‹…Œ…’Ž‚ ‚~$S$. ฅ‘‹ˆ~$\alpha^j$---ŠŽ…œ~$P(x)$, ’Ž ˆ~$\alpha^2j$---ŠŽ…œ; Ž’‘ž„€ ‘‹…„“…’, —’Ž ŠŽ””ˆ–ˆ…’›~$P(x)$ “„Ž‚‹…’‚ŽŸž’ ‘ŽŽ’Ž˜…ˆž~$p^2_i=p_i$, ’.~….~Žˆ €‚›~0 ˆ‹ˆ~1. คŽŠ€†ˆ’…, —’Ž …‘‹ˆ~$R(x)=r_{n-1}x^{n-1}+\cdots+r_1x+r_0$---…“‹…‚Ž‰ ŒŽƒŽ—‹… Ž ŒŽ„“‹ž~2 ‘ … Ž‹…… —…Œ $t$~…“‹…‚›Œˆ ŠŽ””ˆ–ˆ…’€Œˆ, ’Ž~$R(x)$ … Š€’…~$P(x)$ Ž ŒŽ„“‹ž~2. [ฎ’‘ž„€ ‘‹…„“…’, —’Ž ‘ŽŽ’‚…’‘’‚“ž™€Ÿ •…˜-”“Š–ˆŸ ‚…„…’ ‘…Ÿ Ž…™€›Œ Ž€‡ŽŒ.] \ex[ฌ34] \exhead(โ…Ž…Œ€ Ž ’…• „‹ˆ€•.) ฏ“‘’œ~$\theta$---ˆ€–ˆŽ€‹œŽ… —ˆ‘‹Ž, ‹…†€™…… Œ…†„“~0 ˆ~1, …„‘’€‚‹…ˆ… ŠŽ’ŽŽƒŽ ‚ ‚ˆ„… €‚ˆ‹œŽ‰ ……›‚Ž‰ „Žˆ (ŽŽ‡€—…ˆŸ .~4.5.3) …‘’œ~$\theta=/a_1, a_2, a_3, ~\ldots/$. ฏ“‘’œ~$q_0=0$, $p_0=1$, $q_1=1$, $p_1=0$ ˆ~$q_{k+1}=a_kq_k+q_{k-1}$, $p_{k+1}=a_kp_k+p_{k-1}$ ˆ~$k\ge1$. ฎŽ‡€—ˆŒ~$x \bmod 1=x-\floor{x}$ —……‡~$\{x\}$, €~$x-\ceil{x}+1$ —……‡~$\{x\}^+$. ก“„…Œ “Œ…Ž‚€’œ Ž’…‡Šˆ ‚ ’ŽŒ ŽŸ„Š…, Š€Š Žˆ Ž‹“—€ž’‘Ÿ ˆ Ž‘‹…„Ž‚€’…‹œ›• ‚‘’€‚Š€• ‚ ˆ’…‚€‹~$[0, 1]$ ’Ž—…Š~$\{\theta\}$, $\{2\theta\}$, $\{3\theta\}$,~\dots, ’€Š —’Ž …‚›‰ Ž’…‡ŽŠ „€Ž‰ „‹ˆ› ˆŒ……’ ŽŒ…~0, ‚’ŽŽ‰---ŽŒ…~1 ˆ~’.~„. คŽŠ€†ˆ’…, —’Ž ‚‘… ‘‹…„“ž™ˆ… “’‚…†„…ˆŸ ‚…›. ซ…‚›Œ ŠŽ–ŽŒ ˆ’…‚€‹€ ŽŒ…~$s$ „‹ˆ›~$\{t\theta\}$, ƒ„…~$t=rq_k+q_{k-1}$, $0\le r2(c-b)$ ˆ‹ˆ~$c-b>2(b-a)$. คŽŠ€†ˆ’…, —’Ž …‘‹ˆ~$\theta\ne \phi^{-1}$ ˆ‹ˆ~$\theta\ne\phi^{-2}$, ’Ž ˆ …ŠŽ’ŽŽŒ~$n$ ’Ž—Š€~$\{n\theta\}$ „€…’ ‹Ž•Ž… €‡ˆ…ˆ…; …‘‹ˆ †…~$\theta=\phi^{-1}$ ˆ‹ˆ~$\theta=\phi^{-2}$, ’Ž ‹Ž•ˆ• €‡ˆ…ˆ‰ … Ž‹“—€…’‘Ÿ. \ex[ฌ43] (เ.~ฃ•…Œ.) คŽŠ€†ˆ’… ˆ‹ˆ ŽŽ‚…ƒˆ’… ‘‹…„“ž™…… \emph{…„Ž‹Ž†…ˆ… Ž $3d$~„‹ˆ€•:} …‘‹ˆ~$\theta$, $\alpha_1$,~\dots, $\alpha_d$--- ‚…™…‘’‚…›… —ˆ‘‹€, ˆ—…Œ~$\alpha_1=0$, …‘‹ˆ~$n_1$,~\dots, $n_d$---€’“€‹œ›… —ˆ‘‹€ ˆ …‘‹ˆ ’Ž—Šˆ~$\{n\theta+\alpha_i\}$ ‚‘’€‚‹Ÿž’‘Ÿ ‚ ˆ’…‚€‹~$[0, 1]$ ˆ~$0\le n < n_i$, $1\le i\le d$, ’Ž $n_1+\cdots+n_d$~Ž‹“—€ž™ˆ•‘Ÿ ˆ’…‚€‹Ž‚ (‚Ž‡ŒŽ†Ž, “‘’›•) ˆŒ…ž’ … Ž‹…… $3d$~€‡‹ˆ—›• „‹ˆ. \ex[16] ฎ›—Ž “„€—›… Žˆ‘Šˆ Žˆ‡‚Ž„Ÿ’‘Ÿ —€™… …“„€—›• เ€‡“ŒŽ ‹ˆ ‘’ŽŠˆ~12--13 Žƒ€ŒŒ›~C ŽŒ…Ÿ’œ Œ…‘’€Œˆ ‘Ž ‘’ŽŠ€Œˆ~10--11? \rex[21] ฏŽŠ€†ˆ’…, —’Ž ŒŽ†Ž ’€Š ……ˆ‘€’œ Žƒ€ŒŒ“~C, —’Ž ‚Ž ‚“’……Œ –ˆŠ‹… Ž‘’€…’‘Ÿ ‹ˆ˜œ Ž„€ ˆ‘’“Š–ˆŸ “‘‹Ž‚ŽƒŽ ……•Ž„€. แ€‚ˆ’… ‚…Œ…€ €Ž’› ŒŽ„ˆ”ˆ–ˆŽ‚€Ž‰ ˆ …‚Ž€—€‹œŽ‰ Žƒ€ŒŒ. \ex[24] \exhead(แŽŠ€™…›… Š‹ž—ˆ.) ฏ“‘’œ $h(K)$---•…˜-”“Š–ˆŸ, a $g(K)$---’€Š€Ÿ ”“Š–ˆŸ Ž’~$K$, —’Ž, ‡€Ÿ~$h(K)$ ˆ~$g(K)$, ŒŽ†Ž €‰’ˆ~$K$. ญ€ˆŒ…, ˆ •…˜ˆŽ‚€ˆˆ „…‹…ˆ…Œ ŒŽ†Ž Ž‹Ž†ˆ’œ~$h(K)=K \bmod M$ ˆ~$g(K)=\floor{K/M}$; ‚ Œ“‹œ’ˆ‹ˆŠ€’ˆ‚ŽŒ •…˜ˆŽ‚€ˆˆ ‚ Š€—…‘’‚…~$h(K)$ ŒŽ†Ž ‚‡Ÿ’œ ‘’€˜ˆ… €‡Ÿ„›~$(AK/w)\bmod 1$, € ‚ Š€—…‘’‚…~$g(K)$---Ž‘’€‹œ›… €‡Ÿ„›. ฏŽŠ€†ˆ’…, —’Ž ˆ ˆ‘Ž‹œ‡Ž‚€ˆˆ Œ…’Ž„€ –…Ž—…Š …‡ €‹Ž†…ˆŸ ‚ Š€†„Ž‰ ‡€ˆ‘ˆ ‚Œ…‘’Ž~$K$ „Ž‘’€’Ž—Ž •€ˆ’œ~$g(K)$. (ํ’Ž ˆŽƒ„€ ŠŽŽŒˆ’ Ž‘’€‘’‚Ž, …Ž•Ž„ˆŒŽ… „‹Ÿ Ž‹…‰ ‘‘›‹ŽŠ.) จ‡Œ…ˆ’… €‹ƒŽˆ’Œ~C, —’Ž› Ž ŒŽƒ €Ž’€’œ ‘ ’€ŠˆŒˆ ‘ŽŠ€™…›Œˆ Š‹ž—€Œˆ, “‘’€ˆ‚ €‹Ž†…ˆ… ‘ˆ‘ŠŽ‚, Ž … ˆ‘Ž‹œ‡“Ÿ ‚‘ŽŒŽƒ€’…‹œ›• Ÿ—……Š €ŒŸ’ˆ „‹Ÿ "……Ž‹Ÿž™ˆ•" ‡€ˆ‘…‰. \ex[24] (ํ.~ํ‹œŠŽŠ.) ฏŽŠ€†ˆ’…, —’Ž Ž‹œ˜€Ÿ €‘‘…Ÿ€Ÿ ’€‹ˆ–€ ŒŽ†…’ ˆ‘Ž‹œ‡Ž‚€’œ Ž™“ž ‘ „“ƒˆŒˆ ‘‚Ÿ‡€›Œˆ ‘ˆ‘Š€Œˆ €ŒŸ’œ. ฏ“‘’œ Š€†„Ž… ‘‹Ž‚Ž ‘ˆ‘Ž—Ž‰ €ŒŸ’ˆ ‘Ž„…†ˆ’ „‚“•ˆ’Ž‚Ž… Ž‹…~|TAG|, ˆŒ…ž™…… ‘‹…„“ž™ˆ‰ ‘Œ›‘‹: {\medskip\narrower \item{$|TAG|(|P|)=0$} ŽŽ‡€—€…’ ‘‹Ž‚Ž ‚ ‘ˆ‘Š… ‘‚ŽŽ„ŽƒŽ Ž‘’€‘’‚€; $|LINK|(|P|)$~“Š€‡›‚€…’ € ‘‹…„“ž™…… ‘‚ŽŽ„Ž… ‘‹Ž‚Ž. % \item{$|TAG|(|P|)=1$} ŽŽ‡€—€…’ ˆ‘Ž‹œ‡“…ŒŽ… ‘‹Ž‚Ž, … Ÿ‚‹Ÿž™……‘Ÿ —€‘’œž €‘‘…ŸŽ‰ ’€‹ˆ–›; ”ŽŒ€’ Ž‘’€‹œ›• Ž‹…‰ ’ŽƒŽ ‘‹Ž‚€ Žˆ‡‚Ž‹…. % \item{$|TAG|(|P|)=2$} ŽŽ‡€—€…’ ‘‹Ž‚Ž ‚ €‘‘…ŸŽ‰ ’€‹ˆ–…; $|LINK|(|P|)$~“Š€‡›‚€…’ € „“ƒŽ… ‘‹Ž‚Ž. ข‘ŸŠˆ‰ €‡, ŠŽƒ„€ ˆ Ž€Ž’Š… ‘ˆ‘Š€, … Ÿ‚‹Ÿž™…ƒŽ‘Ÿ —€‘’œž €‘‘…ŸŽ‰ ’€‹ˆ–›, Œ› „Ž‘’ˆƒ€…Œ ‘‹Ž‚€ ‘~$|TAG|(|P|)=2$, “†Ž “‘’€Ž‚ˆ’œ~$P\asg|LINK|(|P|)$ „Ž Ž‹“—…ˆŸ ‘‹Ž‚€ ‘~$|TAG|(|P|)\le 1$. (ค‹Ÿ ””…Š’ˆ‚Ž‘’ˆ ŒŽ†Ž ˆ‡Œ…ˆ’œ Ž„“ ˆ‡ …„˜…‘’‚“ž™ˆ• ‘‘›‹ŽŠ; ’Žƒ„€ … ˆ„…’‘Ÿ ‘Ž‚€ ˆ ‘Ž‚€ ……‘Š€Šˆ‚€’œ —……‡ Ž„ˆ ˆ ’… †… ‹…Œ…’› €‘‘…ŸŽ‰ ’€‹ˆ–›.) \medskip} ฏŽŠ€†ˆ’…, Š€Š Ž…„…‹ˆ’œ Ž„•Ž„Ÿ™ˆ… €‹ƒŽˆ’Œ› „‹Ÿ ‚‘’€‚Šˆ ˆ ‚›ŽŠˆ Š‹ž—…‰ ˆ‡ ’€ŠŽ‰ ŠŽŒˆˆŽ‚€Ž‰ ’€‹ˆ–›, …„Ž‹€ƒ€Ÿ, —’Ž ‚ ‘‹Ž‚… ‘~$|TAG|(|P|)=2$ ˆŒ……’‘Ÿ …™… Ž„Ž Ž‹… ‘‘›‹Šˆ~$|AUX|(|P|)$. \ex[16] ฏŽ—…Œ“ ‚ €‹ƒŽˆ’Œ€•~L ˆ~D €‡“ŒŽ ”ˆŠ‘ˆŽ‚€’œ ……Ž‹…ˆ… ˆ~$N=M-1$, € … ˆ~$N=M$? %%646 \ex[10] ข Žƒ€ŒŒ…~L ƒŽ‚Žˆ’‘Ÿ, —’Ž $K$~… „Ž‹†Ž €‚Ÿ’œ‘Ÿ~0.   ‚„“ƒ € ‘€ŒŽŒ „…‹… Ž€ €Ž’€…’ „€†… ˆ~$K=0$? \ex[15] ฏŽ—…Œ“ … Ž‹Ž†ˆ’œ Ž‘’Ž~$h_2(K)=h_1(K)$ ‚~(25), …‘‹ˆ~$h_1(K)\ne0$? \rex[21] ค…‰‘’‚ˆ’…‹œŽ ‹ˆ~(31) …„Ž—’ˆ’…‹œ……~(30) ‚ Š€—…‘’‚… ‡€Œ…› ‘’ŽŠ~10--13 Žƒ€ŒŒ›~D? ค€‰’… Ž’‚…’, ˆ‘•Ž„Ÿ ˆ‡ ‘…„ˆ• ‡€—…ˆ‰~$A$, $S1$ ˆ~$C$. \ex[40] ฏŽ‚…œ’… Œˆˆ—…‘Šˆ ‚Ž‡„…‰‘’‚ˆ… Žƒ€ˆ—…ˆŸ Ž‹€‘’ˆ ‡€—…ˆ‰~$h_2(K)$ ‚ €‹ƒŽˆ’Œ…~D ’€Š, —’Ž: (a)~$1\le h_2(K)\le r$ ˆ~$r=1$, 2, 3,~\dots, 10; (b)~$1\le h_2(K)\le\rho M$ ˆ $\rho={1\over10}$, ${2\over10}$, ${3\over10}$,~\dots, ${9\over10}$. \ex[ฌ25] (เ.~ช“’€.) จ‡Œ…ˆ’… €‹ƒŽˆ’Œ~D ‘‹…„“ž™ˆŒ Ž€‡ŽŒ, “‘’€ŸŸ •…˜-”“Š–ˆž~$h_2(K)$: ‚ ˜€ƒ…~D3 “‘’€Ž‚ˆ’œ~$c\asg 0$, € ‚ €—€‹… ˜€ƒ€~D4 “‘’€Ž‚ˆ’œ~$c\asg c+1$. คŽŠ€†ˆ’…, —’Ž, …‘‹ˆ~$M=2^m$, ‘ŽŽ’‚…’‘’‚“ž™€Ÿ Ž‘‹…„Ž‚€’…‹œŽ‘’œ Ž~$h_1(K)$, $(h_1(K)-1)\bmod M$, ~\dots, $\left(h_1(K)-\perm{M}{2}\right)\bmod M$ “„…’ ……‘’€Ž‚ŠŽ‰ ŒŽ†…‘’‚€~$\set{0, 1,~\dots, M-1}$. ช€Š ’Ž’ Œ…’Ž„, “„“—ˆ ‡€Žƒ€ŒŒˆŽ‚€›Œ „‹Ÿ Œ€˜ˆ›~\MIX, ‚›ƒ‹Ÿ„ˆ’ Ž ‘€‚…ˆž ‘ ’…ŒŸ Žƒ€ŒŒ€Œˆ, €‘‘Œ€’ˆ‚€…Œ›Œˆ € ˆ‘.~42, …‘‹ˆ Ž‚…„…ˆ… €€‹Žƒˆ—Ž ‘‹“—€‰ŽŒ“ ŽŽŽ‚€ˆž ‘Ž ‚’Žˆ—›Œ ŽŠ“—ˆ‚€ˆ…Œ? \rex[20] ฏ…„Ž‹Ž†ˆŒ, —’Ž Œ› •Ž’…‹ˆ › “„€‹ˆ’œ ‡€ˆ‘œ ˆ‡ ’€‹ˆ–›, Ž‘’Ž…Ž‰ ‘ ŽŒŽ™œž €‹ƒŽˆ’Œ€~D, ŽŒ…—€Ÿ ‘ŽŽ’‚…’‘’‚“ž™“ž Ž‡ˆ–ˆž Š€Š “„€‹…“ž. แ‹…„“…’ ‹ˆ ˆ ’ŽŒ “Œ…œ˜€’œ ‡€—…ˆ… ……Œ…Ž‰~$N$, “€‚‹Ÿž™…‰ €‹ƒŽˆ’ŒŽŒ~D? \ex[27] คŽŠ€†ˆ’…, —’Ž €‹ƒŽˆ’Œ~R Ž‘’€‚‹Ÿ…’ ’€‹ˆ–“ ’Ž—Ž ‚ ’€ŠŽŒ †… ‚ˆ„…, Š€Š …‘‹ˆ › $|KEY|[i]$ … ›‹ ‘…‚€ ‚‘’€‚‹…. \rex[23] ฏˆ„“Œ€‰’… €‹ƒŽˆ’Œ, €€‹Žƒˆ—›‰ €‹ƒŽˆ’Œ“~R, „‹Ÿ “„€‹…ˆŸ ‹…Œ…’Ž‚ ˆ‡ €‘‘…ŸŽ‰ ’€‹ˆ–› –…Ž—…Š, Ž‘’Ž…Ž‰ ‘ ŽŒŽ™œž €‹ƒŽˆ’Œ€~C. \ex[ฌ20] ฏ…„Ž‹Ž†ˆŒ, —’Ž ŒŽ†…‘’‚Ž ‚‘…• ‚Ž‡ŒŽ†›• Š‹ž—…‰ ‘Ž‘’Žˆ’ ˆ‡ $MP$~‹…Œ…’Ž‚, ˆ—…Œ Ž‚Ž $P$~Š‹ž—…‰ ˆŒ…ž’ „€›‰ •…˜-€„…‘. (ข …€‹œ›• ‘‹“—€Ÿ• $P$~Ž—…œ ‚…‹ˆŠŽ; €ˆŒ…, …‘‹ˆ Š‹ž—€Œˆ Ÿ‚‹Ÿž’‘Ÿ Žˆ‡‚Ž‹œ›… „…‘Ÿ’ˆ‡€—›… —ˆ‘‹€, €~$M=10^3$, ’Ž~$P=10^7$.) ฏ…„Ž‹Ž†ˆŒ, —’Ž~$M\ge7$ ˆ~$N=7$. ฏ“‘’œ ˆ‡ ŒŽ†…‘’‚€ ‚‘…• ‚Ž‡ŒŽ†›• Š‹ž—…‰ ‘‹“—€‰›Œ Ž€‡ŽŒ ‚›ˆ€ž’‘Ÿ ‘…Œœ €‡‹ˆ—›• ‹…Œ…’Ž‚. ข›€‡ˆ’… —……‡~$M$ ˆ~$P$ ’Ž—“ž ‚…ŽŸ’Ž‘’œ Ž‹“—…ˆŸ •…˜-Ž‘‹…„Ž‚€’…‹œŽ‘’ˆ 1~2~6~2~1~6~1 (’.~….~$h(K_1)=1$, $h(K_2)=2$,~\dots, $h(K_7)=1$). \ex[M19] ฎฎŸ‘ˆ’…, Ž—…Œ“ ‚…€ ”ŽŒ“‹€~(39). \ex[M20] แŠŽ‹œŠŽ •…˜-Ž‘‹…„Ž‚€’…‹œŽ‘’…‰ $a_1\ a_2~\ldots a_9$ ˆ ˆ‘Ž‹œ‡Ž‚€ˆˆ ‹ˆ…‰ŽƒŽ ŽŽŽ‚€ˆŸ „€„“’ Š€’ˆ“ ‡€Ÿ’›• Ÿ—……Š~(21)? \ex[ฌ27] ง€‚…˜ˆ’… „ŽŠ€‡€’…‹œ‘’‚Ž ’…Ž…Œ›~K. [\emph{ใŠ€‡€ˆ…:} “‘’œ $$ s(n,x,y)=\sum_{k\ge0}\perm{n}{k}(x+k)^{k+1}(y-k)^{n-k-1}(y-n); $$ ˆ‘Ž‹œ‡“‰’… ˆŽŒˆ€‹œ“ž ’…Ž…Œ“  …‹Ÿ [”ŽŒ“‹€~(1.2.6-16)] „‹Ÿ „ŽŠ€‡€’…‹œ‘’‚€ ’ŽƒŽ, —’Ž~$s(n, x, y)=x(x+y)^n+ns(n-1, x+1, y-1)$] \ex[M30] ข ’… „€‚ˆ… ‚…Œ…€, ŠŽƒ„€ ํขฌ ›‹ˆ ƒŽ€‡„Ž Œ…„‹……… ›…˜ˆ•, Ž Œˆƒ€ˆž ‹€ŒŽ—…Š ŒŽ†Ž ›‹Ž ‘“„ˆ’œ, ‘ Š€ŠŽ‰ ‘ŠŽŽ‘’œž €Ž’€…’ €‹ƒŽˆ’Œ~L. ชŽƒ„€ ’€‹ˆ–€ ‘’€Ž‚ˆ‹€‘œ Ž—’ˆ Ž‹Ž‰, Ž„ˆ ‹…Œ…’› Ž€€’›‚€‹ˆ‘œ Ž—…œ ›‘’Ž, € „“ƒˆ… ‚…‘œŒ€ Œ…„‹…Ž. ํ’ˆ €‹ž„…ˆŸ €‚Ž„Ÿ’ € Œ›‘‹œ Ž ’ŽŒ, —’Ž, …‘‹ˆ ˆ‘Ž‹œ‡“…’‘Ÿ ‹ˆ…‰Ž… ŽŽŽ‚€ˆ…, ‘…„…Š‚€„€’ˆ—Ž… Ž’Š‹Ž…ˆ… ‚…‹ˆ—ˆ›~$C'_N$ „Ž‚Ž‹œŽ ‚…‹ˆŠŽ. ญ€‰„ˆ’… ”ŽŒ“‹“, ‚›€†€ž™“ž „ˆ‘…‘ˆž —……‡ ”“Š–ˆˆ~$Q_r$, Ž…„…‹…›… ‚ ’…Ž…Œ…~K, ˆ Ž–…ˆ’… …… ˆ~$N=\alpha M$ ˆ~$M\to\infty$. \ex[M21] \exhead(ง€„€—€ Ž ‘’ŽŸŠ….) ญ€ …ŠŽ‰ “‹ˆ–… ‘ Ž„Ž‘’ŽŽˆŒ „‚ˆ†…ˆ…Œ ˆŒ……’‘Ÿ $m$~Œ…‘’ „‹Ÿ ‘’ŽŸŠˆ, €‘Ž‹Ž†…›• ‚ Ÿ„ ˆ ……“Œ…Ž‚€›• Ž’~1 „Ž~$m$. ฌ“† ‚…‡…’ ‚ €‚’ŽŒŽˆ‹… ‘‚Žž „…Œ‹ž™“ž †…“. ข…‡€Ž †…€ Ž‘›€…’‘Ÿ ˆ ’…“…’ …Œ…„‹…Ž Ž‘’€Ž‚ˆ’œ‘Ÿ. ฎ Ž‘‹“˜Ž Ž‘’€€‚‹ˆ‚€…’‘Ÿ %%647 € …‚ŽŒ ‘‚ŽŽ„ŽŒ Œ…‘’…, Ž …‘‹ˆ …’ ‘‚ŽŽ„›• Œ…‘’, Š ŠŽ’Ž›Œ ŒŽ†Ž Ž„ฎ…•€’œ, … Ž‚Ž€—ˆ‚€Ÿ Ž€’Ž (’.~….~…‘‹ˆ †…€ Ž‘“‹€‘œ, ŠŽƒ„€ Œ€˜ˆ€ „Ž‘’ˆƒ‹€ $k\hbox{-ƒŽ}$~Œ…‘’€ „‹Ÿ ‘’ŽŸŠˆ, Ž ‚‘… "Ž‡ˆ–ˆˆ"~$k$, $k+1$,~\dots, $m$ ‡€Ÿ’›), Œ“† ˆŽ‘ˆ’ ‘‚Žˆ ˆ‡‚ˆ…ˆŸ ˆ …„…’ „€‹œ˜… ฏ…„Ž‹Ž†ˆŒ, —’Ž ’Ž Žˆ‘•Ž„ˆ’ ‘ $n$~€‡‹ˆ—›Œˆ Œ€˜ˆ€Œˆ, ˆ—…Œ $j-\hbox{Ÿ}$~†…€ Ž‘›€…’‘Ÿ ‚ ŒŽŒ…’, ŠŽƒ„€ Œ€˜ˆ€ €•Ž„ˆ’‘Ÿ ……„ Œ…‘’ŽŒ~$a_j$. แŠŽ‹œŠŽ ˆŒ……’‘Ÿ ’€Šˆ• Ž‘‹…„Ž‚€’…‹œŽ‘’…‰~$a_1$~\dots{}$a_n$, ˆ ŠŽ’Ž›• ‚‘… Œ€˜ˆ› “„€—Ž ˆ€Š“ž’‘Ÿ, …„Ž‹€ƒ€Ÿ, —’Ž …‚Ž€—€‹œŽ “‹ˆ–€ “‘’€ ˆ ˆŠ’Ž ‘Ž ‘’ŽŸŠˆ … “…‡†€…’? ญ€ˆŒ…, …‘‹ˆ~$m=n=9$ ˆ~$a_1\ldots{}a_9=3\ 1\ 4\ 1\ 5\ 9\ 2\ 6\ 5$, €‚’ŽŒŽˆ‹ˆ €‘Ž‹Ž†€’‘Ÿ ‘‹…„“ž™ˆŒ Ž€‡ŽŒ: \picture{เˆ‘. ‘’. 647} [ใŠ€‡€ˆ…: ‚Ž‘Ž‹œ‡“‰’…‘œ €€‹ˆ‡ŽŒ ‹ˆ…‰ŽƒŽ ŽŽŽ‚€ˆŸ.] \ex[ฌ28] (ค†Ž~เˆŽ„€.) ฏŽŠ€†ˆ’…, —’Ž ‚ ‡€„€—… Ž ‘’ŽŸŠ… ˆ‡ “.~29 ˆ~$n=m$ ‚‘… Œ€˜ˆ› ˆ€Š“ž’‘Ÿ ’Žƒ„€ ˆ ’Ž‹œŠŽ ’Žƒ„€, ŠŽƒ„€ ‘“™…‘’‚“…’ ……‘’€Ž‚Š€~$p_1$ $p_2$~\dots{} $p_n$ ŒŽ†…‘’‚€~$\set{1, 2, ~\ldots, }$, ’€Š€Ÿ, —’Ž~$a_j\le p_j$ „‹Ÿ ‚‘…•~$j$. \ex[ฌ40] ฅ‘‹ˆ ‚ ‡€„€—… Ž ‘’ŽŸŠ… (“.~29) $n=m$, —ˆ‘‹Ž …˜…ˆ‰ ŽŠ€‡›‚€…’‘Ÿ €‚›Œ~$(n+1)^{n-1}$, € ˆ‡ “.~2.3.4.4-22 Œ› ‡€…Œ, —’Ž ’Ž …‘’œ —ˆ‘‹Ž ‘‚ŽŽ„›•, „……‚œ…‚ €„~$n+1$~€‡‹ˆ—›Œˆ ‚…˜ˆ€Œˆ! ญ€‰„ˆ’… ˆ’……‘“ž ‡€‚ˆ‘ˆŒŽ‘’œ Œ…†„“ Ž‘‹…„Ž‚€’…‹œŽ‘’ŸŒˆ Ž‘’€Ž‚ŽŠ ˆ „……‚œŸŒˆ. \ex[ฌ26] คŽŠ€†ˆ’…, —’Ž ‘ˆ‘’…Œ€ “€‚…ˆ‰~(44) ˆŒ……’ …„ˆ‘’‚…Ž… …˜…ˆ…~$(C_0, C_1,~\ldots, C_{M-1})$ ˆ ‹ž›• –…‹›• …Ž’ˆ–€’…‹œ›•~$b_0$, $b_1$,~\dots, $b_{M-1}$, ‘“ŒŒ€ ŠŽ’Ž›• Œ…œ˜…~$M$. ฏŽ‘’Ž‰’… €‹ƒŽˆ’Œ „‹Ÿ €•Ž†„…ˆŸ ’ŽƒŽ …˜…ˆŸ. \ex[ฌ23] ฎฎŸ‘ˆ’…, Ž—…Œ“~(51) ‚‘…ƒŽ ‹ˆ˜œ ˆ‹ˆ†…ˆ… Š ˆ‘’ˆŽŒ“ ‘…„…Œ“ —ˆ‘‹“ Ž, Žˆ‡‚Ž„ˆŒ›• €‹ƒŽˆ’ŒŽŒ~L. [ช€Šˆ… …‘’ŽƒŽ‘’ˆ ›‹ˆ „Ž“™…› ˆ ‚›‚Ž„…~(51)?] \ex[ฌ22] ๆ…‹œ ’ŽƒŽ “€†…ˆŸ---ˆ‘‘‹…„Ž‚€’œ ‘…„……, —ˆ‘‹Ž Ž ‚ €‘‘…ŸŽ‰ ’€‹ˆ–… –…Ž—…Š, ŠŽƒ„€ ‘ˆ‘Šˆ Ž‘’€ž’‘Ÿ €‡„…‹œ›Œˆ, Š€Š € ˆ‘~38. (a)~็…Œ“ €‚€ ‚…ŽŸ’Ž‘’œ~$P_{Nk}$ ’ŽƒŽ, —’Ž „€›‰ ‘ˆ‘ŽŠ ˆŒ……’ „‹ˆ“~$k$, …‘‹ˆ $M^N$~•…˜-Ž‘‹…„Ž‚€’…‹œŽ‘’…‰~(35) €‚Ž‚…ŽŸ’›? (b)~ญ€‰„ˆ’… Žˆ‡‚Ž„Ÿ™“ž ”“Š–ˆž~$P_N(z)\sum_{k\ge0} P_{Nk} z^k$. (c)~ข›€‡ˆ’… —……‡ ’“ Žˆ‡‚Ž„Ÿ™“ž ”“Š–ˆž ‘…„…… —ˆ‘‹Ž Ž ˆ “„€—ŽŒ ˆ …“„€—ŽŒ Žˆ‘Š…. (ฏ…„Ž‹€ƒ€…’‘Ÿ, —’Ž …“„€—›‰ Žˆ‘Š ‚ ‘ˆ‘Š… „‹ˆ›~$k$ ’…“…’ $k+\delta_{k0}$~Ž.) \ex[ฌ21] (ฏŽ„Ž‹†…ˆ… “.~34.) ญ€‰„ˆ’… ‘…„…… —ˆ‘‹Ž Ž ˆ …“„€—ŽŒ Žˆ‘Š…, …‘‹ˆ Ž’„…‹œ›… ‘ˆ‘Šˆ “ŽŸ„Ž—…› Ž ‡€—…ˆŸŒ Š‹ž—…‰. \ex[ฌ22] ญ€‰„ˆ’… „ˆ‘…‘ˆž —ˆ‘‹€ Ž „‹Ÿ Œ…’Ž„€ €‡„…‹œ›• –…Ž—…Š, …‘‹ˆ Žˆ‘Š ›‹ …“„€—›Œ. (แŒ.~(18).) \rex[ฌ29] ญ€‰„ˆ’… „ˆ‘…‘ˆž —ˆ‘‹€ Ž „‹Ÿ Œ…’Ž„€ €‡„…‹œ›• –…Ž—…Š, …‘‹ˆ Žˆ‘Š ›‹ “„€—›Œ. (แŒ.~(19).) \ex[ฌ32] \exhead(จ‘Ž‹œ‡Ž‚€ˆ… „……‚œ…‚ ˆ •…˜ˆŽ‚€ˆˆ.) จ‘Š“‘›‰ Žƒ€ŒŒˆ‘’ ŒŽƒ › Ž›’€’œ‘Ÿ ˆ‘Ž‹œ‡Ž‚€’œ ‚ Œ…’Ž„… –…Ž—…Š ˆ€›… „……‚œŸ Žˆ‘Š€ ‚Œ…‘’Ž ‹ˆ…‰›• ‘ˆ‘ŠŽ‚, ŠŽŒˆˆ“Ÿ ’€ŠˆŒ Ž€‡ŽŒ €‹ƒŽˆ’Œ~6.2.2โ ‘ •…˜ˆŽ‚€ˆ…Œ. ฏŽ€€‹ˆ‡ˆ“‰’… ‘…„…… —ˆ‘‹Ž Ž, “†›• ’ŽŒ“ ŠŽŒˆˆŽ‚€ŽŒ“ €‹ƒŽˆ’Œ“ ˆ ‚ ‘‹“—€… “„€—ŽƒŽ, ˆ ‚ ‘‹“—€… …“„€—ŽƒŽ Žˆ‘Š€. [\emph{ใŠ€‡€ˆ…:} ‘.~‘ ”ŽŒ“‹Ž‰~(5.2.1-11).] \ex[M30] ๆ…‹œ ’ŽƒŽ “€†…ˆŸ---Ž€€‹ˆ‡ˆŽ‚€’œ ‘…„…… —ˆ‘‹Ž Ž ‚ €‹ƒŽˆ’Œ…~C (‘€‘’€ž™ˆ…‘Ÿ –…Ž—Šˆ). ฎŽ‡€—ˆŒ —……‡~$c(k_1, k_2, k_3, ~\dots)$ ŠŽ‹ˆ—…‘’‚Ž •…˜-Ž‘‹…„Ž‚€’…‹œŽ‘’…‰~(35), ‡€‘’€‚‹Ÿž™ˆ• €‹ƒŽˆ’Œ~C Ž€‡Ž‚€’œ Ž‚Ž $k_1$~‘ˆ‘ŠŽ‚ „‹ˆ›~1, $k_2$~‘ˆ‘ŠŽ‚ „‹ˆ›~2 ˆ ’.~„.; $k_1+2k_2+3k_3+\ldots=N$. ญ€‰„ˆ’… …Š“…’Ž… ‘ŽŽ’Ž˜…ˆ…, Ž…„…‹Ÿž™…… ’ˆ —ˆ‘‹€, ˆ ˆ‘Ž‹œ‡“‰’… %%648 …ƒŽ ˆ ‚›‚Ž„… Ž‘’Ž‰ ”ŽŒ“‹› „‹Ÿ ‘“ŒŒ› $$ S_N=\sum_{\scriptstyle j\ge 1\atop \scriptstyle k_1+k_2+\ldots=N}k_jc(k_1, k_2, \ldots). $$ ช€Š ‘‚Ÿ‡€€ ‚…‹ˆ—ˆ€ $S_N$ ‘ —ˆ‘‹ŽŒ Ž ‚Ž ‚…ŒŸ …“„€—ŽƒŽ Žˆ‘Š€ ‘ ˆ‘Ž‹œ‡Ž‚€ˆ…Œ €‹ƒŽˆ’Œ€~C? \ex[M33] ญ€‰„ˆ’… „ˆ‘…‘ˆž —ˆ‘‹€ Ž, Žˆ‡‚Ž„ˆŒ›• ‚ €‹ƒŽˆ’Œ…~C, …‘‹ˆ Žˆ‘Š ›‹ …“„€—›Œ (‘Œ.~(15).) \ex[ฌ40] ฏŽ€€‹ˆ‡ˆ“‰’…, ‘ŠŽ‹œŠŽ €‡ ‚ ‘…„…Œ |R|~“Œ…œ˜€…’‘Ÿ €~1 ˆ ‚‘’€‚Š… $(N+1)\hbox{-ƒŽ}$~‹…Œ…’€ ‘ ŽŒŽ™œž €‹ƒŽˆ’Œ€~C. (ฎŽ‡€—ˆŒ ’Ž —ˆ‘‹Ž —……‡~$T_N$.) \ex[ฌ20] ข›‚…„ˆ’…~(17). \ex[ฌ42] ฏŽ€€‹ˆ‡ˆ“‰’… ŒŽ„ˆ”ˆŠ€–ˆž €‹ƒŽˆ’Œ€~C, ˆ‘Ž‹œ‡“ž™“ž ’€‹ˆ–“ €‡Œ…€~$M'\ge M$. ค‹Ÿ •…˜ˆŽ‚€ˆŸ ˆ‘Ž‹œ‡“ž’‘Ÿ ‹ˆ˜œ …‚›…~$M$ Ž‡ˆ–ˆ‰, ’€Š —’Ž …‚›… $M'-M$~‘‚ŽŽ„›• “‡‹Ž‚, €‰„…›• ‚ ˜€ƒ…~C5, €‘Ž‹Ž†€’‘Ÿ ‚ „ŽŽ‹ˆ’…‹œŽ‰ —€‘’ˆ ’€‹ˆ–›. ช€ŠŽ‰ ‚›Ž~$M$ ˆ ”ˆŠ‘ˆŽ‚€ŽŒ~$M'$, $1\le M \le M'$, „€…’ €ˆ‹“—˜ˆ… •€€Š’…ˆ‘’ˆŠˆ? \ex[ฌ43] \exhead(แ‹“—€‰Ž… ŽŽŽ‚€ˆ… ‘ ‚’Žˆ—›Œ ‘Š“—ˆ‚€ˆ…Œ.) ๆ…‹œ ’ŽƒŽ “€†…ˆŸ---Ž…„…‹ˆ’œ ‘…„…… —ˆ‘‹Ž Ž ‚ ‘•…Œ… Ž’Š›’Ž‰ €„…‘€–ˆ‰ ‘ Ž‘‹…„Ž‚€’…‹œŽ‘’œž ŽŽŽ‚€ˆ‰ $$ h(K), (h(K)+p_1)\bmod M, (h(K)+p_2)\bmod M, \ldots, (h(K)+p_{M-1})\bmod M, $$ ƒ„… $p_1$ $p_2$~\dots $p_{M-1}$---‘‹“—€‰Ž-‚›€€Ÿ ……‘’€Ž‚Š€ ŒŽ†…‘’‚€~$\set{1, 2,~\ldots, M-1}$, ‡€‚ˆ‘Ÿ™€Ÿ Ž’~$h(K)$. จ›Œˆ ‘‹Ž‚€Œˆ, “ ‚‘…• Š‹ž—…‰ ‘ Ž„ˆ€ŠŽ‚›Œ ‡€—…ˆ…Œ~$h(K)$ Ž„€ ˆ ’€ †… Ž‘‹…„Ž‚€’…‹œŽ‘’œ ŽŽŽ‚€ˆ‰, € $(M-1)!^M$~‚Ž‡ŒŽ†›• ‚›ŽŽ‚ $M$~Ž‘‹…„Ž‚€’…‹œŽ‘’…‰ Ž ‘ ’ˆŒ ‘‚Ž‰‘’‚ŽŒ €‚Ž‚…ŽŸ’›. ฌŽ†Ž ’Ž—Ž ‘ŒŽ„…‹ˆŽ‚€’œ ‘ˆ’“€–ˆž, …‘‹ˆ €„ …‚Ž€—€‹œŽ “‘’›Œ ‹ˆ…‰›Œ Œ€‘‘ˆ‚ŽŒ €‡Œ…€~$m$ ‚›Ž‹ˆ’œ ‘‹…„“ž™“ž Ž–…„““. ค…‹€…Œ $n$~€‡ ’€Š“ž Ž…€–ˆž: {\medskip\narrower แ ‚…ŽŸ’Ž‘’œž~$p$ ‡€‰Œ…Œ Š€‰žž ‹…‚“ž ‘‚ŽŽ„“ž Ž‡ˆ–ˆž. ข Ž’ˆ‚ŽŒ ‘‹“—€… (’.~….\ ‘~‚…ŽŸ’Ž‘’œž~$q=1-p$) ‚›……Œ ‹ž“ž Ž‡ˆ–ˆž ’€‹ˆ–›, ŠŽŒ… Š€‰…‰ ‹…‚Ž‰, ˆ—…Œ ‚‘… $m-1$~Ž‡ˆ–ˆ‰ €‚Ž‚…ŽŸ’›. ฅ‘‹ˆ ‚›€€Ÿ Ž‡ˆ–ˆŸ ‘‚ŽŽ„€, ‡€‰Œ…Œ ……; ‚ Ž’ˆ‚ŽŒ ‘‹“—€… ‚›……Œ \emph{‹ž“ž} ‘‚ŽŽ„“ž Ž‡ˆ–ˆž (‚Š‹ž—€Ÿ ‘€Œ“ž ‹…‚“ž) ˆ ‡€‰Œ…Œ ……, ‘—ˆ’€Ÿ, —’Ž ‚‘… ‘‚ŽŽ„›… Ž‡ˆ–ˆˆ €‚Ž‚…ŽŸ’›. \medskip} ญ€ˆŒ…, …‘‹ˆ~$m=5$ ˆ~$n=3$, ’Ž Ž‘‹… ‚›Ž‹…ˆŸ Žˆ‘€Ž‰ Ž–…„“› ŠŽ”ˆƒ“€–ˆŸ (‡€Ÿ’Ž, ‡€Ÿ’Ž, ‘‚ŽŽ„Ž, ‡€Ÿ’Ž, ‘‚ŽŽ„Ž) Ž‹“—€…’‘Ÿ ‘ ‚…ŽŸ’Ž‘’œž $$ {7\over 192}qqq+{1\over6}pqq+{1\over6}qpq+{11\over64}qqp+{1\over3}ppq+{1\over4}pqp+{1\over4}qpp. $$ (ํ’€ Ž–…„“€ ‘ŽŽ’‚…’‘’‚“…’ ‘‹“—€‰ŽŒ“ ŽŽŽ‚€ˆž ‘ ‚’Žˆ—›Œ ‘Š“—ˆ‚€ˆ…Œ, ŠŽƒ„€~$p=1/m$, ˆŽ ŒŽ†Ž ……“Œ…Ž‚€’œ ‹…Œ…’› ’€‹ˆ–› ’€Š, —’Ž …ŠŽ’Ž€Ÿ Ž‘‹…„Ž‚€’…‹œŽ‘’œ Ž ‘Ž‚€„…’ ‘~0, 1, 2,~\dots, € ‚‘… Ž‘’€‹œ›… “„“’ ‘‹“—€‰›Œˆ.) ญ€‰„ˆ’… ”ŽŒ“‹“ „‹Ÿ ‘…„…ƒŽ —ˆ‘‹€ ‡€Ÿ’›• Ž‡ˆ–ˆ‰ ‚ ‹…‚ŽŒ ŠŽ–… Œ€‘‘ˆ‚€ („‚… ‚ ˆ‚…„…ŽŒ ˆŒ……). ฎ…„…‹ˆ’… ’€Š†… €‘ˆŒ’Ž’ˆ—…‘ŠŽ… ‡€—…ˆ… ’Ž‰ ‚…‹ˆ—ˆ› ˆ~$p=1/m$, $n=\alpha(m+1)$, $m\to\infty$. \ex[ฌ43] เ…˜ˆ’… €€‹Žƒ “.~44 ‘ \emph{’…’ˆ—›Œ ‘Š“—ˆ‚€ˆ…Œ,} ŠŽƒ„€ Ž‘‹…„Ž‚€’…‹œŽ‘’œ Ž €—ˆ€…’‘Ÿ ‘~$h_1(K)$, $(h_1(K)+h_2(K))\bmod M$; ‚›Ž „€‹œ…‰˜ˆ• Ž ‘‹“—€… ˆ ‡€‚ˆ‘ˆ’ ‹ˆ˜œ Ž’~$h_1(K)$ ˆ~$h_2(K)$ (’.~….~$(M-2)!^{M(M-1)}$ ‚Ž‡ŒŽ†›• ‚›ŽŽ‚ Ž‘‹…„Ž‚€’…‹œŽ‘’…‰ Ž ‘ ’ˆŒ ‘‚Ž‰‘’‚ŽŒ ‘—ˆ’€ž’‘Ÿ %%649 €‚Ž‚…ŽŸ’›Œˆ). ๏‚‹Ÿ…’‘Ÿ ‹ˆ …„‹€ƒ€…Œ€Ÿ Ž–…„“€ €‘ˆŒ’Ž’ˆ—…‘Šˆ Š‚ˆ‚€‹…’Ž‰ €‚ŽŒ…ŽŒ“ ŽŽŽ‚€ˆž? \ex[M42] ญ€‰„ˆ’…~$C'_N$ ˆ~$C_N$ „‹Ÿ Œ…’Ž„€ Ž’Š›’Ž‰ €„…‘€–ˆˆ, ˆ‘Ž‹œ‡“ž™…ƒŽ Ž‘‹…„Ž‚€’…‹œŽ‘’œ Ž $$ h(K), 0, 1, \ldots, h(K-1), h(K)+1, \ldots, M-1. $$ \ex[M25] ช€ŠŽ… ‘…„…… —ˆ‘‹Ž Ž Ž’…“…’‘Ÿ „‹Ÿ Ž’Š›’Ž‰ €„…‘€–ˆˆ ‘ Ž‘‹…„Ž‚€’…‹œŽ‘’œž Ž $$ h(K), h(K)-1, h(K)+1, h(K)-2, h(K)+2,\ldots\,? $$ ํ’€ Ž‘‹…„Ž‚€’…‹œŽ‘’œ ›‹€ Ž„€†„› …„‹Ž†…€ ˆ‡-‡€ ’ŽƒŽ, —’Ž ‚‘… €‘‘’ŽŸˆŸ Œ…†„“ Ž‘‹…„Ž‚€’…‹œ›Œˆ Ž€Œˆ ˆ —…’ŽŒ~$M$ €‡‹ˆ—› [\emph{ใŠ€‡€ˆ…: …Ž‹œ˜€Ÿ •ˆ’Ž‘’œ ‘“™…‘’‚…Ž Ž‹…ƒ—ˆ’ ‡€„€—“.}] \rex[M21] ค€€ …‘ŠŽ…—€Ÿ Ž‘‹…„Ž‚€’…‹œŽ‘’œ ‚‡€ˆŒŽ …‡€‚ˆ‘ˆŒ›• ‘‹“—€‰›• •…˜-”“Š–ˆ‰~$h_n(K)$. ฏŽ€€‹ˆ‡ˆ“‰’… Œ…’Ž„ Ž’Š›’Ž‰ €„…‘€–ˆˆ, ‚ ŠŽ’ŽŽŒ Ž“ž’‘Ÿ Ž‡ˆ–ˆˆ~$h_1(K)$, $h_2(K)$, $h_3(K)$,~$\ldots\,$. ง€Œ…’œ’…, —’Ž ‚Ž‡ŒŽ†Ž Ž‚’ŽŽ… ŽŽŽ‚€ˆ… Ž„Ž‰ ˆ ’Ž‰ †… Ž‡ˆ–ˆˆ, €ˆŒ… …‘‹ˆ~$h_1(K)=h_2(K)$, Ž ’Ž ‚…‘œŒ€ Œ€‹Ž‚…ŽŸ’Ž. \ex[ขฌ24] ฎŽ™ˆ‚ “.~34 € ‘‹“—€‰ $b$~‡€ˆ‘…‰ ‚ ‹ŽŠ…, Ž…„…‹ˆ’… ‘…„…… —ˆ‘‹Ž Ž (’.~….~Ž€™…ˆ‰ Š ”€‰‹“) $C_N$ ˆ~$C'_N$ ˆ ˆ‘Ž‹œ‡Ž‚€ˆˆ €‡„…‹œ›• –…Ž—…Š, …„Ž‹€ƒ€Ÿ, —’Ž …“„€—›‰ Žˆ‘Š ‚ ‘ˆ‘Š… ˆ‡ $k$~‹…Œ…’Ž‚ ’…“…’~$\min(1, k-b+1)$~Ž. ขŒ…‘’Ž ’Ž—›• ‚…ŽŸ’Ž‘’…‰~$P_{Nk}$ ˆ‡ “.~34 ‚Ž‘Ž‹œ‡“‰’…‘œ \dfn{ˆ‹ˆ†…ˆ…Œ ฏ“€‘‘Ž€} $$ \eqalign{ \perm{N}{k}\left({1\over M}\right)^k \left(1-{1\over M}\right)^{N-k} &={N\over M}{N-1\over M}\ldots{N-k+1\over M}\left(1-{1\over M}\right)^N \left(1-{1\over M}\right)^{-k}{1\over k!}=\cr &=e^{-\rho}\rho^k/k!+O(M^{-1}),\cr } $$ ‘€‚…„‹ˆ‚›Œ ˆ~$N=\rho M$, $M\to\infty$. \ex[M20] ฏŽŠ€†ˆ’…, —’Ž ‚ ŽŽ‡€—…ˆŸ•~(42) $Q_1(M, N)=M-(M-N-1)Q_0(M, N)$. [\emph{ใŠ€‡€ˆ…:} „ŽŠ€†ˆ’… ‘€—€‹€, —’Ž $Q_1(M, N)=(N+1)Q_0(M, N)-NQ_0(M, N-1)$.] \ex[BM16] ข›€‡ˆ’… ”“Š–ˆž~$R(\alpha, n)$, Ž…„…‹…“ž ‚~(55), —……‡ ”“Š–ˆž~$Q_0$, Ž…„…‹…“ž ‚~(42). \ex[ขฌ20] คŽŠ€†ˆ’…, —’Ž~$Q_0(M,N)=\int_0^\infty e^{-t}(1+t/M)^N\,dt.$ \ex[ขฌ20] คŽŠ€†ˆ’…, —’Ž ”“Š–ˆž~$R(\alpha, n)$ ŒŽ†Ž ‚›€‡ˆ’œ —……‡ …Ž‹“ž ƒ€ŒŒ€-”“Š–ˆž, ˆ ˆ‘Ž‹œ‡“‰’… …‡“‹œ’€’ “.~1.2.11.3-9 „‹Ÿ €•Ž†„…ˆŸ €‘ˆŒ’Ž’ˆ—…‘ŠŽƒŽ ‡€—…ˆŸ~$R(\alpha, n)$ ‘ ’Ž—Ž‘’œž „Ž~$O(n^{-2})$) ˆ~$n\to\infty$ ˆ ”ˆŠ‘ˆŽ‚€ŽŒ~$\alpha<1$. \ex[40] จ‘‘‹…„“‰’… Ž‚…„…ˆ… €‹ƒŽˆ’Œ€~C, …‘‹ˆ …ƒŽ ˆ‘Ž‘Žˆ’œ Š ‚…˜…Œ“ Žˆ‘Š“ ’€Š, Š€Š ’Ž Žˆ‘€Ž ‚ ’…Š‘’…. \ex[ขฌ43] ฎŽ™ˆ’… ŒŽ„…‹œ ่€Ÿ---แ“’€, Ž‘“†„€‚˜“ž‘Ÿ Ž‘‹… ’…Ž…Œ›~P, € ‘‹“—€‰ $M$~‹ŽŠŽ‚ €‡Œ…€~$b$. คŽŠ€†ˆ’…, —’Ž~$C(z)=Q(z)/(B(z)-z^b)$, ƒ„… $Q(z)$---ŒŽƒŽ—‹… ‘’……ˆ~$b$ ˆ~$Q(1)=0$. ฏŽŠ€†ˆ’…, —’Ž ‘…„…… —ˆ‘‹Ž Ž €‚Ž $$ 1+{M\over N}C'(1)=1+{1\over b}\left({1\over 1-q_1}+\cdots++{1\over 1-q_{b-1}}-{1\over2}{B''(1)-b(b-1)\over B'(1)-b}\right), $$ ƒ„…~$q_1$~\dots$q_{b-1}$ ‘“’œ ŠŽˆ ŒŽƒŽ—‹…€~$Q(z)/(z-1)$. ง€Œ…ˆ‚ ˆŽŒˆ€‹œŽ… €‘…„…‹…ˆ… ‚…ŽŸ’Ž‘’…‰~$B(z)$ ˆ‹ˆ†…ˆ…Œ ฏ“€‘‘Ž€~$P(z)=e^{b\alpha(z-1)}$, ƒ„… $\alpha=N/Mb$, ˆ ˆ‘Ž‹œ‡Ž‚€‚ ‹€ƒ€†…‚“ ”ŽŒ“‹“ Ž€™…ˆŸ (‘. ‘ ”ŽŒ“‹Ž‰~(2.3.4.4-9) ˆ “.~4.7-8), ˆ‚…„ˆ’… Ž’‚…’ Š ‚ˆ„“~(61). \ex[M48] ฎŽ™ˆ’… ’…Ž…Œ“~K, Ž‹“—ˆ‚ ’Ž—›‰ €€‹ˆ‡ ‹ˆ…‰ŽƒŽ ŽŽŽ‚€ˆŸ ˆ ˆ‘Ž‹œ‡Ž‚€ˆˆ ‹ŽŠŽ‚ €‡Œ…€~$b$. %%650 \ex[ฌ47] ค€…’ ‹ˆ ˆˆ‘›‚€ˆ… Ž‘‹…„Ž‚€’…‹œŽ‘’ŸŒ Ž Ž„ˆ€ŠŽ‚›• ‚…ŽŸ’Ž‘’…‰ ŒˆˆŒ€‹œŽ… ‡€—…ˆ…~$C_N$ ‘…„ˆ ‚‘…• Œ…’Ž„Ž‚ Ž’Š›’Ž‰ €„…‘€–ˆˆ? \ex[M21] (แ.~ค†Ž‘Ž.) ญ€‰„ˆ’… „…‘Ÿ’œ ……‘’€Ž‚ŽŠ ŒŽ†…‘’‚€~$\set{0, 1, 2, 3, 4}$, Š‚ˆ‚€‹…’›• €‚ŽŒ…ŽŒ“ •…˜ˆŽ‚€ˆž ‚ ‘Œ›‘‹… ’…Ž…Œ›~U. \ex[ฌ25] คŽŠ€†ˆ’…, —’Ž …‘‹ˆ ˆˆ‘›‚€ˆ… ‚…ŽŸ’Ž‘’…‰ ……‘’€Ž‚Š€Œ Š‚ˆ‚€‹…’Ž €‚ŽŒ…ŽŒ“ •…˜ˆŽ‚€ˆž (‚ ‘Œ›‘‹… ’…Ž…Œ›~U), ’Ž —ˆ‘‹Ž ……‘’€Ž‚ŽŠ ‘ …“‹…‚›Œˆ ‚…ŽŸ’Ž‘’ŸŒˆ …‚‡Ž‰„…’~$M^a$ ˆ ‹žŽŒ ”ˆŠ‘ˆŽ‚€ŽŒ ŽŠ€‡€’…‹…~$a$, …‘‹ˆ $M$~„Ž‘’€’Ž—Ž ‚…‹ˆŠŽ. \ex[M48] ก“„…Œ ƒŽ‚Žˆ’œ, —’Ž ‘•…Œ€ Ž’Š›’Ž‰ €„…‘€–ˆˆ ‚Š‹ž—€…’ \emph{…„ˆ‘’‚…Ž… •…˜ˆŽ‚€ˆ…,} …‘‹ˆ ˆ‘Ž‹œ‡“…’‘Ÿ Ž‚Ž $M$~Ž‘‹…„Ž‚€’…‹œŽ‘’…‰ Ž, €—ˆ€ž™ˆ•‘Ÿ ‘Ž ‚‘…• ‚Ž‡ŒŽ†›• ‡€—…ˆ‰~$h(K)$ ˆ ‚‘’…—€ž™ˆ•‘Ÿ ‘ ‚…ŽŸ’Ž‘’œž~$1/M$. ็’Ž €‘ˆŒ’Ž’ˆ—…‘Šˆ ‹“—˜… (‚ ‘Œ›‘‹… ŒˆˆŒ€‹œŽ‘’ˆ~$C_N$): €ˆ‹“—˜€Ÿ ‘•…Œ€ ‘ …„ˆ‘’‚…›Œ •…˜ˆŽ‚€ˆ…Œ ˆ‹ˆ ‘‹“—€‰›… ‘•…Œ›, €€‹ˆ‡ˆŽ‚€‚˜ˆ…‘Ÿ ‚ “.~44? \ex[ฌ46] ๏‚‹Ÿ…’‘Ÿ ‹ˆ Œ…’Ž„, €€‹ˆ‡ˆŽ‚€‚˜ˆ‰‘Ÿ ‚ “.~46, €ˆ•“„˜…‰ ‚Ž‡ŒŽ†Ž‰ ‘•…ŒŽ‰ ‘ …„ˆ‘’‚…›Œ •…˜ˆŽ‚€ˆ…Œ? (แ.~‘~“.~60.) \ex[ฌ49] ญ€‘ŠŽ‹œŠŽ •ŽŽ˜€ ŒŽ†…’ ›’œ ‘•…Œ€ ‘ …„ˆ‘’‚…›Œ •…˜ˆŽ‚€ˆ…Œ, …‘‹ˆ ˜€ƒˆ~$p_1$ $p_2$~\dots $p_{M-1}$ (ŽŽ‡€—…ˆŸ “.~44) ”ˆŠ‘ˆŽ‚€› ˆ … ‡€‚ˆ‘Ÿ’ Ž’~$K$? (ฏˆŒ…€Œˆ ’€Šˆ• Œ…’Ž„Ž‚ ‘‹“†€’ ‹ˆ…‰Ž… ŽŽŽ‚€ˆ… ˆ Ž‘‹…„Ž‚€’…‹œŽ‘’ˆ, €‘‘Œ€’ˆ‚€‚˜ˆ…‘Ÿ ‚ “.~20 ˆ~47.) \ex[ฌ25] ฅ‘‹ˆ ‚ €‘‘…ŸŽ‰ ’€‹ˆ–… Žˆ‡‚Ž„Ÿ’‘Ÿ ‘‹“—€‰›… ‚‘’€‚Šˆ ˆ “„€‹…ˆŸ, ’Ž ‘ŠŽ‹œŠŽ “†Ž ‚ ‘…„…Œ …‡€‚ˆ‘ˆŒ›• ‚‘’€‚ŽŠ, —’Ž› ‚‘… $M$~Ž‡ˆ–ˆ‰ Ž›‚€‹ˆ ‚ ‡€Ÿ’ŽŒ ‘Ž‘’ŽŸˆˆ? \ex[M46] ฏŽ€€‹ˆ‡ˆ“‰’… Ž†ˆ„€…ŒŽ… Ž‚…„…ˆ… €‹ƒŽˆ’Œ€~R. แŠŽ‹œŠŽ €‡ ‚ ‘…„…Œ “„…’ ‚›Ž‹Ÿ’œ‘Ÿ ˜€ƒ~R4? \rex[20] \exhead(ช‹ž—ˆ ……Œ…Ž‰ „‹ˆ›.) ขŽ ŒŽƒˆ• ˆ‹Ž†…ˆŸ• €‘‘…Ÿ›• ’€‹ˆ– Š‹ž—ˆ ŒŽƒ“’ ‘Ž‘’ŽŸ’œ ˆ‡ Žˆ‡‚Ž‹œŽƒŽ —ˆ‘‹€ ‹ˆ’…. ข ’€ŠŽŒ ‘‹“—€… …‹œ‡Ÿ Ž‘’Ž ‡€ŽŒˆ’œ Š‹ž— ‚ ’€‹ˆ–…, Š€Š ’Ž „…‹€‹Ž‘œ ‚ Žƒ€ŒŒ€• „€ŽƒŽ €€ƒ€”€. ฏˆ„“Œ€‰’… •ŽŽ˜ˆ‰ ‘Ž‘Ž ˆ‘Ž‹œ‡Ž‚€ˆŸ €‘‘…Ÿ›• ’€‹ˆ– „‹Ÿ •€…ˆŸ Š‹ž—…‰ ……Œ…Ž‰ „‹ˆ›, …‘‹ˆ €Ž’€ ‚…„…’‘Ÿ € Œ€˜ˆ…~\MIX. %% 651 \bye