Answer to Question #250959 in Discrete Mathematics for SWAPNA KAYAL

Question

In a class of n

n students (we consider all students as distinct), we want to make k

k groups where each group must contain at least 1 student. Let S(n,k)

S(n,k) denote the number of ways in which such groups can be formed. Which of the following is/are true? (More than one options may be correct.)

S(n+1,k)=kS(n,k)+S(n,k−1)

S(n+1,k)=kS(n,k)+S(n,k−1)

S(n+1,k+1)=kS(n,k+1)+S(n,k)

S(n+1,k+1)=kS(n,k+1)+S(n,k)

For  n,k>1,S(n,k)=∑

j=1

n−1

(n−1

j

)S(j,k−1)

n,k>1,S(n,k)=∑j=1n−1(n−1j)S(j,k−1)

For  n,k>1,S(n,k)=∑

j=1

n−1

(n

j

)S(j,k−1)

Answer 1

S(n,k), a Stirling number of the second kind, is the number of ways to partition a set of n objects into k non-empty subsets.

Answer:

$S(n+1,k+1)=kS(n,k+1)+S(n,k)$

$S(n,k)=\displaystyle{\sum^{n-1}_{j=1}}\begin{pmatrix} n-1 \\ j \end{pmatrix}S(j,k-1)$