Try this beautiful problem from the Pre-RMO, 2017 based on Number of ways.
There are five cities A, B, C, D, E on a certain island. Each city is connected to every other city by road, find numbers of ways can a person starting from city A come back to A after visiting some cities without visiting a city more than once and without taking the same road more than once. (The order in which he visits the cities such as A \(\rightarrow\) B \(\rightarrow\) C \(\rightarrow\) A and A \(\rightarrow\) C \(\rightarrow\) B \(\rightarrow\) A are different).
Number of ways
Integers
Combinatorics
But try the problem first...
Answer: is 60.
PRMO, 2017, Question 9
Combinatorics by Brualdi
First hint
A B C D E in this way orderwise such that from A person can visit B,C return to A in $4 \choose 2$ with 2! ways of approach
from A person visits B, C, D comes back to A in $4 \choose 3$ with 3! ways of approach
from A person visits B, C, D, E comes back to A in $4 \choose 4$ with 4! ways of approach
Second Hint
ways=\({4 \choose 2}(2!)+{4 \choose 3}(3!)+{4 \choose 4}(4!)\)
Final Step
=12+24+24
=12+48
=60.
Try this beautiful problem from the Pre-RMO, 2017 based on Number of ways.
There are five cities A, B, C, D, E on a certain island. Each city is connected to every other city by road, find numbers of ways can a person starting from city A come back to A after visiting some cities without visiting a city more than once and without taking the same road more than once. (The order in which he visits the cities such as A \(\rightarrow\) B \(\rightarrow\) C \(\rightarrow\) A and A \(\rightarrow\) C \(\rightarrow\) B \(\rightarrow\) A are different).
Number of ways
Integers
Combinatorics
But try the problem first...
Answer: is 60.
PRMO, 2017, Question 9
Combinatorics by Brualdi
First hint
A B C D E in this way orderwise such that from A person can visit B,C return to A in $4 \choose 2$ with 2! ways of approach
from A person visits B, C, D comes back to A in $4 \choose 3$ with 3! ways of approach
from A person visits B, C, D, E comes back to A in $4 \choose 4$ with 4! ways of approach
Second Hint
ways=\({4 \choose 2}(2!)+{4 \choose 3}(3!)+{4 \choose 4}(4!)\)
Final Step
=12+24+24
=12+48
=60.
