自然数(1以上の整数)の分割について質問です。

 
 ここでの自然数の分割とは、ある自然数nを1個以上n個以下の
 自然数の和 (ただし順序を問わない)で表したときの表し方のことです。
 例えば自然数n=6の分割を考えると
 “6”, “5+1”, “4+2”, “4+1+1”, “3+3”, “3+2+1”, “3+1+1+1”,
  “2+2+2”, “2+2+1+1”, “2+1+1+1+1”, “1+1+1+1+1+1” の11通りの
 表し方があります。
 
[質問] 
自然数nの分割に対し、「 「それぞれの表し方」 を数字の並びと考えたとき、
「 「その数字の並びの並べ方の数」 が最大になる表し方 」 」を式として
導出できるでしょうか? ( [補足] 参照のこと)
導出できないとしたらその理由を説明してください。
導出できるとしたらその式を求めてください。

[補足]
n=6の場合を例にして説明します。
・「それぞれの表し方」とは、”6”, “5+1”, “4+2”, “3+3”, “3+2+1”, …, “1+1+1+1+1+1”の11通りの表し方のことです。

* * * コメント欄に続きます * * *

回答の条件
  • 1人5回まで
  • 登録:2007/08/24 01:23:29
  • 終了:2007/08/31 01:25:03

回答(3件)

id:ita No.1

ita回答回数204ベストアンサー獲得回数482007/08/24 19:51:53

ポイント27pt

とりあえず閉じてない式ですが、分解したときの数字iの個数をl_iとおき、

\sum_{i=1}^n i l_i =n かつl_i \geq 0を満たすという条件の元で \frac{(\sum_i l_i)!}{\prod_i (l_i !)}の最大値、ということですね。

id:kokudou

いえ、正確には私の質問は

『 分割した時の数字iの個数をLiとおき、∑_[i=1, n] (i * Li) = n かつ Li ≧ 0 を満たすという条件の下で

 (∑_[i] Li)! / (Π_[i] (Li!) ) 』 の最大値

を式として導出できるかではなく

『 … 』 が最大値をとるときの L1, L2, ..., Ln の各々の値

を式として導出できるかということです。


いずれにしても式で表した方がわかりやすかったと思います。

すみませんでした。


整理すると、本質問は

「制約条件 ∑_[i=1,n](i * Li) = n かつ Li ≧ 0 の下で

関数 f(L1, L2, …, Ln) = (∑_[i] Li)! / (Π_[i] (Li!) ) ・・・(式1)

が最大値をとるときの L1, L2, ..., Ln をnを用いた式で表せられるか。

表せられればその式を求めよ。表せられなければその理由を説明せよ。」

というものになるかと思います。以下に自分なりの解を載せます。


[解]

(式1)が上記の制約条件の下で最大値をとるときの L1, L2, ..., Ln を求めることを考える。


関数fを微分可能にするため、ガンマ関数Γ(x)を使って連続化する。

(8/25 11:15訂正)自然数nについて Γ(n+1) = n! が成り立つので、(式1)は 

f(L1, L2, …, Ln) = Γ(1 + L1 + L2 + … + Ln) / (Γ(1 + L1) * Γ(1 + L2) * … * Γ(1 + Ln) ) ・・・(式2)

と変形できる。


ここで、ラグランジュの未定乗数法を利用すると、L1, L2, ..., Ln の解を求めるには

L↑ = [L1, L2, …, Ln]^t (L↑はn項列ベクトル)とおき、変数λを用いて

F(L↑, λ) = f(L↑) - λ * (∑_[i=1, n](i * Li) - n)       ・・・(式3)

に関する極値条件

∂F/∂Li = ∂f/∂Li - i * λ = 0    (i = 1, 2, …, n)   ・・・(式4)

∂F/∂λ = -(∑_[i=1,n](i * Li) - n) = 0           ・・・(式5)

を連立させて解けばよい。


ここで ∂f/∂Li を計算すると

∂f/∂Li = f * { ( (∂/∂Li) Γ(1 + L1 + L2 + … + Ln) ) / Γ(1 + L1 + L2 + … + Ln) - 

        ( (d/dLi) Γ(1 + Li) ) / Γ(1 + Li) } 

      = f * { Γ'(1 + L1 + L2 + … + Ln) / Γ(1 + L1 + L2 + … + Ln) - Γ'(1 + Li) / Γ(1 + Li) } ・・・(式6)

となる。この後、∂f/∂Li = i * λ に(式6)の結果を代入した式を解く必要がありますが、ここから先がわかりません。


他の解き方でもかまわないですのでよろしくお願いします。

2007/08/25 11:15:24
id:Z9M9Z No.2

Z9M9Z回答回数343ベストアンサー獲得回数112007/08/24 23:25:33

ポイント27pt

(案1)N=2+2+1+...+1 と、(案2)N=3+2+1+...+1 を比べると、

案1= (N-2)!/2!/(N-4)! = (N-2)(N-3)/2

案2= (N-3)!/(N-5)! = (N-3)(N-4)

案2/案1= 2(N-4)/(N-2) > 1 (N > 6のとき)

(案3)N=3+2+2+1+...1 と比べると、

案3=(N-4)!/2!/(N-7)! =(N-4)(N-5)(N-6)/2

案3/案2= (N-5)(N-6)/2(N-3) > 1 (N > 9のとき)

(案4)N=3+3+2+2+1+...+1 と比べると、

案4=(N-6)!/2!/2!/(N-10)! = (N-6)(N-7)(N-8)(N-9)/4

案4/案3= (N-7)(N-8)(N-9)/2(N-4)(N-5) >1 (N>14のとき)

(案5)N=4+3+2+1+...+1 と比べると、

案5=(N-6)!/(N-9)! = (N-6)(N-7)(N-8)

案5/案3= 2(N-6)(N-7)(N-8)/(N-4)(N-5)(N-6) >1 (N>15のとき)

(案6)N=5+4+3+2+1+..+1 は、

案6=(N-10)!/(N-14)!=(N-10)(N-11)(N-12)(N-13)

....

このように、Nの大きさ次第でどっちが大きいか変わることが多いようで、「Nが十分大きいとき」の式はもしかしたら書けるかもしれませんが、そうでないと、最大値を求めるだけでも難問な気がします‥。

そのときの単なる予想としては、種類数が多いほうがよく、種類数がおなじなら各種類の出現数が均等なほうがよさそうです。

とこのあたりで、ギブアップ。

id:kokudou

回答ありがとうございます。


>そのときの単なる予想としては、種類数が多いほうがよく、種類数がおなじなら各種類の出現数が均等なほうがよさそうです。


実際に具体的なnの値について求めると、この予想は間違っているのではないかということがわかります。

n=4から20までの場合には、数字の並びの並べ方の数が最大になる表し方は以下のようになると思います。


   ・・・ 並べ方の数が最大になる表し方  ・・・ 並べ方の数

n= 4 ・・・ 211                     ・・・ 3 ( = 3! / 2! )

n= 5 ・・・ 2111                    ・・・ 4 ( = 4! / 3! )

n= 6 ・・・ 321, 2211                 ・・・ 6 ( = 3!, 4! / (2! * 2!) )

n= 7 ・・・ 3211                    ・・・ 12 ( = 4! / 2! )

n= 8 ・・・ 32111                   ・・・ 20 ( = 5! / 3! )

n= 9 ・・・ 32211, 321111              ・・・ 30 ( = 5! / (2! * 2!), 6! / 4! )

n=10 ・・・ 322111                  ・・・ 60 ( = 6! / (3! * 2!) )

n=11 ・・・ 3221111                 ・・・ 105 ( = 7! / (4! * 2!) )

n=12 ・・・ 32211111                 ・・・ 168 ( = 8! / (5! * 2!) )

n=13 ・・・ 32221111                 ・・・ 280 ( = 8! / (4! * 3!) )

n=14 ・・・ 322211111                ・・・ 504 ( = 9! / (5! * 3!) )

n=15 ・・・ 43221111, 3222111111        ・・・ 840 ( = 8! / (4! * 2!), 10! / (6! * 3!) )

n=16 ・・・ 432211111                ・・・ 1512

n=17 ・・・ 432221111, 4322111111, 3322211111 ・・・ 2520

n=18 ・・・ 4322211111                ・・・ 5040

n=19 ・・・ 43222111111               ・・・ 9240

n=20 ・・・ 432221111111               ・・・ 15840

2007/08/25 22:04:17
id:ita No.3

ita回答回数204ベストアンサー獲得回数482007/08/28 17:23:35

ポイント26pt

Stirling の近似を使うと Log f = S Log S -S - Σ(Li Log Li -Li)

(S=ΣLi とおきました)

f の最大化も Log f の最大化も同じ。

∂Log f/∂Li = Log S - Log Li

で∂Log f/∂Li = -i*λ

をとけばいい。

Log S - Log Li = -i*λより

Li/S = exp(-i*λ)

exp(-λ)=aとおくと

L1/S = a

L2/S = a^2

L3/S = a^3

...

Li/S は合計で1にならないといけないから、nが十分大きければ a=1/2

すなわちnが非常に大きい場合は近似的に全体の半分の個数が1, その半分が2, さらに半分が3, ...

となる時に最大となることが予想されます。

id:kokudou

回答ありがとうございます。


確かにnが非常に大きいときには、この近似が有効だと思います。


実際、式 L1 + 2*L2 + 3*L3 + ... n*Ln = n に

L2 = L1 / 2, L3 = L1 /(2^2), …, Li = L1 / (2^(i-1)) を代入して解くと

 Li = n*2^(n-i) / { 2*(2^n - 1) - n } となります。

これが、nが非常に大きいときに、fが最大値をとるときのLiの近似解だと思います。


また、nの大小に関わらず、Li = 2^( m - (i - 1))  ( m = 0, 1, 2, … . ただし Li < 1 となる i に対しては Li = 0 ) は

 n = L1 + 2*L2 + 3*L3 + ... n*Ln に対してfが最大値をとるときのLiの解ではないかと予想しています。

(証明はできていませんが。)


実際、fが最大値をとるときの解Liは

n = 1 に対しては、L1 = 1 (m = 0) であり、

n = 4 に対しては、L1 = 2, L2 = 1, L3 = L4 = 0 (m = 1) (つまり"2+1+1")であり、

n = 11 に対しては、L1 = 4, L2 = 2, L3 = 1, L4 = L5 = … = L11 = 0 (m = 2) (つまり"3+2+2+1+1+1+1")であり、

n = 26 に対しては、L1 = 8, L2 = 4, L3 = 2, L4 = 1, L5 = L6 = … = L26 = 0 (m = 3) (つまり"4+3+3+2+2+2+2+1+1+1+1+1+1+1+1")であると思います。


しかし、nやLiの値に関わらず、fが最大値をとるときのLiの近似値ではない正確な値を知りたいので引き続き回答を募集します。

2007/08/31 00:50:08
  • id:kokudou
    [補足]の続き

    ・「その数字の並びの並べ方の数」とは、”6”については1通り、”5+1”については5+1, 1+5の2通り、”4+2”については4+2, 2+4の2通り、”3+3”については1通り、 “3+2+1”については3+2+1, 3+1+2, 2+3+1, 2+1+3, 1+3+2, 1+2+3の6通り、…、”1+1+1+1+1+1”については1通りとなります。

    ・「 「その数字の並びの並べ方の数」 が最大になる表し方 」とは、並べ方が6通りある”3+2+1”と”2+2+1+1”の2つの表し方になります。

    ・質問中の 式として導出 というのは、nが一般的な自然数である場合に、n=6における”3+2+1”と”2+2+1+1”のような「 「その数字の並びの順列の数」 が最大になる表し方 」を式で求めることを言います。
  • id:ita
    Stirling の近似を使ってみては?
    http://mathworld.wolfram.com/StirlingsApproximation.html

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

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

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

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