permutation of 5 digit numbers divisible by 3

Question

"The total number of possible combination of 5 digits numbers formed from the digits(0,1,2,3,4,5,6,7,8,9) which are divisible by 3?"

This was the question given to me by my mathematics teacher during out permutation and combination lessons;I was able to solve this with ease but later I was thought of modifing the problem a little bit to

"The total number of possible combination of 5 digits numbers formed from the digits(0,1,2,3,4,5,6,7,8,9) which are divisible by 3 without repetation of any digits? eg 12345 not 33120"

I asked my teacher about the solution of the problem because i was unable to solve it with certain accuracy, he was unable to give me a satisfactory answer.

Can anyone help me in solving this problem thank you.

Answer 1

Update

Among the $10$ digits there are $4$ having remainder $0$ mod $3$, and $3$ each having remainder $1$ or $2$ mod $3$. We have to select $x_0$, $x_1$, $x_2$ of these digits, such that $$x_0+x_1+x_2=5,\qquad x_1-x_2=0\quad {\rm mod}\ 3\ .\tag{1}$$

We can partition $5$ into three nonnegative parts in the following $5$ ways: $$p_1:\ 5+0+0,\quad p_2:\ 4+1+0,\quad p_3:\ 3+2+0,\quad p_4:\ 3+1+1,\quad p_5:\ 2+2+1\ .$$ The first and the second of these cannot be used. Then $p_3$ together with $(1)$ leads to the solutions $(x_0,x_1,x_2)=(2,3,0)$ and $(x_0,x_1,x_2)=(2,0,3)$. For $p_4$ we obtain $(x_0,x_1,x_2)=(3,1,1)$, and for $p_5$ we obtain $(x_0,x_1,x_2)=(1,2,2)$.

It follows that we can select the five digits in $$2{4\choose2}{3\choose3}+{4\choose 3}{3\choose1}{3\choose1}+{4\choose 1}{3\choose2}{3\choose2}=84\tag{2}$$ ways. Multiply this by $5!=120$ to account for their arrangement, and obtain $10\,080$.

In a comment later on the OP has excluded the strings beginning with $0$. In order to account for this we first compute the admissible selections of five digits containing no $0$. To this end it suffices to replace $4$ by $3$ in $(2)$: $$2{3\choose2}{3\choose3}+{3\choose 3}{3\choose1}{3\choose1}+{3\choose 1}{3\choose2}{3\choose2}=42\ .$$ Therefore $84-42=42$ admissible selections of five digits contain a zero, and these give rise to $42\cdot{5!\over5}=1008$ strings beginning with a $0$. Subtract these from $10\,080$, and obtain $9072$ as final result.

Answer 2

Here is a correct solution along the lines of Manthanein's answer:

There are $9\cdot8\cdot7\cdot 6 \cdot5=15\,120$ strings of length $5$ not containing a repeat or zero. Adding $1$ mod $9$ to each digit in such a string changes its sum by $2$ mod $3$. From this we can conclude that exactly one third of these strings have a sum which is divisible by $3$. It follows that there are 5040 valid strings of this kind.

Similarly, there are $9\cdot8\cdot7\cdot 6=3024$ strings of length $4$ not containing a repeat or zero, and exactly one third of these strings have a sum which is divisible by $3$. Given such a string we can insert a $0$ at four different places in order to obtain a valid string of length $5$. It follows that there are ${3024\cdot 4\over3}=4032$ valid strings of this kind.

In all there are $5040+4032=9072$ valid strings of length $5$.

Answer 3

Assuming that we are considering only $5$ digit numbers (i.e. strings beginning with '$0$' are not counted) then the answer can be expressed simply as:

$$\frac{1}{3}\left(\binom{9}{5}5!+\binom{9}{4}4\cdot 4!\right)=9072\tag{Answer}$$

For the $5$ digit numbers to be multiples of $3$ we require their digit sum to be a multiple of $3$.

With this in mind, begin by considering the generating function for number of partitions into $5$ distinct parts with maximum part $9$. This generating function is related to the Gaussian binomial coefficient $\binom{n}{r}_q$. Specifically it is:

$$q^{\binom{5}{2}}\binom{9}{5}_q,$$

and the sum of it's $q^{3k}$ ($k=0,1,2\ldots$) coefficients counts distinct choices of $5$ digits from the set $\{1,2,\ldots,9\}$ that sum to multiples of $3$.

For each such choice a $5$ digit number has $5!$ permutations, therefore the number of $5$ digit numbers, divisible by $3$, using choices from $\{1,2,\ldots,9\}$ is:

$$5!\sum_{k}[q^{3k}]q^{15}\binom{9}{5}_q\tag{1}$$

Where we use the $[q^{3k}]$ operator to evaluate the coefficient of $q^{3k}$ in the generating function.

Similarly the generating function for number of partitions into $4$ distinct parts with maximum part $9$ is:

$$q^{\binom{4}{2}}\binom{9}{4}_q.$$

The sum of it's $q^{3k}$ coefficients count distinct choices of $4$ digits from the set $\{1,2,\ldots,9\}$ that sum to multiples of $3$. We may also use this sum to count the number of choices of $5$ digits from the set $\{0,1,2,\ldots,9\}$ that must include $0$ and who's digit sum is divisible by 3.

For each such choice a $5$ digit number has $4\cdot 4!$ permutations: '$0$' can take positions $2$ to $5$ then the remaining $4$ digits take the $4$ remaining positions in $4!$ ways. The number of $5$ digit numbers, divisible by $3$, using choices from $\{0,1,2,\ldots,9\}$ that must contain '$0$' is:

$$4\cdot 4!\sum_{k}[q^{3k}]q^{10}\binom{9}{5}_q\tag{2}$$

So the required answer is given by:

$$5!\sum_{k}[q^{3k}]q^{15}\binom{9}{5}_q+4\cdot 4!\sum_{k}[q^{3k}]q^{10}\binom{9}{5}_q\tag{3}$$

Using a technique called the "roots of unity filter" we see that $(1)$ gives us:

$$\sum_{k}[q^{3k}]q^{15}\binom{9}{5}_q=\frac{1}{3}\left((1)^{15}\binom{9}{5}_1+(e^{2i\pi/3})^{15}\binom{9}{5}_{e^{2i\pi/3}}+(e^{4i\pi/3})^{15}\binom{9}{5}_{e^{4i\pi/3}}\right).$$

Here we are using the cube roots of unity.

The only non-zero term on the right is $\binom{9}{5}_1=\binom{9}{5}$ since $\binom{9}{5}_q$ has a factor $(1-q^9)$ which is $0$ for $q=e^{2i\pi/3}$ and $q=e^{4i\pi/3}$. Hence

$$\sum_{k}[q^{3k}]q^{15}\binom{9}{5}_q=\frac{1}{3}\binom{9}{5}\tag{4}$$

Similarly the roots of unity filter for $(2)$ gives:

$$\sum_{k}[q^{3k}]q^{10}\binom{9}{4}_q=\frac{1}{3}\left((1)^{10}\binom{9}{4}_1+(e^{2i\pi/3})^{10}\binom{9}{4}_{e^{2i\pi/3}}+(e^{4i\pi/3})^{10}\binom{9}{4}_{e^{4i\pi/3}}\right),$$

and the only non-zero term on the right is $\binom{9}{4}_1=\binom{9}{4}$, hence:

$$\sum_{k}[q^{3k}]q^{10}\binom{9}{4}_q=\frac{1}{3}\binom{9}{4}\tag{5}$$

Putting results $(4)$ and $(5)$ into $(3)$ yields our answer.

---

Note carefully that, should we allow strings beginning '$0$', then $(2)$ becomes instead:

$$5!\sum_{k}[q^{3k}]q^{10}\binom{9}{5}_q,$$

and our answer would be:

$$\frac{1}{3}\left(\binom{9}{5}5!+\binom{9}{4}5!\right)=\frac{2}{3}\binom{9}{5}5!=10\,080$$

Answer 4

There are in total $9*9*8*7*6$ 5 digit numbers with distinct digits. The probability that a number is divisible by 3 in all these cases is $\frac {1}{3}$

Hence the number of numbers with 5 distinct digits satisfying the given conditions is $$9*9*8*7*6* \frac {1}{3}=9072$$