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 Program needed . . . by Leming)

2       1
3       2
4       3
5       6
6       11
7       24
8       47
9       103
10      214
11      481
12      1030
13      2337
14      5131
15      11813
16      26329
17      60958
18      137821
19      321690
20      734428
21      1721998
22      3966556
23      9352353
24      21683445
25      51296030
26      119663812
27      284198136
28      666132304
29      1586230523
30      3734594241
31      8919845275
32      21075282588
33      50441436842
34      119586625008
35      286881743651
36      682038158682
37      1638972182530
38      3906927413303
39      9406152137879
40      22472056451247
41      54179250293408
42      129717291829971
43      313221456747456
44      751296610669843
45      1816290103898606
46      4364276162884639
47      10564366228522933
48      25423289186419875
49      61603562059151316
50      148469252145358808
51      360148324479758398
52      869106865433804787
53      2110095700233524285
54      5098455346557047973
55      12390057717097408538
56      29970227726060634017
57      72888562557661326864
58      176499842031226901381
59      429600857419170466984
60      1041278357437152358167
61      2536196542286478666139
62      6153056349381741585301
63      14997398318018924847928
64      36415646728341951903548
65      88812597580192574525063
66      215825550418242438223860
67      526698364894729912571199
68      1280889862705293577927296
69      3127554316181503287301649
70      7611480898206798369956079
71      18595392659190014140264908
72      45285076599371342669883879
73      110688203671795668277235660
74      269731061685359096419812596
75      659621468982340192204331003
76      1608347489785603397241511596
77      3934899947331339053124909760
78      9599957125050059282635482771
79      23497383827105781742164365797
80      57356780899998599652248264948
81      140445346913283003802613003390
82      343003250570726221462813158332
83      840230790925103153705975373025
84      2053039366403003049949666409068
85      5031007658238870403920117152710
86      12298660818108757545415589434116
87      30149320261600708547986929592390
88      73734219258619332834890575674726
89      180814310616014862689768523024832
90      442394836724735448917277216463620
91      1085229905277955181235904456588703
92      2656264327240487951606370531218366
93      6518016487344095077522813166239962
94      15960060530428381780150591272215609
95      39175508765992561988656569988484369
96      95960278101215884134653913840825280
97      235610003979934719849295201203681289
98      577332543305844394680393171492662521
99      1417925471818225717475443872638589060
100     3475608424184069405814897461789989796

making the answer 3,475,608,424,184,069,405,814,897,461,789,989,796.

 10   dim F(100)
 20   F(1)=1
 30   for I=2 to 100
 40     T=F(I-1)
 50     J=I-2:K=1
 60     while J>=K
 70        T=T+F(J)*F(K)
 75        J=J-1:K=K+1
 80     wend
 85     F(I)=T
 90     print I,T
100   next

 

Posted by Charlie on 2006-11-20 14:39:01