Question

Using the nouns N = {man, rat, horse, flea} and the verbs V = {bites, eats, kicks}, how many "sentences" of the form noun verb noun are there, with the restriction that every word in the sentence has a different length? (For example, "man eats horse" is such a sentence, but "rat bites man" is not, because it contains two words of length three.) Use a decision tree to arrive at your answer.

Answer 1

Given set of the nouns N = {man, rat, horse, flea} and the verbs V = {bites, eats, kicks}.

The number of sentences of the form "noun verb noun" such that each word in a sentence is of different length can be given by the decision tree in the following diagram.

The number of leaves in the decision tree are the number of required sentences. The answer is 12.