How many $7$-digit numbers can be generated with numbers in $S=\{1,2,3,4\}$ such that all of the numbers in $S$ are used at least once?

Question

I need to compute the following (this is not a homework or etc. just a personal curiosity). How many $7$-digit numbers can be generated with numbers in $S=\{1,2,3,4\}$ such that all of the numbers in $S$ are used at least once?

Answer 1

By a brute-force counting algorithm, I obtained a total of $8400$ 7-digit numbers that can be generated with the digits in $S={1,2,3,4}$ such that all of the digits are used at least once.

A possible combinatory solution for this problem is as follows. Once the four digits from $1$ to $4$ have been placed in some positions within our number, there remain three other places $A_1,A_2,A_3$ that can be filled with any digits. We have to consider different cases for this triple.

• If $A_1,A_2,A_3$ are all equal, then our $7$-digit number includes four equal digits and three other different digits (i.e., it is obtained by rearranging a pattern of the form $aaaabcd$, where each letter can be any of the four possible digits). We can place the four equal digits in $\binom 74$ ways, and then the remaining different digits in $3!$ ways. Any of the $4$ possible digits can be that occurring four times, so the possible $7$-digits numbers in this case are

$$4\binom 743!=840$$

• If two of the three numbers $A_1,A_2,A_3$ are equal, then our $7$-digit number includes three equal digits, a pair of other equal digits, and two other different digits (i.e., it is obtained by rearranging a pattern of the form $aaabbcd$). We can place the three equal digits in $\binom 73$ ways, the successive two equal digits in $\binom 42$ ways, and then the remaining different digits in $2$ ways. The pair of digits occurring three and two times can be chosen among the possible four digits in $2\binom 42$ ways, so the possible $7$-digits numbers in this case are

$$4\binom 42 \binom 73 \binom 42=5040$$

• Lastly, if the three numbers $A_1,A_2,A_3$ are all different, then our $7$-digit number includes three pairs of equal digits and another different digit (i.e., it is obtained by rearranging a pattern of the form $aabbccd$). Let us focus on the pairs $aa$, $bb$, and $cc$. We can place the first pair of equal digits in $\binom 72$ ways, the second pair in $\binom 52$ ways, and the third in $\binom 32$ ways, leaving a single way to fill the remaining empty place with the last digit. Note that, by placing the three pairs in this manner, we accounted for all possible combinations resulting from the different order in which $aa$, $bb$, and $cc$ are inserted in the number. The triple of digits $a,b,c$ occurring in pairs can be chosen among the possible four digits in $4$ ways, so the possible $7$-digits numbers in this case are

$$4 \binom 72 \binom 52 \binom 32=2520$$

Collecting all the results we get that, as expected on the basis of the brute-force counting, the searched total number is

$$840+5040+2520=8400$$

corresponding to $\approx 51.3\%$ of all $4^7=16384$ possible $7$-digit numbers obtainable with the digits from $1$ to $4$.

Answer 2

How many $7$-digit numbers can be generated with numbers in $S=\{1,2,3,4\}$ such that all of the numbers in $S$ are used at least once?

By the Inclusion–exclusion principle: $$\underbrace{4^7}_{\text{All numbers that can be formed by }1,2,3,4}-\underbrace{\left[{4\choose 1}3^7-{4\choose 2}2^7+{4\choose 3}1^7\right]}_{\text{Numbers not having at least one of }1,2,3,4}=8400$$