What's wrong in my solution? Ways of choosing 5 items from 3 catagory with 3, 6, 14 items, while having 1 item from each catagory.

Question

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?

Answer 1

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.

Answer 2

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$$

Answer 3

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}.$$

Answer 4

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}.$$