Abstract: Cultural symbol systems such as language, music, or pictorial diagrams are crucial for the storage and transmission of knowledge, ultimately underpinning our capacity for culture. From phonemes in spoken words to notes in a melody or the lines of a diagram, one important feature of such systems is their combinatorial structure: the reuse of building blocks to compose new concepts. The evolution of combinatorial systems is an important area of study because it can help us understand how these systems have become such effective tools in human culture. However, there is a puzzle concerning why combinatorial systems are not more widespread, despite their apparent advantages. This thesis presents work from three studies that contribute to a solution to this puzzle in improving our understanding of how combinatorial systems arise. The first study, using an iterated learning experiment with a virtual whistle as signal-transmission modality, shows that communication systems often begin as iconic, using form-meaning mappings based on resemblance rather than conventions, but trend toward the use of combinatorial structure over time. The second study combines iterated learning with a communication game to show that combinatorial structure is not an inevitable feature of symbol systems, but rather a solution to trading off the simplicity of a repertoire of behaviors and the amount of information they convey. The third study presents a neuro-symbolic generative model, which accounts for the structured generalizations demonstrated by humans in the previous two studies, showing that neural network models without appropriate inductive biases fail to produce the same generalizations. Taken together, this work advances our theoretical understanding of why and how combinatorial structure arises, and sheds light on how symbol systems such as language could have become such powerful and flexible tools for communication and human culture.