Combination with repition, Representation techniques. Consider the following Question:A bagel shop has onion bagels, poppy seed bagels, egg bagels, salty bagels, pumpernick bagels, sesame seed bagels, raisin bagels, and plain bagels. How many ways are there to choose
e.) a dozen bagels with at least three egg bagels and no more than two salty bagels?

In this question, I do have the right answer but not sure if I have the most efficient representation. Later, I will elaborate much more complicated scenarios using the same technique, and ask what then?

My Representation:
First of all, I represent the information in my head as suggested by the book, by Stars and Bars, where the bars represent the division of source items (in this case the 8 types of bagels each have a bar), and stars that represent the items chosen (in our case the dozen bagels chosen). I represent it, to something like this,
$$|*||**|*\dots||$$


*

*If the right of bar have nothing in between, then the bagel represented by the bar is not selected.

*If the right of bar of $z$ times in between, then the bagel represented by the bar is selected $z$ times.


Now that we have a mental model of the problem, it is easy to see that we are just selecting the number of ways we are positioning $*$ or $|$. As the book mentioned, this can be reduced to a Combination problem, let $n$ be the number of choices (bagels types in our case), $r$ be the number of items chosen from $n$ bagels, (a dozen bagels in our case, 
$${{n + r - 1}\choose{r}}$$
$n-1$ since $n$ objects only need $n-1$ bars to divide them.
That all being said, this is still not enough to solve the problem above, we need to factor in "no more than two salty bagels". With Stars and Bars, this can be represented by 3 cases, when when 0 salty bar is Thus we need to add the cases of 0 salty bagels, 1 salty bagels, 2 salty bagels. Suppose the first bar is the salty bagel, and the second bar is the second bagel, the rest have $x$ to represent variable stars.
$$||*x|x|x|x|x|x|x|x|x|x$$
$$|*|*x|x|x|x|x|x|x|x|x|x$$
$$|**|*x|x|x|x|x|x|x|x|x|x$$
The combination of each are added below,
$${{7 + 12 - 3 - 1}\choose{12-3}} + {{7 + 11 - 3 - 1}\choose{11-3}} + {{7 + 10 - 3 - 1}\choose{10-3}}$$
Problem:
As you can see, the representation when the constraint is "at least $b$ of this element" is very easy. By having at least $b$ items of this element, there's only $r-b$ to choose, where $r$ is the number of element chosen. But to represent "no more than $c$ elements are to be chosen", I have to add instances when $0, 1, \dots, c$ elements are in the set. All the problems in this chapter of Generalized Permutation and Combination have this scenario, which if you ask me, does not sound very generalized. So,


*

*How do you efficiently represent "no more than $c$ items of this elements" problems?

*How do you represent when there's more than one "no more than $c$ items of this elements"? (e.g. salty bagels and egg bagels demand for their own maximum items). The only think I can think of now is adding probabilities when $(0 salty, 0 egg), (0, 1), \dots (0, max_{egg}) \dots (max_{salty}, max_{egg}$. But that is very unrealistic in computation standpoint since that will take $O(d^2), d = \max(max_{egg}, max{salty})$, which is very inefficient. Compared to all "at least $b$ elements" problems, it is $O(1)$. I have never seen the book in this current chapter describe such phenomena despite having the chapter title that it should be.
 A: An alternative method for dealing with "no more than c" is to subtract. First find the number with any of that item; then find the number with more than c of that item; then subtract.
In your case you have 8 kinds of bagels and 12 bagels to choose, with a restriction of at least 3 egg bagels and at most 2 salty bagels.
You have to choose 3 of the egg bagels, so you really have 9 bagels to choose. You have to have 9 "take a bagel" instructions (the stars) and 7 "switch to a new kind of bagel" instructions (the bars), and need to arrange these in all ways so you get:
$$
\begin{pmatrix} 9+7 \\ 7 \end{pmatrix}
$$
If you now suppose you have to choose at least 3 salty bagels you then really only have 6 bagels to choose so you get
$$
\begin{pmatrix} 6+7 \\ 7 \end{pmatrix}
$$
But you actually wanted the ones with 2 or less salty bagels, so you subtract the number with more than 2 from the total to get:
$$
\begin{pmatrix} 9+7 \\ 7 \end{pmatrix} - \begin{pmatrix} 6+7 \\ 7 \end{pmatrix}
$$
EDIT: If you had more than one of the "no more than c" restrictions, you may have to use inclusion-exclusion. The opposide of "no more than c of item A and no more than d of item B" is "more than c of item A OR more than d of item B". Hence you would need to subtract those with more than c of item A, and also subtract those with more than d of item B, and then add on those with too many of both.
