When a mixture of particles, which differ in both their size and their density, avalanches downslope, the grains can either segregate into layers or remain mixed, dependent on the balance between particle-size and particle-density segregation. In this paper, binary mixture theory is used to generalize models for particle-size segregation to include density differences between the grains. This adds considerable complexity to the theory, since the bulk velocity is compressible and does not uncouple from the evolving concentration fields. For prescribed lateral velocities, a parabolic equation for the segregation is derived which automatically accounts for bulk compressibility. It is similar to theories for particle-size segregation, but has modified segregation and diffusion rates. For zero diffusion, the theory reduces to a quasilinear first-order hyperbolic equation that admits solutions with discontinuous shocks, expansion fans and one-sided semi-shocks. The distance for complete segregation is investigated for different inflow concentrations, particle-size segregation rates and particle-density ratios. There is a significant region of parameter space where the grains do not separate completely, but remain partially mixed at the critical concentration at which size and density segregation are in exact balance. Within this region, a particle may rise or fall dependent on the overall composition. Outside this region of parameter space, either size segregation or density segregation dominates and particles rise or fall dependent on which physical mechanism has the upper hand. Two-dimensional steady-state solutions that include particle diffusion are computed numerically using a standard Galerkin solver. These simulations show that it is possible to define a Péclet number for segregation that accounts for both size and density differences between the grains. When this Péclet number exceeds 10 the simple hyperbolic solutions provide a very useful approximation for the segregation distance and the height of rapid concentration changes in the full diffusive solution. Exact one-dimensional solutions with diffusion are derived for the steady-state far-field concentration.