I am having problems understanding how to distinguish some combinatorial questions (specifically question 2 below). What distinguishes these two types of questions?

In question 1, I can see that the questions is of the type $x_1 + x_2 + x_3 +...+ x_n = y$ and solve the questions accordingly. But in question 2, I see that it shares similarities (in the choice of wording at least) to question 1 which leads me to assume it is also be solved by setting up the question like $x_1 + x_2 + x_3 +...+ x_n = y$. But the question (question 2) has multiple objects (pennies, nickels, dimes etc.) instead of a single unique set such as question 1.

How does one set up an equation to solve question 2 below?

Question 1
In how many ways can 10 (identical) dimes be distributed among five children if;

a) there are no restrictions?
$x_1 + x_2 + x_3 + x_4 +x_5 = 10 \\={14\choose10}$

b) each child gets at least one dime?
$x_1 + x_2 + x_3 + x_4 +x_5 = 5 \\={9\choose5}$

c) the oldest child gets at least two dimes?
$x_1 + x_2 + x_3 + x_4 +x_5 = 8 \\={12\choose8}$

Question 2
In how many ways can we select five coins from a collection of 10 consisting of one penny, one nickel, one dime, one quarter, one half dollar and five (identical) Susan V. Anthony dollars?

which results with the solution $2^5$

Any help would be much appreciated, thanks!

  • $\begingroup$ In order for us to help you distinguish them, it would help if you pointed out where you see the similarities between them. $\endgroup$ – joriki Oct 9 '15 at 2:02
  • $\begingroup$ @joriki sorry, I will update my question momentarily $\endgroup$ – Miroslav Glamuzina Oct 9 '15 at 2:10

It is best to solve questions in the naturally easiest way.

$Q1$ is about distributing identical objects to distinct boxes, a typical stars and bars problem.

$Q2$ is about choosing from distinct objects, and the easiest way here is to either select or not select from pennies, nickels,... and fill up the needed balance with dollars, hence $2^5$

Having said that, we can apply stars and bars with inclusion-exclusion in a tortuous way !
Imagine that we have 10 identical objects, and 6 distinct boxes marked penny, nickel, ... dollar, and we need a total of $5$ with the restriction that none except the dollar box can accommodate more than one object.
Then, # of ways = $\binom{10}{5} - \binom51\binom85 + \binom52\binom65 = 32$

  • $\begingroup$ Thank you for your answer, that really helps me visualize the math behind it. Cheers. $\endgroup$ – Miroslav Glamuzina Oct 9 '15 at 4:45
  • $\begingroup$ You're welcome ! $\endgroup$ – true blue anil Oct 9 '15 at 5:08

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.