I understand we have to round to the nearest integer because we can’t have a non integer amount of derangements. But i guess I’m a little confused on how we know for sure that rounding will result in the right answer
Don‘t worry, that was not explained in the video. The reason is simply that the approximation 1 - 1/1! + 1/2! - 1/3! - … + (-1)^n/n! = 1/e is somewhat accurate. For when you plot the alternating behaviour of this sequence, you can see that if n is even, then as the next term added is negative, you are currently above the limit, and if n is odd, you are below the limit. But the next term has only size 1/(n+1)!, which is quite small. So we know that D_n = n! (1/e + r_n), where abs(r_n)
I have a question! I generally think of e as being fundamentally related to compounding growth, similarly to how pi is thought of as being fundamentally related to circles. So with that in mind, is there some important relationship between derangements and compounding growth? If there is, it isn't apparent to me.
(If u are a 3b1b reviewer, watch the video before reading my comment lol) I kinda got lost halfway through with all the math jargon 😅. First we were talking about hats and parties and then suddenly set intersections and permutations? The rest of the video seems to be mostly symbol manipulation and I think I'd understand it better if the actual math could be presented more closely to the context of the story. (I.e. talking about permutations of physical hats in a box, rather than items in a set)
Basically we consider the outcomes as ordered quadruples. For example, if there are 4 people, (1,2,3,4) can denote the outcome that everyone receives their hat. (2,1,3,4) denotes the outcome where the first person takes the 2nd guy's hat and the 2nd guy takes the first guy's head and the rest got their own head. So, you can consider the total number of ordering in this ordered quadruple to be 4!. Also, derangement here considers all cases where the i-th entry is NOT EQUAL to i, for all i.
Great video, great animation
I accidentally found the video by searching Euler's hat into TH-cam instead of Google
Discovered this right after taking a combinatorics-heavy discrete math class-- great vid!
I understand we have to round to the nearest integer because we can’t have a non integer amount of derangements. But i guess I’m a little confused on how we know for sure that rounding will result in the right answer
Don‘t worry, that was not explained in the video. The reason is simply that the approximation 1 - 1/1! + 1/2! - 1/3! - … + (-1)^n/n! = 1/e is somewhat accurate. For when you plot the alternating behaviour of this sequence, you can see that if n is even, then as the next term added is negative, you are currently above the limit, and if n is odd, you are below the limit. But the next term has only size 1/(n+1)!, which is quite small. So we know that D_n = n! (1/e + r_n), where abs(r_n)
Very good explanation!
I have a question! I generally think of e as being fundamentally related to compounding growth, similarly to how pi is thought of as being fundamentally related to circles. So with that in mind, is there some important relationship between derangements and compounding growth? If there is, it isn't apparent to me.
How is this related to computer science?
(If u are a 3b1b reviewer, watch the video before reading my comment lol)
I kinda got lost halfway through with all the math jargon 😅. First we were talking about hats and parties and then suddenly set intersections and permutations? The rest of the video seems to be mostly symbol manipulation and I think I'd understand it better if the actual math could be presented more closely to the context of the story. (I.e. talking about permutations of physical hats in a box, rather than items in a set)
Basically we consider the outcomes as ordered quadruples. For example, if there are 4 people, (1,2,3,4) can denote the outcome that everyone receives their hat. (2,1,3,4) denotes the outcome where the first person takes the 2nd guy's hat and the 2nd guy takes the first guy's head and the rest got their own head. So, you can consider the total number of ordering in this ordered quadruple to be 4!. Also, derangement here considers all cases where the i-th entry is NOT EQUAL to i, for all i.
Great vid but can go slower for others