How many $6$-digit numbers contain each of the digits $1$, $2$, and $3$ at least once?

Question

I asked a recent question, which contained this problem:

With the numbers 1,2,3 How many numbers of 6 digits contain the digits 1, 2 and 3 at least once?

The truth is, I ask a lot of questions about combinatorics, because it's something I've been learning on my own.

I like to really understand how it works, the answer to this exercise is:

$V^3_3 * P(6) = 3^3 * \frac{6!}{3! * 3!}$

And what I need to understand is how it has come to be a variation with a permutation with repetition, why the repetition of the permutation is 3! * 3! ? I do not mean the formula, but the logic used to arrive at that solution. Please, if you will answer me in a simple way, abstain, I really want to understand it.

Answer 1

$3^3$ represents the other 3 digits other than 1,2,3, which must occur in the number. And there are $\frac{6!}{3!3!}$ ways to arrange each sequence.

Answer 2

if you will answer me in a simple way.

But the answer you provided uses a clever(or too clever, albeit it's short) way to solve the problem, which I don't think it could be easily explained. Anyway, if you insist on the direct way to solve it, then enumerate all possible descending-size-tuple can do

tuple: (choose tuple) $\cdot$ (choose number)

$(4,1,1): C(6,4)\cdot C(3,1)2!=90,\\ (3,2,1): C(6,3)C(3,2)C(1,1)\cdot 3!=360,\\ (2,2,2): C(6,2)C(4,2)C(2,2)\cdot1=90,$

and to fit the formula, which all beautiful combinatorics symbols are destroyed as follow

$(4,1,1): \frac{6!}{4!1!1!}\cdot C(3,1)=\frac{6!}{3!3!}\cdot(3!\cdot\frac{3}{4}),\\ (3,2,1): \frac{6!}{3!2!1!}\cdot3!=\frac{6!}{3!3!}\cdot (3!\cdot3),\\ (2,2,2): \frac{6!}{2!2!2!}=\frac{6!}{3!3!}\cdot (3\cdot\frac{3}{2!}),$

and the sum of these monsters is exactly $$\frac{6!}{3!3!}\cdot(18+9,\textrm{which is}\ 3^3).$$

---

My trying to "create" $3^3$ in the formula is that by first assign one mark($O$) to each number then deal with the other three, e.g.

$$\begin{array}{c|c|c} 1 & 2 & 3\\ O & O & O\\ \color{blue}{OO} & \color{blue}{O} & \cdot\\ \end{array},$$

which represent a choice of "three $1$, two $2$, one $3$". There are a total of $3^3$ ways to assign those $\color{blue}{O}$'s. And apparently this way is too clever because $3^3$ will cause "two(or more) different assignment orders, the same result", and thus you would have to subtract those repetitions and this is just for the first part, $3^3$, of the formula. To come up with the idea behind the other part, $\large\frac{6!}{3!3!}$, you would have to consider all three different possible size tuples, $(4,1,1),(3,2,1),(2,2,2)$ and the repetitions in the first part, in a single line.

Answer 3

As near as I can tell, the fact that the numerical answer, $540$, to the OP's problem can be written as $3^3{6\choose3}$ is purely coincidental. That is, it suggests a generalization to a formula $n^n{2n\choose n}$ that is wrong for other values of $n$.

One way to solve the problem in general uses Inclusion-Exclusion. For the OP's problem, this gives

$$3^6-{3\choose1}2^6+{3\choose2}1^6=729-3\cdot64+3=540$$

In general -- if you want to count the numbers of ways to write a $2n$-"digit" number consisting of "digits" $1$ to $n$ with each "digit" used at least once -- inclusion-exclusion gives us

$$\sum_{k=0}^n(-1)^k{n\choose k}(n-k)^{2n}$$

as a formula for the answer. We find

$$\begin{align} 1^2-0^2&=1\not=1^1{2\choose1}\\ 2^4-2\cdot1^4+0^4&=14\not=2^2{4\choose2}\\ 3^6-3\cdot2^6+3\cdot1^6-0^6&=540=27\cdot20=3^3{6\choose3}\\ 4^8-4\cdot3^8+6\cdot2^8-4\cdot1^8+0^8&=40824\not=4^4{8\choose4} \end{align}$$

The sequence of correct answers, $1,14,540,40824,\ldots$, is A210029 at OEIS. The formula $n!*S2(2n,n)$, is given there, where $S2$ refers to "Stirling numbers of the second kind." But that's a far cry from a generalization of $V_3^3*P(6)$, whatever those symbols refer to.