5

選択された「p」個の数字がソートされるように、「p」個の数字(n より小さい p)を選択する「n」個の数字があるとします。選択した番号を繰り返すことができます。選択できる組み合わせの数をどのように計算できますか? たとえば、{1,2,3,4,5,6} (n=6) という数字のセットがあり、並べ替えられたセット (p=3) から 3 つの数字を選択するとします。したがって、{1,2,3}、{1,1,2}、{2,3,6}、{4,5,5}、{5,5,5} を持つことができます.......これらの組み合わせはすべてソートされているため、有効です。取得できるそのような並べ替えられた組み合わせの数をどのように見つけることができますか?

並べ替えられたという言葉の意味は、n 個の要素のセットからp個の要素を選択する場合、選択されたp個の要素を並べ替える必要があるということです。

次の小さな例を見てください。

セットが{1,2,3,4}(つまり n = 4) で、3 つの要素 (p = 3) を選択する場合、p 個の要素を (置換で) 選択できる方法の数は になります4*4*4=64。したがって、選択には{1,1,1},{1,1,2},{1,1,3}{1,1,4},{1,2,1}.....{3,1,1}...{4,4,4}. ただし、これらの選択では、すべてがソートされるわけではありません。この例では、{1,2,1}と{3,1,1}はソートされていません。

ソートされた選択の数を取得したい。
ありがとう。

4

3 に答える 3

6

並べ替えが結果にどのように影響するかわかりません。繰り返しのある可能な組み合わせごとに、対応するソートされた順列があります。

したがって、質問は、置換によって一度にp個取られるn個の要素の組み合わせの数に要約されます。これは簡単な式です。（n-1 + p）C（p）=階乗（n-1 + p）/（階乗（p）*階乗（n-1））

ここに画像の説明を入力してください

これが式の説明であり、もう1つはwolframからのものです。

于 2012-10-26T05:57:36.773 に答える
1

k要素のセットから置換のある要素を選択できる方法の数は、要素のセットから置換のない要素をn選択できる方法の数と同じです。後者の値は二項係数で、その値はkn + k - 1n+k-1 choose k(n+k-1)!/(k! (n-1)!)

非公式のデモンストレーション:

n 個の青いボックスがあるとします。それらを一列に並べて（並べ替えられるように）、k個の赤いボールを取ります。赤いボールは列の最後以外の好きな場所に置くので、列は青いボックスで終わる必要があります。次に、赤いボールごとに、次の青いボックスを選択します。2 つ以上の赤いボールが並んでいる場合、それらは両方とも同じ青いボックスに対応します。

したがって、赤いボールと青いボックスのすべての配置は、青いボックスの置換を伴う選択に対応し、青いボックスのすべての選択は、赤いボールと青いボックスの何らかの配置に対応します。

赤いボールと青いボックスを並べる方法は何通りありますか? 私の列は青いボックスで終わらなければならないので、それを取り除き、残りの n-1 個の青いボックスと k 個の赤いボールを好きなように並べることができます。または、言い換えると、k + n-1 の位置から k を選択し、それらの位置に赤いボールを置き、残りの位置を青いボックスで埋めることができます。

于 2012-10-26T05:04:37.013 に答える