use strict; use warnings; my ($n, $k) = (20, 11); print "S($n, $k) = ", S_formulaic($n, $k), "\n"; print "S($n, $k) = ", S_recursive($n, $k), "\n"; sub S_recursive { my ($n, $k) = @_; return 1 if $n == 0 && $k == 0; return 0 if $k == 0; return 1 if $k == 1; return 1 if $n == $k; return S_recursive($n - 1, $k - 1) + $k * S_recursive($n - 1, $k); } sub S_formulaic { my ($n, $k) = @_; my $sum = 0; for my $j (0 .. $k) { $sum += (-1) ** ($k - $j) * C($k, $j) * $j ** $n; } return (1 / fact($k)) * $sum; } sub C { my ($n, $k) = @_; my $p = 1; $p *= $_ for ($n - $k + 1) .. $n; return $p / fact($k); } sub fact { my ($n) = @_; my $p = 1; $p *= $_ for 2 .. $n; return $p; }