# How to calculate inclusion probability under sampling without replacement

I am quite new to sampling method.

The task is sampling without replacement with unequal probabilities, but I have problem in calculating inclusion probability.

I want to sample $n$ units from the population of size $N$ through the following procedure in the figure. After the procedure, I need to calculate the inclusion probability in order to get the Horvits-Tompson estimator, an unbiased estimator of the Population Total.

But I don't know how to calculate inclusion probability, because I need to traverse $n!\binom{N-1}{n-1}$ n-tuples (e.g. add the probability of $50!\binom{999}{49}$ n-tuples), it's huge and not realistic!!!

My ultimate goal is to have an unbiased estimator of the Population Total, based on $p_i(k)$ constructed by myself.

How can I do this?

The inclusion probability is also written as the following $p(u_i)$:

$p(i) = \sum_{(i_1, i_2, ..., i_n)\in S(i)}{p(i_1, i_2, ..., i_n)}$ where $S(i)$ is consisting of n-tuples where unit $i$ and other $(n-1)$ different units . There are $n!\binom{N-1}{n-1}$ elements in $S(i)$!

The formula is from paper: SAMPLING WITH VARYING PROBABILITIES WITHOUT REPLACEMENT: ROTATING AND NON-ROTATING SAMPLES.