[Σ]Sukarabe's Easy Living: シグマの公式と組合せの話

« Shredder Daily Chess Puzzle for iGoogle | メイン | 迷惑メールきたる »

2007年08月21日（火曜日）

シグマの公式と組合せの話 [ 数学 ]

先日、知り合いに教わった $\sum_{k=1}^{n}k^2$ の求め方。知ってる？って聞かれて、いや、と答えたのだが、なんかDeja-vuのような気もする。最近、すぐに忘れるから(笑)。以下で組合せの記号が出てくるが、普通 ${}_n{\rm C}_r$ と書くところを、ここでは $C(n,r)$ と書く。mimeTeXでこれを書くと、ときどきうまく行かないものだから。

$n$ を自然数として、 $1\leq x<z\leq n+1$ , $1\leq y<z\leq n+1$ を満たす整数の組 $(x,y,z)$ の個数を考えるのだという。なるほど。 $z=k+1$ と固定すれば、 $x$ , $y$ はそれぞれ $1$ から $k$ の $k$ 通りずつだから、 $(x,y)$ のペアは $k^2$ 通り。それを $k=1$ , $2$ , $\cdots$ , $n$ でシグマすれば良いから、 $\sum_{k=1}^{n}k^2$ になる。

これを別の方法で数えようというのであった。 $x$ と $y$ が等しいか否かで場合分けする。 $x=y$ のときは、 $1$ から $n+1$ から異なる2個を選んで、大きい数を $z$ , 小さい数を $x$ と $y$ にすればよいので、 $C(n+1,2)$ 通り。 $x\neq y$ のときは、 $1$ から $n+1$ から異なる3個を選ぶことになる。最大のものを $z$ とし、残りを $x$ と $y$ に割り振る。どちらを $x$ にするかで2倍だけあるから、 $C(n+1,3)$ の2倍。以上を合わせれば、上の $\sum_{k=1}^{n}k^2$ に一致するはずだから、
$\sum_{k=1}^{n}k^2=C(n+1,2)+C(n+1,3)\times2=\frac{n(n+1)}{2}+\frac{n(n+1)(n-1)}{6}\times2$
となる。

ふーん、いろんな事を考えるものだ。それにしても、やっぱり、何処かで読んだことあるかも・・・。

投稿者 sukarabe : 2007年08月21日 14:23

トラックバック

このエントリーのトラックバックURL:
http://njet.oops.jp/cgi/mt/mt-tb-alt.cgi/1597

にゃ～るほど～～面白いですねぇ。
僕は初耳でした。
暇つぶしにk^3の和の公式も計算してみちゃいました。
っていうか，暇人？＞自分（苦笑）

投稿者オオハシ : 2007年08月21日 20:19

オオハシさん、こんにちは。
なるほど、同じ方針で3乗の和も計算できそうですね。(x,y,z,w)でwだけが他より大きいという組の個数ですからね。でも、x,y,zの値で異なるものが何個かで分類することになるから、少し手間がかかりますね。お疲れ様！(^_^)

この話、最初は面白いと思ったのですが、よくよく考えると、良く知られている次のヴァリエーションにすぎないようにも思います。
C(n+1,3)を3つのうちで最大になるものの値ごとに分けてシグマして、
Σ C(k,2)=C(n+1,3)
とするやつです。まあ、累乗和を直接組合せの問題に結びつけるところがミソなんでしょうね。

投稿者 sukarabe : 2007年08月22日 06:58

ははぁ。勉強になります。

ΣC(k,2)=C(n+1,3)

ΣC(k,1)=C(n+1,2)

を使えば，

Σk^2=Σk(k-1)+Σk=2ΣC(k,2)+ΣC(k,1)

とやって理屈を考えないで導けちゃうってことかぁ。

というか，裏技的な感じで扱われることが多い，

Σk(k+1)=n(n+1)(n+2)/3

Σk(k+1)(k+2)=n(n+1)(n+2)(n+3)/4

などの公式なんかがむしろサクッとでてきちゃいますねぇ。

いやぁ，知識が浅いのがsukarabeさんにバレてしまいお恥ずか
しいですが，いろいろ分かってすごくためになりました。

投稿者オオハシ : 2007年08月23日 00:29

いやいや、知っている内容でも、ちょっと見方を変えると「へえ～」ということもありますし、日々新たな発見ですよ(^_^)。

投稿者 sukarabe : 2007年08月23日 10:39

コメントしてください

comment spam対策のため，名前とメールの入力が必須になっていますが，メールアドレスは公開されません。Web SiteのURLは任意です。Type Key IDをお持ちの方はType Keyをサイン・インしてくださってもいいです。