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


※以前、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"が最大になる並べ方である。

回答の条件
  • 1人5回まで
  • 13歳以上
  • 登録:2012/02/01 23:24:57
  • 終了:2012/02/07 21:14:32

ベストアンサー

id:Hyperion64 No.1

Hyperion64回答回数791ベストアンサー獲得回数842012/02/02 12:08:08

ポイント50pt

 結論からいうと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となるような分割表現は今のところなさげである。もしくはかなり難しいという結論を出しました。

id: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)

2012/02/03 22:16:09

その他の回答(1件)

id:Hyperion64 No.1

Hyperion64回答回数791ベストアンサー獲得回数842012/02/02 12:08:08ここでベストアンサー

ポイント50pt

 結論からいうと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となるような分割表現は今のところなさげである。もしくはかなり難しいという結論を出しました。

id: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)

2012/02/03 22:16:09
id:ita No.2

ita回答回数203ベストアンサー獲得回数472012/02/03 23:52:13

ポイント50pt

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

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

id:kokudou

ありがとうございます。面白いグラフですね。

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

そうですか?完全には一致していませんが、他のNと比べるとかなり一致しているように見えます。

実数に拡張した計算式や整数の場合の全検索の方法(プログラミング)を知りたいのですが、よろしければ教えてもらえないでしょうか。

2012/02/04 12:32:18
  • id:ita
    kokudouさんの特殊ケースの命題、自分も同じ事を考えていました。
    N=1,4,11,26,57,120,247 の場合について実際に全検索を行い、
    すべて 大きいほうから 1,2,4,8,... が最大を与えることを確認しました。
    成り立ちそうですね。どうやって証明するのか。。。
  • id:ita
    全検索のコードです。特殊ケースの命題が成り立つと仮定して
    たとえばN=100の場合でもL7以上は0であると仮定してかなり高速化できました。
    N=200程度でも一瞬で終わります
    http://d.hatena.ne.jp/ita/00010423
    Liまで値を設定して、合計がNになるまであと残りがいくつか(=R)を与えて、
    Li+1の値を0からR/(i+1)まで回して自分自身を再帰的に呼ぶループを使っています。

    実数の場合の式は、Cに標準で入ってるtgamma(x)というのを使いました。
    xが整数のときtgamma(x+1)=xの階乗、になります。値が大きくなるのでその対数を使いました
    G(X)=log(tgamma(x+1))として、 G(L1+L2+..Lm)-G(L1)-G(L2)-...-G(Lm)を最大化します。
    初期値 L1=N, そのほかを0にして、その後は乱数を使い適当に二つLiとLjを選び、
    -0.01~0.01の小さい乱数δを出して Liをδ/i減らし Ljをδ/j増やします
    (L1+2 L2 +...は保存されます)。評価関数を計算し変化する前より減っていたらLi,Ljを
    もとに戻し、増加していたらそのまま、というのをひたすら繰り返します。またLi,Ljどちらか
    0以下になったらこの場合も元に戻します。

  • id:kokudou
    ありがとうございます。
    また返事がおそくなりすみません。

    コードを実行したら、以下のようにsegmentation faultとなりました。
    環境依存があるのでしょうか。
    また、#C の後ろの箇所には何が出力されるのが期待値であるかよくわかっていません。
    解説いただけたら助かります。

    実数の場合は、乱数を使うというのが難しいですね。

    XXX:~/PartitionNumber$ ./a.exe
    # just 1 = 1
    # just 2 = 4
    # just 3 = 11
    # just 4 = 26
    # just 5 = 57
    # just 6 = 120
    # just 7 = 247
    # just 8 = 502
    # just 9 = 1013
    # just 10 = 2036
    # just 11 = 4083
    # just 12 = 8178
    # just 13 = 16369
    # just 14 = 32752
    # just 15 = 65519
    # just 16 = 131054
    # just 17 = 262125
    # just 18 = 524268
    # just 19 = 1048555
    # just 20 = 2097130
    1 #C=1.000000
    1 1 #C=1.000000
    1 1 #C=1.000000
    10776 [main] a 4272 _cygtls::handle_exceptions: Error while dumping state (pro
    bably corrupted stack)
    Segmentation fault (core dumped)
    XXX:~/PartitionNumber$
  • id:ita
    あ、失礼しました
    164行を以下のように修正してください
    for(i=2;i<=dm;i++)nk[i]=0;
  • id:ita
    #C=
    は場合の数の最大数です。
  • id:ita
    場合の数はまともに計算するとすぐlong int の上限を超えてしまうので、対数を取って実数で比較しています。
    なので厳密にいうと微妙な誤差で誤判定している可能性もあります。
    最後に表示するときはexpに入れて戻しています。
  • id:kokudou
    ありがとうございます。動きました。

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません