We can also solve this with inclusion-exclusion: Note that !n = n! - number of perms *with* fixed points. The number of perms with k fixed points or more is nCk * (n-k)! (We choose k points as our fixed points, and we don't care about the rest), denote this set of permutations by A_k. We want the size of the union of A1, A2, ..., An, which is exactly given by inclusion-exclusion. So we have: !n = n! - nC1 * (n-1)! + nC2 * (n-2)! + ... + (-1)^n * nCn * 0! = sum_(k = 0 to n) (-1)^(k) (n!)/(k!) Now that's very slick, taking the limit: n!/(sum_(k = 0 to n) (-1)^(k) (n!)/(k!)) = 1/sum_(k = 0 to n) (-1)^(k) 1/(k!) And the denominator is precisely the taylor expansion of e^(-1), so we get e as final answer
The method I used to deduce the subfactorial formula is the inclusion-exclusion principle. We know that there are n! different permutations of n different elements,but to calculate !n,we need to get rid of the ones which map any element to itself,and there are (n-1)! such mappings,which means we subtract n*(n-1)!=n!/1! from the total. However by doing so we subtracted those mappings which map 2 different elements to themselves,there are nC2 combinations of 2 different elements,so we add back nC2*(n-2)!=n!/2!. By doing so we added twice those which maps 3 different elements to themselves,so we substract nC3*(n-3)!=n!/3!...so on In the end we get !n=n!-n!/1!+n!/2!-n!/3!+...+(-1)^n
Another real good video. But I am unfamiliar with the concept of derangement and so at my advanced age, I would need to study this much more carefully to fully understand. But I really like learning math that is new to me. And you explain math very, very well. So I always enjoy your videos. Thanks.
At 12:45, I'm curious why you take the bottom to mean d1 and d0. I would've taken the bottom to be d2 and d1 since we know those values are 1 and 0 respectively. Since you have the recursion formula dn = (n-1)(dn-1 + dn-2), you can always solve for d0. So we can assign it a value for the sake of completeness, but it seems unnecessary for solving the problem.
a hmmm @ 7:00 the dangerous ambiguity of mixing up, for example, address label of n-1 with the content that is n-1? I wonder how such a thing can be handled in a way to make relationship explicit and by so doing removing the ambiguities?
We can also solve this with inclusion-exclusion:
Note that !n = n! - number of perms *with* fixed points.
The number of perms with k fixed points or more is nCk * (n-k)! (We choose k points as our fixed points, and we don't care about the rest), denote this set of permutations by A_k.
We want the size of the union of A1, A2, ..., An, which is exactly given by inclusion-exclusion. So we have:
!n = n! - nC1 * (n-1)! + nC2 * (n-2)! + ... + (-1)^n * nCn * 0! = sum_(k = 0 to n) (-1)^(k) (n!)/(k!)
Now that's very slick, taking the limit:
n!/(sum_(k = 0 to n) (-1)^(k) (n!)/(k!)) =
1/sum_(k = 0 to n) (-1)^(k) 1/(k!)
And the denominator is precisely the taylor expansion of e^(-1), so we get e as final answer
This is the way I typically do it in class.
So the density of the derangements over all the permutations is 1/e for big values of n. Amazing.
That feels intuitive to me somehow
The method I used to deduce the subfactorial formula is the inclusion-exclusion principle.
We know that there are n! different permutations of n different elements,but to calculate !n,we need to get rid of the ones which map any element to itself,and there are (n-1)! such mappings,which means we subtract n*(n-1)!=n!/1! from the total.
However by doing so we subtracted those mappings which map 2 different elements to themselves,there are nC2 combinations of 2 different elements,so we add back nC2*(n-2)!=n!/2!.
By doing so we added twice those which maps 3 different elements to themselves,so we substract nC3*(n-3)!=n!/3!...so on
In the end we get
!n=n!-n!/1!+n!/2!-n!/3!+...+(-1)^n
Another real good video. But I am unfamiliar with the concept of derangement and so at my advanced age, I would need to study this much more carefully to fully understand.
But I really like learning math that is new to me.
And you explain math very, very well.
So I always enjoy your videos.
Thanks.
The Prof is channelling Eric Meijer (of Haskell fame) with his groovy flashy Tie-Dye T-Shirt!
Who?
@@cycklist Dr?
@@cycklist Googling is hard, as history has shown over and over again
Haskell mentioned let’s go
That's a good place, indeed.
At 12:45, I'm curious why you take the bottom to mean d1 and d0. I would've taken the bottom to be d2 and d1 since we know those values are 1 and 0 respectively.
Since you have the recursion formula dn = (n-1)(dn-1 + dn-2), you can always solve for d0. So we can assign it a value for the sake of completeness, but it seems unnecessary for solving the problem.
He chose n=0,1 as his base case. Your choice works too
a hmmm @ 7:00 the dangerous ambiguity of mixing up, for example, address label of n-1 with the content that is n-1?
I wonder how such a thing can be handled in a way to make relationship explicit and by so doing removing the ambiguities?
Can the subfactorial be interpolated as the factorial can? What's !(1/2)?
!n can be expressed in the integral form of ∫ 0 to +inf (x-1)^n e^(-x) dx so I think yes. Insert n=1/2 and !(1/2)≈0.326
@@yuging-q2l yes, and to be exact, that 0.326 number is (+√π)/(2e)
At 6:50 is that a French version of relabel? Or is it just not quite reliable? I think the subject matter is slightly deranged...
Is the third line at 12:36 a mistake or did he do something else? I didn’t quite get why he didn’t just use the recursion to directly get the result
Yes, it should have been d_(n-2) - (n-2)*d_(n-3) and same mistake in the next line. But in the last line it is correct.
Derangements are pretty rad.
A disappointingly low value for all friends of Secret Santa.
17:24
...to stop.
@@Igorious92😁
"And that's a good place..."
@15:20 where does the first 1 in the expansion come from?
Wouldn’t that be corresponding to the d_0/0! term but that should be 0 not 1
When n=0, what one permutation changes all numbers if not any number?
That’s a good place
2stop
One suggestion for a future video : What is the sum of the serie with general term (!n)/(n!)-1/e ?
Beautiful
"And that's a good place ..." (and that's a good place to stop) => not even time for the abortion of time?
It's a good place to what??? 😢
Combinatorial math?
Sounds like a doctor's approach.
We can't be surprised that it's e again. How many factorial-based numbers >1 are there?
this is getting out of hand, it’s absolutely deranged!
everywhere i go i see his face Mr Euler. Your number is everywhere ...
And that's a good place to... The rest of this sentence is left as an exercise to the reader
Would have been simpler to just ask for the limit of (!n/n!) in the first place
But then we would not have gotten a chance to look at derangements.
This all looks deranged 😂
there exist a better understandable explication by blackpennredpenn😂
Hehe Dn
Let me see if I have this right: !n = pizza