MHB How Can I Understand and Use the Stars and Bars Selection Formula?

[CStudent]

Hey.

I find it difficult to understand the logic and the appropriate usage of the formula:
$\dbinom{N+K-1}{N}$

I don't really understand what's posed behind the scenes of that one.

So I have some example for an exercise which requires the usage of this formula, but I know only to substitute robotically numbers without any understanding.

* How many ways we can insert 16 indistinguishable balls to 4 drawers such that in every drawer we have at least 3 balls?

So I know we should insert at the beginning 3 balls to every drawer and the remainder is 4 balls.
How do I continue and use this formula? I want to understand the formula.

Thanks.

 

[I like Serena]

Hi CStudent,

It is the extended form where zero balls in a drawer is allowed.
Let's start with the form where every drawer must have at least 1 ball.At least 1 star in every drawer
Suppose we have $n=4$ stars to divide over $k=3$ drawers with at least $1$ star in each.
It means we have to divide $k-1=2$ dividers over the $n-1=3$ gaps between the stars, yes?
For instance like this:
\begin{array}{}\star && \star &\mid& \star &\mid & \star & = & \text{$n$ stars in $k$ drawers}\end{array}
It gives us $\binom{n-1}{k-1}$ possibilities.

Now do the same thing with $n+k$ stars.
For instance:
\begin{array}{}\star && \star &\mid& \star &\mid & \star &&\star && \star && \star & = & \text{$n+k$ stars in $k$ drawers}\end{array}
It means that there are $\binom{n+k-1}{k-1}$ possibilities to have at least 1 star in every drawer, yes?
At least 0 stars in every drawer
Now remove $1$ star from each drawer, removing a total of $k$ stars. The example becomes:
\begin{array}{}\star&\mid &\mid & \star &\star & \star & = & \text{$n$ stars in $k$ drawers ($0$ allowed)}\end{array}
It brings us back to $n$ stars where now every drawer contains at least $0$ stars.
Therefore there are still $\binom{n+k-1}{k-1}$ possibilities.
And since generally $\binom NK =\binom N{N-K}$, it follows that $\binom{n+k-1}{k-1} = \binom{n+k-1}{n}$.

 

[CStudent]

I lost you here:
t means we have to divide k−1=2 k−1=2 dividers over the n−1=3 n−1=3 gaps between the stars, yes?

 

[I like Serena]

I lost you here:
It means we have to divide k−1=2 dividers over the n−1=3 gaps between the stars, yes?

How can we divide $n=4$ stars over $k=3$ drawers?
Let's list them:
\[\begin{array}{}1.&\star &\mid& \star &\mid& \star & & \star \\
2.&\star &\mid& \star && \star &\mid & \star \\
3.&\star && \star &\mid& \star &\mid & \star \end{array}\]
That's $3$ possibilities, isn't it?
It depends on where we put the dividers (bars) that indicate which stars go into which drawer.
There are 3 gaps to choose from, and we have 2 dividers.
Choosing 2 from 3 gaps is indeed $\binom 32=3$ possibilities.

 

[CStudent]

There are 3 gaps to choose from, and we have 2 dividers.

Don't that.
I understand there are 3 gaps and 2 dividers, I can't visualize how I choose dividers from gaps. I don't understand what does it mean at al...
Thank you

 

[I like Serena]

There are 3 gaps to choose from, and we have 2 dividers.

Don't that.
I understand there are 3 gaps and 2 dividers, I can't visualize how I choose dividers from gaps. I don't understand what does it mean at al...
Thank you

I'm not sure what you don't understand... can you clarify?

We choose 2 gaps from the 3 available gaps.
In those 2 gaps we put a divider.
The result is that we get the division of the stars to put into the 3 drawers.

 

[CStudent]

I'm not sure what you don't understand... can you clarify?

We choose 2 gaps from the 3 available gaps.
In those 2 gaps we put a divider.
The result is that we get the division of the stars to put into the 3 drawers.

Thanks!
What if I would like to insert 16 indistinguishable balls into 4 drawers such that every drawer has and odd number of balls?

 

[I like Serena]

Thanks!
What if I would like to insert 16 indistinguishable balls into 4 drawers such that every drawer has and odd number of balls?

We start with $\frac{16+4}{2}=10$ balls and we put at least 1 ball in every drawer.
To do so, we select $3$ of the $9$ gaps between the balls for a total of $\binom 93$ combinations.
Then we double the number of balls in each drawer and afterwards we remove a ball from each drawer.