We use recent methods of algorithmics and combinatorics to compute exact (but slow) or approximate (but fast) statistics of number of occurrences of motifs in proteomes (set of proteins for one species). We demonstrate that statistical over- or under-representation of motifs in complete proteomes may be an indicator of whether, in that organism, we are looking at chance occurrences of the motif or whether the occurrences are sufficiently numerous to suggest a systematic, and thus functionally important occurrence. This has important implications on databank annotations.