In which n represents the number of items, and r represents the number of items chosen out of n no. Of items , where ,n>=r
Answers
Answer:
hey DEAR /
S(r, 0) = 0, trivial.
S(r, 1) represents the circular permutation which is equal to (r – 1)!
S(r, 1) represents the circular permutation which is equal to (r – 1)!S(r, n) where r = n, equals 1.
S(r, 1) represents the circular permutation which is equal to (r – 1)!S(r, n) where r = n, equals 1.S(r, r -1) = rC2
S(r, 1) represents the circular permutation which is equal to (r – 1)!S(r, n) where r = n, equals 1.S(r, r -1) = rC2Recommended: Please try your approach on {IDE} first, before moving on to the solution.
An important identity of the Stirling numbers that S(r, n) = S(r – 1, n – 1) + (r – 1) * S(r – 1, n)
Approach: For simplicity, denote the r distinct objects by 1, 2, …, r. Consider the object “1”. In any arrangement of the objects, either
“1” is the only object in a circle or
1” is the only object in a circle or“1” is mixed with others in a circle.
1” is the only object in a circle or“1” is mixed with others in a circle.In case 1, there are s(r – 1, n – 1) ways to form such arrangements. In case 2, first of all, the r — 1 objects 2, 3, …, r are put in n circles in s(r — 1, n) ways; then “1” can be placed in one of the r — 1 distinct spaces to the “immediate right” of the corresponding r — 1 distinct objects. By multiplication principle, there are (r — 1)s(r — 1, n) ways to form such arrangements in case 2. The identity now follows from the definition of s(r, n) and addition principle.
Using the initial values S(0, 0) = 1, s(r, 0) = 0 for r > 1 and s(r, 1) = (r — 1)! for r > 1, and applying the identity we proved, we can easily get the Stirling number by computing it in a recursive way.
In the code we have three functions that are used to generate the Stirling numbers, which are nCr(n, r), which is a function to compute what we call (n – choose – r), the number of ways we can take r objects from n objects without the importance of orderings. factorial (int n) is, unsurprisingly, used to compute the factorial of a number n. The function Stirling number(r, n) works recursively using the four base cases discussed above and then recursing using the identity we proved.
hope it's helpful for you
Answer:are you asking for the formula of nCr or nPr?
Here you go:nPr=n!/(n-r)!
nCr=n!/r!(n-r)!