4
$\begingroup$

I have this statement:

Prove the bar and star formula for positive integers $\binom{n-1}{k-1}$

My attempt was:

Imagine I have a certain equation:

$x_1 + x_2 + ...+x_k=n$

Now, i have:

$\underbrace{**********}_\text{n times}$, $\underbrace{||||||||}_\text{(k-1) times}$

Since, the solutions must be positive, the bars cannot go before the first star, after the last star or two bars together.

So, the first bar have $n-1$ positions, the second bar have $n-2$ position, the third bar have $n-3$ position, etc. Also there are $k-1$ bars, so the last bar have $n -(k-1)$ positions, that is $n-k+1$.

Thus, there are $(n-1)(n-2)\cdot ....\cdot (n-k+1) = \frac{(n-1)!}{(n-k)!}$ possible combinations.

But from here, i can't get the formula to prove. I know that i need to divide by ($k-1)!$, but why? What elemets i am overcounting?

A graphic explanation would be quite useful. Thanks in advance.

$\endgroup$
2
$\begingroup$

HINT: Bars are identical. So they cannot switch places among themselves.

$\endgroup$
2
$\begingroup$

A less complicated method would be to consider that the number of solutions to $$x_1+x_2+...+x_k=n$$ in positive integers is the same as the number of solutions to $$(x_1+1)+(x_2+1)+...+(x_k+1)=n$$ in non-negative integers That's just solving $$x_1+x_2+...+x_k=n-k$$ using the normal stars and bars method.


Also, I'd like to suggest a different way of thinking about the combination operation that can make your arguments much easier to understand. $\binom{n}{k}$ represents the number of $k$-element subsets from a set of $n$ elements. Let me apply that reasoning to this problem to show you how much easier it is to solve.

In this case, we need to find the number of ways to sort $n-k$ stars and $k-1$ bars into $n-1$ slots. So all we're doing is choosing which $n-1$ slots to put the $k-1$ bars into. Rather than do that one at a time, we can just say, bang, that number is $\binom{n-1}{k-1}$ by what the definition of the binomial coefficient. Avoiding juggling factorials is a great strategy for improving your day!

$\endgroup$
  • $\begingroup$ Good way, thanks for that trick $\endgroup$ – Eduardo S. Aug 19 at 23:20

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.