Combining two things can create amazing new things - whether mixing water and flour or feeding large datasets into neural networks. Hypothesizing rules and theories for recombination, testing those hypotheses, and communicating our findings to each other are key cognitive mechanisms that allow us to navigate an open-ended world of possible combinations. However, in contrast to this open-ended and highly-complex search problem, cognition is constrained by its capacity. Using ideas from information theory, we hypothesize that the compressibility of recombination rules predicts how successfully people find and use these rules. In a combinatorial discovery game, we find that people indeed learn quicker and collect more points when the rules are more compressible. Interestingly, people use fewer words to communicate their findings when the rules are either too easy or too hard to compress, revealing an inverse-U shaped relationship between compressibility and communication effort.