We have four characters (Lets say these are A, B, C, and D)
It is required to create a 7 digit password with below limitations: - Each of those characters shall be included at least once in every single password
How many different password can be created?
(If there was no limitation, it could have been calculated by 4^7 formulae which would give us 16384)
However, the correct answer 8400 because of the given limitation. Is there anybody who may help to solve that problem?
On
You can use the inclusion-exclusion principle. Take all $4^7$ passwords and subtract the ones missing one letter. There are $3^7$ missing $A$, so you would subtract $4 \cdot 3^7$. You have now subtracted the ones missing two letters twice, so you need to add them back in once each, which is $6 \cdot 2^7$. You have now subtracted the ones with only one letter three times, added them three times, so need to subtract them once again for $4 \cdot 1^7$ $$4^7-4\cdot 3^7+6\cdot 2^7-4=8400$$
First include ABCD. Three alphabets are to be chosen.
Four possible choices. $$4 \times \frac{7!}{4!1!1!1!} = 840$$
Due to asymmetry of A and B, left multiply it by two. $$2 \times \binom{4}{2} \times \frac{7!}{3!2!1!1!} = 5040$$
Note that $\binom{4}{3} = \binom{4}{3}$. $$4 \times \frac{7!}{2!2!2!1!} = 2520$$
Adding them up gives the desired answer $840 + 5040 + 2520 = 8400$.