Sampling With and Without Replacement¶

Definition¶

Let $A$ be a finite set of $n$ distinct objects, and draw $k$ of them one at a time.

With replacement: each drawn object is put back before the next draw, so the same object can be drawn more than once.
Without replacement: drawn objects are removed, so all $k$ drawn objects are distinct and $k\le n$ $n$ .

A sample is ordered if the order of the draws is recorded, and unordered if only which objects were drawn (with their multiplicities) matters.

Interpretation¶

The two choices give four counting problems. Ordered samples are counted with the multiplication rule; an unordered sample without replacement is a combination, obtained from the ordered count by dividing out the $k!$ orders of the same $k$ objects.

Two-by-two table of the counts for drawing 3 of 10 tickets: 1000 and 720 ordered samples, 220 and 120 unordered, with an arrow dividing 720 by 3! to get 120.

The table places the four counts of the first example, $k=3$ draws from $n=10$ tickets, in a grid: the columns say whether drawn tickets are put back, the rows whether the order is recorded. Only in the column without replacement does every unordered sample come from exactly $3!=6$ ordered ones, so dividing $720$ by $3!$ gives $\binom{10}{3}=120$ $120$ . With replacement the same division fails, because $1000/3!$ is not even an integer: a sample with repeats has fewer than $3!$ orders, which is why the $220$ unordered samples with replacement are not equally likely.

With replacement, every draw faces the same $n$ objects, so the history of earlier draws changes nothing; in the language of Week 2, the draws are independent with the same distribution. Without replacement, each draw changes what remains, so the draws are dependent: after a red ball is removed, a second red ball is less likely.

Draw $n$ balls from an urn with $N$ balls, $K$ of them white, and count the white balls drawn. Both counts have mean $nK/N$ , but without replacement the variance carries the extra factor $(N-n)/(N-1)$ $1)$ . Make $N$ large compared with $n$ and the two distributions merge.

Two common slips are worth naming. First, "without replacement" does not by itself mean "unordered": dealing cards one by one is ordered sampling without replacement, and a hand of cards is the unordered version of the same experiment. Second, the unordered samples with replacement must not be treated as equally likely, as the Key Results explain.

Key Results¶

The number of possible samples of size $k$ from $n$ distinct objects is:

ordered, with replacement: $n^k$ ;
ordered, without replacement: $n(n-1)\cdots(n-k+1)=n!/(n-k)!$ $k)!$ , the number of $k$ -permutations; it is $0$ when $k>n$ $n$ ;
unordered, without replacement: the binomial coefficient $\binom{n}{k}$ ;
unordered, with replacement: $\binom{n+k-1}{k}$ , by stars and bars.

In the first three cases every sample is equally likely when each draw is uniform, so naive probability applies. The unordered samples with replacement are not equally likely, so probabilities should be computed from ordered samples instead.

Each ordered sample without replacement corresponds to exactly $k!$ orderings of one unordered sample, so $\binom{n}{k}=\dfrac{n!}{k!\,(n-k)!}$ $\frac{n !}{k ! ( n - k )!}$ .
Without replacement, the $j$ th draw on its own is still uniform over all $n$ objects: by symmetry, as many ordered samples have a given object in place $j$ as in place $1$ . Only the joint behaviour of the draws differs from sampling with replacement.
A particular object is included in the sample with probability $k/n$ without replacement and $1-(1-1/n)^k$ with replacement; the latter is smaller for $k\ge2$ $2$ , because repeats waste draws.
With replacement, all $k$ draws are distinct with probability $n(n-1)\cdots(n-k+1)/n^k$ $1) / n^{k}$ , the ratio of the two ordered counts.

Looking ahead to Week 3: if $n$ balls are drawn from an urn with $N$ balls, $K$ of them white, the number of white balls drawn has the binomial distribution $\operatorname{Bin}(n,K/N)$ with replacement and the hypergeometric distribution without replacement. Both have mean $nK/N$ ; sampling without replacement has the smaller variance, and the two are close when $N$ is large compared with $n$ .

Examples¶

Choosing $3$ of $10$ numbered tickets gives $10^3=1000$ ordered samples with replacement, $10\cdot9\cdot8=720$ ordered samples without replacement, $\binom{10}{3}=120$ unordered samples without replacement, and $\binom{12}{3}=220$ unordered samples with replacement.
In the same setting, ticket number $7$ is among the three draws with probability $3/10=0.3$ without replacement, and $1-0.9^3=0.271$ with replacement.
An urn holds $20$ balls, $8$ of them red, and $6$ are drawn. The probability of no red ball is $0.6^6\approx0.0467$ with replacement, but $\binom{12}{6}/\binom{20}{6}=924/38760\approx0.0238$ without replacement.
From the same urn, two balls are drawn without replacement. Of the $20\cdot19=380$ ordered pairs, $8\cdot7=56$ are red–red and $12\cdot8=96$ are non-red–red, so the second ball is red with probability $152/380=0.4=8/20$ $8/20$ , the same as the first.
Two draws with replacement from $\{1,2\}$ give the $\binom{3}{2}=3$ unordered samples $\{1,1\}$ , $\{1,2\}$ and $\{2,2\}$ , but with probabilities $\tfrac{1}{4},\tfrac{1}{2},\tfrac{1}{4}$ : the mixed sample arises from the two ordered samples $(1,2)$ and $(2,1)$ .
In the birthday problem, assigning birthdays to $k$ people is ordered sampling with replacement from $365$ days ( $365^k$ outcomes), and all birthdays distinct is ordered sampling without replacement. Hence

\mathbb{P}(\text{no match})=\frac{365!/(365-k)!}{365^k}.

Prerequisites¶

Sources¶

Probability Theory for EOR · Week 1
Probability Theory for EOR · Week 3 (binomial and hypergeometric distributions)

Aliases: sampling with replacement, sampling without replacement, ordered and unordered samples Keywords: sampling table, urn model, drawing with replacement, drawing without replacement, n^k, ordered sample, unordered sample

Last updated: 17 October 2026 21:53