What if it still took two individuals to reproduce?
I find it interesting that when we imagine more than two sexes, we assume that some n-way mating is required.
In the world of life on earth, we have examples where there are more than two sexes, such as slime molds. In these cases, it requires only that two individuals of different sexes mate to produce viable offspring. The main difference is that a greater percentage of the population is a potential mate. Unlike what Woody Allen wrote in "Annie Hall", "Bisexuality increases your chance of getting a date on Saturday night," these are heterosexual organisms, but with many sexes. Reviewing articles for this answer the number of sexes varies by species and study from 5 to thousands. The first number I remember was 13, so the odds are 12/13 that a random individual will be appropriate.
A driving factor in gender is protecting mitochondrial bodies from conflict. You can think of the entire cell, and all of reproduction, as a method through which mitochondria close themselves. The mitochondria of males are not passed to the offspring. Only the mitochondria in female cells are cloned. The whole gender we call male is, from the view of the mitochondria, sacrificed -- cut off from propagation -- by the benefits of having the female mitochondria cloned.
If the OP was considering a system like this, how does it affect the calculation?
The calculations haven't considered mitochondrial diseases in humans, which have several sources, including random mutations with each mitochondria, as well as changes in the cell nuclear DNA. Mitochondrial diseases that come from nuclear DNA follow the normal sexual inheritance pattern. Mutational mitochondrial diseases tend to result in early death, so probably impact the replacement rate but not the minimum population size.
If the number of sexes was high enough, the minimum size of the population would be cut in half. If we look at the problem as the number of different genotypes an individual might reproduce:
- Lower stable limit of reproduction partners: $L$
- The fraction with whom an individual may reproduce: $F = 1/2$
- Total population lower stable limit: $P = (1/F) * L$
If each member of a population could reproduce with $12/13$ths of the population:
- $P = (1/(12/13))*L$ or $(13*L)/12)$
Other answers have assumed $P=5000$, which for the 2-sex system gives $L = 2500$. Substituting $L$ into the 13-sex equation gives $P=5417$, which is a much more efficient population to support in a resource-constrained setting.