How many 5-digit numbers can we assemble from the numbers 2,3,4,5,6,7,8,9 if the digits in each number can be repeated only once

combinatorics

The wording here threw me off.

The answer given is $8 \times 7 \times 6 \times 5 \times 4$.

This suggests that "repeated once" means only used once. I interpreted "repeated once" to mean a digit $2,…,9$ can be used either once or twice (at most). Suppose I instead wish to answer the question that I interpreted it as. That is, I can use each digit once or twice but not more than twice.

I split this into 3 cases. The first is where no digit is repeated. The number of ways we can get this is $8 \cdot7 \cdot6 \cdot5 \cdot4 $.

Now suppose we have one repeat then we have $\left[\binom{5}{2} \cdot 8\right] \cdot 7 \cdot 6 \cdot 5$ ways. That is, we can choose two slots out of five to put the first digit in.

Now suppose we have two repeats then we have $\left[\binom{5}{2} \cdot 8\right] \cdot \left[\binom{3}{2} \cdot 7\right]\cdot 6$. That is, we can choose two slots out of five to put the first digit in. Then we have to choose two of the remaining three slots to put the next digit in.

In summing the cases we get the result. Am I correct?

Best Answer

$\left[\binom{5}{2} \cdot 8\right] \cdot \left[\binom{3}{2} \cdot 7\right]\cdot 6$

The two repeated case is over counting, suppose the five seats are

$$\_~,~\_~,~\_~,~\_~,~\_~$$

First, you choose two seats, and fill in $2$

$$2~,~2~,~\_~,~\_~,~\_~$$

Next, you choose two seats, and fill in $3$

$$2~,~2~,~\_~,~3~,~3~$$

This is as the same as below:

First, you choose two seats, and fill in $3$

$$\_~,~\_~,~\_~,~3~,~3~$$

Next, you choose two seats, and fill in $2$

$$2~,~2~,~\_~,~3~,~3~$$

So you are over counting by twice. $$===========\text{Therefore, the correct answer is:}===========$$

$$8\cdot7\cdot6\cdot5\cdot4+\left[\binom{5}{2}\cdot8\cdot 7\cdot 6\cdot5\right]+\color{red}{\frac{1}2}\left[ \binom{5}{2}\cdot8\binom{3}{2}\cdot7\cdot6\right]=28560$$

Alternative method, no over counting risk, which is

"All cases" -" five repeated case" -" four repeated case"-" three repeated case"

$$8^5-\binom{5}{5}\cdot8-\binom{5}{4}\cdot8\cdot 7-\binom{5}{3}\cdot8\cdot7^2=28560$$

Related Solutions

[Math] How many 6 digit numbers are possible with no digit appearing more than thrice

A start: Here it is easier to count the complementary number: the number of 6 digit positive integers with four or more of one digit repeated.

This reduces to only four cases: (4, 1, 1), (4, 2), (5, 1), (6).

The rest:

(6) is simply $9$. These are $(111111, 222222, \dots, 999999)$.

(5, 1) is a little trickier. First there are $9 * 8$ ways to choose two distinct digits that aren't either zero and assign each to $5$ or $1$. Then there are ${6 \choose 1}$ ways to permute the order.

Now there's case where one is zero. There are $9$ ways to choose the other digit (it can't be zero or else the entire number is zero). For each combination, there are similarly ${6 \choose 1}$ ways to permute the order. In particular, there are ${6 \choose 1}$ ways to permute five zeros and one of the other digit and another ${6 \choose 1}$ ways to permute one zero and five of the other digit. Exactly half of these are valid by symmetry.

Indeed, the bijection that flips each digit demonstrates this property: if we map, e.g., $aaaa0a \mapsto 0000a0$, exactly one of these will be valid for each pair. In this case, we have $a00000, a0aaaa, aa0aaa, aaa0aa, aaaaa0a, aaaaa0$ as valid strings. In total this gives

$$(9 * 8 + 9) * {6 \choose 1} = 486.$$

(4, 2) is similar. There are $9*8$ ways to initially choose and then ${6 \choose 2}$ ways to permute the order.

If one is zero, again there are $9$ ways to choose the other digit and for each combination the number of ways to permute the order is ${6 \choose 2}$. This is

$$(9 * 8 + 9) {6 \choose 2} = 1215.$$

Finally (4, 1, 1). There are $9 * {8 \choose 2}$ ways to choose non-zero digits and assign them to a frequency. There are then $6! / 4!$ permutations. This gives

$$9 * {8 \choose 2} * 6! / 4! = 7560.$$

Now choose a triplet of unique digits $(a, b, c)$ where one is zero. There are ${9 \choose 2}$ ways of doing so. Now, consider the ${6 \choose 4}$ ways to make a string from four $r$'s (r for repeated) and two $s$'s (s for single). If we are given $rsrrrs$, for example, there are now $3!$ ways to choose one of the digits as the repeated and the other two each into one $s$ spot. Of these, two are invalid, namely when we choose the repeated digit to be zero. You can convince yourself this holds for any string. Thus, this gives

$$4{9 \choose 2}{6 \choose 4} = 2160$$

The grand total is $11430$. There are $900000$ six digit numbers in total, so the desired number is $\boxed{888570}$.

Verified solution on computer in Python:

def get_frequencies(cycle):
    result = 0
    for num in range(10**5, 10**6):
        digit_freq = [0]*10
        for digit in get_digits(num):
            digit_freq[digit] += 1
        digit_cycle = sorted([x for x in digit_freq if x != 0], reverse=True)
        if digit_cycle == cycle:
            result += 1
    return result

def get_digits(num):
    r = []
    while num > 0:
        r.append(num % 10)
        num /= 10
    return r

Running with the following main function:

def main():
    print get_frequencies([6], 6)
    print get_frequencies([5, 1], 6)
    print get_frequencies([4, 2], 6)
    print get_frequencies([4, 1, 1], 6)

Outputs the following lines:

Or, more directly, we can use this program:

def get_frequency_atmost(max_freq, n):
    result = 0
    for num in range(10**(n-1), 10**n):
        digit_freq = [0]*10
        for digit in get_digits(num):
            digit_freq[digit] += 1
        if max(digit_freq) > max_freq:
            result += 1
    return 10**n - 10**(n-1) - result

which prints $888570$ on input get_frequency_atmost(3, 6).

[Math] Find out the number six digit natural numbers such that each digit in number appears at least twice

You counted all the cases except the case in which there are three digits that each appear twice.

There are $9$ ways to select the leading digit, $5$ ways to choose the other position for the leading digit, $\binom{9}{2}$ ways to select the other two digits, and $\binom{4}{2}$ ways to choose the positions of the smaller of those digits. Therefore, the number of six-digit positive integers in which there are three digits that each appear twice is $$\binom{9}{1}\binom{5}{1}\binom{9}{2}\binom{4}{2} = 9720$$

You counted each such case twice. For instance, take the number $837783$. You counted it in two ways:

You selected $8$ as the leading digit, then chose to place it in the fifth position. You selected $3$ as the second digit, then chose to place it in the second and sixth positions. You chose $7$ as the third digit and placed it in the third and fourth positions.
You selected $8$ as the leading digit, then chose to place it in the fifth position. You selected $7$ as the second digit, then chose to place it in the third and fourth positions. You chose $3$ as the third digit and placed it in the second and sixth positions.

Best Answer

Related Solutions

[Math] How many 6 digit numbers are possible with no digit appearing more than thrice

[Math] Find out the number six digit natural numbers such that each digit in number appears at least twice

Related Question