0
$\begingroup$

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!

$\endgroup$
2
  • $\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
    Commented Oct 9, 2015 at 2:02
  • $\begingroup$ @joriki sorry, I will update my question momentarily $\endgroup$ Commented Oct 9, 2015 at 2:10

1 Answer 1

1
$\begingroup$

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$

$\endgroup$
2
  • $\begingroup$ Thank you for your answer, that really helps me visualize the math behind it. Cheers. $\endgroup$ Commented Oct 9, 2015 at 4:45
  • $\begingroup$ You're welcome ! $\endgroup$ Commented Oct 9, 2015 at 5:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .