Answer to Question #281726 in Discrete Mathematics for Neha

Question

A man, a woman, a boy, a girl, a dog, and a cat are walking down a long and

winding road one after the other.

(a) In how many ways can this happen?

(b) In how many ways can this happen if the dog comes first?

(c) In how many ways can this happen if the dog immediately follows the boy?

(d) In how many ways can this happen if the dog (and only the dog) is between

the man and the boy?

Answer 1

(a) In how many ways can this happen?

Soln: There are 6 ! = 720 ways for six creatures to form a line

(b) In how many ways can this happen if the dog comes first?

Soln: If the dog comes first, the others can form 5 ! lines behind=120 ways

(c) In how many ways can this happen if the dog immediately follows the boy?

Soln:If the dog immediately follows the boy, then the dog-boy pair should be thought of as a single object to be put into a line with four others. There are 5 ! = 120 such lines. 

(d) In how many ways can this happen if the dog (and only the dog) is between

Soln:If the man, dog, and boy appear in this order, then thinking of man-dog-boy as a single object to be put into a line with three others, we see that there are 4 ! possible lines. Similarly, there are 4 ! lines in which the boy, dog, and man appear in this order. So, by the addition rule, there are 4 ! + 4 ! = 48 lines in which the dog (and only the dog) is between the man and the boy.