Stars and bars is a counting method for distributing identical objects into distinct boxes. It helps students count solutions to equations without listing every possibility. This cheat sheet is useful for combinations problems, integer solutions, and probability questions involving repeated choices.
It gives quick formulas and decision rules for common cases in grades 11-12.
The core idea is to represent objects as stars and dividers between groups as bars. The number of nonnegative integer solutions to is . For positive integer solutions, first give each variable , then count the remaining objects.
Problems with upper bounds often need subtraction, cases, or inclusion-exclusion.
Key Facts
- The number of nonnegative integer solutions to is .
- The number of positive integer solutions to is when .
- Stars and bars counts distributions of identical objects into distinct boxes using stars and bars.
- The binomial coefficient formula is .
- If each variable must satisfy , substitute so that .
- If a variable has an upper bound such as , count all solutions and subtract the solutions with .
- The number of ways to choose items from types with repetition allowed is .
- Stars and bars does not apply directly when the objects are distinct or when the boxes are identical.
Vocabulary
- Stars and bars
- A counting method that uses stars for identical objects and bars for dividers between distinct groups.
- Nonnegative integer solution
- A solution in which every variable is an integer greater than or equal to .
- Positive integer solution
- A solution in which every variable is an integer greater than or equal to .
- Binomial coefficient
- The value , which counts the number of ways to choose items from items.
- Upper bound
- A maximum allowed value for a variable, such as .
- Inclusion-exclusion
- A counting strategy that subtracts forbidden cases and adds back cases that were subtracted more than once.
Common Mistakes to Avoid
- Using for positive solutions is wrong because that formula allows variables to equal . For positive solutions, use .
- Treating distinct objects as identical is wrong because stars and bars assumes the objects being distributed are identical. If the objects are distinct, use a different counting method.
- Forgetting that the boxes are distinct is wrong because stars and bars counts different assignments to labeled categories. Swapping values between two named variables usually creates a different solution.
- Ignoring upper bounds is wrong because the basic formula only handles lower bounds. When restrictions like appear, subtract invalid cases or use inclusion-exclusion.
- Choosing the wrong number of bars is wrong because groups require exactly dividers. Using bars overcounts the number of groups.
Practice Questions
- 1 How many nonnegative integer solutions are there to ?
- 2 How many positive integer solutions are there to ?
- 3 How many ways can identical pencils be distributed among students if each student receives at most pencils?
- 4 Explain why stars and bars can count the number of ways to buy donuts from flavors, but cannot directly count the number of ways to assign different books to students.
Understanding Stars and Bars Counting Reference
A useful way to understand the method is to focus on positions rather than on the objects themselves. Suppose seven identical tokens are shared among three labeled teams. A row of stars represents the tokens, while two bars split that row into three sections.
A section may be empty if zero is allowed. The arrangement star star bar bar star star star star star means the first team gets two, the second gets zero, and the third gets five.
Every valid distribution creates one arrangement, and every arrangement creates one valid distribution. This one-to-one match is the reason counting positions works.
The labels on the boxes matter completely. Three candies given to Ana, Ben, and Chen form a different situation from three candies placed into three unlabeled jars. With named people, changing who receives an amount changes the result.
With identical jars, swapping two groups may not create a new outcome. Students often lose marks by using stars and bars before checking this detail. The objects must be interchangeable as well.
Six identical red counters work, but six numbered tickets do not. Distinct objects require methods that track each object, such as permutations, subsets, or multinomial counting.
Lower limits are handled by reserving the required amount before counting the flexible part. For example, if four students must each receive at least two identical stickers, first set aside eight stickers. Only the leftover stickers need to be distributed freely.
This idea works even when the minimums differ between variables. Subtract each minimum from its variable, then count the new nonnegative amounts. Always check whether the total is large enough to meet the required minimums.
If it is not, there are zero distributions. This check is simple, but it prevents applying a formula to an impossible situation.
Upper limits need more care because a bar arrangement can create a group that is too large. One approach is to count every unrestricted distribution, then remove the invalid ones. For a condition such as no box receives more than four objects, an invalid case has at least five in one box.
Temporarily reserve five objects for that box and count what remains. If two boxes can exceed the limit at once, those cases may be removed twice, so they must be added back once. This is inclusion-exclusion.
It is important to list which restrictions can overlap before calculating. In probability problems, first count the allowed outcomes, then compare that count with the size of the full sample space.