Hard to count subsets

Question

Suppose $\mathcal{B}=\{0,1\}^N$ is the set of binary sequences of length $N$. I am looking for examples of subsets $\mathcal{A}\subset \mathcal{B}$ which are easy to describe, in the sense that all sequences in $\mathcal{A}$ have some common property easy to define, but which are very hard to count, i.e. calculating the size of $\mathcal{A}$ would require writing a complicated program, preferably more complicated than a dynamic programming algorithm. Is there any official list with examples of such sets ?

Answer 1

How about sets where consecutive blocks of ones have different size.