What's the bijection between Stars and Bars and Integer Solutions to an Equality?
The second quotation below keeps mentioning "bijection", but it never explicitly defines it. So what's the formula for that bijection?
A story instead of stars and bars - Making Your Own Sense
On to the third problem. As I said earlier, many people teach students to reduce other problems to this, and then remember a formula for the number of ways to solve this. I, on the other hand, still tell the same sort of story. This time, I imagine starting with the equation 0 + 0 + 0 = 0, and then moving along the positions. At each stage I can add 1 to the number there currently, or I can move ahead to the next position. As long as I add 1 ten times, it will work. Once more, I can represent this with a picture. I’ve got “+1” for the action of increasing a position by 1, and and arrow for moving to the next position. The picture shows how to get 3+2+5=10 and 6+0+4=10. Except for the change of symbols, the pictures are the same as the other ones, so the number of solutions is still 12C2.
Sweet!
In the traditional stars and bars method, the stars represent objects and the bars represent dividers between them. In my method, the symbols always represent instructions in a story of how the collection/allocation/solution is constructed. And yes the symbols do always match the context of the problem. I find this much easier to remember and apply. Plus it’s cuter!
Integer Equations - Stars and Bars | Brilliant Math & Science Wiki
0 answers
1 comment thread