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

自然数(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通りの表し方のことです。

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

●質問者: kokudou
●カテゴリ:学習・教育 科学・統計資料
✍キーワード:コメント欄 数字 整数 自然数
○ 状態 :終了
└ 回答数 : 3/3件

▽最新の回答へ

1 ● ita
●27ポイント

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

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

◎質問者からの返答

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

『 分割した時の数字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)の結果を代入した式を解く必要がありますが、ここから先がわかりません。


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


2 ● Z9M9Z
●27ポイント

(案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が十分大きいとき」の式はもしかしたら書けるかもしれませんが、そうでないと、最大値を求めるだけでも難問な気がします‥。

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

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

◎質問者からの返答

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


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


実際に具体的な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


3 ● ita
●26ポイント

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, ...

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

◎質問者からの返答

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


確かに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の近似値ではない正確な値を知りたいので引き続き回答を募集します。

関連質問


●質問をもっと探す●



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