1
$\begingroup$

I have this problem with combinations that requires one to make a group of 10 from 4 objects and one has many of each of these 4 distinct object types. This type of problem I believe would follow the Stars+Bars approach. But I have difficulty visualizing it this way.

So to make a context based example, say we have 4 veggies these being: S-spinach C-corn T-tomato B-broccoli

We have as many of these veggies that we need. So the addition to this problem is that we must have at least 1 Tomato and at least 2 Broccoli.

If the total amount of each veggies was finite, then one can do a product of Combinations(regular type of combination) Since we have this infinite amount of veggies then we use, i guess the formula: C(m+n-1,m), is now used for the Combinations, but this would mean we look at it from Bars and Stars way.

So an example possible list is: TBBXXXXXXX Where X represents any of the other veggies. Another: TTBBXXXXXX etc

So there is a lot of combinations to go thru when AT Least is fairly small. I guess one can do the inclusion-exclusion principle on this then.

But not fully certain how to go forward. Hope someone can help here.

$\endgroup$
  • 1
    $\begingroup$ Hint. Can you do stars and bars for $7$ vegetables of $4$ kinds and then just toss in the tomatoes and broccoli you must have? $\endgroup$ – Ethan Bolker Nov 18 '17 at 19:00
  • $\begingroup$ Hi, not sure. so it seems you are choosing the minimum amount of the condition 1T and 2B, so hence you are left with 7 veggies but they can be chosen from the 4 types. $\endgroup$ – Palu Nov 18 '17 at 19:12
  • $\begingroup$ But I am still having difficulty deciding how to choose the stars and bars for this. $\endgroup$ – Palu Nov 18 '17 at 19:14
  • $\begingroup$ SO, if i start out and i say that I have 10 spaces then fix 3 spaces with vertical bars, then I have 7 spaces left from which to put more veggies. So i guess these spaces will be the stars. Would I be correct in this way. $\endgroup$ – Palu Nov 18 '17 at 19:21
  • $\begingroup$ how would this be done in the formula, based on the number of bars and stars. $\endgroup$ – Palu Nov 18 '17 at 19:22
2
$\begingroup$

In your example you can think of it as the number of sollutions to the equation

$S + C + T + B = x$

Where $S,C,T,B$ are the total number of each vegetable, and $x$ is the total number of vegetables. Which is a standard stars and bars problem like you said.

To use a concrete example lets say $x = 10$. So the answer above is simply $\binom{4 + 10 -1}{10}$

With the stipulation that you must have at least one tomato and at least two broccoli. It's still the same problem, except now you start out knowing what 3 of the vegetables are. So it's the number of solutions to

$S + C + T + B = 7$ and we have an answer of $\binom{4 + 7 - 1}{7}$

$\endgroup$
  • $\begingroup$ OK, so the answer is not C(7,4), you are saying that it is now C(10,7)? So its because we are now going to choose 7 veggies to fill the remaining 7 spaces from 4 different kinds of veggies. I still don't see how the formula value of C(10,7) relates to the stars and bars. I want to understand if the formula can be written in some form like C(bars, stars). $\endgroup$ – Palu Nov 18 '17 at 21:16
  • $\begingroup$ Is it really necessary for you to write down all the 286 combinations by hand? If not, learn stars and bars method and inclusion-exclusion principle with smaller problems and ask here for a list of the combinations for the larger problem. $\endgroup$ – IV_ Nov 18 '17 at 22:14
  • $\begingroup$ I am not asking to write down all these combinations, just to understand that the numbers in the C(4+7-1,7) can be written in a way like C(bars+stars-1,stars) something like that. $\endgroup$ – Palu Nov 18 '17 at 22:52
  • $\begingroup$ SO the one below gives 286, but that is without the constraint, and with constraints is C(10,7) = 120. $\endgroup$ – Palu Nov 18 '17 at 22:57
  • $\begingroup$ @Palu You would do it exactly the same way you normally do a stars and bars. It's now you know where 3 of the total come from so you are only trying to find the combinations of the 4 fruit that add up to 7 total. Or do you mean "how do you normally do a stars and bars problem?"? $\endgroup$ – XRBtoTheMOON Nov 19 '17 at 2:51
0
$\begingroup$

You are looking for the number of combinations with repetition. The number of combinations of size $k$ of $n$ objects is $\binom{n+k-1}{k}$.

$$\binom{4+10-1}{10}=286$$

Because their number is too large, it wood be no good way to try to write down all these combinations by hand. (There are generating algorithms available for this kind of combinations.)

You would calculate all integer partitions of 10 of length $\le$ 4. Its number is 23. Take e.g. the partition (1,2,2,5). You would choose all combinations where one of your 4 objects is contained 1 times, another of your 4 objects is contained 2 times, again another also 2 times and again another 5 times. You should generate this combinations with the same systematic procedure. You can use also the inclusion-exclusion principle.

You can represent your combinations graphically by the stars and bar method, but this is not necessary. You can use your representation with S, C, T and B. To proceed systematically, you should sort your symbols in the combinations alphabetically.

$\endgroup$

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.