泥庭

2010年10月31日

分割数(Project Euler 76)

Filed under: Project Euler — yone64 @ 3:59 AM

Project EulerのProblem76。

5は数の和として6通りに書くことができる:

  • 4 + 1
  • 3 + 2
  • 3 + 1 + 1
  • 2 + 2 + 1
  • 2 + 1 + 1 + 1
  • 1 + 1 + 1 + 1 + 1

2つ以上の正整数の和としての100の表し方は何通りか.

えっと、分割数っていうんですね。結構有名らしいです。
最初、全く解けそうになかったので、とりあえず手で書ける範囲で書き出してみました。

image

書き出してみても、しばらくは法則が発見できなかったのですが、

  • +1を含む物は、個数合計が1ずつ少ないものと同じ数ある。【オレンジ】
  • それ以外は、すべて合計が個数分少ないものと同じ数ある。(すべてに1足した物)【青】

で、あることが判明。漸化式が導かれればこっちのものですね。
なお、この分割数は、一般項がまだ求められていないらしい。へぇ。

広告

コメントする »

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

RSS feed for comments on this post. TrackBack URI

コメントを残す

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

WordPress.com ロゴ

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

Twitter 画像

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

Facebook の写真

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

Google+ フォト

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

%s と連携中

WordPress.com Blog.

%d人のブロガーが「いいね」をつけました。