combinatorics - Given that at least $n$ elements from $A$ must be members in $C$, how many different sets C can be created by combining elements from $A$ and $B$?

Generalized Problem:

Let $A$ and $B$ be two sets where $|A|=a$ and $|B|=b$.

Let $C\subset A\wedge B, |C|=c$.

Given that at least $n$ elements from $A$ musts be members in $|C|$, how many distinct sets $C$ can be created by combining a total of $c$ elements from $A\wedge B$?

Example: A team of 23 football players and 3 trainers have been awarded 10 tickets to a concert. To increase their probability of receiving a ticket, the cunning trainers deceitfully tell the players that at least 1 trainer must attend the concert. In how many different ways can the tickets be distributed among the 26 team members?

When initially trying to solve this problem I penned the following: $${3\choose1} {25\choose9}=3\times2042975=6128925$$

I thought that ${3\choose1}$ gives the number of ways to choose one of the teachers; and that ${25\choose9}$ gives the number of ways to choose nine people from the remaining 23 players and 2 trainers. Then, I thought that the product of ${3\choose1} {25\choose9}$ would equal total number of ways to distribute the tickets due to the rule of product. (This method does not provide the correct answer.)

After attempting to solve the problem with the above method, I tried to solve it in a different way:

$$\text{"number of allowed ticket distributions" = "total number of ticket distributions"} - \text{"number of ticket distributions with no trainers"} = {26\choose10} - {23\choose10} = 4167669$$

This method yields the correct answer.

My Questions:

• Why does the first method fail? Where is the my reasoning flawed?


• What combinations arise when using the first method that do not when using the second method?

Answer

There is multiple counting in the first method.

Let's call the trainers $A,B,C$ and the players $1,2,\dots23$.

Then possibility $A,B,1,2,3,4,5,6,7,8$ is counted if $A$ is the "chosen" trainer and $B$ is among the other $9$, but it is also counted if $B$ is the "chosen" trainer and $A$ is among the other $9$.