 # Alternative way of writing the stars and bars formula where each bar is associated with at least one logiski9s 2022-07-08 Answered
Alternative way of writing the stars and bars formula where each bar is associated with at least one star.
I was looking for a different way of writing the formula of the number of different k-tuples of non-negative integers whose sum is equal to n and I thought of this formula followed by this combinatorial proof:
$\sum _{i=1}^{k}\left(\genfrac{}{}{0}{}{n+1}{i}\right)\left(\genfrac{}{}{0}{}{k-1}{i-1}\right)$
The first combination is the number of positions that we can choose from to place the bars. There are $n+1$ positions to choose from, since now we can also place the bars before and after the stars. The next combination is the number of different ways of splitting the stars between the positions that were chosen for the bars to be placed.
Lastly, we'll have to add all the different ways of combinations of bar positions and number of bars in each position. I haven't found a flaw in my proof yet but I can't seem to conclude that the above formula is equal to
$\left(\genfrac{}{}{0}{}{n+k-1}{k-1}\right)$
Could someone more experienced verify my proof or show me where the flaw is?
You can still ask an expert for help

## Want to know more about Discrete math?

• Live experts 24/7
• Questions are typically answered in as fast as 30 minutes
• Personalized clear answers

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it Kiana Cantu
Step 1
Your formula and argument are incorrect, but they can both be made correct with a small change. The correct formula is $\sum _{i=1}^{n+1}\left(\genfrac{}{}{0}{}{n+1}{i}\right)\left(\genfrac{}{}{0}{}{k-2}{i-1}\right)$
The idea is this; once you have chosen the i spaces out of $n+1$ which will receive bars, you now need to split the $k-1$ bars into i non-empty groups. This can be done in $\left(\genfrac{}{}{0}{}{k-2}{i-1}\right)$ ways; if we now imagine a line of $k-1$ bars, with $k-2$ spaces between them, then such a partition is uniquely chosen by selecting a subset of $i-1$ spaces, and splitting at those spaces.
Step 2
This combinatorial proof establishes the fact that
$\sum _{i=1}^{n+1}\left(\genfrac{}{}{0}{}{n+1}{i}\right)\left(\genfrac{}{}{0}{}{k-2}{i-1}\right)=\left(\genfrac{}{}{0}{}{n+k-1}{k-1}\right)$
It is easy to give an alternative proof of this by rewriting $\left(\genfrac{}{}{0}{}{k-2}{i-1}\right)$ as $\left(\genfrac{}{}{0}{}{k-2}{k-1-i}\right)$, and applying Vandermonde's identity.

We have step-by-step solutions for your answer!