人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

自然数の分割についての疑問

※以前、http://q.hatena.ne.jp/1187886206 で質問しましたが、回答が得られなかったため再度質問します。一度ご覧ください。

自然数nの分割(※1)の並べ方のパターン(※2)が最大になる並べ方(※3)を式として導出してください。
導出できないとしたらその理由を教えてください。
なおこの問題は何かに掲載されていたわけではなく、自分で勝手に考えた問題です。

整理すると、この問題は、
「自然数nの分割後の各数字iの個数をLiとしたとき、
制約条件 ?_[i=1,n](i * Li) = n, かつ Li ≧ 0 の下で、
f(L1, L2, …, Ln) = (?_[i] Li)! / (Π_[i] (Li!) ) ・・・(式1)
が最大値をとるときの各Liをnを用いて表せられるか」
という問題になると考えています。

【補足】
※1 自然数nの分割:
例 n=4の場合、"4", "3+1", "2+2", "2+1+1", "1+1+1+1"の5通り
※2 自然数nの分割の並べ方のパターン:
例 n=4の場合、"4"、"2+2"、"1+1+1+1"はそれぞれ1通り、
"3+1"は"1+3"とあわせて2通り、"2+1+1"は"1+2+1"と"1+1+2"とあわせて3通り。
※3 自然数nの分割の並べ方のパターンが最大になる並べ方:
例 n=4の場合、※2から、"2+1+1"が最大になる並べ方である。

●質問者: kokudou
●カテゴリ:学習・教育 科学・統計資料
○ 状態 :終了
└ 回答数 : 2/2件

▽最新の回答へ

1 ● Hyperion64
●50ポイント ベストアンサー

結論からいうとnの関数では表現できないと思われます。
その証明はないですが、証拠らしいものを見つけましたので報告します。ここでの議論は証明ではなく、推論だということをお断りしておきます。

まず、自前でその組み合わせ数を計算してみたのですが、最初の項目はこうなります。

1, 1, 2, 3, 4, 6, 12, 20, 30, 60, 105, 168, 280, 504, 840, 1512, 2520, 5040, 9240, 15840

ここで例えば、n=9の時には {3,2,1,1,1,1}と {3,2,2,1,1}がともにmax=30となるのが分かりました。つまりMAXな分割には複数解があるのでその一義的な表現は困難になると感じました。

さらに、この数列がnで表現できないとMAXな分割の表現もできないと思われます。その証拠を以下に示しておきます。

数学的に定義できている数列はオンライン数列百科https://oeis.org/で調べられます。
これがサーチした下記結果です。
https://oeis.org/search?q=1%2C+1%2C+2%2C+3%2C+4%2C+6%2C+12%2C+20%2C+30%2C+60%2C+105%2C+168%2C+280&language=english&go=Search

上のリンクがダメであれば、「1, 1, 2, 3, 4, 6, 12, 20, 30, 60, 105, 168, 280」を直接、入力してみてください。

A102462 というIDの数列のexplicitな表現はないと読み取れるのですが。
専門家たちの研究結果がこのサイトには集結しているはずです。
よって、nを与えてMAXなA102462となるような分割表現は今のところなさげである。もしくはかなり難しいという結論を出しました。


kokudouさんのコメント
回答ありがとうございます。 推論ではありますが、このアプローチは新鮮でした。 オンライン数列百科はこういうふうに使えるのですね。 本質問における、特定条件のケースになりますが、 以前のhttp://q.hatena.ne.jp/1187886206に記載した 以下の命題1は成り立つ感じがしています(itaさんの近似から発想)。 これが成り立つことは証明できるでしょうか? またこのような、特定条件で※3が求められるパターンは他にあるかわかりますか? --- 命題1 自然数nが、n=2^(m+1)-m-2 (m = 1, 2, 3,,,) を満たすとき、 ?_[i=1,n](i * Li) = n かつ Li ≧ 0 を満たす各Liの中で、 式1が最大値を取る時の各Liは Li = 2^(m - i) (i <= m) = 0 (i > m) である。 --- 具体例 m=1 -> n=1, L1=1 (このとき、※3の並べ方は、1) m=2 -> n=4, L1=2, L2=1 (このとき、※3の並べ方は、2,1,1) m=3 -> n=11, L1=2^2, L2=2, L3=1 (このとき、※3の並べ方は、3,2,2,1,1,1,1) m=4 -> n=26, L1=2^3, L2=2^2, L3=2, L4=1 (このとき、※3の並べ方は、4,3,3,2,2,2,2,1,1,1,1,1,1,1,1) m=5 -> n=57, L1=2^4, L2=2^3, L3=2^2, L4=2, L5=1 (このとき、※3の並べ方は、5,4,4,3,3,3,3,2,2,2,2,2,2,2,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1)

2 ● ita
●50ポイント

階乗はΓ関数を使って実数に一般化できるので、Nが実数の場合にLiも実数にして数値的に最大化してみました。横軸がN,線がL1,L2,・・・の値です。具体的な式は不明です。
f:id:ita:20120203233754p:image
だいたい上から半分、半分、、になっていますね。
また点は整数に限った場合の全検索による結果です。

でもN=57などの特殊な場合については、実数の場合のLiは整数からはずれていました。


kokudouさんのコメント
ありがとうございます。面白いグラフですね。 > N=57などの特殊な場合については、実数の場合のLiは整数からはずれていました そうですか?完全には一致していませんが、他のNと比べるとかなり一致しているように見えます。 実数に拡張した計算式や整数の場合の全検索の方法(プログラミング)を知りたいのですが、よろしければ教えてもらえないでしょうか。
関連質問

●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ