find the number of five digit combinations from the set ${1,2,3,4,5}$ where some digits occur at least three times

Question

So to solve this, I started with the total and subtract where some digit occurs only once or twice.

Total = $5^5$

Digits are only used once $= 5! = 120$

Digits occur twice: I'm starting to think this is where the inclusion exclusion comes into play because as lulu pointed out, AABCD can occur but AABBD could also occur which is still under the condition that digits occur twice but is counted twice under AA and BB.

So I think I need to find the total number of combination of digits occurring twice and then remove the double counted combinations.

Is this the correct way to do this? I'm trying to think of an easier way to do this using inclusion/exclusion.

Answer 1

Considering how few digits are remaining after you do a digit three times, it's probably easier to do:

A) Number of ways with a digit three times and two once +

B) Number of ways with a digit three times and one digit twice +

C) Number of ways with one digit four times and one digit once +

D) Number of ways with one digit five times.

A) is (number of ways to choose triple)(number of ways to choose singles)(ways to place triples)(remaining ways to put singles)=$5*(4*3/2){5 \choose 3}*({2 \choose 1}{1 \choose 1})=600$

B) is (number of ways to choose triple)(number of ways to choose pair)(ways to place triples)(remaining ways to put pair)=$5*4*{5\choose 3}*{2 \choose 2}= 200$

C) is (number of ways to choose quadruple)(number of ways to choose single)(ways to place quadruple)(remaining ways to put single)=$5*4*{5\choose 4}*{1 \choose 1}= 100$

D) is (number of ways to choose quintuple)(ways to place quadruple)=$5*{5\choose 5} = 5$

Total:$905$.

Doing it your way:

Total 5 numbers: is $5^5=3125$

A) number of ways all different: $5!=120$

B) number of ways where two are the same: (# values of the pair)(# values of remaining 3)(where to put the pair)(where to put the 3 remaining)= $5*{4 \choose 3}{5 \choose 2}*3! = 1200$

C) number of ways two pairs are the same:(# values of the two pairs)(# value of the remaining 1)(where to put the first pair)(where to put the second pair)(where to put on remaining)= ${5\choose 2}{3 \choose 1}{5\choose 2}{3 \choose 2}{1 \choose 1} = 900$

Total: $ 3125 - 120 - 1200 - 900 = 905$

Answer 2

It should be possible to do it that way. The partitions of the number $5$ are

• $1+1+1+1+1$ (exclude)
• $2+1+1+1$ (exclude)
• $2+2+1$ (exclude)
• $3+1+1$
• $3+2$
• $4+1$
• $5$

So we start off with $5^5=3125$ length-5 sequences of numbers from $\{1,2,\ldots,5\}$.

• Exclude the $5!=120$ sequences without repetition (i.e., those represented by $1+1+1+1+1$).

• Exclude the $\binom{5}{2,1,1,1} [5]_4=1200$ sequences with one symbol occuring exactly twice, and the rest occurring exactly once (i.e., those represented by $2+1+1+1$). Here $[5]_4=5 \times 4 \times 3 \times 2$ is the falling factorial.

• Exclude the $\binom{5}{2,2,1} [5]_3=900$ sequences with one symbol occuring exactly twice, and the rest occurring exactly once (i.e., those represented by $2+2+1$).

This gives $$5^5-5!-\binom{5}{2} [5]_4-\binom{5}{2,2,1} [5]_3=905.$$

---

Alternatively, we can just include the sequences corresponding to the other partitions

• There are $5$ sequences with the same symbol occurring five times (i.e., those represented by $5$).

• There are $\binom{5}{4,1} [5]_2=100$ sequences with one symbol occurring exactly four times, and the other symbol occurring once (i.e., those represented by $4+1$).

• There are $\binom{5}{3,2} [5]_2=200$ sequences with one symbol occurring exactly three times, and the other symbol occurring exactly twice (i.e., those represented by $3+2$).

• There are $\binom{5}{3,1,1} [5]_3=600$ sequences with one symbol occurring exactly three times, and two other symbols occurring exactly once (i.e., those represented by $3+1+1$).

When we sum those up, we get $905$.

Answer 3

Write $55555$. You can leave that as it is, or you can replace one $5$ by another digit in ${5\choose 1}\cdot4$ ways, or you can replace two $5$s with other digits in ${5\choose2}\cdot4^2$ ways, makes $1+20+160=181$ possibilities. Multiply this by $5$ to obtain the final result $905$.