Combinatorics practice problems

Q1. A rack has 5 different shoe pairs. Find the number of ways in which 4 shoes can be chosen so that no complete pair is chosen.

Solution:

One wrong way to do it is this:
First shoe can be chosen in 10 ways.
Second shoe can be chosen in 8 ways since I can't choose the remaining shoe from the first pair which I chose in the first step.
Similarly, 3rd shoe in 6 and 4th shoe in 4 ways.
So total ways:
10*8*6*4 = 80 * 24 = 1920 ways.

But this is wrong.
Why? To understand that, let's see this simpler problem:
How many ways to choose 3 different digits from 1,2,3,4,5?
Correct answer: 5C3 = 10.
But if I say that first digit can be chosen in 5 ways, second in 4 and third in 3 and hence the total number of ways are 5*4*3 = 60? What's the mistake here?
The mistake is that we are counting ordered triplets.
We are treating 1,2,3 and 3,2,1 as distinct but they are the same.
So to fix it we divide it by 3! which is 6.
So 60/6 = 10 which is correct.

So we can fix our mistake which we made earlier if we divide our answer by 4!.
So correct answer will be 80.

A simpler way to solve the original problem is this:

First decide which 4 pairs you will pick in 5C4 ways.
Then pick one shoe from each pair in 2C1 ways.
So finally: 5C4*2C1*2C1*2C1*2C1 = 80. 80 is the right answer.

Q2: Find the number of words which can be made using all the letters of the word 'STRANGE' which neither start with 'S' nor end with 'E'.

Solution:
Total possible: 7!
- (Start with S and/or End with E)
Start with S = 6!
End  with E = 6!
Start with S AND End with E = 5!
7! - (6! + 6! - 5!)

Q3: If digits can't be repeated then how many 5 digits number which are divisible by 3, can be made using 0,1,2,3,4,7,8?

Solution 1:
Group numbers by %3.
0,3 => remainder 0
1,4,7 => remainder 1
2,8 => remainder 2

We can create numbers divisible by 3 using following combinations:
00111 => 2 digits with remainder 0 and 3 with remainder 1.
01122 => similarly explained.
There is no other way.

00111=> We have to make numbers with 0,3,1,4,7 which is 4*4!
01122 => We have to choose one digit with remainder 0, 2 with remainder 1, 2 with remainder 2.
3C2*2C2 for choosing non zero remainder digits.
For 0 remainder
case 1: we choose 3. So total ways 3*5!
case 2: we choose 0. So total ways 3*4*4!

Finally: 3*5! + 4*(4*4!) = 360 + 384 = 744.

Solution 2:
Sum all digits to get 25.
Keep removing 2 digits to get numbers divisible by 3.
Case 1: 24
Remove: 0,1 => 5!

Case 2: 21
Remove: 0,4 => 5!
Remove: 1,3 => 4*4!

Case 3: 18
Remove: 0,7 => 5!
Remove 3,4 => 4*4!

Case 4: 15
Remove: 2,8 => 4*4!
Remove: 3,7 => 4*4!

Total: 3*5! + 4(4.4!) = 744