Great video! I wanted to comment some motivation for the recursive formulas because I think it’s a fun exercise to see how to derive them! For the recursive formula for stirring numbers of the second kind at 7:17, we can think about it in the following way: Say you have n objects and k similar boxes, pick your favorite object and call it O. Now O can either go in a box by itself or it can be in a box with some other objects. There are S(n-1,k-1) ways to put it in a box by itself (since all boxes are similar, we put in a box and then must put the remaining n-1 objects into k-1 boxes). Then, to find the number of ways to put O in a box with at least one other object, we first put the remaining n-1 objects into the k boxes. Then, we pick a box to put O in. There are k ways to pick this box. So there are k * S(n-1,k) ways to do this. Since the two cases share no overlap we can sum them resulting in the recursive formula. A very similar argument follows for the recursive formula at 21:30. Now instead of placing O in a box we place it on a circle. The argument for the first term is identical to the one above. The second term follows from first placing the n-1 objects on k circles. Then there are n-1 ways to place O onto one of the k circles taking into account placement relative to the objects already there. I didn’t argue for the uniqueness of each arrangement but it’s not too hard to see that it holds!
I love it! In fact, that how I memorized the formula too! Just memorizing terms is kind of hard for me, but with the reasoning in mind, it is easy to derive a formula on the fly!
Very nice explanation! It confirmed what I thought. Another explanation for the 2nd term of the Stirling Numbers of the First Kind would be to realize that there are M "gaps" between M points on a circle. You could think of it as saying each of the M objects has exactly one "gap" to the left (or, thinking alternately, the right) of it. And if you are dealing with multiple circles, you just add the number of "gaps" from all the circles up to get how many choices your favorite object O can be added.
Hey @ken the dawg, pretty nice explanation. Its very thoughtful to come up with something so easy to understand. Actually I wanted your help with an assignment. This is assignment's second part which is the number of ways to partition n elements into k boxes with each box having atleast 2 elements. This is famous by the name of associated stirling numbers but I tried to use your logic but I am unable to match my result to the answer. I have (for atleast 2 in each box) S(n, k) = S(n-2, k-1) + (k*k)(S(n-2, k). I came up using the following logic. Say you take two numbers and give them their own box (the first term above). Or you find when those two numbers are together in a box k*S(n-2, k), or when two numbers are in different boxes so k*(k-1)*S(n-2, k). The addition of last two cases gives the term (k*k)S(n-2, k). So total addition gives the above result. But the result everywhere else is S(n, k) = k*S(n-1, k) + (n-1)S(n-2, k-1). I can't even think of how this n-1 can come up in the answer. Please help. I am too much frustrated and tried a lot many times and different ways but always end up with something involving only k's and no n in multiplication.
@@harshitkumar9708 This was a fun one to think about! I had to glance at the general equation found at: en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind#cite_ref-14 to get a sense of how to derive the result as it wasn't obvious to me. Here is the idea for the general problem of finding the number of ways to partition n distinct balls into k indistinguishable boxes with each box having atleast size r (in your case r = 2) To begin, pick your favorite ball of the set and call it O. Now, there are two cases for size (meaning total number of balls) of the box containing O. Either, 1) O is in a box of size > r 2) O is in a box of size = r In the first case, we place all the other balls such that each box has size at least r. There are S_r(n - 1, k) ways to do that. Then, we place O in one of these boxes, of which there are k ways, and that box is now guaranteed to have size greater than r. In the second case, we need to pick r - 1 other balls of the n - 1 remaining balls to go in the size r box with O. There are exactly (n - 1 choose r - 1) ways to do so. Now, we are left with n - r balls to place in k - 1 boxes, each containing at least r balls of which there are S_r(n - r, k - 1) ways to do so. I hope that helps! -Ken
Due to sickness, other commitments, laziness, I am sorry for being inactive for so long. I am still busy, but will try to upload more regularly. Let me know what kind of video you would like to see!
would love to see more about stirling numbers, it'll be fun to see them in their generating function's context, and the thing you talked about linear algebra
Great video! I haven't seen many videos about these interesting sets of numbers. I also like how you explained the reasoning behind the base cases (e.g. S(n,n), S(n,0), S(0,0) ).
Thank u very much for this video, it really helped me a lot to understand what stirling numbers stand for. You really explained it way better, than my professor did. :D
The explanation was very nice, I now understand what Stirling numbers of the first kind are, and I have a problem related to Stirling numbers of the first kind:- Given an rearrangement of the numbers 1 to n, let's define the number of boxes. Each box contains all the numbers starting from a particular number until it reaches a number less than the particular number, and now the next box starts from the next number of the rearrangement. So for example, the rearrangement-1,2,4,3,5 will be partitioned as (1)(2)(4,3)(5). This is because the first box starts from 1 and ends there as 2
Not so well at all , you didn't mention the difference between first kind and second kind .You only said well about second kind.For first kind , you have skipped many understandings. I think your explanation regarding first kind is incomplete.
![What are Stirling Numbers of the Second Kind? [Discrete Mathematics]](http://i.ytimg.com/vi/hKYc9mwPJBA/mqdefault.jpg)
Great video!
I wanted to comment some motivation for the recursive formulas because I think it’s a fun exercise to see how to derive them!
For the recursive formula for stirring numbers of the second kind at 7:17, we can think about it in the following way:
Say you have n objects and k similar boxes, pick your favorite object and call it O. Now O can either go in a box by itself or it can be in a box with some other objects. There are S(n-1,k-1) ways to put it in a box by itself (since all boxes are similar, we put in a box and then must put the remaining n-1 objects into k-1 boxes). Then, to find the number of ways to put O in a box with at least one other object, we first put the remaining n-1 objects into the k boxes. Then, we pick a box to put O in. There are k ways to pick this box. So there are k * S(n-1,k) ways to do this. Since the two cases share no overlap we can sum them resulting in the recursive formula.
A very similar argument follows for the recursive formula at 21:30. Now instead of placing O in a box we place it on a circle. The argument for the first term is identical to the one above. The second term follows from first placing the n-1 objects on k circles. Then there are n-1 ways to place O onto one of the k circles taking into account placement relative to the objects already there.
I didn’t argue for the uniqueness of each arrangement but it’s not too hard to see that it holds!
I love it! In fact, that how I memorized the formula too! Just memorizing terms is kind of hard for me, but with the reasoning in mind, it is easy to derive a formula on the fly!
Very nice explanation! It confirmed what I thought.
Another explanation for the 2nd term of the Stirling Numbers of the First Kind would be to realize that there are M "gaps" between M points on a circle. You could think of it as saying each of the M objects has exactly one "gap" to the left (or, thinking alternately, the right) of it. And if you are dealing with multiple circles, you just add the number of "gaps" from all the circles up to get how many choices your favorite object O can be added.
@@alkankondo89 That is a great explanation for it!
Hey @ken the dawg, pretty nice explanation. Its very thoughtful to come up with something so easy to understand.
Actually I wanted your help with an assignment.
This is assignment's second part which is the number of ways to partition n elements into k boxes with each box having atleast 2 elements. This is famous by the name of associated stirling numbers but I tried to use your logic but I am unable to match my result to the answer.
I have (for atleast 2 in each box) S(n, k) = S(n-2, k-1) + (k*k)(S(n-2, k).
I came up using the following logic. Say you take two numbers and give them their own box (the first term above).
Or you find when those two numbers are together in a box k*S(n-2, k),
or when two numbers are in different boxes so k*(k-1)*S(n-2, k).
The addition of last two cases gives the term (k*k)S(n-2, k).
So total addition gives the above result.
But the result everywhere else is S(n, k) = k*S(n-1, k) + (n-1)S(n-2, k-1).
I can't even think of how this n-1 can come up in the answer. Please help.
I am too much frustrated and tried a lot many times and different ways but always end up with something involving only k's and no n in multiplication.
@@harshitkumar9708 This was a fun one to think about! I had to glance at the general equation found at: en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind#cite_ref-14 to get a sense of how to derive the result as it wasn't obvious to me.
Here is the idea for the general problem of finding the number of ways to partition n distinct balls into k indistinguishable boxes with each box having atleast size r (in your case r = 2)
To begin, pick your favorite ball of the set and call it O. Now, there are two cases for size (meaning total number of balls) of the box containing O. Either,
1) O is in a box of size > r
2) O is in a box of size = r
In the first case, we place all the other balls such that each box has size at least r. There are S_r(n - 1, k) ways to do that. Then, we place O in one of these boxes, of which there are k ways, and that box is now guaranteed to have size greater than r.
In the second case, we need to pick r - 1 other balls of the n - 1 remaining balls to go in the size r box with O. There are exactly (n - 1 choose r - 1) ways to do so. Now, we are left with n - r balls to place in k - 1 boxes, each containing at least r balls of which there are S_r(n - r, k - 1) ways to do so.
I hope that helps! -Ken
This was a great introductory video that helped me get started on the topic! Really appreciate your time and enthusiasm.
Due to sickness, other commitments, laziness, I am sorry for being inactive for so long. I am still busy, but will try to upload more regularly. Let me know what kind of video you would like to see!
using Stirling numbers in some questions.( in other words applications ).
Will do!
Two way of counting theorem and application
Could you answer this: How many ways can you arrange n similar objects in m similar boxes that each box has minimum 2 objects? (2m
Really great video, explaining both the intuition and giving the formulas!
Helped me so much dude, thanks! Keep up the good work :)
would love to see more about stirling numbers, it'll be fun to see them in their generating function's context, and the thing you talked about linear algebra
Thank you for this video dude! Appreciate your attention to detail in explaining the concept. Much help in solving my Combinatorics hw haha
Thank you sooo much !!!!
This was so helpful.
Greetings from Poland
Thank you sooo much for this informative video! literally saved my life
Glad this could help!
thank you so much this was so clear and really helped me understand it!!!
Great video! I haven't seen many videos about these interesting sets of numbers. I also like how you explained the reasoning behind the base cases (e.g. S(n,n), S(n,0), S(0,0) ).
You are a star mate keep it up!
Aww thank you for your kind words!
yess... you explained so beautifully ..
Thank you!
Great video! This helps a lot for understanding my lecture class.😀
4:33 shouldnt the no of items of arrangement be 5p3?
Amazing video! Very clear while also very detailed.
You explained very well. Thanks!
@5:00 You say there isn't a formula, but the Wikipedia page on these numbers lists one.
because of your video, i am going to do great on my paper....thank you
great explenation, way better than my professor
u r just awesome.. really liked it.. really showing ur hard work to make the information simple and understandable
Thank u very much for this video, it really helped me a lot to understand what stirling numbers stand for. You really explained it way better, than my professor did. :D
Was amazing video❤️❤️
Great video. Though, how do know that S(3,2)= 3?
This was really helpful. Thank you
You are very welcome!
This was so helpful, thank you so much!
Thank you a lot! Very useful and clear video
Not only there is a recursive formula but also an explicit formula.
Great video 👍🏻
Good Job Bro!
Thanks. What if you want to have minimum 2 objects in each box? How do you calculate it?
And what will it be for similar objects?
When would you use the first kind versus the second kind?
Very helpful video, thank you sir
You are great man!
Very well explained👌👌👍👍 .....plss make a playlist on combinatorics or number theory......it is much needed plzzz plzzzz
Sure thing! Combinatorics is my favorite topic in math!
@@nchoosekmath could you make videos on combinatorics fast plsss😇😇😇
And plss suggest book for combinatorics and number theory🤗🤗🤗
But if you just put 1 in the first or the second box, the box that is left will be empty too? Could you elaborate on that?
each box must have an element according to definition of the problem
Thanks man you helped me understand it
I am glad!
The explanation was very nice, I now understand what Stirling numbers of the first kind are, and I have a problem related to Stirling numbers of the first kind:-
Given an rearrangement of the numbers 1 to n, let's define the number of boxes. Each box contains all the numbers starting from a particular number until it reaches a number less than the particular number, and now the next box starts from the next number of the rearrangement. So for example, the rearrangement-1,2,4,3,5 will be partitioned as (1)(2)(4,3)(5). This is because the first box starts from 1 and ends there as 2
big thanks this was really helpful!
these numbers have some relation with bernoulli numbers,can you make a video on that topic?
Fantastic idea! I will prepare a video about that!
@@nchoosekmath thank you
Great video!
Thank you!
thank you
Good 👍👍
Thank you! Cheers!
Unfortunately, the quality is horrible, but the content is really interesting ...
Thank you!
why S(0,0)=1?
Thank youu
great
tnx a lot
great
Not so well at all , you didn't mention the difference between first kind and second kind .You only said well about second kind.For first kind , you have skipped many understandings. I think your explanation regarding first kind is incomplete.
Your explanation for S(n, n) is completely wrong.
Thank you!
Thank you