shiqi

shiqi

Study GIS, apply to world
twitter
github
bento
jike
HomeArchivesPortfolios强化学习专栏

Combinations and Permutations

#Math95
AI Translation
This post is translated from Chinese into English through AI.View Original
AI-generated summary
The "n choose m" problem involves placing n balls into m distinguishable boxes, with 8 possible scenarios depending on whether empty boxes are allowed. The formula for combinations is given as C(n, m) = A(n, m) / m! = n! / (m!(n-m)!). In the scenario where balls are identical, boxes are distinguishable, and empty boxes are not allowed, the formula is C(n-1, m-1) or C(n-1, m-1) when n >= m. The solution involves initially placing 1 ball in each box and then distributing the remaining n-m balls accordingly.

Combination "n balls into m boxes" problem.

Balls and boxes have two attributes: indistinguishable and distinguishable. The problem can also be divided into whether there can be empty boxes, so there are a total of 8 cases.

Note: In the text, C(n, m) can be read as "n choose m", which means selecting m out of n. n is on top and m is on the bottom.

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

equals (note that the positions of m and n are different)

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

Scenarios#

Same balls, different boxes, no empty boxes#

(n−1m−1)\binom{n-1}{m-1}

or

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

or

Cn−1m−1,n>=mC_{n-1}^{m-1}, n>=m
0,n<m0, n<m

Using the stars and bars method: there are n-1 gaps among n balls, and now we need to divide them into m boxes without any empty boxes, so we just need to choose m-1 gaps from the n-1 gaps.

Same balls, different boxes, allow empty boxes#

(n+m−1m−1)\binom{n+m-1}{m-1}

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

Continuing the discussion in the first scenario, we can assume that each of the m boxes already has 1 ball, so in other words, we now have m+n identical balls to be placed in m different boxes without any empty boxes. This is the first scenario.

Different balls, same boxes, no empty boxes#

The second kind of Stirling number 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

This scenario is the second kind of Stirling number. Let's understand the recurrence relation.

For the nth ball, if the previous n-1 balls have already been placed in m boxes, then the nth ball can be placed in any of the boxes, so m*dp[n-1][m];

If the previous n-1 balls have already been placed in m-1 boxes, then the nth ball must be placed in a new box, so dp[n-1][m-1].

Other cases cannot be transferred.

Different balls, same boxes, allow empty boxes#

sigma dp[n][i],0<=i<=m,dp[n][m] is the second kind of Stirling number in scenario 3

In this scenario, under the premise of scenario 3, we enumerate the number of boxes used.

Different balls, different boxes, no empty boxes#

dp[n][m]*fact[m],dp[n][m] is the second kind of Stirling number in scenario 3, fact[m] is the factorial of m

Because the balls are different, the situation where dp[n][m] gives the same boxes can be considered as the answer by defining the order of the boxes.

Different balls, different boxes, allow empty boxes#

power(m,n) represents m to the power of n

Each ball has m choices, so it is equal to m^n.

Same balls, same boxes, allow empty boxes#

dp[n][m]=dp[n][m-1]+dp[n-m][m], n>=m
dp[n][m]=dp[n][m-1], n<m
Boundary: dp[k][1]=1,dp[1][k]=1,dp[0][k]=1

Now there are n balls and m boxes. I can choose to put 1 ball in each box or not choose this operation.

If I choose this operation, then I can transfer from dp[n-m][m].

If I don't choose this operation, then I can transfer from dp[n][m-1].

Same balls, same boxes, no empty boxes#

dp[n-m][m], same as the 7th scenario, n>=m
0, n<m

Because there are no empty boxes required, we first put 1 ball in each box, and then there are n-m balls left. The answer can be obtained based on scenario 7.

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

References#

Loading...
Ownership of this post data is guaranteed by blockchain and smart contracts to the creator alone.