For the equal probability/frequency case, this approach may work for you. 

Let $K$ be the total sample size, $N$ be the number of different items observed, $N_1$ be the number of items seen once, $N_2$ be the number of items seen twice, $A=N_1(1− {N_1 \over K} )+2N_2,$ and $\hat Q = {N_1 \over K}.$ 
 
Then an approximate 95% confidence interval on the total population size $n$  is given by 

$$ \hat n_{Lower}={1 \over {1-\hat Q+{1.96 \sqrt{A} \over K} }}$$

$$\hat n_{Upper}={1 \over {1-\hat Q-{1.96 \sqrt{A} \over K} }}$$
    
When implementing, you may need to adjust these depending on your data. 

The method is due to Good and Turing. A reference with the confidence interval is Esty, $\it{The \ Annals \ of \ Statistics},$ 1983 [1]. 

For the more general problem, Bunge has produced free software that produces several estimates. Search with his name and the word CatchAll. 



[1] Esty, Warren W. (1983),  
"A Normal Limit Law for a Nonparametric Estimator of the Coverage of a Random Sample"  
Ann. Statist., Volume 11, Number 3, 905-912.  
https://projecteuclid.org/euclid.aos/1176346256