# permutation of 5 digit numbers divisible by 3

"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.

• Is $01234$ a valid number?
– orlp
Feb 8, 2018 at 11:49
• Divisibility by 3 has a special property: iff a number $n$ is divisible by 3, so must be its sum of digits. Note that this check does not care about order of the numbers. So WLOG we can assume $d_1 < d_2 < d_3 < d_4 < d_5$ and then multiply by $5! = 120$ at the end to permute the numbers. Nevertheless it's still a difficult problem (to solve in general, it's trivial to program a bruteforce approach of a problem this size).
– orlp
Feb 8, 2018 at 12:53
• no 01234 in not valid Feb 8, 2018 at 19:36
• Following the idea of @orlp, you can group the numbers according to their equivalence modulo 3. So, we get the 3 sets $S_0 = \{0,3,6,9\}, S_1 =\{1,4,7\},S_2 = \{2,5,8\}.$ Then, consider all the ways we can pick elements from each set so that their sum is 0 modulo 3. E.g. $(s_0,s_0,s_0, s_1,s_2), (s_0,s_0, s_1,s_1,s_1), (s_0,s_0, s_2,s_2,s_2), (s_0, s_1, s_1, s_2, s_2)$ where with some abuse of notation $s_i$ represents an element in $S_i$. I think those are all the possible combinations considering that the restrictions of uniqueness (we can't have $(s_1,s_2,s_2,s_2,s_2)$ since $|S_2|=3$). Feb 10, 2018 at 3:52

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.

• The clarity of this answer caused me to blurt out an emphatic, joyful expletive in a quiet study area, much to my chagrin. I would be remiss if I failed to praise work that resonated with me so. Well done! Feb 8, 2018 at 17:03
• Doesn't this arrangement include the numbers which start with 0, which according to the OP doesn't need to be counted Feb 9, 2018 at 4:16

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$.

• Thanks for explanation along the "lines of my answer." Feb 9, 2018 at 13:57

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,$$

$$\frac{1}{3}\left(\binom{9}{5}5!+\binom{9}{4}5!\right)=\frac{2}{3}\binom{9}{5}5!=10\,080$$
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$$
• This is not a sound argument. The probability of $\frac{1}{3}$ applies to the full number line, and does not in general hold for finite sets of numbers, and I especially see no obvious reason why it should hold for a finite set of numbers as complex as 'no repeated digits'. For example $\frac{1}{100}$ numbers are divisible by $100$, but if you exclude repeated digits none are divisible by $100$.