A programming exercise

I. Cnop
icnop@vub.ac.be

Counting onto maps

Stirling numbers

Built-in StirlingS2

Look up in Help:

StirlingS2

StirlingS2[15, 7]

Table[StirlingS2[m, n], {m, 30}, {n, m}] // TableForm

Traditional notation

(Subscript[𝒮, 7]^((4)))

Counting surjective maps is done by multiplying with n! (factorial)

% 4!

Table[n! StirlingS2[m, n], {m, 30}, {n, m}] // 
      TableForm

n =. ;

A plot in Logarithmic scale (on the value axis)

ListPlot3D[Table[Log[StirlingS2[m, n]], {m, 40}, {n, 40}]]

ListPlot3D[
      Table[Log[10, StirlingS2[m, n]], {m, 40}, {n, 40}]]

Dit geeft het aantal cijfers weer

Recursive definition

It can easily be proved that these numbers satisfy the following relations

Clear[s]

Fix initial values:

s[m_, 1] := 1;

Sine there are no surjections for  the initial number  m smaller than the goal size  n  and there is only 1 up to permutations for   m = n

s[m_, m_] := 1;

For fixed  m  we have the following relation

s[m_, n_] := s[m, n] = s[m - 1, n - 1] + n s[m - 1, n]

This allows to compute Stirling numbers line by line

Timing[s[15, 7]]

Timing[s[125, 12]]

So this is fast!

Table[s[m, n], {m, 28}, {n, m}] // TableForm