Animal vocal sequences including human speech are organized into hierarchical sequences composed of voice primitives. In human speech, these primitives are known as phonemes or phones. By contrast, the corresponding vocal primitives in animals have been poorly studied. What sets of vocal gestures span the vocal repertoire of an animal and what regularities apply to animal vocal repertoires across individuals and across species? In birdsong, the roughly hundred-millisecond long song syllables are often considered basic vocal units, since syllables display little acoustic variability within types but large differences across types. However, neurophysiology suggests that vocal units should be sought at a much finer 10-ms resolution imposed by the pace of neural dynamics. We propose a simple data-driven approach to song repertoires. Inspired by the minimum dominating set problem in computer science, we compute the repertoire of a song sequence as the minimum set of vocal exemplars that has the property that any short-time song spectrum lies within a distance $\delta$ of an exemplar. To good approximation, we find that for all $\delta$, the size of the zebra finch song repertoire obeys a power-law as a function of singing amount, similar to Heap’s power law of human language. By comparing repertoires and their scaling laws in diverse species, we provide insights into the hierarchical organization of animal vocalizations.