Difference between revisions of "Stirling numbers of the second kind"

From Fōrmulæ wiki
Jump to: navigation, search
(Creation of page)
 
(→‎Description (from Rosetta Code))
 
Line 4: Line 4:
  
 
{| class="wikitable" style="width:100%;"
 
{| class="wikitable" style="width:100%;"
−
| Stirling numbers of the second kind, or Stirling partition numbers, are the
+
| 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 [http://rosettacode.org/wiki/Bell_numbers Bell numbers], and may be derived from them.
−
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:
 
Stirling numbers of the second kind obey the recurrence relation:

Latest revision as of 10:43, 20 September 2019

This page is a solution to the task Stirling numbers of the second kind in the Rosetta Code, written in Fōrmulæ.

Description (from Rosetta Code)

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

Solution

Recursive

StirlingNumberSecondKindCode01.png

Table up to S2(12, 12):

StirlingNumberSecondKindOutput01a.png

Non recursive

A faster, non recursive version is presented:

StirlingNumberSecondKindCode02.png

Table up to S2(12, 12):

StirlingNumberSecondKindOutput02a.png

(The result is the same as recursive version)

Extra

Maximum value of S2(100, k) for k ≤ 100:

StirlingNumberSecondKindSnippet03a.png


Retrieved from "https://wiki.formulae.org/mediawiki/index.php?title=Stirling_numbers_of_the_second_kind&oldid=3595"