# $6$-digit permutation problem

How many $$6$$-digit different numbers greater than $$400000$$ can be formed from the digits $$2$$, $$2$$, $$5$$, $$6$$, $$7$$, $$7$$, $$8$$?

Note: $$22$$ and $$77$$ are allowed in the number. For instance, $$622775$$ is allowed.

My approach: $$5$$ ways to choose the first digit, $$6$$ ways to choose the second, $$5$$ ways to choose the third, $$4$$ ways to choose the fourth, $$3$$ ways to choose the fifth and $$2$$ ways to choose the sixth. So the total arrangement is $$5\times 6\times 5\times 4\times 3\times 2 = 3600$$. But with the $$2,2, 7, 7$$ coming up, I think there is more do be done with it. I tried dividing $$3600$$ by $$(2! \times 2!)$$. I tried this with a small number of digits and it gave the wrong answer. I am stuck. Can anyone help me with the answer or hint. Thanks

• dividing by $2!$ once eliminate permutation of the two $2$s. divide by $2!$ again to eliminate permutation of the two $7$s as well Jul 29 '20 at 6:08
• @RezhaAdrianTanuharja: I tried that too with 1, 1, 2, 2, 3 greater than 300 being three digits and still didn't get the answer correct. Jul 29 '20 at 6:10
• oops sorry i misread the question. you need to count three cases: two $2$s and one $7$, two $7$s and one $2$, two $2$s and two $7$s Jul 29 '20 at 6:14
• @RezhaAdrianTanuharja: what do you mean by the case two 2 and 7? Do you mean not using these digits in the arrangement? Could you explain that case for me? Jul 29 '20 at 6:19
• $622775$ has two $2$s and two $7$s. $622758$ has two $2$s and one $7$ Jul 29 '20 at 7:33

We make numbers $$>4\,000\,000$$. With the $$7$$ given digits one can write $${7!\over2!\cdot2!}=1260$$ different strings. From these we should exclude the strings beginning with a $$2$$. There are $${6!\over2!}=360$$ of them. It follows that there are $$900$$ allowed $$7$$-digit strings. Now you just omit their last digit when writing them up, and you obtain $$900$$ admissible strings in the sense of the problem.

• A very nice approach. Jul 29 '20 at 9:21
• @Christian Blatter: that is an elegant solution. Can you explain the factor of 2! in 6!/2!? I guess it comes from two 7s, right? Jul 29 '20 at 10:24
• @DYBnor: Yes. There is just one $2$ left. Jul 29 '20 at 10:50

Since the number must exceed $$40000000$$, the leading digit may be $$5$$, $$6$$, $$7$$, or $$8$$. Of these digits, only $$7$$ may be repeated. Therefore, it makes sense to handle the case in which the leading digit is $$7$$ separately from the others.

Since there are a total of seven available digits, six of them must be used. Since those digits are $$2, 2, 5, 6, 7, 7, 8$$, there must be at least one repeated digit, but both $$2$$ and $$7$$ may appear twice.

The leading digit is $$5$$, $$6$$, or $$8$$: The leading digit can be chosen in three ways.

Both $$2$$ and $$7$$ appear twice: Select the leading digit from among $$5$$, $$6$$, or $$8$$. If both $$2$$ and $$7$$ appear twice, then we must choose two of the remaining five positions for the $$2$$s and two of the remaining three positions for the $$7$$s. We then have two choices for the final open position, namely one of the two numbers from among $$5$$, $$6$$, or $$8$$ which we did not choose as the leading digit. Hence, there are $$\binom{3}{1}\binom{5}{2}\binom{3}{2}\binom{2}{1}$$ such numbers.

Exactly one of $$2$$ or $$7$$ appears twice: Select the leading digit from among $$5$$, $$6$$, or $$8$$. Choose whether $$2$$ or $$7$$ appears twice. Choose which two of the remaining five positions are occupied by that number. Each of the remaining three positions must be filled with one of the three distinct digits that remain, which can be done in $$3!$$ ways. For example, if the leading digit is $$5$$ and $$2$$ appears twice, the remaining digits are $$6$$, $$7$$, $$7$$, and $$8$$. However, since only $$2$$ appears twice, $$7$$ can only appear once. Thus, the final three positions would have to be filled with $$6$$, $$7$$, and $$8$$. Hence, there are $$\binom{3}{1}\binom{2}{1}\binom{5}{2}3!$$ such numbers.

The leading digit is $$7$$: The remaining digits are $$2, 2, 5, 6, 7, 8$$. Therefore, $$2$$ appears either once or twice.

The digit $$2$$ appears twice: If $$2$$ appears twice, we must choose two of the five remaining positions for the $$2$$s. We then choose which three of the remaining four distinct digits $$5, 6, 7, 8$$ appear in the remaining three positions, and arrange them in those positions. There are $$\binom{5}{2}\binom{4}{3}3!$$ such numbers.

The digit $$2$$ appears once: If $$2$$ appears once, we must fill the remaining five positions with the distinct digits $$2, 5, 6, 7, 8$$, which can be done in $$5!$$ ways.

Total: Since the cases described above are mutually exclusive and exhaustive, the number of six-digit numbers greater than $$400000$$ which can be formed using the digits $$2, 2, 5, 6, 7, 7, 8$$ is $$\binom{3}{1}\binom{5}{2}\binom{3}{2}\binom{2}{1} + \binom{3}{1}\binom{2}{1}\binom{5}{2}3! + \binom{5}{2}\binom{4}{3}3! + 5! = 900$$

First, let's find all the possible numbers using 2256778. Since it's using 7 digits, number of possibilities will be the same as using 7 digits. The possibilities'll be $$\frac{7! = 5040}{2!2! = 4} = 1260$$ You can see that there's $$1260$$ possibilities. When you use 5 digits by knowing your first digit, that'll be $$\frac{1260}{7}$$ making $$180$$. The only way that it'll be less than $$400000$$ will be the numbers starting with 2, which has 180 possibilities. Therefore, the answer'll be $$1260-180=$$ $$1080$$

• There are 360 numbers starting with 2 (6!/2!) Jul 29 '20 at 9:48

We apply generating function to the problem. First, we find how many 6-digit number can be formed from 2, 2, 5, 6, 7, 7, 8 starting with any digit. Notice that 2, 2, 7, 7, can appeal at most 2, which corresponds to $$(1 + x + \frac{x^{2}}{2!})^{2}$$. Also, 5, 6, 8 can appeal at most 1, which corresponds to $$(1 + x)^{3}$$. Now find the coefficient of $$\frac{x^{6}}{6!}$$ in the product $$(1 + x + \frac{x^{2}}{2!})^{2}(1 + x)^{3} = \frac{x^{7}}{4} + \frac{7x^{6}}{4} + \frac{23x^{5}}{4} + \frac{45x^{4}}{4} + 14x^{3} + 11x^{2} + 5x + 1$$, which is $$\frac{6! \times 7}{4} = 1260$$.

Next, find the 6-digit numbers that begin with 2. In that case, 5 slots to fill using 2, 5, 6, 7, 7, 8. Again, 7, 7, can appeal at most 2 giving $$(1 + x + \frac{x^{2}}{2!})$$ and 2, 5, 6, 8 can appeal at most 1 giving (1 + x)^{4}. Since the have 5 choices, we find the coefficient of $$\frac{x^{5}}{5!}$$ in the product $$(1 + x + \frac{x^{2}}{2!})(1 + x)^{4} = \frac{x^{6}}{2} + 3x^{5} + 8x^{4} + 12x^{3} + \frac{21x^{2}}{2} + 5x + 1$$, which is $$5! \times 3 = 360$$.

Finally, the 6-digit number can't start with 2, and hence total number of arrangement is $$1260 -360 = 900$$ ways.