sampling with and without replacement

Picture a bag of numbered balls. You draw some out. Two very different rules can govern the draws. Sampling WITH replacement: after each draw you note the ball, then PUT IT BACK and shake, so the same ball can appear again and every draw faces the identical bag. Sampling WITHOUT replacement: once drawn, a ball stays out, so it cannot reappear and the bag shrinks with each draw. This single choice changes the counts and the probabilities, sometimes dramatically.

Counting reflects the rule. With replacement, every one of k draws independently sees all n balls, so the number of ordered outcomes is n times n times ... = n^k, and each draw is independent of the others with unchanging probabilities. Without replacement, the first draw sees n, the second n-1, and so on, giving n times (n-1) times ... times (n-k+1) = n!/(n-k)! ordered outcomes; here draws are dependent, since earlier draws change what is left. For example, drawing 2 balls from {1,2,3} with replacement gives 3^2 = 9 ordered results; without replacement gives 3 times 2 = 6.

Why it matters: 'without replacement' is the difference between the binomial and hypergeometric distributions, between a fair raffle and repeated independent trials, and is the reason the birthday problem works (people are sampled birthdays without replacement when we ask for a match). A useful intuition: when the bag is huge compared with how many you draw, with and without replacement give nearly the same answer, because removing a few barely changes the bag — that is why the hypergeometric distribution approaches the binomial for large populations.