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 re(2): Program needed . . . by Federico Kereki)

then we get

2       1
3       2
4       3
5       6
6       11
7       23
8       46
9       98
10      207
11      451
12      983
13      2179
14      4850
15      10905
16      24631
17      56011
18      127912
19      293547
20      676157
21      1563372
22      3626149
23      8436379
24      19680277
25      46026618
26      107890609
27      253450711
28      596572387
29      1406818759
30      3323236238
31      7862958391
32      18632325319
33      44214569100
34      105061603969
35      249959727972
36      595405363473
37      1419855914607
38      3389524479050
39      8099766813570
40      19374186136140
41      46384328517112
42      111146809165122
43      266552682265118
44      639754054803187
45      1536638374367584
46      3693555574543651
47      8884204649055027
48      21383602613828364
49      51501493576783437
50      124115016908960463
51      299284329327592851
52      722086038540594854
53      1743130822668362889
54      4210157426126929793
55      10173859583519033930
56      24597126243198759014
57      59495869434450194896
58      143974655017644718094
59      348558271005906100616
60      844206159208807054529
61      2045499569096283221895
62      4958179972866730572551
63      12022969328821086710364
64      29165037890838539578082
65      70773347864023719770582
66      171802146496610097519585
67      417190639528111446770779
68      1013405655241184415852284
69      2462468880790152941279280
70      5985395828928747830707833
71      14552778100739451597075215
72      35393719712730809489290451
73      86105380575713265798811097
74      209534148915752971906161599
75      510030986091596821585587504
76      1241802284488914041806071461
77      3024262793585753830542718048
78      7367072230435035735914703359
79      17950473826186485808766524097
80      43748166298406074100165156764
81      106645908705895186413843585533
82      260031824362822308996718870500
83      634168120133303611054509027359
84      1546947706732104170486643361489
85      3774313656277441559498755236651
86      9210630365092252808401739685165
87      22481624182119802928656075014331
88      54884662988678948399811499433020
89      134016230818483951131182484937715
90      327299265300988751439224581625959
91      799488296094557358578760802052204
92      1953245860469458186958527594063777
93      4772849784961405441248983134896131
94      11664686021905422496334056044980747
95      28512887984332668599209035723441823
96      69707693362642383731710653732858756
97      170447287925675703040430908531836451
98      416838603237108467066464398213155878
99      1019560119620720464013531852138491082
100     2494155217372585318678938493802359939

giving

2,494,155,217,372,585,318,678,938,493,802,359,939

Sloane's A001190.

   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
   65      if J=K then T=T+F(J)*(F(K)+1)//2
   70       :else 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

Edited on November 20, 2006, 3:58 pm

Posted by Charlie on 2006-11-20 15:52:58