Exact calculation of pattern probabilities

We describe two algorithms for calculating the probability of m-symbol length-n patterns over k-element distributions, a partition-based algorithm with complexity roughly 2^{O(m log m)} and a recursive algorithm with complexity roughly 2^{O(m+log n)} with the precise bounds provided in the text. The problem is related to symmetric-polynomial evaluation, and the analysis reveals a connection to the number of connected graphs.