整数値多項式

まだまだ,こんなのが好きですフヒ.高校生に数学教えてるからなー

n個の中からk個のものを取り出す手順は{}_nC_k=\frac{n(n-1)\cdots(n-k+1)}{k!}

を学ぶと,右辺の多項式がどんな整数nでも割り切れ,整数値を返すという性質に違和感を感じる時期がある.

じゃあ,逆に「いつも整数値を返す多項式の必要十分条件」って?,という疑問が沸く.

実はこれはGeorge Polyaが解決しているらしい.

すべての整数nに対して,多項式P(n)が整数値をとるための必要十分条件は,

整数A_0,A_1,A_2,\cdots,A_kを用いて

P(n)=A_0+A_1\ {}_nC_1+A_2\ {}_nC_2+\cdots+A_k\ {}_nC_kとかける

ふつう,P(n)はnのべき乗の多項式で書かれてるので,

基底変換[ 1 ,n ,n^2 ,n^3 ,\cdots ,n^k ] \Leftrightarrow [ 1 ,{}_nC_1 ,{}_nC_2 , {}_nC_3 ,\cdots , {}_nC_k ]をしよう.

すると,

n^3 = 0 + 1{}_nC_1+ 6{}_nC_2+ 6{}_nC_3となるが,その各係数は

0
1-0=1
1 7-1=6
8-1=7 12-6=6
8 19-7=12
27-8=19
27

はじめに縦に,3つの3乗数を書き,その右に下から上を引いた数を書いて三角形ができたときの,

一番右上の辺が,基底変換の係数になっているんだって.

すべての整数nについて,n^3-nが6で割り切れることを証明せよ.

これは標準的な高校の教科書レベルですが,普通の解き方はこう.

n^3-n = (n+1)n(n-1)より,連続する3整数には必ず偶数と3の倍数が含まれるので,これらの積には6が必ず含まれる.

これを,Polyaの定理と基底変換による解法をすると

n^3-n = ({}_nC_1+ 6{}_nC_2+ 6{}_nC_3) - ({}_nC_1) = 6({}_nC_2+ {}_nC_3)となる.

かなり応用力のある定理と解法である.いくつかの計算結果を残す.

n^4 = {}_nC_1+14{}_nC_2+36{}_nC_3+24{}_nC_4

n^5 = {}_nC_1+30{}_nC_2+150{}_nC_3+240{}_nC_4+120{}_nC_5

n^6 = {}_nC_1+62{}_nC_2+540{}_nC_3+1560{}_nC_4+1800{}_nC_5+720{}_nC_6

広告

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中