組み合わせと順列

排列組み合わせ "n 個のボールを m 個の箱に入れる" 問題。

ボールと箱は区別できず、区別できる 2 つの属性があります。問題は空の箱を持つことができるかどうかに分けられるため、合計 8 つの場合があります。

注意：文中の C (n,m) は n choose m と読みます。つまり、n 個から m 個を選ぶことを表します。n は上に、m は下になります。

\binom{n}{m}= \frac{A_{n}^{m}}{m!}=\frac{n!}{m!(n-m)!}

となります（m と n の位置が異なることに注意してください）。

C_{n}^{m}= \frac{A_{n}^{m}}{m!}= \frac{n!}{m!(n-m)!}

シナリオ#

\binom{n-1}{m-1}

または

C(n-1,m-1), n>=m

または

C_{n-1}^{m-1}, n>=m

0, n<m

仕切り法を使用します：n 個のボールの間には n-1 個のスペースがあり、それを m 個の箱に分ける必要がありますが、空の箱は許されません。したがって、n-1 個のスペースから m-1 個のスペースを選ぶだけです。

\binom{n+m-1}{m-1}

C(n+m-1,m-1)

1 番目の場合で続けて考えます。m 個の箱に 1 つのボールを入れると仮定します。つまり、同じボールが m+n 個あり、それを m 個の異なる箱に入れる必要がありますが、空の箱はありません。これが 1 番目の場合です。

第 2 種スターリング数 dp [n][m]
dp[n][m]=m*dp[n-1][m]+dp[n-1][m-1],1<=m<n
dp[k][k]=1,k>=0
dp[k][0]=0,k>=1
0,n<m

この場合は第 2 種スターリング数です。この転送方程式を理解しましょう。

n 番目のボールについて、前の n-1 個のボールがすでに m 個の箱に入っている場合、n 番目のボールをどの箱に入れても構いませんので、m*dp [n-1][m] です。

前の n-1 個のボールが m-1 個の箱に入っている場合、n 番目のボールを新しい箱に入れる必要があるため、dp [n-1][m-1] です。

他の場合は転送できません。

sigma dp [n][i],0<=i<=m,dp [n][m] は場合 3 の第 2 種スターリング数です。

この場合は、場合 3 の前提のもとで、使用する箱の数を列挙します。

dp [n][m]*fact [m],dp [n][m] は場合 3 の第 2 種スターリング数で、fact [m] は m の階乗です。

ボールが異なるため、dp [n][m] で得られる箱が同じ場合、箱に順序を定義するだけで、答えが得られます。

power (m,n) は m の n 乗を表します。

各ボールには m 種類の選択肢がありますので、m^n となります。

dp[n][m]=dp[n][m-1]+dp[n-m][m], n>=m
dp[n][m]=dp[n][m-1], n<m
境界 dp [k][1]=1,dp [1][k]=1,dp [0][k]=1

n 個のボールと m 個の箱があります。すべての箱に 1 つのボールを入れることを選択するかどうか選択できます。

この操作を選択した場合、dp [n-m][m] から転送されます。

この操作を選択しなかった場合、dp [n][m-1] から転送されます。

dp [n-m][m]、dp は 7 番目の場合と同じで、n>=m
0, n<m

空の箱を要求するため、まず各箱に 1 つのボールを入れ、残りは n-m 個のボールがあり、場合 7 に従って答えが得られます。

————————————————