2
$\begingroup$

I know that the formula $C(n-1,r-1)$ is used when we need to distribute n identical objects in $r$ distinct groups(such that every group receives atleast 1 object).

Suppose 10 objects need to be divided into 3 groups such that each group receives atleast one object. By using the above formula , we also consider the case such as $(1,2,7)$ $(1,7,2)$ $(2,1,7)$ $(2,7,1)$ $(7,1,2)$ $(7,2,1)$ ways.

But in this case we need to consider only one out of these possibilities.

One might think of using $C(n-1,r-1)$ and then dividing the result by $r!$. That way you should get the answer as $C(9,2)\div3! = 6$. But by writing out all the possibilities, you get 8 different ways!

So is there any formula/algorithm to solve this?.

P.S: I have tried the following (for the above question)

  1. Consider first digit to be 1 . Therefore The division is of the form $(1,x_1,x_2)$. Now we apply the above formula for solutions of $x_1$ and $x_2$ and divide it by $2!$

  2. Consider first digit to be 2. Therefore the division is of the form $2,y_1,y_2$ such that $y_1>2$ and $y_2>2$ (Since the cases where $y_1$ and $y_2$ is less than or equal to 2 are already considered in step 1). We do some simple shifting of values and find the ways in which this can be done

  3. Similarly we consider first digit to 3 and continue in the above manner and calculate the number of ways.

  4. In the end add out the possibilities of all the cases

While this algorithm works for division into 3 groups , but it will become very long if the division is extended more.

So is there any generalised formula for doing this?

$\endgroup$
3
  • 1
    $\begingroup$ Hint: use stars and bars. For example $(1,2,7)$ would be represented by $$\star\mid\star\,\star\mid\star\,\star\,\star\,\star\,\star\,\star\,\star$$ $\endgroup$
    – user519413
    Jul 28, 2020 at 4:42
  • $\begingroup$ @M.Nestor . I checked it. I works great and also simple . Thanks! $\endgroup$
    – Jdeep
    Jul 28, 2020 at 5:09
  • 1
    $\begingroup$ Please do not delete posts once they are answered. $\endgroup$
    – quid
    Jul 28, 2020 at 22:38

1 Answer 1

1
$\begingroup$

You can use this method. Your question is

How to distribute n identical things into r identical groups?

Suppose you have a 10 identical objects and 3 identical groups. If you were given that the sizes of the group are in the order $g_{1}\geq g_{2}\geq g_{3}$ , you would have only considered $(7,2,1)$. Applying this for a general case.

Algorithm: To distribute n identical objects into r(here, r=3) similar groups of differing(some maybe equal) sizes:

Let the group sizes be denoted by $x_{1},x_{2},x_{3}$ then $x_{1}+x_{2}+x_{3}=n$

Also, since $x_{1}\geq x_{2} \geq x_{3}$, let $$x_{1}=x_{3}+a+b$$ $$x_{2}=x_{3}+a$$ $$x_{3}=x_{3}$$

Adding $x_{1},x_{2},x_{3}$,

$3(x_{3}+1)+2a+b=n$ (where a,b,$x_3$ are whole numbers)

or, $3x_{3}+2a+b=n-3$

Finding the number of distinct tuples for (a,b,$x_3$) will give you the answer.

The tuples set for $n=10$ is $\{(2,0,1),(1,0,4),(1,1,2),(1,2,0),(0,0,7),(0,1,5),(0,2,3),(0,3,1)\}$

Algorithm: To distribute n identical objects into r similar groups of differing(some maybe equal) sizes:

Let the group sizes be denoted by $x_{1},x_{2},x_{3}...x_r$ then $x_{1}+x_{2}+x_{3}...x_{r}=n$

Also, since $x_{1}\geq x_{2} \geq x_{3}...\geq x_{r}$, let $$x_{r}=x_{r}$$ $$x_{r-1}=x_{r}+c_1$$ $$...$$ $$x_{1}=x_{r}+c_1+c_2+...c_r$$

Adding $x_{1},x_{2},x_{3},...x{r}$,

$r(x_{r}+1)...+2c_2+c_1=n$ (where $c_1,c_2,...,x_r$ are whole numbers)

or, $$rx_{r}...+2c_2+c_1=n-r$$ (where $c_1,c_2,...,x_r$ are whole numbers)

Finding the number of distinct tuples for ($c_1,c_2,...,x_r$) will give you the answer. This can be done using multinomial-theorem or a computer program if the number n and groups are large.

A follow up for the answer has been asked and can be linked here: How to use Bars and Stars method for equations with more than 1 non unity coefficients?

$\endgroup$
10
  • $\begingroup$ One of them may have an equality. Eg (3,3,4) $\endgroup$
    – Jdeep
    Jul 28, 2020 at 5:00
  • $\begingroup$ @NoahJ.Standerson Yes, it seems to miss, I have edited it check this out $\endgroup$ Jul 28, 2020 at 5:09
  • $\begingroup$ Have added tuple set as well $\endgroup$ Jul 28, 2020 at 5:17
  • $\begingroup$ Added general form $\endgroup$ Jul 28, 2020 at 5:51
  • $\begingroup$ What formula did you use for finding the distinct tuples of (a,b,x3)? $\endgroup$
    – Jdeep
    Jul 28, 2020 at 5:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .