Stirling numbers of the second kind and sampling with replacement

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).



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



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,

Indirect recursion using mXparser

Hello,

Today I will present how flexible mXparser really is. As an example we will approximate  and  using indirect recursion steps, which means two functions depending on each other. Let us start with a bit of theory starting with basic trigonometric identities:




Above formals can be equivalently written as




Please notice that knowing the solution for smaller value  it is possible to get solution for the original one .  This simply means that mentioned trigonometric identities are in fact example of recursion - here indirect recursion as  function is using , and  is using . The complete recursion definition requires base case definition (stop condition).

For  near to  function  can be well approximated exactly by , while in case of  constant  is pretty good approximation. This gives good stop condition.

For small  let us define two recursive functions:




Once again please notice that  (and  separately) is using both  and .

We expect that smaller parameter  is giving better approximations - below you will find functions graphs separately for  and .

import org.mariuszgromada.math.mxparser.*;
...
/* Recursive functions definition */
Constant a = new Constant("a", 0.1);
Function s = new Function("s(x) =  if( abs(x) < a, x, 2*s(x/2)*c(x/2) )", a);
Function c = new Function("c(x) =  if( abs(x) < a, 1, c(x/2)^2-s(x/2)^2 )", a);

/* Pointing that 's' is using 'c', and 'c' is using 's' */



Best regards,

mXparser - user defined functions applied to Fundamental theorem of calculus

Fundamental Theorem of Calculus is a kind of a link between two most important calculus concepts: derivative and integral.

Fundamental Theorem of Calculus - formal statement

For continuous real-valued function  defined on closed interval  let  be the function given by



The  is uniformly continuous on , differentiable on the open interval , and



Fundamental Theorem of Calculus - mXparser test

import org.mariuszgromada.math.mxparser.*;
...
/* Function */
Function f = new Function("f(x) = sin(x)");

/* Antiderivative */
Function F = new Function("F(x) = int(f(t), t, 0, x)", f);

/* function = derivative ( antiderivative ) */
Argument x = new Argument("x = pi");
Expression e = new Expression("f(x) - der(F(x), x)", x, f, F);
mXparser.consolePrintln("Res : " + e.getExpressionString() + " = " + e.calculate());
mXparser.consolePrintln("Computing time = " + e.getComputingTime() + " s.");

Res : f(x) - der(F(x), x) = 6.237833817291525E-8
Computing time = 0.411 s.


Best regards,