Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I recently came upon a comment in the mathematics overflow stating that the infinite string of pi was similar to The Library of Babel. This library is a universe containing every possible combination of a 410 page book. There are a finite number of books and every book is unique. After doing a little digging, I found a website that allows a user to search for a specific string in the library and see how many books contain that string. Since the website was only for entertainment purposes, the number of matches changes every page refresh, even with the same search.

This got me thinking, is it possible to calculate how many books contain a give string? I came up with a formula, but I'm not entirely sure if it is correct.

General Information
Pages: 410
Letters Per Page: 3200
Max Length of Search String: (410 * 3200)
Total Characters: 30 (English Alphabet, space, comma, period, question mark)
Total Books: $30^{(3200*410)}$

Books With Search String:

$m = $ Max Possible Length of Search String = (410 * 3200)
$l = $ Length of Input Search String

$$\sum_{x=0}^{m - l}\left\{x!*30(m-l + 1)\right\}$$

share|improve this question
    
If you're interested in the "Library of Babel" en.wikipedia.org/wiki/The_Library_of_Babel –  Andrew Nov 2 '12 at 21:42
add comment

1 Answer

up vote 1 down vote accepted

The total number of 410 page books is "only" $30^{410\cdot 1600}$. Even if the books are doublesided, 410 are just 410 pages (printed on 205 sheets of paper, for simplicity). And there is no reason for a factorial here. The number of books with a given search string of length $l\le 410\cdot 1600$ at the very beginning is then $30^{410\cdot 1600-l}$. A first guess for the number of books with the given string at any position is then $$(410\cdot1600-l-1)\cdot30^{410\cdot 1600-l}.$$ However there is a tiny error (compared to the overall result): Books may contain a search string at several offsets; and to make things complicated: Whether or not the offsets in the same book may overlap, depends on the actual search pattern.

share|improve this answer
    
Good Call! I don't know why I placed that factorial there. I will edit my question and remove it. –  Dave C Nov 2 '12 at 19:06
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.