We use a combinatorial approach to obtain exact expressions for the many-body density of states of fermionic and bosonic gases with equally spaced single-particle spectra. We identify a mapping that reveals a remarkable property, namely, fermionic and bosonic gases have the same many-body density of states, up to a shift corresponding to ground state energy. Additionally, we show that there is a regime, comprising the validity range of the Bethe approximation, where the many-body density of states becomes independent of the number of particles.