[Math] Given $n$ identical things need to distribute among $r$ objects such that each object can have at least 1 thing

combinatorics

$\dbinom{n+r−1}{r−1}$ is the answer for the distribution of $n$ identical objects among $r$ persons. Not for the groups, because groups are considered as identical it do not have name. Ex. two identical balls can to be distributed among two persons $[(2,0)(0,2)(1,1)]$ in three ways. But when we go for groups $(2,0)$ and $(0,2)$ considered as the same, so now the answer will be only two.

What will be the formula if we want to remove the same groups ex. in the above example if we want $(2,0)$ and $(0,2)$ to be considered same and want the answer $2$ so what will be the formula in that case?

Best Answer

There are the partitions of $n$ into $r$ or fewer parts.

There is no pleasant "closed form" formula.

Related Solutions

[Math] How to calculate the number of ways of partitioning n identical objects into r different groups such that each group has same number of objects

Try this much smaller example: partition a set of $2$ items into two sets of $1$ item each.

The number of ways to choose the contents of the first subset is $\binom{2}{1} = 2.$ But in fact there is only one way to partition the set into two subsets of one item each: each item goes in its own subset.

The difference is that if one subset has six items and the other has four, then no partition that puts the first item into the subset of six can be the same as any partition that puts that same item into the subset of four. But if the subsets are of equal size, we can put the first item into either subset and still finish with the same partition; there is nothing to distinguish the two subsets except which items are in them.

Combinatorics – Proof of Stars and Bars Formula

The fault lies in our inability to "choose" a bar twice (which we would need to do for empty inner bins).

Consider ten stars and four bars (corresponding to five bins):

*|**|**|****|*

There are five bins. The first starts on the left and goes until the first "|". The final bin begins with the final "|", and goes right from there.

**|***|*|****|

Now the right-most bin is empty. This is all well and good, but what if we want an inner bin to be empty? We must choose the same "place" twice, which we can't do.

So instead of only counting the spaces between (and beside) the "*" characters above, we allow for fourteen characters - ten stars and four bars. We can choose adjacent characters to be bars to represent an (inner) empty bin.

**|***||****|*

$(2,3,0,4,1)$

Best Answer

Related Solutions

[Math] How to calculate the number of ways of partitioning n identical objects into r different groups such that each group has same number of objects

Combinatorics – Proof of Stars and Bars Formula

Related Question