組み合わせと順列

排列組み合わせ "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 に従って答えが得られます。

参考文献