# All 6-digit numbers consist of [6] which must contain 1,2,3

I'm required to find all possible numbers which consist of {1,2,3,4,5,6}, and include each of {1,2,3} at least once. For example: 113124 is good, but not 464612 because it's missing 3. My approach was to first calculate all the sequences which contain 1,2,3 once. Which would be: $$6\times5\times4\times3^3$$. The reasoning is that you have 6 different places to place 3, then 5 for 2, and 4 for 1. Because I'm looking now for sequences which contain each digit only once I'd fill the 3 rest spots with {4,5,6} meaning $$3^3$$. Now for the case where you have a digit twice it would be: $$3\times{6\choose2}\times4\times3\times3^2$$. Using the same reasoning but this time you have $$6\choose2$$ ways to choose 2 positions for a number, then you are left with 4 places for the other number and so on. And you multiply by 3 for each number. So you carry on up to 4 times the same number, because if you would continue for 5 you don't have enough spots to fill in the other 2 numbers you must have, so the formula is: $$6*5*4*3^3 + 3*{6\choose2}*4*3*3^2+3*{6\choose3}*3*2*3+3*{6\choose4}*2$$

Yet the answer is incorret, it's a question a friend asked me to do so I'm not aware of the exact solution, from what I recall he said the answer is roughly 11,000.

• Inclusion-Exclusion – Haran Jan 14 '19 at 10:48

Let $$A$$ denote the set of $$6$$-digit numbers with digits in $$\{1,2,3,4,5,6\}$$.
For $$i=1,2,3,4,5,6$$ let $$A_i$$ denote the set of elements of $$A$$ that do not contain $$i$$ as digid.
Then with inclusion/exclusion and symmetry we find:$$|A_1\cup A_2\cup A_3|=3|A_1|-3|A_1\cap A_2|+|A_1\cap A_2\cap A_3|=3\cdot5^6-3\cdot4^6+3^6$$so that: $$|A|-|A_1\cup A_2\cup A_3|=6^6-3\cdot5^6+3\cdot4^6-3^6=11340$$