This project considers the theoretical limits of resource allocation overheads in vehicular ad hoc networks (VANETs), where the resource allocation procedure may consume extensive system resources. A permutation-based model is proposed to analyze the overhead limits where the unordered resource allocation patterns are considered as a permutation process. The minimum bits to represent the resource allocation information can be derived based on the permutation-based model. The bipartite graph is applied to describe the resource reuse in the respective domains for practical scenarios, and the dynamicity is taken into consideration. The proposed permutation-based model is applied to analyze the resource allocation overheads of two typical resource allocation schemes in VANETs: time-division multiple access (TDMA) and cluster-based algorithms. The proposed methodology provides new insights in a tradeoff analysis between overheads and system efficiency when analyzing the capacity of the VANETs.