In the "Your own adventure" books, the reader starts at page 1, and every page either (1) ends the story, or (2) sends him to another page, or (3) offers a choice among two possible pages.

Knowing that:

each page can be reached from only one other page -- except for the 1st page, that cannot be reached from any page;

that all pages can eventually be reached by picking an appropriate path from page 1;

that if a book can be converted into another just by reordering choices and renumbering pages, they are considered to be the same;

and that these books are always 100 pages long...

How many essentially different books can be published?

(In reply to maybe solution by Charlie)

For 5 pages, I think there would be 6 possibilities rather than the 5 predicted by the Fibonacci series:

Straight through, 1,2,3,4,5.

One branch of 1 page off a mainline of 4, with the branch being off the first, second or third page. This is 3 more.

A branch from the first page that leads to two sets of two pages each without branch.

A brance from the first page leading on the one hand to an ending and on the other to a 2-branch.

With 1,1,2,3,6, it starts to look like Sloan A003214, Number of binary forests with n nodes.

Posted by Charlie on 2006-11-20 12:25:05