a subfactorial limit

[@Just-in-time3]

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

[@Calcprof]

This is the way I typically do it in class.

[@franksaved3893]

So the density of the derangements over all the permutations is 1/e for big values of n. Amazing.

[@sugarfrosted2005]

That feels intuitive to me somehow

[@ChuffingNorah]

The Prof is channelling Eric Meijer (of Haskell fame) with his groovy flashy Tie-Dye T-Shirt!

[@cycklist]

Who?

[@ChuffingNorah]

@@cycklist Dr?

[@stefanalecu9532]

​@@cycklist Googling is hard, as history has shown over and over again

[@CielMC]

Haskell mentioned let’s go

[@yuging-q2l]

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

[@edwardlulofs444]

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.

[@Wielorybkek]

That's a good place, indeed.

[@gregsarnecki7581]

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...

[@miraj2264]

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.

[@minamagdy4126]

He chose n=0,1 as his base case. Your choice works too

[@kajdronm.8887]

A disappointingly low value for all friends of Secret Santa.

[@TheMemesofDestruction]

Derangements are pretty rad.

[@pierreabbat6157]

Can the subfactorial be interpolated as the factorial can? What's !(1/2)?

[@yuging-q2l]

!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

[@xinpingdonohoe3978]

​@@yuging-q2l yes, and to be exact, that 0.326 number is (+√π)/(2e)

[@Alan-zf2tt]

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?

[@divisix024]

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

[@thomasrl194]

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.

[@kcz6865]

When n=0, what one permutation changes all numbers if not any number?

[@Happy_Abe]

@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

[@rainerzufall42]

"And that's a good place ..." (and that's a good place to stop) => not even time for the abortion of time?

[@kajdronm.8887]

"And that's a good place..."

[@MonsieurSeize]

One suggestion for a future video : What is the sum of the serie with general term (!n)/(n!)-1/e ?

[@wilderuhl3450]

That’s a good place

[@orionspur]

2stop

[@goodplacetostop2973]

17:24

[@Igorious92]

...to stop.

[@BikeArea]

​@@Igorious92😁

[@alre9766]

Beautiful

[@singious]

Sounds like a doctor's approach.

[@xinpingdonohoe3978]

We can't be surprised that it's e again. How many factorial-based numbers >1 are there?

[@DeanCalhoun]

this is getting out of hand, it’s absolutely deranged!

[@RafaelSCalsaverini]

It's a good place to what??? 😢

[@emre_galois]

everywhere i go i see his face Mr Euler. Your number is everywhere ...

[@maxhagenauer24]

Combinatorial math?

[@andrewparker8636]

And that's a good place to... The rest of this sentence is left as an exercise to the reader

[@franepoljak9605]

This all looks deranged 😂

[@WRSomsky]

Would have been simpler to just ask for the limit of (!n/n!) in the first place

[@talastra]

But then we would not have gotten a chance to look at derangements.

[@stefanschroder4694]

there exist a better understandable explication by blackpennredpenn😂

[@CielMC]

Hehe Dn

[@SeanChapman-q1k]

Let me see if I have this right: !n = pizza