5
$\begingroup$

I have searched a lot and don't really understand the answers I've come across. So apologies in advance if I'm repeating a common question.

The problem is as follows: Distribute $69$ identical items across $4$ groups where each groups needs to contain at least $5$ items.

The way I see the problem: $x_1 + x_2 + x_3 + x_4 = 69$, $x_i \geq 5$

Could this then be the same as: $x_1 + x_2 + x_3 + x_4 = 49$, $x_i \geq 0$, and therefore be solved using ${n + k -1} \choose {k - 1}$ = ${52}\choose{3}$ = $\frac{52!}{3!(52 - 3)!}$ = $\frac{52!}{3!49!}$

Or am I thinking completely wrong here?

$\endgroup$
1
  • 3
    $\begingroup$ That's the exact way I would solve it: Give five items to each group, then distribute the remaining items without any constraints using stars and bars. $\endgroup$
    – Arthur
    Feb 4, 2018 at 15:07

2 Answers 2

3
$\begingroup$

Precisely, yes. What you did is correct. If you're interested, the "rigorous" mathematical approach would be the following:

$x_1 + x_2 + x_3 + x_4 = 69$, where $x_i \geq 5$ for all $i \in [1,4]$

Let's take $x_1$ as an example:

$x_1 \geq 5$

By simple subtraction from both sides, we see that:

$x_1 - 5 \geq 0$

Stars and bars is really easy to solve when $x_i \geq 0$ for all $i$. That's because it essentially translates to a scenario where you can pick $0$ or more of each item to place in each "bucket". Notice that the left-hand side of that inequality is indeed $\geq 0$. In that case, so we no longer have to refer to it as the "left-hand side of the inequality", let's call it $x_1'$.

$x_1' = x_1-5\geq0$

Now, let's just focus on the equality part:

$x_1' = x_1 - 5$

Rearranging:

$x_1 = x_1' +5$

And now, let's repeat this process for all other variables:

$x_2 = x_2'+5$

$x_3 = x_3' + 5$

$x_4 = x_4' + 5$

And substitute these all back into the original equation:

$x_1'+5+x_2'+5+x_3'+5+x_4'+5 = 69$

Then, subtracting all the $5$s from both sides, this simply becomes:

$x_1'+x_2'+x_3'+x_4' = 49$

Where all $x_i' \geq 0$. And there! You can now proceed solving this just as you did.

More on the stars and bars part, because I hate memorizing equations:

x1|x2|x3|x4

The variables indicate valid buckets where we can place stars. Let's call the leftmost bucket $x_1$, all the way to $x_4$ on the rightmost.

We have $49$ stars that we can put in these buckets to indicate "Hey, I would like this many of the variable $x_i$, please!"

And then the problem simply becomes a permutation of a multiset. If you've solved problems that ask you how many ways you can scramble the letters in the word "SORRY", for example, then this is precisely what you're doing—you translate the problem into an identical scenario. In this case, you're scrambling two "letters": the bars (|) and the stars (*).

So in your case, you've got $3$ bars and $49$ stars. You have $52$ "slots" in your "word". You choose $3$ of those to be the bars and the rest to be stars:

$52 \choose 3$ $49 \choose 49$ = $\frac{52!}{3!49!}$

$\endgroup$
1
$\begingroup$

You are completely right.

Distribute 5 items to each $x_i$ before using star and bars. Hence we get to find non negative integral solutions of $$a+b+c+d=49$$ Hence the answer would be $\binom {52}{3}$

$\endgroup$

You must log in to answer this question.

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