Day 4: Four Calling Birds

Let $M$ represent the set all possible melodies without any restriction. Additionally, let $M_{A}$ represent the set of all melodies that don't contain the note $A$ , $M_{B}$ represent the set of all melodies that don't contain the note $B$ , and in a similar way we define $M_{C}$ and $M_{D}$ . According to the question we have to find the cardinality of the set of all melodies where none of the 4 notes is missing. Therefore, we should find the cardinality of the set $M - ( M_{A} \cup M_{B}\cup M_{C}\cup M_{D})$ . Now using the Principle of Inclusion and Exclusion we get that the cardinality of the last set is $\left| M \right| - \left| M_{A} \cup M_{B} \cup M_{C} \cup M_{D}\right| =$ $\left| M\right| - \left|M_{A}\right|-\left|M_{B}\right|-\left|M_{C}\right|-\left| M_{D}\right| + \left| M_{A}\cap M_{B}\right| +....$ Using the facts that $\left|M\right|=4^{7}$ , $\left|M_{A}\right| =\left|M_{B}\right|=\left|M_{C}\right|=\left|M_{D}\right|=3^{7}$ , $\left|M_{A}\cap M_{B}\right| =\left| M_{A}\cap M_{C}\right|=...=2^{7}$ , $\left| M_{A}\cap M_{B} \cap M_{C}\right| = \left|M_{A}\cap M_{B}\cap M_{D}\right| =...=1^{7}=1$ and $\left|M_{A}\cap M_{B} \cap M_{C}\cap M_{D}\right|=0^{7}=0$ we obtain that the answer is going to be $4^{7}- {4\choose 1} 3^{7} +{4\choose 2 } 2^{7}-{4\choose 3} 1^7 +{4\choose 4} 0^{7} =8400$

I tried that, but unfortunately I didn't notice that the coefficient of $(-1)^{n}n^{7}$ was the binomial coefficient rather than $n+1$ .

That is a very elegant approach! It generalises very nicely; I did not think of applying the Principle of Inclusion and Exclusion in this way. I'm not too sure how to explain it formally but here is my alternative (outlined) attempt:

We want to find the number of ways of using all four notes. We can do this by taking the total number of possible melodies with at most four notes, then we take away the number of possible melodies with at most three notes, then we add back the ones with at most two notes and so on. This gives the required result.

Please may you show me how to explain it formally? I'm not sure what meaning to assign the sets with in order to use PIE.

That's precisely the best approach, I can think of!

This method works for 6 and 4 but not for 7 and 4. Can you tell me why?

*Well, this is not a specific method but just that how many same note one can have and i can elaborate this if you want but please clear my doubt. @Michael Ng

You have a good idea however you have counted melodies more than once. For example you can choose A-B-C-D first then add the rest with As say. But then you can also choose -AB-C-D and add As to get the same melody, so you have over-counted. Hope this helps! :)