The exact question is:

b) Sandra wishes to buy some applications (apps) for her smartphone but she only has enough money for 5 apps in total. There are 3 train apps, 6 social network apps and 14 games apps available. Sandra wants to have at least 1 of each type of app. Find the number of different possible selections of 5 apps that Sandra can choose?

How I approached this question :
As we need to choose 1 from each catagory, the first three apps can be choosen in :
3 x 6 x 14 = 252 ways.
Now, for the remaining 2 apps, we can choose from the 20 apps (3 + 6 + 14 - the installed 3 apps)
So, number of combinations should be 20C2 = 190, so finally the answer I got to was 3 x 6 x 14 x 190 = 47880 which is wrong, the answer is 13839 ways. After trying another method I got 13839 but, I need to know why this method is wrong. Can anyone explain this?

  • For reference, the following Mathematica code confirms by brute force that the answer is 13839: Count[Map[{Count[#, y_ /; 1 <= y <= 3], Count[#, y_ /; 4 <= y <= 9], Count[#, y_ /; 10 <= y <= 23]} &, Subsets[Range[23], {5}]], x_ /; Min[x] >= 1] – Meni Rosenfeld Oct 15 at 14:52
up vote 7 down vote accepted

You are overcounting many, many choices, such as the following selections:

  • train app A, SNS app B, games app C, games app D, games app E
  • train app A, SNS app B, games app D, games app C, games app E

Your method counts these two selections as different (the italicised part is the "at least one of each app" requirement), but they are the same.

  • Ok, I see now why my answer is wrong but, can you point out where/what step in my solution this overlap occurs? Is it possible to change my solution to avoid this error? – abnas Oct 15 at 11:35
  • 2
    @abnas When you start saying "the remaining two apps are selected from the unselected 20", that is where you overcount. There is no easy fix to your attempt. – Parcly Taxel Oct 15 at 11:36

As Parcly Taxel pointed out, you overcount many times because picking the people in two different counts(using your method) doesn't account for the ordering.

My attempt(casework) is the following:

The possible group sizes per element must be either: 1, 1, 3 or 1, 2, 2.

Case 1: 1, 1, 3

There are different combinations based on the different choices of the largest group. So we compute them separately, giving

$$\binom{3}{1}\binom{6}{1}\binom{14}{3} + \binom{3}{1}\binom{6}{3}\binom{14}{1} + \binom{3}{3}\binom{6}{1}\binom{14}{1} = 7476.$$

Case 2: 1, 2, 2

Similarly the the last one, we have $$\binom{3}{1}\binom{6}{2}\binom{14}{2}+\binom{3}{2}\binom{6}{1}\binom{14}{2}+\binom{3}{2}\binom{6}{2}\binom{14}{1} = 6363.$$

Summing the two cases gives a total of $$\boxed{13839}.$$

  • Is there no easier way than to enumerate all possibilities of the number of apps from each category to install? – BallpointBen Oct 15 at 18:47
  • I'm not sure. I was trying to come up with a nice bijection using letters of the alphabet, but this direct casework was all I could come up with. – math783625 Oct 16 at 1:05

As pointed out by @Parcly Taxel,
You are overcounting the apps; keep in mind that order is irrelevant here, so train1,train2 is same as train2,train1. This is where overccounting crept into your solution.

So, how to avoid this overcounting?

Take 3T,6S and 14G apps.
In total, you want 5 apps.

So make selections like: $$(1T,1S,3G),(1T,3S,1G),(3T,1S,1G),(2T,2S,1G),(2T,1S,2G),(1T,2S,2G)$$ Now, count for number of ways you have for each of the above selection, and add.

$$(^3C_1^6C_1^{14}C_3) + (^3C_1^6C_3^{14}C_1) + (^3C_3^6C_1^{14}C_1) + (^3C_2^6C_1^{14}C_1) + (^3C_2^6C_1^{14}C_2) + (^3C_1^6C_2^{14}C_2) = 13839$$

  • This is the method I, after checking my answer used to get to the correct answer. So, is this the only method to solve this problem? @math783625 used a slightly different style but it is basically the same method as this one.But, is it possible to solve this without using the different selections you used or a more direct method ? – abnas Oct 15 at 11:48
  • you can compensate for overcounted apps from your solution, but it will ultimately yield the same result as we posted. – idea Oct 15 at 11:52

I found another solution using the Inclusion-Exclusion Principle and Complementary Counting.

Let $S_3, S_6, S_{14}$ be the sets of 5 objects that do not contain a 3, 6, and 14, respectively.

The number of sets that are missing at least 1 of 3, 6, or 14 is $$|S_3 \cup S_6 \cup S_{14}| = |S_3| + |S_6| + |S_{14}| - |S_3 \cap S_6| - |S_3\cap S_{14}| -|S_6\cap S_{14}| + |S_3\cap S_6\cap S_{14}|.$$

$|S_3| = \binom{20}{5}, |S_6| = \binom{17}{5}, |S_{14}| = \binom{9}{5},$

$|S_3 \cap S_6| = \binom{14}{5}, |S_3\cap S_{14}| = \binom{6}{5}, |S_6\cap S_{14}| = 0,$

$|S_3\cap S_6\cap S_{14}| = 0.$

Evaluating gives 19810 as the number of sets that are missing 1 of 3, 6, or 14. The total number of sets is $\binom{23}{5} = 33649,$ so the number of sets that are not missing any of 3, 6, or 14 is $$33649 - 19810 = \boxed{13839}.$$

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.