1
$\begingroup$

Let's say that you have an amount of 100 euros and you want to distribute all of it between 3 persons without taking into consideration the decimal fractions of the euro.

If we started with some simple scenarios, then we could say:

If instead of 3 we had just one person and since we have to distribute all of the amount then we would have just a single case.

If we had 2 persons then, I guess, that we would have 100 different combinations, of distribution among the persons.

For let's say 3 persons, I have tried to solve it with Binomial coefficient, since we are talking only about integers, like this:

C(n,r) = C(100,3) = (100!)/(3!(100−3)!) = 161.700  

But the result seems pretty high and I guess that this is probably because this formula takes into consideration that every n is different, or something like that.

However, in a problem where n is currency unit and there is also the rule of distributing all of the amount, which means that we want to exclude the combinations like
1€-1€-1€,
1€-1€-2€,
... then to be honest, I do not know how to approach this problem to create a formula, so any ideas would be much appreciated.

$\endgroup$
  • 1
    $\begingroup$ Google "stars and bars." $\endgroup$ – saulspatz Jul 6 '19 at 15:47
  • $\begingroup$ @saulspatz Doesn't "stars and bars" lead to a binomial coefficient? Which again is solved using nCr ? $\endgroup$ – user634882 Jul 6 '19 at 15:50
  • $\begingroup$ Yes, of course. I was responding to the last line, which I take to be the question. $\endgroup$ – saulspatz Jul 6 '19 at 15:52
  • $\begingroup$ Are you assuming that each person receives at least some of the money? $\endgroup$ – N. F. Taussig Jul 6 '19 at 15:58
  • $\begingroup$ @N.F.Taussig I would like to be able to calculate both of the cases. For example to be able to determine the minimum amount of each person. $\endgroup$ – user634882 Jul 6 '19 at 16:03
1
$\begingroup$

Let "o" represent $1$ Euro and let "|" represent divisor. It is obvious that we need $2$ divisors and applying repeated permutation into "ooo...o||" ($100$ "o" and $2$ divisors) gives us $\binom{102}{2}=5151$ different distribution. $$\\$$ For example, "ooo...o|ooo...|ooo" ($51$ "o" on left, $46$ "o" on middle, $3$ "o" on right) is $51$ Euro for $1^{st}$ person, $46$ Euro for $2^{nd}$ person and $3$ Euro for $3^{rd}$ person.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ great! thanks for the example using stars and bars but how does the binomial coefficient is configured when you need to make sure that in every combination each person gets an X minimum value? Because the default binomial coefficient I think that also include the scenarios where each person gets zero (euros or "O"s) $\endgroup$ – user634882 Jul 6 '19 at 21:01
  • 1
    $\begingroup$ If each person gets X minimum value, then the result will be $\binom{102-3x}{2}$ (first give each one in X amount, then use stars and bars) $\endgroup$ – Taha Direk Jul 6 '19 at 21:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy