Exercises marked with (*) require further reading/search beyond the suggested texts.
1. What is Benzer's conservative estimate of the probability that a randomly chosen, symmetric, 19 x 19 binary matrix can be arranged in dictionary order?
Answer:
Prob [has dict order] ≤ (n!)^2 / 2^(n* (n-1) /2)
Using n = 19:
Prob ≤ (19!)^2 / 2^(19* 18 /2)
Prob ≤ 4,944 * 10^(-18)
© 2015 Joao Meidanis