### Sampling with replacement

Some time ago I considered the * problem of sampling with replacement* exactly

**n**-elements from

**n**-element set. As a result of such an operation output set may contains duplicates – let us here assume that we received exactly

**k**unique elements (of course 1 ≤ k ≤ n). Then the question came:

### Number of ways with k-unique outputs

**What is the number of ways to obtain exactly k unique elements sampling with replacement n-elements from n-element set?**

Above question relates to * bootstrap estimation*, as the answer gives distribution of unique elements (its number) in bootstrap samples.

Let * B(n,k)* be the function representing the number of such ways.

### 1st step – partial permutation (k-permutation of n aka variation without repetition)

Pretty standard – the number of ways to choose **k** different elements of n paying attention to the order – this is a variation without repetition * V(n,k)*.

$$V(n,k)=\frac{n!}{(n-k)!}$$

### 2nd step – Stirling numbers of the second kind

Let us think form the other perspective, forgetting for a moment about just sampled **k** unique elements and the need of additional **n-k** (though it’s true). Instead let’s imagine that we have **n** items, including **k** unique. The trick is now to understand that having **k** different elements in a set of **n** elements is generating division of original set into **k** non-empty disjunctive subsets. How many ways to divide **n**-element set into k-subsets? This is the Stirling number of the second kind marked * S2 (n, k).* Finally

$$B(n,k)=V(n,k)\times S_2(n,k)$$

### mXparser – Math Parser – definition

import org.mariuszgromada.math.mxparser.*; ... Function V = new Function("V(n,k) = n! / (n-k)!"); Function B = new Function("B(n,k) = V(n,k) * Stirl2(n,k)", V); int n = 5; for (int k = 0; k <= n; k++) mXparser.consolePrintln("B(" + n + "," + k + ") = " + B.calculate(n,k) );

Result

[mXparser-v.2.3.1] B(5,0) = 0.0 [mXparser-v.2.3.1] B(5,1) = 5.0 [mXparser-v.2.3.1] B(5,2) = 300.0 [mXparser-v.2.3.1] B(5,3) = 1500.0 [mXparser-v.2.3.1] B(5,4) = 1200.0 [mXparser-v.2.3.1] B(5,5) = 120.0

Best regards,

*Mariusz Gromada*