Stars and bars with constraints

Question

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?

Answer 1

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}$

Answer 2

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!}$