MathDB

A binary decision tree is a list of

n

yes/no questions, together with instructions for the order in which they should be asked (without repetition). For instance, if

n = 3

, there are

12

possible binary decision trees, one of which asks question

2

first, then question

3

(followed by question

1

) if the answer was yes or question

1

(followed by question

3

) if the answer was no. Determine the greatest possible

k

such that

2^k

divides the number of binary decision trees on

n = 13

questions.

Problem Statement