すうじあむ

(0件) (2件)

コメントはまだありません。

タグをつけるにはログインが必要です。

\newcommand{\DS}{\displaystyle} \newcommand{\TS}{\textstyle} \newcommand{\QS}{\begin{quote}} \newcommand{\QE}{\end{quote}} \newcommand{\EQ}{\QS$\DS} \newcommand{\EN}{$\QE} \newcommand{\EQQ}{\QS\vspace*{0.6em} $\DS} \newcommand{\ENN}{$\vspace*{0.6em} \QE} \newcommand{\ML}{\begin{list}{\labelitemi}{\itemsep 0pt \parsep 0pt}} \newcommand{\LE}{\end{list}} \newcommand{\inv}[1]{\frac{1}{#1}} \newcommand{\nfrac}[2]{\frac{\,#1\,}{\,#2\,}} \newcommand{\ninv}[1]{\nfrac{1}{#1}} \newcommand{\hr}{\noindent\hrulefill} \newcommand{\comb}[2]{\mbox{}_{#1}{\rm C}_{#2}} \newcommand{\LR}[1]{\left( #1 \right)} \newcommand{\LRA}[1]{\left| #1 \right|} \newcommand{\LRB}[1]{\left[ #1 \right]} \newcommand{\LRC}[1]{\left\{ #1 \right\}} \newcommand{\LRF}[1]{\left\lfloor #1 \right\rfloor} \newcommand{\hsp}{\\ \hspace*{0.5cm}} \newcommand{\comment}[1]{} \newcommand{\lno}[1]{\ \ \dotfill\ (#1)} \newcommand{\mb}[1]{\mbox{\boldmath $#1$}} \newcommand{\nN}{\mb{N}} \newcommand{\nZ}{\mb{Z}} \newcommand{\nQ}{\mb{Q}} \newcommand{\nR}{\mb{R}} \newcommand{\nC}{\mb{C}} \newcommand{\hdr}[1]{\noindent\underline{\bf #1}} \newcommand{\RA}{\rightarrow} \newcommand{\UL}{\underline} \newcommand{\OL}{\overline} % tab | \newcommand{\Not}{\neg} \newcommand{\And}{\wedge} \newcommand{\Or}{\vee} \newcommand{\Imp}{\rightarrow} \newcommand{\Eqv}{\equiv} \newcommand{\EQV}{\Leftrightarrow} \newcommand{\Eq}{\exists} \newcommand{\Aq}{\forall} \newcommand{\PROB}[2]{ \hr \hsp {\bf 問題 #1}： {#2} \vspace*{-0.6em} \hr \vspace*{0.8em} } \newcommand{\PROBW}[2]{ \hr \vspace*{0.3em} \hsp {\bf 問題 #1}： {#2} \vspace*{-0.3em} \hr \vspace*{0.8em} } KNT さんの記事 \#937「代数的数が可算集合であることについての質問です。」から派生した問題です。 $f(x)$ を整数係数の多項式： \EQ f(x) = a_n x^n + a_{n-1} x^{n-1} + \cdots + a_1 x + a_0 \hspace*{1.0cm} (n\geq 0,\ \ a_0,\ a_1,\ \cdots,\ a_n \in \nZ,\ a_n \neq 0) \EN とし、その「高さ」$h = h(f)$ を以下のように定義します。 \EQ h = h(f) = n + |a_0| + |a_1| + \cdots + |a_n| \lno{1} \EN そこのコメントにも書いたことですが、高さ $h$ の多項式の総数を $P(h)$ と書きます。 ただしコメントでは定数項だけからなる多項式は除いて考えましたが、 以下ではこれも加えることにします。 各 $h (\geq 1)$ に対し、「定数多項式」（$n=0$）は $f(x) = \pm h$ の２個ずつあります。 $f(x)=0$ をどうするかは悩ましいのですが、除外して考えたほうが扱いやすくはあります（後述）。 問題は $P(h)$ の値です。 まずこれをノーヒントの問題としましょう。 \PROB{1}{高さ $h (\geq 1)$ の多項式の総数 $P(h)$ を求めよ。} このままだとかなりの難問ですが、この段階で考えたい人は次ページ以降は見ないでください。 一応実際の値を掲げておきましょう。 手計算で調べられるのは $h=5$ ぐらいが限度でしょう。 \begin{center} \begin{tabular}{|r||r|r|r|r|r|r|r|r|}\hline $h$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\\hline $P(h)$ & 1(0) & 2 & 4 & 10 & 24 & 58 & 140 & 338 \\\hline \end{tabular} \end{center} \noindent $h=0$ のとき、$P(0)=1$ は $f(x)=0$（定数 $0$ の多項式）を含めた場合、 $P(0)=0$ は含めない場合です。 記事 \#937 のコメント 3 に掲げた値より 2 ずつ増えているのは、上述のように定数多項式を加えたからです。 \\ 一応、「予備問題」として次にも触れておきましょう。 これはすでに、記事 \#937 コメント 2 で KNT さんが触れられているものです。 \\ \noindent \UL{\bf 予備問題} \begin{itemize} \item 高さ $h$、次数 $n$ で係数 $a_k$ がすべて $0$ 以上の多項式の個数は $\comb{h-1}{n}$ であることを示せ。 \item 高さ $h$ で係数 $a_k$ がすべて $0$ 以上の多項式の総数は $2^{h-1}$ であることを示せ。 \\ これについて、組合せ論的な意味づけは可能か？ \\ \end{itemize} 次ページ以降では $P(h)$ の答を示し（つまり証明問題の形に直し）、 さらにいくつかの部分問題に分けたものをヒントとして示します。 \newpage 結論から言えば、$P(h)$ は次の漸化式を満たします。 \EQ \left\{ \begin{array}{l} P(1) = 2,\ \ P(2) = 4 \\ P(h) = 2 P(h-1) + P(h-2)\hspace*{0.8cm}(h \geq 3) \end{array} \right. \lno{2} \EN $P(0)=0$ と定義すれば、１行目は「$P(0)=0,\ \ P(1) = 2$」に置き換えることができます。 \\ それはともかくとして、上を証明問題の形にすれば次の問題 2 になります。 \PROB{2}{$P(h)$ は漸化式 (2) を満たすことを示せ。} 要するに (2) について、組合せ論的な説明・意味づけができればいいわけですが、 これでもまだかなり難しいでしょう。 (2) から直接、帰納的に考えるのが自然でしょうが、 一般項も求めておきましょう。 これは通常の大学入試レベルの問題ですね。 \PROBW{3}{$\DS P(h) = \frac{(1+\sqrt{2})^h - (1-\sqrt{2})^h}{\sqrt{2}}\ \ \ (h \geq 1)$ を示せ。 \lno{3}} $2 < 1 + \sqrt{2} < 3$、また $(1-\sqrt{2})^h\RA 0\ \ (h\RA\infty)$ ですから、 \#938 のコメント 4 で述べた「$2^h$ と $3^h$ の間」はここに反映されています。 \\ この $P(h)$ はよく知られた数列らしく、$P(0)=1$ としたものは ``On-line Encyclopedia of Integer Sequences'' に \begin{quote} \verb+http://www.research.att.com/~njas/sequences/A052542+ \end{quote} として掲載されています。 $P(0)=0$ としたほうがさらよく知られていて、全体を半分にした： \EQ p_0 = 0,\ \ p_1 = 1,\ \ p_n = 2 p_{n-1} + p_{n-2} \lno{4} \EN は「ペル数 (Pell number)」と言うそうです。 $P(h) = 2 p_h$、つまり $p_h$ は $P(h)$ の半分であることに注意。 したがって多項式全体の符号を反転したものは同一と見なせば、 $p_h$ はその個数、つまり高さ $h$ で最高次係数が正であるような多項式の個数になります (この場合、$f(x)=0$ は自動的に除外されます）。 \begin{quote} \verb+http://www.research.att.com/~njas/sequences/A000129+ \\ \verb+http://ja.wikipedia.org/wiki/ペル数+ \\ \verb+http://en.wikipedia.org/wiki/Pell_number+ \\ \verb+http://mathworld.wolfram.com/PellNumber.html+ \end{quote} 上記のように、問題 2 ではまだ難しいということであれば、さらに分解して考えることになります。 それは次ページにて。 \newpage 高さ $h$ の多項式を考える際に、１ページの予備問題では次数による分類を考えましたが、 分類する上では、次数ではなく、（係数が $0$ でない項の）項数で考えるほうが扱いやすいでしょう。 項数が $k$ の多項式の場合、予備問題のように係数がすべて正の多項式 $1$ 個ごとに、 各係数について正負を組み合わせた合計 $2^k$ 個の多項式が対応することになります。 それを踏まえて結論を言えば、$P(h)$ について次の等式が成り立ちます。 \EQ P(h) = \sum_{k=1}^{k\leq \frac{h+1}{2}} \comb{h}{2k-1} \cdot 2^k \hsp\hspace*{0.3cm} = \comb{h}{1}\cdot 2 + \comb{h}{3}\cdot 2^2 + \comb{h}{5}\cdot 2^3 + \cdots + \left\{\begin{array}{l@{\hspace*{0.5cm}}l} \comb{h}{h}\cdot 2^{(h+1)/2} & (h\ は奇数) \\ \comb{h}{h-1}\cdot 2^{h/2} & (h\ は偶数) \\ \end{array} \right. \lno{5} \EN 例えば： \EQ P(4) = \comb{4}{1}\cdot 2 + \comb{4}{3} \cdot 2^2 = 24 \\ P(5) = \comb{5}{1}\cdot 2 + \comb{5}{3} \cdot 2^2 + \comb{5}{5} \cdot 2^3 = 58 \EN (5) で $k$ は項数を表しますから、 高さ $h$、項数 $k$ で、それらの係数はすべて正の多項式の個数が $\comb{h}{2k-1}$ であることを示せば (5) が証明できたことになります。 これを問題としましょう。 \PROB{4}{ 式 (5) を満たす $P(h)$ は式 (2)（及び (3)）を満たすことを示せ。 \hsp {\bf 問題 5}： 高さ $h$、項数 $k$ で係数がすべて正の多項式は $\comb{h}{2k-1}$ 個あることを示せ。 \hsp {\bf 問題 6}： それを用いて式 (5)、さらには式 (2), (3) が元の問題の解であることを示せ。 } \noindent なお (5) と予備問題とを照らし合わせると、派生的に次のお馴染みの公式が得られます。 \EQ 2^{h-1} = \sum_{k=1}^{k\leq \frac{h+1}{2}} \comb{h}{2k-1} = \comb{h}{1} + \comb{h}{3} + \cdots + \left\{\begin{array}{l@{\hspace*{0.5cm}}l} \comb{h}{h} & (h\ は奇数) \\ \comb{h}{h-1} & (h\ は偶数) \\ \end{array}\right. \\ \EN 問題 5 もまだこのままでは難しいかもしれません。 そこで次の等式を示してください。 \PROBW{7}{$n \geq k \geq 0$ のとき、次の等式を示せ。 \EQ \sum_{m=k}^{n} \comb{m}{k} \cdot\comb{n+k-m}{k} \ =\ \comb{k}{k} \cdot\comb{n}{k} + \comb{k+1}{k}\cdot\comb{n-1}{k} + \cdots + \comb{n}{k}\cdot\comb{k}{k} \hsp\hspace*{2.7cm} = \comb{n+k+1}{2k+1} \lno{6} \EN} これをうまく活用し、意味づけができれば (5) の証明に使えます。 ただし係数などは適当に付け替える必要があります （まず $k$ は $k-1$ で置き換えたほうがいいでしょう）。 私の最初の解もこの道筋に沿ったものでした。 \\ （この式 (6) は「ファンデルモンドの等式」なるものと関係があるようです。）