Stirling numbers of the second kind: Difference between revisions
No edit summary |
m (→{{header|ALGOL 68}}: Removed unneeded semi-colon) |
||
| Line 120: | Line 120: | ||
FOR n FROM 0 TO max n - 1 DO |
FOR n FROM 0 TO max n - 1 DO |
||
FOR k FROM 1 TO n DO |
FOR k FROM 1 TO n DO |
||
s2[ n + 1, k ] := k * s2[ n, k ] + s2[ n, k - 1 ] |
s2[ n + 1, k ] := k * s2[ n, k ] + s2[ n, k - 1 ] |
||
OD |
OD |
||
OD; |
OD; |
||
Revision as of 16:19, 13 June 2021
You are encouraged to solve this task according to the task description, using any language you may know.
Stirling numbers of the second kind, or Stirling partition numbers, are the number of ways to partition a set of n objects into k non-empty subsets. They are closely related to Bell numbers, and may be derived from them.
Stirling numbers of the second kind obey the recurrence relation:
S2(n, 0) and S2(0, k) = 0 # for n, k > 0 S2(n, n) = 1 S2(n + 1, k) = k * S2(n, k) + S2(n, k - 1)
- Task
- Write a routine (function, procedure, whatever) to find Stirling numbers of the second kind. There are several methods to generate Stirling numbers of the second kind. You are free to choose the most appropriate for your language. If your language has a built-in, or easily, publicly available library implementation, it is acceptable to use that.
- Using the routine, generate and show here, on this page, a table (or triangle) showing the Stirling numbers of the second kind, S2(n, k), up to S2(12, 12). it is optional to show the row / column for n == 0 and k == 0. It is optional to show places where S2(n, k) == 0 (when k > n).
- If your language supports large integers, find and show here, on this page, the maximum value of S2(n, k) where n == 100.
- See also
- Related Tasks
11l
<lang 11l>[(Int, Int) = BigInt] computed
F sterling2(n, k)
V key = (n, k)
I key C :computed
R :computed[key]
I n == k == 0
R BigInt(1)
I (n > 0 & k == 0) | (n == 0 & k > 0)
R BigInt(0)
I n == k
R BigInt(1)
I k > n
R BigInt(0)
V result = k * sterling2(n - 1, k) + sterling2(n - 1, k - 1)
:computed[key] = result
R result
print(‘Stirling numbers of the second kind:’) V MAX = 12 print(‘n/k’.ljust(10), end' ‘’) L(n) 0 .. MAX
print(String(n).rjust(10), end' ‘’)
print() L(n) 0 .. MAX
print(String(n).ljust(10), end' ‘’)
L(k) 0 .. n
print(String(sterling2(n, k)).rjust(10), end' ‘’)
print()
print(‘The maximum value of S2(100, k) = ’) BigInt previous = 0 L(k) 1 .. 100
V current = sterling2(100, k)
I current > previous
previous = current
E
print("#.\n(#. digits, k = #.)\n".format(previous, String(previous).len, k - 1))
L.break</lang>
- Output:
Stirling numbers of the second kind: n/k 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 1 0 1 2 0 1 1 3 0 1 3 1 4 0 1 7 6 1 5 0 1 15 25 10 1 6 0 1 31 90 65 15 1 7 0 1 63 301 350 140 21 1 8 0 1 127 966 1701 1050 266 28 1 9 0 1 255 3025 7770 6951 2646 462 36 1 10 0 1 511 9330 34105 42525 22827 5880 750 45 1 11 0 1 1023 28501 145750 246730 179487 63987 11880 1155 55 1 12 0 1 2047 86526 611501 1379400 1323652 627396 159027 22275 1705 66 1 The maximum value of S2(100, k) = 7769730053598745155212806612787584787397878128370115840974992570102386086289805848025074822404843545178960761551674 (115 digits, k = 28)
ALGOL 68
Uses the LONG LONG INT mode of Algol 68g which allows large precision integers. As the default precision of LONG LONG INT is too small, the precision is specified via a pragmatic comment. <lang algol68>BEGIN
# show some Stirling numbers of the second kind #
# specify the precision of LONG LONG INT, somewhat under 160 digits are # # needed for Stirling numbers of the second kind with n, k = 100 # PR precision 160 PR MODE SINT = LONG LONG INT;
# returns a triangular matrix of Stirling numbers up to max n, max n #
PROC make s2 = ( INT max n )REF[,]SINT:
BEGIN
REF[,]SINT s2 := HEAP[ 0 : max n, 0 : max n ]SINT;
FOR n FROM 0 TO max n DO FOR k FROM 0 TO max n DO s2[ n, k ] := 0 OD OD;
FOR n FROM 0 TO max n DO s2[ n, n ] := 1 OD;
FOR n FROM 0 TO max n - 1 DO
FOR k FROM 1 TO n DO
s2[ n + 1, k ] := k * s2[ n, k ] + s2[ n, k - 1 ]
OD
OD;
s2
END # make s2 # ;
# task requirements: #
# print Stirling numbers up to n, k = 12 #
BEGIN
INT max stirling = 12;
REF[,]SINT s2 = make s2( max stirling );
print( ( "Stirling numbers of the second kind:", newline ) );
print( ( " k" ) );
FOR k FROM 0 TO max stirling DO print( ( whole( k, -10 ) ) ) OD;
print( ( newline, " n", newline ) );
FOR n FROM 0 TO max stirling DO
print( ( whole( n, -2 ) ) );
FOR k FROM 0 TO n DO
print( ( whole( s2[ n, k ], -10 ) ) )
OD;
print( ( newline ) )
OD
END;
# find the maximum Stirling number with n = 100 #
BEGIN
INT max stirling = 100;
REF[,]SINT s2 = make s2( max stirling );
SINT max 100 := 0;
FOR k FROM 0 TO max stirling DO
IF s2[ max stirling, k ] > max 100 THEN max 100 := s2[ max stirling, k ] FI
OD;
print( ( "Maximum Stirling number of the second kind with n = 100:", newline ) );
print( ( whole( max 100, 0 ), newline ) )
END
END</lang>
- Output:
Stirling numbers of the second kind: k 0 1 2 3 4 5 6 7 8 9 10 11 12 n 0 1 1 0 1 2 0 1 1 3 0 1 3 1 4 0 1 7 6 1 5 0 1 15 25 10 1 6 0 1 31 90 65 15 1 7 0 1 63 301 350 140 21 1 8 0 1 127 966 1701 1050 266 28 1 9 0 1 255 3025 7770 6951 2646 462 36 1 10 0 1 511 9330 34105 42525 22827 5880 750 45 1 11 0 1 1023 28501 145750 246730 179487 63987 11880 1155 55 1 12 0 1 2047 86526 611501 1379400 1323652 627396 159027 22275 1705 66 1 Maximum Stirling number of the second kind with n = 100: 7769730053598745155212806612787584787397878128370115840974992570102386086289805848025074822404843545178960761551674
C
<lang c>#include <stdbool.h>
- include <stdio.h>
- include <stdlib.h>
typedef struct stirling_cache_tag {
int max; int* values;
} stirling_cache;
int stirling_number2(stirling_cache* sc, int n, int k) {
if (k == n)
return 1;
if (k == 0 || k > n || n > sc->max)
return 0;
return sc->values[n*(n-1)/2 + k - 1];
}
bool stirling_cache_create(stirling_cache* sc, int max) {
int* values = calloc(max * (max + 1)/2, sizeof(int));
if (values == NULL)
return false;
sc->max = max;
sc->values = values;
for (int n = 1; n <= max; ++n) {
for (int k = 1; k < n; ++k) {
int s1 = stirling_number2(sc, n - 1, k - 1);
int s2 = stirling_number2(sc, n - 1, k);
values[n*(n-1)/2 + k - 1] = s1 + s2 * k;
}
}
return true;
}
void stirling_cache_destroy(stirling_cache* sc) {
free(sc->values); sc->values = NULL;
}
void print_stirling_numbers(stirling_cache* sc, int max) {
printf("Stirling numbers of the second kind:\nn/k");
for (int k = 0; k <= max; ++k)
printf(k == 0 ? "%2d" : "%8d", k);
printf("\n");
for (int n = 0; n <= max; ++n) {
printf("%2d ", n);
for (int k = 0; k <= n; ++k)
printf(k == 0 ? "%2d" : "%8d", stirling_number2(sc, n, k));
printf("\n");
}
}
int main() {
stirling_cache sc = { 0 };
const int max = 12;
if (!stirling_cache_create(&sc, max)) {
fprintf(stderr, "Out of memory\n");
return 1;
}
print_stirling_numbers(&sc, max);
stirling_cache_destroy(&sc);
return 0;
}</lang>
- Output:
Stirling numbers of the second kind: n/k 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 1 0 1 2 0 1 1 3 0 1 3 1 4 0 1 7 6 1 5 0 1 15 25 10 1 6 0 1 31 90 65 15 1 7 0 1 63 301 350 140 21 1 8 0 1 127 966 1701 1050 266 28 1 9 0 1 255 3025 7770 6951 2646 462 36 1 10 0 1 511 9330 34105 42525 22827 5880 750 45 1 11 0 1 1023 28501 145750 246730 179487 63987 11880 1155 55 1 12 0 1 2047 86526 611501 1379400 1323652 627396 159027 22275 1705 66 1
C++
<lang cpp>#include <algorithm>
- include <iomanip>
- include <iostream>
- include <map>
- include <gmpxx.h>
using integer = mpz_class;
class stirling2 { public:
integer get(int n, int k);
private:
std::map<std::pair<int, int>, integer> cache_;
};
integer stirling2::get(int n, int k) {
if (k == n)
return 1;
if (k == 0 || k > n)
return 0;
auto p = std::make_pair(n, k);
auto i = cache_.find(p);
if (i != cache_.end())
return i->second;
integer s = k * get(n - 1, k) + get(n - 1, k - 1);
cache_.emplace(p, s);
return s;
}
void print_stirling_numbers(stirling2& s2, int n) {
std::cout << "Stirling numbers of the second kind:\nn/k";
for (int j = 0; j <= n; ++j) {
std::cout << std::setw(j == 0 ? 2 : 8) << j;
}
std::cout << '\n';
for (int i = 0; i <= n; ++i) {
std::cout << std::setw(2) << i << ' ';
for (int j = 0; j <= i; ++j)
std::cout << std::setw(j == 0 ? 2 : 8) << s2.get(i, j);
std::cout << '\n';
}
}
int main() {
stirling2 s2;
print_stirling_numbers(s2, 12);
std::cout << "Maximum value of S2(n,k) where n == 100:\n";
integer max = 0;
for (int k = 0; k <= 100; ++k)
max = std::max(max, s2.get(100, k));
std::cout << max << '\n';
return 0;
}</lang>
- Output:
Stirling numbers of the second kind: n/k 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 1 0 1 2 0 1 1 3 0 1 3 1 4 0 1 7 6 1 5 0 1 15 25 10 1 6 0 1 31 90 65 15 1 7 0 1 63 301 350 140 21 1 8 0 1 127 966 1701 1050 266 28 1 9 0 1 255 3025 7770 6951 2646 462 36 1 10 0 1 511 9330 34105 42525 22827 5880 750 45 1 11 0 1 1023 28501 145750 246730 179487 63987 11880 1155 55 1 12 0 1 2047 86526 611501 1379400 1323652 627396 159027 22275 1705 66 1 Maximum value of S2(n,k) where n == 100: 7769730053598745155212806612787584787397878128370115840974992570102386086289805848025074822404843545178960761551674
D
<lang d>import std.bigint; import std.conv; import std.functional; import std.stdio;
alias sterling2 = memoize!sterling2Impl; BigInt sterling2Impl(int n, int k) {
if (n == 0 && k == 0) {
return BigInt(1);
}
if ((n > 0 && k == 0) || (n == 0 && k > 0)) {
return BigInt(0);
}
if (n == k) {
return BigInt(1);
}
if (k > n) {
return BigInt(0);
}
return BigInt(k) * sterling2(n - 1, k) + sterling2(n - 1, k - 1);
}
void main() {
writeln("Stirling numbers of the second kind:");
int max = 12;
write("n/k");
for (int n = 0; n <= max; n++) {
writef("%10d", n);
}
writeln;
for (int n = 0; n <= max; n++) {
writef("%-3d", n);
for (int k = 0; k <= n; k++) {
writef("%10s", sterling2(n, k));
}
writeln;
}
writeln("The maximum value of S2(100, k) = ");
auto previous = BigInt(0);
for (int k = 1; k <= 100; k++) {
auto current = sterling2(100, k);
if (current > previous) {
previous = current;
} else {
writeln(previous);
auto ps = previous.to!string;
writefln("(%d digits, k = %d)", ps.length, k - 1);
break;
}
}
}</lang>
- Output:
Stirling numbers of the second kind: n/k 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 1 0 1 2 0 1 1 3 0 1 3 1 4 0 1 7 6 1 5 0 1 15 25 10 1 6 0 1 31 90 65 15 1 7 0 1 63 301 350 140 21 1 8 0 1 127 966 1701 1050 266 28 1 9 0 1 255 3025 7770 6951 2646 462 36 1 10 0 1 511 9330 34105 42525 22827 5880 750 45 1 11 0 1 1023 28501 145750 246730 179487 63987 11880 1155 55 1 12 0 1 2047 86526 611501 1379400 1323652 627396 159027 22275 1705 66 1 The maximum value of S2(100, k) = 7769730053598745155212806612787584787397878128370115840974992570102386086289805848025074822404843545178960761551674 (115 digits, k = 28)
Factor
<lang factor>USING: combinators.short-circuit formatting io kernel math math.extras prettyprint sequences ; RENAME: stirling math.extras => (stirling) IN: rosetta-code.stirling-second
! Tweak Factor's in-built stirling function for k=0
- stirling ( n k -- m )
2dup { [ = not ] [ nip zero? ] } 2&&
[ 2drop 0 ] [ (stirling) ] if ;
"Stirling numbers of the second kind: n k stirling:" print "n\\k" write 13 dup [ "%8d" printf ] each-integer nl
<iota> [
dup dup "%-2d " printf [0,b] [
stirling "%8d" printf
] with each nl
] each nl
"Maximum value from the 100 _ stirling row:" print 100 <iota> [ 100 swap stirling ] map supremum .</lang>
- Output:
Stirling numbers of the second kind: n k stirling: n\k 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 1 0 1 2 0 1 1 3 0 1 3 1 4 0 1 7 6 1 5 0 1 15 25 10 1 6 0 1 31 90 65 15 1 7 0 1 63 301 350 140 21 1 8 0 1 127 966 1701 1050 266 28 1 9 0 1 255 3025 7770 6951 2646 462 36 1 10 0 1 511 9330 34105 42525 22827 5880 750 45 1 11 0 1 1023 28501 145750 246730 179487 63987 11880 1155 55 1 12 0 1 2047 86526 611501 1379400 1323652 627396 159027 22275 1705 66 1 Maximum value from the 100 _ stirling row: 7769730053598745155212806612787584787397878128370115840974992570102386086289805848025074822404843545178960761551674
FreeBASIC
<lang freebasic>dim as integer S2(0 to 12, 0 to 12) 'initially set with zeroes dim as ubyte n, k dim as string outstr
function padto( i as ubyte, j as integer ) as string
return wspace(i-len(str(j)))+str(j)
end function
for k = 0 to 12 'calculate table
S2(k,k)=1
next k for n = 1 to 11
for k = 1 to 12
S2(n+1,k) = k*S2(n,k) + S2(n,k-1)
next k
next n
print "Stirling numbers of the second kind" print outstr = " k" for k=0 to 12
outstr += padto(12, k)
next k print outstr print " n" for n = 0 to 12
outstr = padto(2, n)+" "
for k = 0 to 12
outstr += padto(12, S2(n, k))
next k
print outstr
next n</lang>
Stirling numbers of the second kind k 0 1 2 3 4 5 6 7 8 9 10 11 12 n 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 2 0 1 1 0 0 0 0 0 0 0 0 0 0 3 0 1 3 1 0 0 0 0 0 0 0 0 0 4 0 1 7 6 1 0 0 0 0 0 0 0 0 5 0 1 15 25 10 1 0 0 0 0 0 0 0 6 0 1 31 90 65 15 1 0 0 0 0 0 0 7 0 1 63 301 350 140 21 1 0 0 0 0 0 8 0 1 127 966 1701 1050 266 28 1 0 0 0 0 9 0 1 255 3025 7770 6951 2646 462 36 1 0 0 0 10 0 1 511 9330 34105 42525 22827 5880 750 45 1 0 0 11 0 1 1023 28501 145750 246730 179487 63987 11880 1155 55 1 0 12 0 1 2047 86526 611501 1379400 1323652 627396 159027 22275 1705 66 1
Fōrmulæ
In this page you can see the solution of this task.
Fōrmulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text (more info). Moreover, there can be multiple visual representations of the same program. Even though it is possible to have textual representation —i.e. XML, JSON— they are intended for transportation effects more than visualization and edition.
The option to show Fōrmulæ programs and their results is showing images. Unfortunately images cannot be uploaded in Rosetta Code.
Go
<lang go>package main
import (
"fmt" "math/big"
)
func main() {
limit := 100
last := 12
s2 := make([][]*big.Int, limit+1)
for n := 0; n <= limit; n++ {
s2[n] = make([]*big.Int, limit+1)
for k := 0; k <= limit; k++ {
s2[n][k] = new(big.Int)
}
s2[n][n].SetInt64(int64(1))
}
var t big.Int
for n := 1; n <= limit; n++ {
for k := 1; k <= n; k++ {
t.SetInt64(int64(k))
t.Mul(&t, s2[n-1][k])
s2[n][k].Add(&t, s2[n-1][k-1])
}
}
fmt.Println("Stirling numbers of the second kind: S2(n, k):")
fmt.Printf("n/k")
for i := 0; i <= last; i++ {
fmt.Printf("%9d ", i)
}
fmt.Printf("\n--")
for i := 0; i <= last; i++ {
fmt.Printf("----------")
}
fmt.Println()
for n := 0; n <= last; n++ {
fmt.Printf("%2d ", n)
for k := 0; k <= n; k++ {
fmt.Printf("%9d ", s2[n][k])
}
fmt.Println()
}
fmt.Println("\nMaximum value from the S2(100, *) row:")
max := new(big.Int).Set(s2[limit][0])
for k := 1; k <= limit; k++ {
if s2[limit][k].Cmp(max) > 0 {
max.Set(s2[limit][k])
}
}
fmt.Println(max)
fmt.Printf("which has %d digits.\n", len(max.String()))
}</lang>
- Output:
Stirling numbers of the second kind: S2(n, k): n/k 0 1 2 3 4 5 6 7 8 9 10 11 12 ------------------------------------------------------------------------------------------------------------------------------------ 0 1 1 0 1 2 0 1 1 3 0 1 3 1 4 0 1 7 6 1 5 0 1 15 25 10 1 6 0 1 31 90 65 15 1 7 0 1 63 301 350 140 21 1 8 0 1 127 966 1701 1050 266 28 1 9 0 1 255 3025 7770 6951 2646 462 36 1 10 0 1 511 9330 34105 42525 22827 5880 750 45 1 11 0 1 1023 28501 145750 246730 179487 63987 11880 1155 55 1 12 0 1 2047 86526 611501 1379400 1323652 627396 159027 22275 1705 66 1 Maximum value from the S2(100, *) row: 7769730053598745155212806612787584787397878128370115840974992570102386086289805848025074822404843545178960761551674 which has 115 digits.
Haskell
<lang haskell>import Text.Printf (printf) import Data.List (groupBy) import qualified Data.MemoCombinators as Memo
stirling2 :: Integral a => (a, a) -> a stirling2 = Memo.pair Memo.integral Memo.integral f
where
f (n, k)
| n == 0 && k == 0 = 1
| (n > 0 && k == 0) || (n == 0 && k > 0) = 0
| n == k = 1
| k > n = 0
| otherwise = k * stirling2 (pred n, k) + stirling2 (pred n, pred k)
main :: IO () main = do
printf "n/k" mapM_ (printf "%10d") ([0..12] :: [Int]) >> printf "\n" printf "%s\n" $ replicate (13 * 10 + 3) '-' mapM_ (\row -> printf "%2d|" (fst $ head row) >> mapM_ (printf "%10d" . stirling2) row >> printf "\n") table printf "\nThe maximum value of S2(100, k):\n%d\n" $ maximum ([stirling2 (100, n) | n <- [1..100]] :: [Integer]) where table :: (Int, Int) table = groupBy (\a b -> fst a == fst b) $ (,) <$> [0..12] <*> [0..12]</lang>
- Output:
n/k 0 1 2 3 4 5 6 7 8 9 10 11 12 ------------------------------------------------------------------------------------------------------------------------------------- 0| 1 0 0 0 0 0 0 0 0 0 0 0 0 1| 0 1 0 0 0 0 0 0 0 0 0 0 0 2| 0 1 1 0 0 0 0 0 0 0 0 0 0 3| 0 1 3 1 0 0 0 0 0 0 0 0 0 4| 0 1 7 6 1 0 0 0 0 0 0 0 0 5| 0 1 15 25 10 1 0 0 0 0 0 0 0 6| 0 1 31 90 65 15 1 0 0 0 0 0 0 7| 0 1 63 301 350 140 21 1 0 0 0 0 0 8| 0 1 127 966 1701 1050 266 28 1 0 0 0 0 9| 0 1 255 3025 7770 6951 2646 462 36 1 0 0 0 10| 0 1 511 9330 34105 42525 22827 5880 750 45 1 0 0 11| 0 1 1023 28501 145750 246730 179487 63987 11880 1155 55 1 0 12| 0 1 2047 86526 611501 1379400 1323652 627396 159027 22275 1705 66 1 The maximum value of S2(100, k): 7769730053598745155212806612787584787397878128370115840974992570102386086289805848025074822404843545178960761551674
J
test=: 1 i.~ (0 = *) , = s2=: 0:`1:`($:&<: + ] * <:@:[ $: ])@.test M. s2&>table i. 13 +----+--------------------------------------------------------------------+ |s2&>|0 1 2 3 4 5 6 7 8 9 10 11 12| +----+--------------------------------------------------------------------+ | 0 |0 0 0 0 0 0 0 0 0 0 0 0 0| | 1 |0 1 0 0 0 0 0 0 0 0 0 0 0| | 2 |0 1 1 0 0 0 0 0 0 0 0 0 0| | 3 |0 1 3 1 0 0 0 0 0 0 0 0 0| | 4 |0 1 7 6 1 0 0 0 0 0 0 0 0| | 5 |0 1 15 25 10 1 0 0 0 0 0 0 0| | 6 |0 1 31 90 65 15 1 0 0 0 0 0 0| | 7 |0 1 63 301 350 140 21 1 0 0 0 0 0| | 8 |0 1 127 966 1701 1050 266 28 1 0 0 0 0| | 9 |0 1 255 3025 7770 6951 2646 462 36 1 0 0 0| |10 |0 1 511 9330 34105 42525 22827 5880 750 45 1 0 0| |11 |0 1 1023 28501 145750 246730 179487 63987 11880 1155 55 1 0| |12 |0 1 2047 86526 611501 1379400 1323652 627396 159027 22275 1705 66 1| +----+--------------------------------------------------------------------+ >./ 100 s2&x:&> i. 101 7769730053598745155212806612787584787397878128370115840974992570102386086289805848025074822404843545178960761551674
references:
customized power: [1]
rising and falling factorial: [2] [3]
Java
<lang java> import java.math.BigInteger; import java.util.HashMap; import java.util.Map;
public class SterlingNumbersSecondKind {
public static void main(String[] args) {
System.out.println("Stirling numbers of the second kind:");
int max = 12;
System.out.printf("n/k");
for ( int n = 0 ; n <= max ; n++ ) {
System.out.printf("%10d", n);
}
System.out.printf("%n");
for ( int n = 0 ; n <= max ; n++ ) {
System.out.printf("%-3d", n);
for ( int k = 0 ; k <= n ; k++ ) {
System.out.printf("%10s", sterling2(n, k));
}
System.out.printf("%n");
}
System.out.println("The maximum value of S2(100, k) = ");
BigInteger previous = BigInteger.ZERO;
for ( int k = 1 ; k <= 100 ; k++ ) {
BigInteger current = sterling2(100, k);
if ( current.compareTo(previous) > 0 ) {
previous = current;
}
else {
System.out.printf("%s%n(%d digits, k = %d)%n", previous, previous.toString().length(), k-1);
break;
}
}
}
private static Map<String,BigInteger> COMPUTED = new HashMap<>();
private static final BigInteger sterling2(int n, int k) {
String key = n + "," + k;
if ( COMPUTED.containsKey(key) ) {
return COMPUTED.get(key);
}
if ( n == 0 && k == 0 ) {
return BigInteger.valueOf(1);
}
if ( (n > 0 && k == 0) || (n == 0 && k > 0) ) {
return BigInteger.ZERO;
}
if ( n == k ) {
return BigInteger.valueOf(1);
}
if ( k > n ) {
return BigInteger.ZERO;
}
BigInteger result = BigInteger.valueOf(k).multiply(sterling2(n-1, k)).add(sterling2(n-1, k-1));
COMPUTED.put(key, result);
return result;
}
} </lang>
- Output:
Stirling numbers of the second kind: n/k 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 1 0 1 2 0 1 1 3 0 1 3 1 4 0 1 7 6 1 5 0 1 15 25 10 1 6 0 1 31 90 65 15 1 7 0 1 63 301 350 140 21 1 8 0 1 127 966 1701 1050 266 28 1 9 0 1 255 3025 7770 6951 2646 462 36 1 10 0 1 511 9330 34105 42525 22827 5880 750 45 1 11 0 1 1023 28501 145750 246730 179487 63987 11880 1155 55 1 12 0 1 2047 86526 611501 1379400 1323652 627396 159027 22275 1705 66 1 The maximum value of S2(100, k) = 7769730053598745155212806612787584787397878128370115840974992570102386086289805848025074822404843545178960761551674 (115 digits, k = 28)
Julia
<lang julia>using Combinatorics
const s2cache = Dict()
function stirlings2(n, k)
if haskey(s2cache, Pair(n, k))
return s2cache[Pair(n, k)]
elseif n < 0
throw(DomainError(n, "n must be nonnegative"))
elseif n == k == 0
return one(n)
elseif n == 0 || k == 0
return zero(n)
elseif k == n - 1
return binomial(n, 2)
elseif k == 2
return 2^(n-1) - 1
end
ret = k * stirlings2(n - 1, k) + stirlings2(n - 1, k - 1) s2cache[Pair(n, k)] = ret return ret
end
function printstirling2table(kmax)
println(" ", mapreduce(i -> lpad(i, 10), *, 0:kmax))
sstring(n, k) = begin i = stirlings2(n, k); lpad(k > n && i == 0 ? "" : i, 10) end
for n in 0:kmax
println(rpad(n, 2) * mapreduce(k -> sstring(n, k), *, 0:kmax))
end
end
printstirling2table(12) println("\nThe maximum for stirling2(100, _) is: ", maximum(k-> stirlings2(BigInt(100), BigInt(k)), 1:100))
</lang>
- Output:
0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 1 0 1 2 0 1 1 3 0 1 3 1 4 0 1 7 6 1 5 0 1 15 25 10 1 6 0 1 31 90 65 15 1 7 0 1 63 301 350 140 21 1 8 0 1 127 966 1701 1050 266 28 1 9 0 1 255 3025 7770 6951 2646 462 36 1 10 0 1 511 9330 34105 42525 22827 5880 750 45 1 11 0 1 1023 28501 145750 246730 179487 63987 11880 1155 55 1 12 0 1 2047 86526 611501 1379400 1323652 627396 159027 22275 1705 66 1 The maximum for stirling2(100, _) is: 7769730053598745155212806612787584787397878128370115840974992570102386086289805848025074822404843545178960761551674
Kotlin
<lang scala>import java.math.BigInteger
fun main() {
println("Stirling numbers of the second kind:")
val max = 12
print("n/k")
for (n in 0..max) {
print("%10d".format(n))
}
println()
for (n in 0..max) {
print("%-3d".format(n))
for (k in 0..n) {
print("%10s".format(sterling2(n, k)))
}
println()
}
println("The maximum value of S2(100, k) = ")
var previous = BigInteger.ZERO
for (k in 1..100) {
val current = sterling2(100, k)
previous = if (current > previous) {
current
} else {
println("%s%n(%d digits, k = %d)".format(previous, previous.toString().length, k - 1))
break
}
}
}
private val COMPUTED: MutableMap<String, BigInteger> = HashMap() private fun sterling2(n: Int, k: Int): BigInteger {
val key = "$n,$k"
if (COMPUTED.containsKey(key)) {
return COMPUTED[key]!!
}
if (n == 0 && k == 0) {
return BigInteger.valueOf(1)
}
if (n > 0 && k == 0 || n == 0 && k > 0) {
return BigInteger.ZERO
}
if (n == k) {
return BigInteger.valueOf(1)
}
if (k > n) {
return BigInteger.ZERO
}
val result = BigInteger.valueOf(k.toLong()) * sterling2(n - 1, k) + sterling2(n - 1, k - 1) COMPUTED[key] = result return result
}</lang>
- Output:
Stirling numbers of the second kind: n/k 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 1 0 1 2 0 1 1 3 0 1 3 1 4 0 1 7 6 1 5 0 1 15 25 10 1 6 0 1 31 90 65 15 1 7 0 1 63 301 350 140 21 1 8 0 1 127 966 1701 1050 266 28 1 9 0 1 255 3025 7770 6951 2646 462 36 1 10 0 1 511 9330 34105 42525 22827 5880 750 45 1 11 0 1 1023 28501 145750 246730 179487 63987 11880 1155 55 1 12 0 1 2047 86526 611501 1379400 1323652 627396 159027 22275 1705 66 1 The maximum value of S2(100, k) = 7769730053598745155212806612787584787397878128370115840974992570102386086289805848025074822404843545178960761551674 (115 digits, k = 28)
Mathematica / Wolfram Language
<lang Mathematica>TableForm[Array[StirlingS2, {n = 12, k = 12} + 1, {0, 0}], TableHeadings -> {"n=" <> ToString[#] & /@ Range[0, n], "k=" <> ToString[#] & /@ Range[0, k]}] Max[Abs[StirlingS2[100, #]] & /@ Range[0, 100]]</lang>
- Output:
k=0 k=1 k=2 k=3 k=4 k=5 k=6 k=7 k=8 k=9 k=10 k=11 k=12 n=0 1 0 0 0 0 0 0 0 0 0 0 0 0 n=1 0 1 0 0 0 0 0 0 0 0 0 0 0 n=2 0 1 1 0 0 0 0 0 0 0 0 0 0 n=3 0 1 3 1 0 0 0 0 0 0 0 0 0 n=4 0 1 7 6 1 0 0 0 0 0 0 0 0 n=5 0 1 15 25 10 1 0 0 0 0 0 0 0 n=6 0 1 31 90 65 15 1 0 0 0 0 0 0 n=7 0 1 63 301 350 140 21 1 0 0 0 0 0 n=8 0 1 127 966 1701 1050 266 28 1 0 0 0 0 n=9 0 1 255 3025 7770 6951 2646 462 36 1 0 0 0 n=10 0 1 511 9330 34105 42525 22827 5880 750 45 1 0 0 n=11 0 1 1023 28501 145750 246730 179487 63987 11880 1155 55 1 0 n=12 0 1 2047 86526 611501 1379400 1323652 627396 159027 22275 1705 66 1 7769730053598745155212806612787584787397878128370115840974992570102386086289805848025074822404843545178960761551674
Nim
As for Stirling numbers of first kind, a simple program using recursive definition is enough to solve the task when not using big numbers. <lang Nim>import sequtils, strutils
proc s2(n, k: Natural): Natural =
if n == k: return 1 if n == 0 or k == 0: return 0 k * s2(n - 1, k) + s2(n - 1, k - 1)
echo " k ", toSeq(0..12).mapIt(($it).align(2)).join(" ") echo " n" for n in 0..12:
stdout.write ($n).align(2) for k in 0..n: stdout.write ($s2(n, k)).align(8) stdout.write '\n'</lang>
- Output:
k 0 1 2 3 4 5 6 7 8 9 10 11 12 n 0 1 1 0 1 2 0 1 1 3 0 1 3 1 4 0 1 7 6 1 5 0 1 15 25 10 1 6 0 1 31 90 65 15 1 7 0 1 63 301 350 140 21 1 8 0 1 127 966 1701 1050 266 28 1 9 0 1 255 3025 7770 6951 2646 462 36 1 10 0 1 511 9330 34105 42525 22827 5880 750 45 1 11 0 1 1023 28501 145750 246730 179487 63987 11880 1155 55 1 12 0 1 2047 86526 611501 1379400 1323652 627396 159027 22275 1705 66 1
Now, to solve the second part of the task, we have to use big numbers. As for Stirling numbers of first kind, we also use a cache to avoid to repeat multiple times the same computations.
<lang Nim>import tables import bignum
var cache: Table[(Natural, Natural), Int]
proc s2(n, k: Natural): Int =
if n == k: return newInt(1) if n == 0 or k == 0: return newInt(0) if (n, k) in cache: return cache[(n, k)] result = k * s2(n - 1, k) + s2(n - 1, k - 1) cache[(n, k)] = result
var max = newInt(-1) for k in 0..100:
let s = s2(100, k) if s > max: max = s else: break
echo "Maximum Stirling number of the second kind with n = 100:" echo max</lang>
- Output:
Maximum Stirling number of the second kind with n = 100: 7769730053598745155212806612787584787397878128370115840974992570102386086289805848025074822404843545178960761551674
Perl
<lang perl>use strict; use warnings; use bigint; use feature 'say'; use feature 'state'; no warnings 'recursion'; use List::Util qw(max);
sub Stirling2 {
my($n, $k) = @_;
my $n1 = $n - 1;
return 1 if $n1 == $k;
return 0 unless $n1 && $k;
state %seen;
return ($seen{"{$n1}|{$k}" } //= Stirling2($n1,$k ) * $k) +
($seen{"{$n1}|{$k-1}"} //= Stirling2($n1,$k-1))
}
my $upto = 12; my $width = 1 + length max map { Stirling2($upto+1,$_) } 0..$upto+1;
say 'Unsigned Stirling2 numbers of the second kind: S2(n, k):'; print 'n\k' . sprintf "%${width}s"x(1+$upto)."\n", 0..$upto;
for my $row (1..$upto+1) {
printf '%-3d', $row-1;
printf "%${width}d", Stirling2($row, $_) for 0..$row-1;
print "\n";
}
say "\nMaximum value from the S2(100, *) row:"; say max map { Stirling2(101,$_) } 0..100;</lang>
- Output:
Unsigned Stirling2 numbers of the second kind: S2(n, k): n\k 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 1 0 1 2 0 1 1 3 0 1 3 1 4 0 1 7 6 1 5 0 1 15 25 10 1 6 0 1 31 90 65 15 1 7 0 1 63 301 350 140 21 1 8 0 1 127 966 1701 1050 266 28 1 9 0 1 255 3025 7770 6951 2646 462 36 1 10 0 1 511 9330 34105 42525 22827 5880 750 45 1 11 0 1 1023 28501 145750 246730 179487 63987 11880 1155 55 1 12 0 1 2047 86526 611501 1379400 1323652 627396 159027 22275 1705 66 1 Maximum value from the S2(100, *) row: 7769730053598745155212806612787584787397878128370115840974992570102386086289805848025074822404843545178960761551674
Phix
with javascript_semantics include mpfr.e constant lim = 100, lim1 = lim+1, last = 12 sequence s2 = repeat(0,lim1) for n=1 to lim1 do s2[n] = mpz_inits(lim1) mpz_set_si(s2[n][n],1) end for mpz {t, m100} = mpz_inits(2) for n=1 to lim do for k=1 to n do mpz_set_si(t,k) mpz_mul(t,t,s2[n][k+1]) mpz_add(s2[n+1][k+1],t,s2[n][k]) end for end for printf(1,"Stirling numbers of the second kind: S2(n, k):\n n k:") for i=0 to last do printf(1,"%5d ", i) end for printf(1,"\n--- %s\n",repeat('-',last*10+5)) for n=0 to last do printf(1,"%2d ", n) for k=1 to n+1 do printf(1,"%9s ",{mpz_get_str(s2[n+1][k])}) end for printf(1,"\n") end for for k=1 to lim1 do mpz s100k = s2[lim1][k] if mpz_cmp(s100k,m100) > 0 then mpz_set(m100,s100k) end if end for printf(1,"\nThe maximum S2(100,k): %s\n",shorten(mpz_get_str(m100)))
- Output:
Stirling numbers of the second kind: S2(n, k): n k: 0 1 2 3 4 5 6 7 8 9 10 11 12 --- ------------------------------------------------------------------------------------------------------------------------------ 0 1 1 0 1 2 0 1 1 3 0 1 3 1 4 0 1 7 6 1 5 0 1 15 25 10 1 6 0 1 31 90 65 15 1 7 0 1 63 301 350 140 21 1 8 0 1 127 966 1701 1050 266 28 1 9 0 1 255 3025 7770 6951 2646 462 36 1 10 0 1 511 9330 34105 42525 22827 5880 750 45 1 11 0 1 1023 28501 145750 246730 179487 63987 11880 1155 55 1 12 0 1 2047 86526 611501 1379400 1323652 627396 159027 22275 1705 66 1 Maximum value from the S2(100, *) row: 7769730053598745155...3545178960761551674 (115 digits)
Prolog
<lang prolog>:- dynamic stirling2_cache/3.
stirling2(N, N, 1):-!. stirling2(_, 0, 0):-!. stirling2(N, K, 0):- K > N, !. stirling2(N, K, L):- stirling2_cache(N, K, L), !. stirling2(N, K, L):- N1 is N - 1, K1 is K - 1, stirling2(N1, K, L1), stirling2(N1, K1, L2), !, L is K * L1 + L2, assertz(stirling2_cache(N, K, L)).
print_stirling_numbers(N):- between(1, N, K), stirling2(N, K, L), writef('%8r', [L]), fail. print_stirling_numbers(_):- nl.
print_stirling_numbers_up_to(M):- between(1, M, N), print_stirling_numbers(N), fail. print_stirling_numbers_up_to(_).
max_stirling2(N, Max):-
aggregate_all(max(L), (between(1, N, K), stirling2(N, K, L)), Max).
main:- writeln('Stirling numbers of the second kind up to S2(12,12):'), print_stirling_numbers_up_to(12), writeln('Maximum value of S2(n,k) where n = 100:'), max_stirling2(100, M), writeln(M).</lang>
- Output:
Stirling numbers of the second kind up to S2(12,12):
1
1 1
1 3 1
1 7 6 1
1 15 25 10 1
1 31 90 65 15 1
1 63 301 350 140 21 1
1 127 966 1701 1050 266 28 1
1 255 3025 7770 6951 2646 462 36 1
1 511 9330 34105 42525 22827 5880 750 45 1
1 1023 28501 145750 246730 179487 63987 11880 1155 55 1
1 2047 86526 611501 1379400 1323652 627396 159027 22275 1705 66 1
Maximum value of S2(n,k) where n = 100:
7769730053598745155212806612787584787397878128370115840974992570102386086289805848025074822404843545178960761551674
Python
<lang Python> computed = {}
def sterling2(n, k): key = str(n) + "," + str(k)
if key in computed.keys(): return computed[key] if n == k == 0: return 1 if (n > 0 and k == 0) or (n == 0 and k > 0): return 0 if n == k: return 1 if k > n: return 0 result = k * sterling2(n - 1, k) + sterling2(n - 1, k - 1) computed[key] = result return result
print("Stirling numbers of the second kind:") MAX = 12 print("n/k".ljust(10), end="") for n in range(MAX + 1): print(str(n).rjust(10), end="") print() for n in range(MAX + 1): print(str(n).ljust(10), end="") for k in range(n + 1): print(str(sterling2(n, k)).rjust(10), end="") print() print("The maximum value of S2(100, k) = ") previous = 0 for k in range(1, 100 + 1): current = sterling2(100, k) if current > previous: previous = current else: print("{0}\n({1} digits, k = {2})\n".format(previous, len(str(previous)), k - 1)) break </lang>
- Output:
Stirling numbers of the second kind: n/k 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 1 0 1 2 0 1 1 3 0 1 3 1 4 0 1 7 6 1 5 0 1 15 25 10 1 6 0 1 31 90 65 15 1 7 0 1 63 301 350 140 21 1 8 0 1 127 966 1701 1050 266 28 1 9 0 1 255 3025 7770 6951 2646 462 36 1 10 0 1 511 9330 34105 42525 22827 5880 750 45 1 11 0 1 1023 28501 145750 246730 179487 63987 11880 1155 55 1 12 0 1 2047 86526 611501 1379400 1323652 627396 159027 22275 1705 66 1 The maximum value of S2(100, k) = 7769730053598745155212806612787584787397878128370115840974992570102386086289805848025074822404843545178960761551674 (115 digits, k = 28)
Raku
(formerly Perl 6)
<lang perl6>sub Stirling2 (Int \n, Int \k) {
((1,), { (0, |@^last) »+« (|(@^last »*« @^last.keys), 0) } … *)[n;k]
}
my $upto = 12;
my $mx = (1..^$upto).map( { Stirling2($upto, $_) } ).max.chars;
put 'Stirling numbers of the second kind: S2(n, k):'; put 'n\k', (0..$upto)».fmt: "%{$mx}d";
for 0..$upto -> $row {
$row.fmt('%-3d').print;
put (0..$row).map( { Stirling2($row, $_) } )».fmt: "%{$mx}d";
}
say "\nMaximum value from the S2(100, *) row:"; say (^100).map( { Stirling2 100, $_ } ).max;</lang>
- Output:
Stirling numbers of the second kind: S2(n, k): n\k 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 1 0 1 2 0 1 1 3 0 1 3 1 4 0 1 7 6 1 5 0 1 15 25 10 1 6 0 1 31 90 65 15 1 7 0 1 63 301 350 140 21 1 8 0 1 127 966 1701 1050 266 28 1 9 0 1 255 3025 7770 6951 2646 462 36 1 10 0 1 511 9330 34105 42525 22827 5880 750 45 1 11 0 1 1023 28501 145750 246730 179487 63987 11880 1155 55 1 12 0 1 2047 86526 611501 1379400 1323652 627396 159027 22275 1705 66 1 Maximum value from the S2(100, *) row: 7769730053598745155212806612787584787397878128370115840974992570102386086289805848025074822404843545178960761551674
REXX
Some extra code was added to minimize the displaying of the column widths. <lang>/*REXX program to compute and display Stirling numbers of the second kind. */ parse arg lim . /*obtain optional argument from the CL.*/ if lim== | lim=="," then lim= 12 /*Not specified? Then use the default.*/ olim= lim /*save the original value of LIM. */ lim= abs(lim) /*only use the absolute value of LIM. */ numeric digits max(9, 2*lim) /*(over) specify maximum number in grid*/ @.=
do j=0 for lim+1
@.j.j = 1; if j==0 then iterate /*define the right descending diagonal.*/
@.0.j = 0; @.j.0 = 0 /* " " zero values. */
end /*j*/
max#.= 0 /* [↓] calculate values for the grid. */
do n=0 for lim+1; np= n + 1
do k=1 for lim; km= k - 1
@.np.k = k * @.n.k + @.n.km /*calculate a number in the grid. */
max#.k= max(max#.k, @.n.k) /*find the maximum value for a column. */
max#.b= max(max#.b, @.n.k) /*find the maximum value for all rows. */
end /*k*/
end /*n*/
/* [↓] only show the maximum value ? */
do k=0 for lim+1 /*find max column width for each column*/
max#.a= max#.a + length(max#.k)
end /*k*/
w= length(max#.b) /*calculate max width of all numbers. */ if olim<0 then do; say 'The maximum value (which has ' w " decimal digits):"
say max#.b /*display maximum number in the grid. */
exit /*stick a fork in it, we're all done. */
end
wgi= max(5, length(lim+1) ) /*the maximum width of the grid's index*/ say '═row═' center("columns", max(9, max#.a + lim), '═') /*display header of the grid.*/
do r=0 for lim+1; $= /* [↓] display the grid to the term. */
do c=0 for lim+1 until c>=r /*build a row of grid, 1 col at a time.*/
$= $ right(@.r.c, length(max#.c) ) /*append a column to a row of the grid.*/
end /*c*/
say center(r, wgi) strip( substr($,2), 'T') /*display a single row of the grid. */
end /*r*/ /*stick a fork in it, we're all done. */</lang>
- output when using the default input:
═row═ ══════════════════════════════columns══════════════════════════════ 0 1 1 0 1 2 0 1 1 3 0 1 3 1 4 0 1 7 6 1 5 0 1 15 25 10 1 6 0 1 31 90 65 15 1 7 0 1 63 301 350 140 21 1 8 0 1 127 966 1701 1050 266 28 1 9 0 1 255 3025 7770 6951 2646 462 36 1 10 0 1 511 9330 34105 42525 22827 5880 750 45 1 11 0 1 1023 28501 145750 246730 179487 63987 11880 1155 55 1 12 0 1 2047 86526 611501 1379400 1323652 627396 159027 22275 1705 66 1
- output when using the input of: -100
The maximum value (which has 115 decimal digits): 7769730053598745155212806612787584787397878128370115840974992570102386086289805848025074822404843545178960761551674
Ruby
<lang ruby>@memo = {}
def sterling2(n, k)
key = [n,k] return @memo[key] if @memo.key?(key) return 1 if n.zero? and k.zero? return 0 if n.zero? or k.zero? return 1 if n == k return 0 if k > n res = k * sterling2(n-1, k) + sterling2(n - 1, k-1) @memo[key] = res
end
r = (0..12) puts "Sterling2 numbers:" puts "n/k #{r.map{|n| "%11d" % n}.join}"
r.each do |row|
print "%-4s" % row
puts "#{(0..row).map{|col| "%11d" % sterling2(row, col)}.join}"
end
puts "\nMaximum value from the sterling2(100, k)"; puts (1..100).map{|a| sterling2(100,a)}.max </lang>
- Output:
Sterling2 numbers:n/k 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 1 0 1 2 0 1 1 3 0 1 3 1 4 0 1 7 6 1 5 0 1 15 25 10 1 6 0 1 31 90 65 15 1 7 0 1 63 301 350 140 21 1 8 0 1 127 966 1701 1050 266 28 1 9 0 1 255 3025 7770 6951 2646 462 36 1 10 0 1 511 9330 34105 42525 22827 5880 750 45 1 11 0 1 1023 28501 145750 246730 179487 63987 11880 1155 55 1 12 0 1 2047 86526 611501 1379400 1323652 627396 159027 22275 1705 66 1
Maximum value from the L(100, *) row: 7769730053598745155212806612787584787397878128370115840974992570102386086289805848025074822404843545178960761551674
Sidef
<lang ruby>func S2(n, k) { # Stirling numbers of the second kind
stirling2(n, k)
}
const r = (0..12)
var triangle = r.map {|n| 0..n -> map {|k| S2(n, k) } } var widths = r.map {|n| r.map {|k| (triangle[k][n] \\ 0).len }.max }
say ('n\k ', r.map {|n| "%*s" % (widths[n], n) }.join(' '))
r.each {|n|
var str = ('%-3s ' % n)
str += triangle[n].map_kv {|k,v| "%*s" % (widths[k], v) }.join(' ')
say str
}
with (100) {|n|
say "\nMaximum value from the S2(#{n}, *) row:"
say { S2(n, _) }.map(^n).max
}</lang>
- Output:
n\k 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 1 0 1 2 0 1 1 3 0 1 3 1 4 0 1 7 6 1 5 0 1 15 25 10 1 6 0 1 31 90 65 15 1 7 0 1 63 301 350 140 21 1 8 0 1 127 966 1701 1050 266 28 1 9 0 1 255 3025 7770 6951 2646 462 36 1 10 0 1 511 9330 34105 42525 22827 5880 750 45 1 11 0 1 1023 28501 145750 246730 179487 63987 11880 1155 55 1 12 0 1 2047 86526 611501 1379400 1323652 627396 159027 22275 1705 66 1 Maximum value from the S2(100, *) row: 7769730053598745155212806612787584787397878128370115840974992570102386086289805848025074822404843545178960761551674
Alternatively, the S2(n,k) function can be defined as: <lang ruby>func S2((0), (0)) { 1 } func S2(_, (0)) { 0 } func S2((0), _) { 0 } func S2(n, k) is cached { S2(n-1, k)*k + S2(n-1, k-1) }</lang>
Tcl
<lang Tcl>proc S2 {n k} {
set nk [list $n $k]
if {[info exists ::S2cache($nk)]} {
return $::S2cache($nk)
}
if {($n > 0 && $k == 0) || ($n == 0 && $k > 0)} {
return 0
}
if {$n == $k} {
return 1
}
if {$n < $k} {
return 0
}
set n1 [expr {$n - 1}]
set k1 [expr {$k - 1}]
set r [expr {($k * [S2 $n1 $k]) + [S2 $n1 $k1]}]
set ::S2cache($nk) $r
}
proc main {} {
puts "Stirling numbers of the second kind:"
set max 12 ;# last table line to print
set L 8 ;# space to use for 1 number
puts -nonewline "n\\k"
for {set n 0} {$n <= $max} {incr n} {
puts -nonewline [format %${L}d $n]
}
puts ""
for {set n 0} {$n <= $max} {incr n} {
puts -nonewline [format %-3d $n]
for {set k 0} {$k <= $n} {incr k} {
puts -nonewline [format %${L}s [S2 $n $k]]
}
puts ""
}
puts "The maximum value of S2(100, k) = "
set previous 0
for {set k 1} {$k <= 100} {incr k} {
set current [S2 100 $k]
if {$current > $previous} {
set previous $current
} else {
puts $previous
puts "([string length $previous] digits, k = [expr {$k-1}])"
break
}
}
} main</lang>
- Output:
Stirling numbers of the second kind: n\k 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 1 0 1 2 0 1 1 3 0 1 3 1 4 0 1 7 6 1 5 0 1 15 25 10 1 6 0 1 31 90 65 15 1 7 0 1 63 301 350 140 21 1 8 0 1 127 966 1701 1050 266 28 1 9 0 1 255 3025 7770 6951 2646 462 36 1 10 0 1 511 9330 34105 42525 22827 5880 750 45 1 11 0 1 1023 28501 145750 246730 179487 63987 11880 1155 55 1 12 0 1 2047 86526 611501 1379400 1323652 627396 159027 22275 1705 66 1 The maximum value of S2(100, k) = 7769730053598745155212806612787584787397878128370115840974992570102386086289805848025074822404843545178960761551674 (115 digits, k = 28)
Visual Basic .NET
<lang vbnet>Imports System.Numerics
Module Module1
Class Sterling
Private Shared ReadOnly COMPUTED As New Dictionary(Of String, BigInteger)
Private Shared Function CacheKey(n As Integer, k As Integer) As String
Return String.Format("{0}:{1}", n, k)
End Function
Private Shared Function Impl(n As Integer, k As Integer) As BigInteger
If n = 0 AndAlso k = 0 Then
Return 1
End If
If (n > 0 AndAlso k = 0) OrElse (n = 0 AndAlso k > 0) Then
Return 0
End If
If n = k Then
Return 1
End If
If k > n Then
Return 0
End If
Return k * Sterling2(n - 1, k) + Sterling2(n - 1, k - 1)
End Function
Public Shared Function Sterling2(n As Integer, k As Integer) As BigInteger
Dim key = CacheKey(n, k)
If COMPUTED.ContainsKey(key) Then
Return COMPUTED(key)
End If
Dim result = Impl(n, k)
COMPUTED.Add(key, result)
Return result
End Function
End Class
Sub Main()
Console.WriteLine("Stirling numbers of the second kind:")
Dim max = 12
Console.Write("n/k")
For n = 0 To max
Console.Write("{0,10}", n)
Next
Console.WriteLine()
For n = 0 To max
Console.Write("{0,3}", n)
For k = 0 To n
Console.Write("{0,10}", Sterling.Sterling2(n, k))
Next
Console.WriteLine()
Next
Console.WriteLine("The maximum value of S2(100, k) = ")
Dim previous = BigInteger.Zero
For k = 1 To 100
Dim current = Sterling.Sterling2(100, k)
If current > previous Then
previous = current
Else
Console.WriteLine(previous)
Console.WriteLine("({0} digits, k = {1})", previous.ToString().Length, k - 1)
Exit For
End If
Next
End Sub
End Module</lang>
- Output:
Stirling numbers of the second kind: n/k 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 1 0 1 2 0 1 1 3 0 1 3 1 4 0 1 7 6 1 5 0 1 15 25 10 1 6 0 1 31 90 65 15 1 7 0 1 63 301 350 140 21 1 8 0 1 127 966 1701 1050 266 28 1 9 0 1 255 3025 7770 6951 2646 462 36 1 10 0 1 511 9330 34105 42525 22827 5880 750 45 1 11 0 1 1023 28501 145750 246730 179487 63987 11880 1155 55 1 12 0 1 2047 86526 611501 1379400 1323652 627396 159027 22275 1705 66 1 The maximum value of S2(100, k) = 7769730053598745155212806612787584787397878128370115840974992570102386086289805848025074822404843545178960761551674 (115 digits, k = 28)
Wren
<lang ecmascript>import "/big" for BigInt import "/fmt" for Fmt
var computed = {}
var stirling2 // recursive stirling2 = Fn.new { |n, k|
var key = "%(n),%(k)" if (computed.containsKey(key)) return computed[key] if (n == 0 && k == 0) return BigInt.one if ((n > 0 && k == 0) || (n == 0 && k > 0)) return BigInt.zero if (k == n) return BigInt.one if (k > n) return BigInt.zero var result = stirling2.call(n-1, k-1) + stirling2.call(n-1, k)*k computed[key] = result return result
}
System.print("Unsigned Stirling numbers of the second kind:") var max = 12 System.write("n/k") for (n in 0..max) Fmt.write("$10d", n) System.print() for (n in 0..max) {
Fmt.write("$-3d", n)
for (k in 0..n) Fmt.write("$10i", stirling2.call(n, k))
System.print()
} System.print("The maximum value of S2(100, k) =") var previous = BigInt.zero for (k in 1..100) {
var current = stirling2.call(100, k)
if (current > previous) {
previous = current
} else {
Fmt.print("$i\n($d digits, k = $d)", previous, previous.toString.count, k - 1)
break
}
}</lang>
- Output:
Unsigned Stirling numbers of the second kind: n/k 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 1 0 1 2 0 1 1 3 0 1 3 1 4 0 1 7 6 1 5 0 1 15 25 10 1 6 0 1 31 90 65 15 1 7 0 1 63 301 350 140 21 1 8 0 1 127 966 1701 1050 266 28 1 9 0 1 255 3025 7770 6951 2646 462 36 1 10 0 1 511 9330 34105 42525 22827 5880 750 45 1 11 0 1 1023 28501 145750 246730 179487 63987 11880 1155 55 1 12 0 1 2047 86526 611501 1379400 1323652 627396 159027 22275 1705 66 1 The maximum value of S2(100, k) = 7769730053598745155212806612787584787397878128370115840974992570102386086289805848025074822404843545178960761551674 (115 digits, k = 28)
zkl
<lang zkl>fcn stirling2(n,k){
var seen=Dictionary(); // cache for recursion
if(n==k) return(1); // (0.0)==1
if(n<1 or k<1) return(0);
z1,z2 := "%d,%d".fmt(n-1,k), "%d,%d".fmt(n-1,k-1);
if(Void==(s1 := seen.find(z1))){ s1 = seen[z1] = stirling2(n-1,k) }
if(Void==(s2 := seen.find(z2))){ s2 = seen[z2] = stirling2(n-1,k-1) }
k*s1 + s2; // k is first to cast to BigInt (if using BigInts)
}</lang> <lang zkl>// calculate entire table (cached), find max, find num digits in max N,mx := 12, [1..N].apply(fcn(n){ [1..n].apply(stirling2.fp(n)) }).flatten() : (0).max(_); fmt:="%%%dd".fmt("%d".fmt(mx.numDigits + 1)).fmt; // "%9d".fmt println("Stirling numbers of the second kind: S2(n,k):"); println("n\\k",[0..N].pump(String,fmt)); foreach row in ([0..N]){
println("%3d".fmt(row), [0..row].pump(String, stirling2.fp(row), fmt));
}</lang>
- Output:
Stirling numbers of the second kind: S2(n,k): n\k 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 1 0 1 2 0 1 1 3 0 1 3 1 4 0 1 7 6 1 5 0 1 15 25 10 1 6 0 1 31 90 65 15 1 7 0 1 63 301 350 140 21 1 8 0 1 127 966 1701 1050 266 28 1 9 0 1 255 3025 7770 6951 2646 462 36 1 10 0 1 511 9330 34105 42525 22827 5880 750 45 1 11 0 1 1023 28501 145750 246730 179487 63987 11880 1155 55 1 12 0 1 2047 86526 611501 1379400 1323652 627396 159027 22275 1705 66 1
GNU Multiple Precision Arithmetic Library
<lang zkl>var [const] BI=Import("zklBigNum"); // libGMP N=100; S2100:=[BI(2)..N].apply(stirling2.fp(BI(N))).reduce(fcn(m,n){ m.max(n) }); println("Maximum value from the S2(%d,*) row (%d digits):".fmt(N,S2100.numDigits)); println(S2100);</lang>
- Output:
Maximum value from the S2(100,*) row (115 digits): 7769730053598745155212806612787584787397878128370115840974992570102386086289805848025074822404843545178960761551674