Home › Forums › Math Olympiad, I.S.I., C.M.I. Entrance › Combinatorics › Stirling Numbers

Tagged: Stirling Numbers

- This topic has 4 replies, 4 voices, and was last updated 1 year, 8 months ago by swastik pramanik.

- AuthorPosts
- November 18, 2018 at 10:57 pm #24379Ashani DasguptaKeymasterNovember 18, 2018 at 11:03 pm #24383Ananya BhattacharyaParticipant
Will try. But need to think about how recursion can play a role here.

Thank You Sir.November 19, 2018 at 10:55 pm #24415Prasad sParticipantSir, solved the first one

November 19, 2018 at 10:59 pm #24416November 23, 2018 at 1:12 pm #24439swastik pramanikParticipantSolution for the

**second problem**:Let us consider \(r\) objects which are to be distributed in \(n\) identical boxes with no box empty. So, by definition we can place \(r\) objects in \(n\) identical boxes in \(S(r,n)\).

Let \(P=\{p_1,p_2,…,p_r\}\) be the set of \(r\) objects and \(T=\{t_1,t_2,…,t_n\}\) be the set of \(n\) identical boxes.

Now we divide the problem into two disjoint cases.

**Case 1:**When box \(t_1\) contains only object \(p_1\) then,The remaining \(r-1\) objects can be distributed to the remaining \(n-1\) boxes in \(S(r-1,n-1)\) ways.

**Case 2:**When box \(t_1\) will have the object \(p_1\) and also some other objects then,The remaining \(r-1\) objects are first put in the \(n\) boxes in \(S(r-1,n)\) ways. After distributing the \(r-1\) objects in \(n\) boxes each box becomes distinct. Hence, we can place \(p_1\) in the \(n\) boxes in \(n\) ways. Thus, the number of ways of such distribution is \(nS(r-1,n)\).

Thus, we have $$S(r,n)=S(r-1,n-1)+nS(r-1,n)$$ as required.

- AuthorPosts

- You must be logged in to reply to this topic.