Repertoire size is generally used to describe the complexity of bird song, and it can be estimated by counting the number of unique song elements (i.e. syllables). However, the counting approach reflects how researchers work with complex songs, but it does not necessary describe biological functions. Given the constraints of mate sampling, in species with complex songs, females are unlikely to count and compare the full repertoire of all singing males. They are more likely to rely on patterns that are qualitatively comparable between individuals and can be evaluated during short sampling sessions. The study of such structural patterns requires knowledge about the full repertoire of the population. Based on a computerized syllable coding system, we have created a syllable library for a Hungarian population of the Collared Flycatcher Ficedula albicollis, which allowed us to define variables by considering the entire repertoire of the species. These variables include the occurrence of rare and common syllables within individual repertoires, the degree of linkage of syllables within and between singing bouts, the evenness of the distribution of syllables across songs (entropy), the degree of syntactical variety, the rate of syllable sharing between individuals. We show that these song variables can predict repertoire size (i.e. song complexity), and could be reliably assessed from small samples of songs. They also correlate with mating success and measures of male quality. Therefore, we infer that by considering the species’ entire repertoire, short-term patterns of syllable use may be important feature from the listener’s perspective.