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.

  • 2
    $\begingroup$ Inclusion-Exclusion $\endgroup$ – 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$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.