Subfactorial, a recursive approach

Start learning today, click brilliant.org/... to check out Brillant.org. First 200 people to sign up will get 20% off your annual premium subscription!
In how many ways are there that we can do gift exchanges so that no one gets his/hers own gift back? Watch and find out this "derangement" concept! #derangement #ChristmasGift
Check out !0, • 0!=1 and !0=?
Zero subfactorial
Derangement, recursive formula of subfactorial, brilliant.org/...
Please subscribe for more math content!
☀️support bprp on Patreon: / blackpenredpen
Guess what my first job was! • My First Job Story ,
My simple setup: 😃 • My Simple KZbin Setu... ,
Check out my site & social media
😃 blackpenredpen...
😃 / blackpenredpen
😃 / blackpenredpen
Thank you for supporting! You're awesome and I know it!
blackpenredpen | 曹老師

[@christophermusso]

Small error: In the expression for !3 on the right side of board you have !(2-1) instead of !(3-2).

[@blackpenredpen]

Ah yes. Thank you.

[@christophermusso]

@@blackpenredpen You're welcome. Thank you for all the great vids!

[@wowo316g5]

B

[@blackpenredpen]

4! = number of ways to sit 4 people in 4 chairs !4 = number of ways for them to do Christmas gift exchange so that no one gets his/her own gift back

[@ErickSousa-lx3qr]

Hello. How can I calculate the derrangements of some elements when there are repeated ones? For example : How many derrangements does the word "purple" have? Pleade help me !!! I can't find this in any place of internet.

[@Lordoftheflies234]

Prove that lim n->infinity of n!/!n = e ;)

[@blackpenredpen]

Ericktubao xd I did the video for you kzbin.info/www/bejne/fnvNhmSlrKl1ps0

[@ErickSousa-lx3qr]

@@blackpenredpen Thank you so much !!!

[@aniruddhvasishta8334]

Is there a non recursive formula for subfactorial(n)?

[@alekseikhalin5808]

1:37 "I think you guys know the answer, I don't..." Shows the answer on his back Not bad, bprp

[@blackpenredpen]

Jhames Struggle : )

[@valeriobertoncello1809]

What, this video was uploaded 50 minutes ago, how is this comment 4 days old???

[@Guysudai1]

unlisted video quickly probably?

[@blackpenredpen]

Guysudai1 yes

[@mustardthe2ndkingoffastfoo570]

@@valeriobertoncello1809 D-mail

[@omarifady]

The really saddest story in math is that !1=0 😭😭😭😭💔

[@blackpenredpen]

Fady Omari true.....

[@sarveshjadhav4315]

But, the real question is what is 'i!' And '!i' ?

[@alekseikhalin5808]

Sarvesh that's not a *real* question.

[@NeerajSharmah2c2o4]

That's an imaginary question sir.

[@markorezic3131]

An imaginary question, that could have a real solution?!

[@someonesomeone4099]

Sarvesh Gamma function 😂?

[@rossjennings4755]

¡! is what a character in a Spanish-language cartoon says when startled, and !¡ is a percussive alveolar click. But that doesn't really answer the question, does it?

[@ffggddss]

Also, !0 = 1. When there are no objects, doing nothing (the identity permutation) results in no object left in its original place! This definition also satisfies the recursion. And another useful way to write the recursion is !(n+1) = n[!n + !(n-1)] Fred

[@AndDiracisHisProphet]

yea, as if mathematicians have 3 different friends... 7:45 that is a much more realistic situation

[@alexyoize]

1:37 spoileeeer!!! ;-;

[@blackpenredpen]

: )

[@pocarski]

now i have a fancy way of describing my life: "subfactorial one"

[@welltypedwitch]

That shirt is so genius!

[@ryanjagpal9457]

What does it say?

[@nanashi_74_]

1:36 he spoiled the answer 😂

[@jumbochamploon2591]

but what is !0 ? Is it 0 because all 0 people get their own gift back or 1 because nobody gets their own gift back?

[@tejaskrishna6802]

1

[@jameroth7661]

Look at the formula for !2= (1)(!1+!0) we know !2=1 and !1=0 so we can conclude 1=(1)(0+!0) if we simplify this we see that !0=1

[@zepic3173]

@@jameroth7661 that logic doesn't work

[@Uni-Coder]

@@zepic3173 Wikipedia "Derangement" says that !0 = 1

[@elliottsampson1454]

!1=0(!0+!-1) 0=0(1+!-1) 0=0×1+0×!-1 0=0×!-1 0/0=!-1 Well that didn't work Let me try again !0=-1(!-1+!-2) 1=-(!-1+!-2) -1=!-1+!-2 that still doesn't narrow it down much

[@canaDavid1]

If you test this formula on normal factorial (using n!=n(n-1)!) (n-1)((n-1)!+(n-2)!) (n-1)(n-1)!+(n-1)(n-2)! (n-1)(n-1)!+(n-1)! (n-1+1)(n-1)! n(n-1)! n! So this holds for factorial also. Interesting how much initial values change the result.

[@CarmenLC]

wait theyre the same fibonacci-ish formula with different starting values? wow

[@rituchandra6325]

basically, subfactorial is the number of possible derangements of a group?! wow

[@NonTwinBrothers]

Some friends were talking about gift giving Naturally first think I thought of was this!

[@washizukanorico]

Great video, didn t know about this derangement. The part about the “proof” of the recurring definition was kinda obscure to me ... I mean after thinking about it for a while I got convinced it worked but a better illustration (maybe a tree or whatever) would have been nice. I know it s hard to present complex stuff clearly most of the times ... but hey you ve get two differently colored pen, we know you can do it :) Thank you for teaching this new concept to me!

[@dude7038]

7:47 Hollywood actor 😂

[@matteopagnini5795]

May i ask why you can generalize the formula to as many people as you like as you say at 6:12

[@gurpremsingh]

Wow you're really good at explaining! Loved it❤

[@tsukibackup1513]

blackpenredpen: *asks complicated math question* also blackpenredpen: *showes answer on back* you're my favourit youtuber. I like your ways of doing things.

[@dwaraganathanrengasamy6169]

Thank you so much for such a great gift. It helps me remember it. 😍

[@blackpenredpen]

Dwaraganathan Rengasamy thank you!!!!

[@yuvrajsinghraj]

Here's a JEE Advanced Derangement Problem Six cards and six envelopes are numbered 1, 2, 3, 4, 5, 6 and cards are to be placed in envelopes so that each envelope contains exactly one card and no card is placed in the envelope bearing the same number and moreover the card numbered 1 is always placed in envelope numbered 2. Then the number of ways it can be done is

[@granadierfc1953]

When 0!=1 , and !1=0

[@howdy832]

And !0 = 1

[@subhrajyotidutta4725]

How do we prove limit n->inf n!/!n=e

[@DarwinSPPD]

I kind of expected !4 to be an inverse factorial function from 4. Proven wrong.

[@Hampardo]

No inverse for factorial, since 0!=1!

[@Mr.Sandman-83]

4! for him: A mathematical process. 4! for me: FOUR

[@DavidMartinez-ht8pp]

Why nobody uses n¡ for that instead of !n that can be confusing if you are multiplying, ex: x!n, is it x!*n or x*!n? It would be easier if it was xn¡ and you would know which part is subfactactoriated

[@ananyapathak8701]

Christmath gift ..!

[@holyshit922]

Solve ordinary differential equation and find series expansion of the result (x^3+x^2)A'(x)+(x^2-1)A(x)=-x A(0)=0

[@MOHNAKHAN]

So, Which way you are gifting me...?

[@MemeLord42]

TIL I thought completely wrong of subfactorial, I thought !n = (n-1)!

[@MediTation-dc4cn]

Dude it's okay, just don't scream so much

[@That_One_Guy...]

There's this weird formula that i don't know how to proof but it's much better than recursive approach : !n = Round(n! / e) (you get the 1/e from Maclaurin series of e^x when x = -1)

[@Shishir27]

(Deranged)ments

[@BetaNegative]

Thanks for explaining person 1 getting D means person 4 can't also get D. I'm serious! Maybe it's clear in retrospect, but I wasn't able to understand this from the textbook or anywhere else online.

[@sharpmind2869]

0!=1 and !1=0 great 😊😎

[@mjz5853]

原来!n就是错排数啊……其他地方有用这个记号的么……

[@neverdie0001]

Will OEIS add the sub factorial sequence “0129…”?

[@asish6892]

What is !0?

[@soumitradas3714]

Sir,can you make a video on Lambert's W function !! I've no idea about that. Waiting for your video.

[@JJPMaster]

He did. A year ago

[@lewisbulled6764]

Hey blackpenredpen, could you help me with this question please? Differentiate (ax^2+bx+c)*ln(x+sqrt(1+x^2))+(dx+e)*sqrt(1+x^2) with respect to x

[@eyeofthasky]

9:05 NO! 3-2 !^^ its always "n-2" :D ..luckily 3-2 is the same as 2-1 xD

[@jarikosonen4079]

What about inverse factorial as x!=120 and x!=y ?

[@hermdude]

Interesting. My first thought was that the notation's similar to the relationship between exponentiation and tetration, so I assume !4 = 4!×3!×2!×1!.

[@blackpenredpen]

hermdude that's a "superfactorial". In fact it's on my to do list. : )

[@Wecoc1]

And he finally did it, guys!

[@yassinenacif418]

8:55 3-1 mm.... is 2, Yaeh don't worry I know that don't worry; Hhahaha

[@wellpickup4186]

Hi bro I'm from Indian. I want to tell you that you are so good at math.. I just want to be like you

[@blackpenredpen]

learn something with me thank you!!

[@imperr0r723]

Bprp

[@ryanjagpal9457]

Yeah this makes no sense to me, the note equation thing and the !1, !2, !3 looks clapped

[@mnnasimi]

Sir could please solve (COS20+√3 SIN20)/COS40

[@malignusvonbottershnike563]

Did you ever get an answer? Anyway lol, just turn cos(20) + sqrt(3)*sin(20) into one expression in the form R*sin(20+x), using trig addition formulae. That should come out to be 2*sin(20+30), which is 2*sin(50), but that also equals 2*cos(90-50) = 2*cos(40). So that divided by cos(40) is just equal to 2. Pretty neat!

[@bandamkaromi]

Oh Dear!! lol n! vs !n #MerryChristmas #MathForFun #HappyMath

[@blackpenredpen]

yup

[@RJN0607]

This math major never heard of sub factorials. What is !0?

[@LorddualDesigner]

Sorry. Very boring. However, i like your videos. Gave like.

[@mathsyt7267]

OMGOSH... JC maths didn’t even teach!!’nn

[@Areejfz]

The answer is 9 because it was just behind you😁😅🤣 1:36

[@saritanjay]

Hello sir can you make video on integral of x/e^x-1 please sir

[@whatd0605]

I think !4 must mean 1*2*3*4 since it's the opposite of 4!

[@MelomaniacEarth]

Shirt told the ANSWER idk whether correct or not😂😬

[@saultube44]

Never heard of Derangements nor !n, thank you for the lesson Math Master

[@particleonazock2246]

Thumbnail reminds me of Mathologer.

[@user-zx9em4cd7m]

Doraemon music in the backgrounds at the start lol

[@luanascimento3794]

from where I come people would call it chaotic permutation

[@serhiyovych_]

I am drunk as fuck, I didn't understand a single word...

[@shubham1999]

Sir, how to find inverse laplace of s?

[@periyavarchinnavar492]

!4=9 this thing written back on your shirt

[@ethitlan]

Is that... is that Doraemon I hear at the beginning?

[@petermaguire8139]

It seems each specific derangement of n items can be identified in either the !(n-1) or !(n-2) term depending on whether the exchange was a direct swap or not 0 in the MATH exapmle, AMHT, HTAM and THMA are all a result of direct swaps and are present in the !2 term of !4 = 3(!3 + !2) as 3(!2) = 3(1) = 3 i.e. 3 terms, with the other 6 terms being contained in the !3 part of the equation. However since !3 = 2(!2 + !1) it shows all terms are expressed by some expanded !2 term, with items expressed by larger !n implies a greater number of swaps occuring to reach that state - this seems like a trivial point but I wonder can this be related to disorder and degrees of freedom in a system.

[@CarmenLC]

wait… fibonacci? so how is phi related to 1/e?

[@stumbling]

What about !!n? I don't know if this is a real definition but to me this would be like a sudoku puzzle, where only derangements that are derangements of each other are accepted. For example, MATH AMHT THMA HTAM This looks cool but the operator would be trivial by this definition since, !!n = n.

[@Behroozifyable]

Dear BlackandRedpen guy, I have a question on derrangement for you. There are 6 cups and 6 saucers. Each of the 6 has 2 white, 2 red, 2 orange. What is the probability that after a random arrangement no cup goes on top of the same colour saucer?

[@aintgonnatakeit]

I have covid and I can't really do much. So listening to your videos has been a lifesaver. Thanks so much!

[@victorkushnir8843]

You can actually make it a little more simple. !n is basically a rounding up or down (depending on a parity of n ) of (n!/e) .....

[@YorangeJuice]

Four tactforial, if you will

[@DjVortex-w]

Whenever I participate in a secret santa, I always bring a gift that I wouldn't mind receiving myself, so it wouldn't actually suck if I get my own gift.

[@sainathreddyvarikuti4835]

How to send question to u

[@Titurel]

I want that shirt though!

[@rahulchowdhury7635]

sir what is the answer of !0

[@archieharrodine3925]

This is really interesting... but what would subfactorial of a half be?

[@reetjaiswal3950]

Actually sometimes after I buy a gift for someone I feel like keeping it for myself so it'd be great if it came back

[@enerjae7174]

I just cheated and used n!/e for !n

[@DanNguyen-oc3xr]

Wait, how does this work?

[@subhrajyotidutta4725]

This only works if n tends to infinity

[@DanNguyen-oc3xr]

@@subhrajyotidutta4725 so the limit as n approaches to infinity of !n = the limit as n approaches to infinity of n!/e? Can you explain how you came up to this conclusion?

[@enerjae7174]

@@DanNguyen-oc3xr Basically, if you were to divide !n by n! you'd get a value that approaches 1/e as n increases, which is why I divided 24 by e to get !4. I believe for all whole numbers that are 3 or greater, you can divide by e and the answer will be the closest whole number.

[@shambosaha9727]

@@DanNguyen-oc3xr In combinatorics, there is a principle called the Inclusion-Exclusion Principle, you can look it up. Using this principle, one can find that !n = n! (1/0! - 1/1! +1/2! -1/3! +...+(-1)^n * 1/n!) A value that approaches n!/e as n get larger and larger, which can be proved by Taylor series.

[@wahyuadi35]

I'm interested in joining in brilliant.org, but it costs some money. :(

[@stumbling]

I feel like this should be called "exchange factor".

[@giansieger8687]

is there an explicit formula for the subfactorial?

[@ampisiades]

!Nice watch

[@Supreme-oq8ii]

Beard where😱

[@aintgonnatakeit]

7:50 hahaha

[@jakolu]

With only 4 people, there's a 15/24=62.5% chance of at least one person getting their own gift back...

[@Flourish38]

yeah I guess you could calculate the odds of that happening by doing (n! - !n)/(n!)

[@sagarmaindola]

Doraemon

[@JPL454]

Wow

[@wpbn5613]

this recursive formula also works for normal factorials

[@yegorgorodzha9921]

Yes! And only the initial condition !1=0 makes it go in a different direction

[@robotkarel]

148349

[@khajiit92]

is this unlisted on purpose?

[@DjVortex-w]

I wonder if it's a mistake.

[@blackpenredpen]

WarpRulez No. I just want to space out the uploads.

[@windywinend586]

!4!

[@admink8662]

Is it possible to get x! = !x?

[@subhrajyotidutta4725]

Yes

[@skalderman]

0 it is

[@noahniederklein8081]

Dang this is actually cool!

[@hopp2184]

Hey blackpenredpen, I have a video idea about recursion. For every iteration a(n)=k*a(n-1)+c Find the explicit form of a(n) :)

[@funkyflames7430]

Lol, that is easy man. a(n) = (k^n)* a(0) + c((1 - k^n)/(1 - k)) Where a(0) is the 0th term You can look up iterative functions on wikipedia and find loads of info

[@kingdagat9642]

In my knowledge based on my engineering colleagues, we solve !n by n!/e , is this acceptable?

[@elietheprof5678]

Seems close enough, someone could maybe devise a proof of how the two converge? Idk

[@That_One_Guy...]

I think it might have to do with the integral definition of n! and of course !n

[@lorexcod]

Can !0 exist?

[@swenji9113]

Yes, it is 1. The only permutation of a trivial set happens to be a derangement. Indeed, there is no element so no element can be sent to itself

[@gnikola2013]

Oh boi, I do love Hmats!

[@susilxavier7675]

I find the answer at 1:37

[@msolec2000]

Ouch, my ears...

[@philipjohnregala339]

Can you please integrate from 0 to + infinity (1-a)a^x dx = 1 what would be the value of a? it's been a year now, I'm still messing with this problem. Thanks a lot!

[@anankelpis]

As (1-a) is a constant, you can just write it outside of the integral. The integral of a^x dx then evaluates to a^x/ln(a). Plugging in the bounds you get 1/ln(a)(a^inf - 1). As your integral must not diverge, we can conclude a < 1. Then a^inf tends to 0. The whole equation simplifies to ln(a) - a + 1 = 0, which has the obvious solution a = 1. Other solutions do not exist, which you can verify by the following: Let f(a) = ln(a) - a + 1. Then f'(a) = 1/a - 1. Thus, the function has a maximum for a = 1. Furthermore, f''(a) = -1/a^2, thus the function is concave everywhere. Unfortunately, a = 1 is not a solution of your integral equation. Thus, it has no real solutions. You might want to try finding imaginary solutions with f(a) = 0 and Re(ln(a)) < 0, which I am not an expert in. I hope I could help.

[@angelmendez-rivera351]

Stefan Albrecht How does the equation simplify to ln(a) - a + 1 from the premise that a < 1? 1/ln(a)*(a^Inf - 1) = 1 with a < 1 implies 1/ln(a)*(-1) = 1. Multiplying each side by ln(a) (which we can do, since a priori we know a cannot be 1 because the original integral does not work) gives ln(a) = -1. This then has a = 1/e, and (1 - 1/e)*1/e^x = e^(-x) - e^(-x+1). e^-x integrated from 0 to positive infinity is -e^-Inf - -e^0 = 0 + 1 = 1, while the second integral is simply 1/e. This does not subtract to 1, so I think this is a much easier proof that there is no real solution. For complex solutions, we simply note that a^Inf - 1 = ln(a) = ln |a| + i arg z. On the other hand, a^b, where is complex, = e^(b ln a) = e^(b ln |a|)*(cos(b arg a) + i sin(b arg a)). Now, the exponential will converge with |a| < 1 as b -> infinity. Now, we already disconfirmed arg a = 0, because we showed no positive real solutions exist. However, for any other arg a, the limit does not exist for the expression above. Therefore, there are no complex solutions.

[@anankelpis]

@@angelmendez-rivera351 I think you have forgotten the factor of (1-a) that the original integral contains. It is (1 - a) * Integral a^x dx = 1/ (a^inf - 1)/ln(a) = 1/(1-a) 0 = 1 + ln(a)/(1-a) = (1-a+ln(a))/(1-a) and with a not equal to 1 this gives 0 = 1 - a + ln(a)

[@angelmendez-rivera351]

Stefan Albrecht I see, understood.

[@angelmendez-rivera351]

Stefan Albrecht In such a case, then it is easy to see why we should restrict ourselves to Re(log(a)) < 0 since we already know that a^Infinite only converges for |a| < 1, and the case of |a| = 1 was already discarded. Namely, log(a) = log|a| + i arg a, so Re(log(a)) < 0 implies log |a| < 0, which implies 0 < |a| < 1. As for f(a) = log(a) - a + 1, we know the complex logarithm, so we can substitute as log |a| + i arg a - Re(a) - i Im(a) + 1 = [log |a| - Re(a) + 1] + i[arg a - Im(a)] = 0. From here, we must proceed to solve 2 independent equations, log |a| - Re(a) + 1 = 0 and arg a - Im(a) = 0. I’ll post a new comment when I find the way to continue solving the problem.

[@jcmc3445]

the ending was epic! :)