Dora and Stirling Numbers
Dora, as we all know is an explorer.
Little did we know that she is a researcher on Mathematical numbers.
This time she got attracted towards Stirling numbers and Dora and Boots together in their usual way, set out for their findings on this kind of numbers.
Dora came to know that Stirling numbers of the second kind describe the number of ways a set with nelements can be partitioned into m disjoint, non-empty subsets. For example, there are seven ways to split a four-element set into two parts:
{1, 2, 3} u {4},
{1, 2, 4} u {3},
{1, 3, 4} u {2},
{2, 3, 4} u {1},
{1, 2} u {3, 4},
{1, 3} u {2, 4},
{1, 4} u {2, 3}.
There is a recurrence which allows you to compute S(n, m) for all m and n.
S(0, 0) = 1,
S(n, 0) = 0, for n > 0,
S(0, m) = 0, for m > 0,
S(n, m) = m*S(n-1, m) + S(n-1, m-1), for n, m > 0.
Given integers n and m satisfying 1 <= m <= n, compute S(n, m) .
Dora's task was to write a program that reads two positive integers n and m, computes S(n, m) and outputs the result. Can you assist Dora in this tedious task?
Input Format :
Input consists of 2 integers --- n and m.
Output Format :
Output consists of an integer that corresponds to S(n,m).
Refer sample input and output for formatting specifications.
Sample Input:
4
2
Sample Output:
7
Inputs
10 5
5 0
9 7
1 1
No comments: