A Lifelong Mathematical Obsession

[@AnotherRoof]

CLARIFICATIONS AND CORRECTIONS Correction: In my efforts to simplify the derivation to make it more video-friendly, I did make a mistake. Sorry about this! The final formula is slightly wrong in that the k=0 case in the final sum should yield n!, when in fact the k=0 case as presented in the video yields 0. The k=0 case is "count all permutations which contain at least 0 forbidden pairs" which is equivalent to "count all permutations" which is of course n! but I didn't account for that in my simplification! One viewer suggested this alternate presentation, which I agree with: Take the sum from k=1 to n-1 and add n! on at the end. Clarification: So I really should clarify, I didn't entirely come up with this proof! As I mention at 00:00:34, this problem is already solved, and at 01:05:14 I mention this is an adaptation of Abramson and Moser's proof. They go about things much more generally and *then* apply it to this problem. I took some of their ideas and adapted them specifically for this problem from the start. The idea of counting "forbidden pairs" is my own way of streamlining their solution but I don't do enough *new* stuff to take credit for deriving this formula.

[@Jrakula10]

although you did mention that its an adaptaion of moser's proof, you mention it at the end of an hour long video. aint nobody going to see it. for future reference i think its better to put it at the start of the video! also great video!

[@christianbarnay2499]

@@Jrakula10 He mentions it right at the start. He says he knew there already was a proof but it seemed very complex to him and for years he didn't dedicate himself to fully understand it. But now he finally made that effort.

[@AnotherRoof]

@@christianbarnay2499 Thanks for defending me, I appreciate that -- but to be fair I think @Adam Jrakula does raise a legitimate concern and I do regret not being crystal clear about that upfront!

[@comma_thingy]

@@Jrakula10 Then again, references do generally go at the end of a paper anyway, and this isn't even being presented as a new proof so an interested party should be able to find the relevant information

[@JohnDoe-ti2np]

Great video! And congratulations on being able to contribute to your lifelong obsession by proving John Keith's conjecture. But as of this writing, the OEIS still lists it as a conjecture. Did you publish your proof, or at least make it publicly available somewhere? If so, then the OEIS entry should be updated.

[@hakr14]

Oh my god. At 00:03:30, I had a realization: "this is that shuffling problem!" As a kid, I breifly became obsessed with the idea that a collection of items wasn't really, truly shuffled, unless you could do it in a way such that none of them are adjacent to one or more of their original neighbors. As a teen, I realized that it's trivially impossible to do this for 2 items, and provably impossible for 3 (i just worked through each of the 6 permutations). Never gave it much thought after that... Haven't watched past this point yet, so I imagine you bring this equivalence up. I've never left a comment before finishing a video before, but it's been a while since I've been excited about a problem like this. I guess we were both weird kids, huh? Thanks for this content, it's somehow always more engaging than I expect.

[@kikones34]

Ironically, shuffling it that way makes it a worse shuffle, since you know that it's impossible for two items to be adjacent to their original neighbors, whereas true random shuffling gives you no information about the order of the items!

[@loganabel9321]

He mentions this later as "forbidden pairs", and says it's a bijection of the original problem

[@lorenzodiambra5210]

now I'm still thinking about it 🤣

[@lorenzodiambra5210]

6:44 please do any of us comment readers know what the problem of counting the unequal shapes of n adjacent squares can be called?

[@rossjennings4755]

This makes me curious about the asymptotic behavior of the solution for large n. If you randomly shuffle a large number of items, how likely is the resulting shuffle to have this property? Does it approach 1, or 0, or some finite number? The solution we ended up with is complicated enough that it's hard to tell.

[@finminder2928]

Proving some obscure conjecture, relating it to a toy problem thought up when you were young. The process is such a cool thing.

[@enochliu8316]

9:17 There is indeed a piece in Shogi that moves like that, the Dragon King. The puzzle can be restated as the n Dragon King problem.

[@AnotherRoof]

Someone else made that comment during the premiere -- really great fact! And the "n dragon kings problem" is way more badass.

[@Schindlabua]

In fairy chess it's sometimes referred to as the Admiral, a combination of Rook and Ferz. (Ferz being a bishop that can only move one square)

[@SgtSupaman]

@@AnotherRoof , the piece is also known, more briefly, as the dragon. The "n dragons problem" rolls off the tongue a bit better, I think.

[@pocarski]

@@Schindlabua Very interesting, where I'm from, Ferz is just another name for the queen (and the more common one actually)

[@Jrakula10]

4:24 that's got to be the best fidgeting habit. imagine some genius seeing your randomly fidget in public and calls you out for going through all the permutations.

[@PhilippeCarphin]

The skill with which he moves his fingers independently is really impressive.

[@obscurity3027]

His ring finger dexterity is phenomenal!

[@olanmills64]

😏

[@fasullamail]

There is where I realised I'm not psycho enough for this specific problem...

[@asailijhijr]

He has been practising since he was about 6. This doesn't diminish the impressiveness.

[@w花b]

Is that how it feels to be trapped in your own body?

[@HappyNBoy]

So... I just now realized that this is "the urinal problem" as my friend and I referred to it, where there's a line of guys waiting to use the urinals and you don't want to be that guy who walks right up to the guy just before you in line who hasn't started peeing yet, so you can't pick an adjacent urinal to the person directly before you, but can be adjacent to an already in use urinal.

[@RichConnerGMN]

mathematical pissing

[@plfreeman111]

One of these your friends? people.scs.carleton.ca/~kranakis/Papers/urinal.pdf

[@pomtubes1205]

:/

[@pomtubes1205]

:0

[@stephenj9470]

Almost, but there are a few more constraints. If there are 5 urinals, and the first two people go to 1 and 5 respectively, you can't go to 2. You are required to choose #3 and #3 alone.

[@ThatsRaf]

Man, you single-handedly reinvigorated my interest in math 10 years after I graduated (comp sci). I can't believe how clear and concise you make it all out to be. Kudos!

[@Fogmeister]

Single-handedly 😂 Get it! 😂

[@lorenzodiambra5210]

16:54 I'm probably wrong but could not think that the function and the sum from n to 0 of the possibilities of a finger down on n?

[@tylerduncan5908]

This premier is amazing and it's really impressive that you managed to come up with a solution. While elegant simple proofs are often well liked, it's important to also appreciate problems with solutions that take a lot of skill, time, and rigor

[@AnotherRoof]

I really should clarify that this isn't entirely my own work -- as I say in the description and at 01:05:14, this proof is an adaptation of Abramson and Moser's approach!

[@AsianChuGaming]

You have such a natural talent for teaching and balancing tangible clarity with abstract principles. I've been using the kCx equation for years for all sorts of subjects but I think only after watching this do I recognize the power of it and understand how to apply it when working out problems. I found your channel last week and literally finished every one of your videos in 2 days. Your series on numbers and set theory is among the most impactful knowledge I have ever received and sent me down an obsessive rabbit hole that has made math more exciting than it ever has been. Thank you so much for what you do.

[@aguyontheinternet8436]

holy crap I used to do this as a kid. I would tap my fingers using the exact same rules you described, and would spend countless hours thinking on the patterns as well. My parents actually had a conversation with me because I would tap the patterns out during conversation and apparently that isn't okay.

[@lyrimetacurl0]

😮

[@bencheevers6693]

I cannot believe the quality of this presentation and education, I believe that I actually followed and understood the whole presentation and that seriously surprises me, I mean I'm not dumb but haven't been in school for 10 years and the only math I do is what's needed in trades, addition subtraction fractions and occasionally some geometry

[@anthonycannet1305]

9:29 should’ve called it the N dragons problem because the king+rook is the same way a dragon in Shogi moves. In Shogi, the way pieces promote is different. Each piece promotes to a specific other piece, and most pieces can promote. If you move the rook to a promotion square, it promotes to a dragon which can move like a rook but also 1 space diagonally, which is a king+rook so we can just call it a dragon. Similarly the bishop’s promotion is the horse (different from the knight) which moves like a king+bishop

[@billionai4871]

I'm stopped at minute 10, but I wanna take a crack at solving this my way. I'm a computer scientist, so while closed formulas and proofs that they work are interesting, I'm usually more fond of finding an algorithm that can get to the answer instead, and the moment you mentioned that in the 6 case, removing finger number 3 gives you a 2 case and a 3 case, my brain instantly latched on to a Dynamic Programming (DP) algorithm. DP works when solving a smaller version of the problem will inform the bigger version in a way that will reduce the amount of calculations that you need to do. A common way to show this strategy is with the fibbonacci sequence: If I want to calculate f(15), I will need f(14) and f(13); the catch with DP is that I will create a "memoization" vector that will remember previous solutions, so if I calculate f(13) first, when is time to look at f(14), I already know f(13) and it is just a lookup. This problem is a little harder than a straight forward DP, but it is still solvable, but we need 2 memoization vectors: solutions_edge, solutions_other; For convenience, imagine that the first vector will always start with the number 1, and it will be apparent why it is important soon (if not yet). The second one has all other solutions for the N sized problem (including the ones starting the other edge). My idea is: 1. Solve the case starting in pin 1; when we do that, we have exactly the case N-1 except we can't pick pin 1 again, so we have solutions_other(N-1); Save this number in solutions_edge(N) 2. Iterate through all the possible pins from 2 up until N/2 (inclusive); by removing pin I, you get 2 groups of size A and B such that A + B + 1 = N. Then you have multiple ways of solving your new situation: 2.1 solve A and B separately; if you start with A, there are solutions_other(A) possibilities to do it, and moving on to be you have solutions_edge(B)+solutions_other(B); Similarly, you may start with B, for a total of 2 * (solutions_other(A) + solutions_other(B)) + solutions_edge(A) + solutions_edge(B); 2.2 for the other cases, you have to have enough legal moves in the B side to be able to interweave A moves in the illegal possibilities, so for every B permutation, follow it and if you find move than A illegal moves, that permutation is illegal, move on to the next. For every legal legal permutation of B that you find, you can calculate how many solutions it can have as follows: 2.2.1: If you have L illegal moves in the B permutation, you can space them my with A choose L options of moves on the A group; so far the permutation has A choose L moves 2.2.2: for the remainder A-L options, you can interweave them as you'd like in the B+L locations; which give you (B+L) choose (A-L) options 2.2.3: the final part is figuring out if for a given set of A-L choices, they can be side by side instead of neighboured by B moves. I haven't figured out how to do it yet. 2.3: Save this number to solutions_other(N) 3. do solutions_other(N)

[@Bruno-el1jl]

Man, this was such a pleasurable adventure! To have that come full circle since childhood must have felt amazing. Thank you kindly random handsome mathematician for the treat. Definitely excited for your future work! Keep sharing! ;)

[@laurenlewis4189]

4:24-4:36 in another life you were one of the best prog drummers. That was actually a really sick beat

[@ancbi]

Another life second channel?

[@junerae]

truly beautiful, thank you. the abstractions built up in "Forbidden Pair Options Part 2" are so satisfying. also, i must be that formula's mother because i think it's pretty great...

[@thomasporter4627]

I think it would help to say "every row of pascal's triangle alternating sums to 0, except the first row. This is the key that makes the whole formula work because the permutations we're interested in, those with 0 forbidden pairs, correspond to the first row and is why the final formula counts only them. Excellent video!

[@heartache5742]

0th actually

[@columbus8myhw]

It adds up to 0^n (where the first row is n=0) :P

[@heartache5742]

@@columbus8myhw but 0⁰ is usually either undefined or 1

[@anneaunyme]

I truly like this video. I think it is the best so far I have ever seen that manages to be both understandable and honest about how chaotic it often is for a mathematician to find a solution.

[@JavierRuizGonzalez]

Alex's introduction is absolutely true: lots of interesting steps, perfectly detailed as always. A very beautiful enumeration problem... Thanks!

[@minerscale]

This is a fantastic video! I love that you didn't start with the proof but rather constructed a story about your attempts to solve it with more and more powerful tools. Awesome problem too!

[@macronencer]

This was an extremely enjoyable journey. Very good and clear explanations, and I particularly liked that you planned your terminology to be as intuitive as possible ("cell", "bin" etc.) As a software engineer, I always love it when people take the time to choose the most meaningful words to minimise confusion.

[@quantumgaming9180]

How do you not have 1 million subscribers yet?? This channel is a not a gold mine, but a DIAMOND mine

[@-_-_-_-_]

I just happened to come across this channel and I'm left wondering why the algorithm gods didn't recommend this to me sooner. Another Roof, I absolutely love the longer math videos. You've gained a long-term viewer. This video was so good in fact that I had to make a Patreon account!

[@codatheseus5060]

I beat through the fire and the flames on expert and I'm still impressed by your dexterity

[@alifarhat667]

It’s funny, because I also conceived of something like this problem as a child. But with two caveats: I considered the CYCLIC case, so 15 and 51 are forbidden, and derived one path, but with five different starting points and two directions, so ultimately 10 paths. But I’ve never sat down and proved that list is exhaustive

[@AnotherRoof]

I also thought about this too and it's another one of my fidgeting habits! And it is exhaustive for the 5-case but not 6-case and beyond. This is easy to see if you draw the graphs; for 5-case you get a "pentagram" graph but for the 6-case you get a "Star of David" plus some extra edges which yields more solutions!

[@RubikxsMan]

I conceived of the problem in this way, (also with my fingers), years ago and hadn't thought of it since. Glad to have stumbled upon a video on it.

[@oleg-avdeev]

If I remember correctly trying to solve something similar, adding cyclic property means that you’re trying to position kings on a torroidal chess board so that no king is in check. Haven’t watched the video yet, this might get mentioned

[@AnotherRoof]

@@oleg-avdeev In this case it's actually a cylindrical board because the first choice is allowed to be adjacent to the final choice. There's an amazing ebook out there with lots of problems like this for different pieces on different boards -- will edit my comment later with a link.

[@RichConnerGMN]

holy shit cyclic geometry dash

[@AsgerJon]

I can read Danish, and the paragraph at 9:31 is well explained, despite being so old that nouns were capitalized, a practice abandoned in modern Danish. Also, passive voice triggers the grammar police in English. Danish provides a conjugation of the verb indicating passive voice. "For n=4 obtains thus only two... ", anyway, here's a translation into modern English. An Assignment of Combinatorics by S. Hertzsprung To determine to number of ways, by which numbers 1, 2, 3, 4 ... n could be placed in a row such that the difference between each adjacent pair of numbers everywhere must be numerically different from 1. (Meaning, that 3 must not be to the immediate left nor right of 2 or 4, 7 neither to the immediate right nor left of 6 or 8 and so on. - For n = 4, one obtains this only two possible arrangements, even 2413 and the reverse 3142.

[@mr.inhuman7932]

Yes, AnotherRoof, I will come with you on this journey.

[@pelegsap]

This is, without exaggerating, one of the best videos I've ever watched on KZbin.

[@Ash_The_Composer]

Because of the difference in strength of your fingers, its clear and audible at 4:30 tgat each solution is uique

[@hvok99]

This may be my favorite video on KZbin to date.

[@martywsmarty]

Another great video ! This channel is really underrated

[@joe_z]

1:03:10 In the grand scheme of things, at least it has a formula that can be written on one line as a composition of relatively simple functions and summations, even if it's not quite closed form.

[@aguyontheinternet8436]

32:56 small problem, taking the alternating sum of the top row clearly doesn't equal 0

[@souptime8635]

Danish speaker here. The two letters at 9:33 says A combinatorics exercise (by S. Hertzsprung) Determine the number of ways in which the numbers 1, 2, 3, 4, ..., n could be positioned in rows such that the difference everywhere between two numbers next to each other is numerically different from 1. (This means that for example the number 3 cannot stand to the right or to the right to 2 or 4. 7 cannot be to the right or to the left of 6 or 8 and so on. For n=4 there are only two possible arrangements, which is 2413 and its opposite 3142). (5) gives the result u_n, n for n = 1, 2, 3, 4, 5, 6, 7, 8 ..... to be 1, 0, 0, 2, 14, 90, 646, 5242

[@sevret313]

Yup, this exact problem has struct me too. I'm 3:28 in, so I think I want to stop it here and see how far I can get myself.

[@crsmith6226]

Before watching more of it I feel like there has to be some sort of geometric solution to this problem. Something involving choosing vertexes of a polyhedra. I can’t think of it now off the top of my head but it *feels* like there should be.

[@AnotherRoof]

I would love to see a proof based on this approach! I talk about path-complement graphs at some point and maybe they could tie in to the geometric interpretation...

[@angeldude101]

Pascal's triangle played a large role in this proof, and also shows up a lot in geometry, so I would not be surprised in the slightest. The 2^r((n-k)Cr) looks suspiciously similar to the formula 2^(n-m)(nCm) for finding the m-cubes on the boundary of an n-cube.

[@echo.1209]

I love the idea of you tapping out those patterns and one day some other mathematician picks up on the patterns, happens to know about the problem and its solutions, and you become good friends.

[@tunafllsh]

The stars and bars problem is the one I learned in the combinatorial class in my first year of university. I understand it, yet always forget how the solution goes the next day.

[@mr.inhuman7932]

Your work is amazing. Please please please keep on going. For our sake!

[@AnotherRoof]

Thanks! As long as people continue to watch and support me, I have no intention of stopping.

[@ArtificialDjDAGX]

12:40 it strikes me here that this is tangentially, or perhaps even more than just that, related to the P vs NP clique problem. (Best optimization for finding an answer for a graph that I could think of was to apply forbidden pairs to the brute force search, so as to minimize the amount of checks that have to be performed) Ofc. now that I'm looking at the wikipedia entry for the clique problem, it seems like it could be somewhat of an inverse of the one in the video, as it doesn't want vertices with connected edges, while the clique problem only wants connected edges.

[@nyuh]

whoa this is feature length ive only watched a few minutes definitely gonna go back to watch some more thats kinda wild that youve been thinking about this problem lieterally from as a child and the fact that youre actually studying maths so you can figure the problem out... amazing

[@studogYT]

This video is amazing on every level: clear explanation of the problem, logical clear steps to solution, excellent visual aids (the stacking black cards to make the equation especially), excellent video editing (jump cutting to remove the writing on the blackboard for example), an interesting starting problem, the personal historical context, the examination of existing discussion/proofs. Double thumbs up, if I could.

[@CelestinWIDMER]

3:52 I did that as too as a child. I was so happy when I found that there was only one solution (and the symmetrical) for the 4 digits case.

[@biscuitz7422]

Regarding the question at 4:09 for 5-building cases - Spoilers below: Spoilers: I think there's 14 cases that work? It helps that there are a lot of symmetrical cases, so the logic is fairly easily repeatable once you decide on your starting building. - Pushing down either 1 or 5 first gets you back to the 4-building case, so two options apiece for each starting building for a total of 4 combinations, those being 1-3-5-2-4 / 1-4-2-5-3 / 5-2-4-1-3 / 5-3-1-4-2. [4] - Pushing down either 2 or 4 first (we'll pick 2 for the sake of example) forks depending on whether you select the opposite extreme building (5) or the twin of your first destroyed building (4). Picking 5 next only has one valid solution (the one roof showed off in the video) since picking 1 next breaks the puzzle; Picking 4 next forces 1 and then leaves either 3 - 5 or 5 - 3 as valid ends. That means each start has 3 valid solutions for a total of 6 combinations here, those being 2-4-1-3-5 / 2-4-1-5-3 / 2-5-3-1-4 / 4-1-3-5-2 / 4-2-5-1-3 / 4-2-5-3-1. [6] - Pushing down 3 first forks at your second decision (either 1 or 5), and then forks again at your 3rd decision (the two most extreme building opposite to your second selection) for a grand total of 4 combinations. This one isn't super interesting since your only "bad" moves are expressly illegal actions (per the game rules, obviously destroying irl buildings requires some very specific permits lmao), but what can you do. The 4 combinations are 3-1-4-2-5 / 3-1-5-2-4 / 3-5-1-4-2 / 3-5-2-4-1. [4]

[@conor.brennan]

this is crazy to see, I've had this problem in my mind since I was a kid. I wasn't thinking about buildings, just thinking about twitching my fingers

[@AnotherRoof]

I hope you find this solution as cathartic as I did!

[@cloud7982]

Bro when you cycled through the possible combinations you made a sick beat 😂

[@minimath5882]

One of the weirdest thing I learned from this video is that I cannot independently move my fingers like he does at 4:16

[@PhilippeCarphin]

The first time he did it I was like "Oh sh*t"

[@TheLuckySpades]

Commenting for the Algorithm and also to say that this was a blast of a video, love them crunchy combinatorics

[@HomeBologn]

The fact that you understand your problem well enough to make an engaging long-form video that uses simple language that a layperson can understand is extremely impressive. I hope that you're teaching High School or Middle School in the US. We need this kind of Math education here so desperately. Not nearly as badly as we need *proper* Theological education in schools, but still.

[@zachrodan7543]

Like you, i first concieved of this problem as a child, and also in terms of n=5... although in my formulation it was always just about ways of arranging the numbers while separating consecutive numbets. I then spent all of last summer quarter working out the answers for up to n=8... by creating an adjacency graph, counting the allowable hamiltonian paths and circuits on those graphs, and then using some symmetry to get the final counts (there are as many ways to start at 1 and end at 2 as there are ways to start at n and end at n-1; you can go either direction on a path, and you can start at any point on a path that is a closed loop) Probably doesn't help my attempts that i apparently undercounted, at least in the case od n=6, where I only found 76 ways to do it... [Insert mathematically flavored profanity here]

[@AnotherRoof]

@@zachrodan7543 I just want to say that I love that you're working your way through my catalogue and I'm enjoying reading all of your comments!

[@yogesh1535]

Amazing explanation, I just loved the way you discovered this problem in your childhood and made this problem your ambition in the upcoming years of your life

[@puzzlinggamedev]

another nice metaphor for these kind of problems could be music, if you think of playing N notes with similar conditions

[@AnotherRoof]

Yeah, I used to do exactly my finger fidgeting thing but on the piano!

[@puzzlinggamedev]

@@AnotherRoof I wonder, were all the 14 melodies similar in some aesthetic way?

[@AnotherRoof]

@@puzzlinggamedev To be honest it sounds kind of ugly 😂

[@TheLuckySpades]

Sounds like an even stricter version of the Twelve-tone Technique

[@bejoscha]

Very nice video! Love the story and style of presentation. Just browsed in by YT recommendations and was not disappointed.

[@AnotherRoof]

The almighty algorithm must have been pleased with my offering...

[@entitree.]

that triangle plot twist at the end reminded me of how pi sometimes shows up in random and unexpected places. what a wonderful and engaging video, I hope you're proud of your skills in videomaking and teaching!

[@brutalbjoern]

I've thought about this as a kid when trying to lay my fingers over each other without having neighboring fingers touch on a single hand, but I was just happy with one solution which I was physically flexible enough to do

[@jucom756]

55:50 you'll probably address this later, but you actualy overcounted on this step, because the permutations of for example 123 54 6 and 123 4 65 both have k forbidden pairs but overlap on 123654 and 654123. So multiplying by (n-k)! Is overcounting. In your math you account for this, but you describe it as "the number of permutations with at least k forbidden pairs" which isn't true because of the double counting.

[@youtubepremium9253]

It's beautiful that with such simple tools you can solve challenging problems. Very elegant solution

[@omrishavit8843]

I don't mean to nitpick but at 6:21 I think you mean to say there's no known way to /efficiently/ compute the number of Hamiltonian paths in an arbitrary graph. There is a way to compute the number of paths: simply iterate through all permutations of nodes and count the ones that are indeed Hamiltonian paths! Yes the problem is NP complete, which, assuming P≠NP, means there's no algorithm that can solve it in polynomial time. Regardless, there is always a correct brute-force algorithm for all problems in NP

[@Tassdo]

To continue the nitpicking, counting Hamiltonian paths isn't actually a problem in NP as it is a counting problem, not a decision problem. The natural complexity class this problem falls into is #P (sharp P). Your overall point still stands though.

[@MrRyanroberson1]

16:00 while solving polyominoes, i developed a kind of thought-pattern about polynomials like (x-1)^n. this is another such case. pair xy, x pair y, and xy pair are all positive, whereas triple y, y triple, pair pair are negative, and quadruple is positive again to compensate for the overcompensation. there are 4 triples each, 8 pair pairs and 2 quadruples, so all in all the answer is 36 - 8 - 8 + 2 = 22 possible forbiddens. problem solved!

[@MrRyanroberson1]

16:55 i'm guessing this is the inclusion/exclusion principle

[@v0id_d3m0n]

Really cool, and i could actually follow along and understand it! That concrete example really helped, and I loved the feeling of recognising the three techniques/bits of knowledge mentioned prior to the construction of the formula.

[@LucaIlarioCarbonini]

You can have your finger tapping game at minute 4:24 in a pentatonic scale and hear it, some permutations are allowed but you can pick your favourite I guess.

[@iamtraditi4075]

This was really really good! Thank you for presenting this video! Deep explorations of math that anyone can enjoy are really valuable and it's one of the reasons I enjoy this channel so much :)

[@AnotherRoof]

Comments like this make my day -- thanks for watching and glad you enjoyed!

[@philippenachtergal6077]

25:22 Ok, challenge accepted Pure V = 21 - 6 - 7 + 2 = 10 ( +2 because substracting VS and VC has already substracted VCS twice, so you have to put it back one) Like wise you get Pure C = 15-6-5+2=6, Pure S = 17-7-5+2=7 Only VC =6-2=4 ; only VS = 7-2=5, only CS=5-2=3, VCS = 2 Total = 10+6+7+4+5+3+2=37 So none is 47-37=10

[@Blananas2]

I know I'm probably not even 5th person to say something like this in the comments, but you know a puzzle's lovely when you come up with the puzzle in your head during the intro, before you explain it yourself. Great explanation and presentation as always, keep up the good work!

[@mr.inhuman7932]

Excited.

[@MichaelFJ1969]

Excellent and clear explanation. Thank you for your effort in presenting your solution to a wide audience.

[@ThaStam]

Here's an interesting observation: As n gets larger, the ratio of the number of "legal" permutations of 1-n divided by the total number of permutations (n!) gets closer and closer to about 0.1353 (the ratio as a function of n seems to be constantly increasing with a limit of about 0.1353, or at least that's what some testing up to n=2500 showed). That would mean that for sufficiently large values of n (for n>=58 according to my testing) the number of legal permutations could be approximated by: n!*0.1353

[@zachrodan7543]

Another way to justify nC0=1 is that nCk could be interpreted as Given a set with n elements, how many subsets are there with k elements. Every set has the empty set as a subset, and since a set is only defined by its elements, there is exactly one empty subset.

[@Fine_Mouche]

2:45 : what about if instead of not allow the neighbors we don't allow to destroy the closest / the 2 closest ?

[@EpicMathTime]

This is probably the best math video I've ever watched.

[@GaryFerrao]

I’m so happy for you. 😊❤ and i liked this long video

[@willgoodwin-moore947]

I THOUGHT I WAS THE ONLY PERSON WHO DID THIS :’) i was so happy when i came across this

[@Jaylooker]

Is that alternating sum a Euler characteristic of some topological space? You can use the Riordan matrix with the different Pascal triangle at 1:04:20 to fill in to lower triangular matrix. This derives a generating function for this sequence.

[@stef3232]

Oh i am glad that I found your channel. Love your long videos and enjoy going deep here 👍

[@aperson6821]

You just made me remember of finger fidgeting I used to do. It was basically the game you described, but I would repeat the sequence over and over. My reasoning was that tapping two neighboring fingers consecutively "felt bad" in a sort of OCD-manner. This repeating meant that a sequence such as "24153" would be invalid, because repeating it would yield a 3 followed by a 2.

[@SgtSupaman]

That's interesting that you have this form of a cyclical approach, because another comment mentions a different cyclical approach. For theirs, every number has two neighbors, so, using n=5 as an example, 1 is obviously a neighbor of 2 but also a neighbor of 5, since that is the opposite end. What's funny is that these two different approaches of being cyclical work out to the exact same ten solutions in total for n=5 (though I doubt this holds for higher values of n).

[@aperson6821]

@@SgtSupaman Interesting! Maybe our games are more similar than one might think. They both introduce one extra ”pair” that has to follow the rules - mine being the first and last digits in terms of position in the sequence, while the other game checks specifically digits ”1” and ”n” against each other.

[@johnl4885]

Have you looked into Gosper/Zeilberger techniques to find a closed form? Or conclude that there isn't one... At the very least an asymptotic approximation seems in order. I enjoy your enthusiasm, keep it up!

[@fibbooo1123]

The cliff hanger was too much, so I joined the patreon- and the extended cut was amazing!

[@eueumesmoaquelecara4638]

4:02 I'm impressed that you can lower each finger fully independently, I can't do that.

[@Fine_Mouche]

i have a thing i work time to time on since 2015 (mostly with programming because i'm not good enough in maths to solve it) i posted the no-constrain (lvl 0) version on quora and a mathematician answered me with big maths i can hardly understand but he gave me a python program with it (take care it use cmd parameters), on quora : What is the average number of steps it takes for a mobile moving randomly forward or backward along a polygon to visit all edges/sides (=/= all vertex/summits)? But the big question is what about if lvl 0 is visit all edges/sides (=/= all vertex/summits) : -lvl 1: lvl0 + return to the starting point. -lvl 2: lvl1 + by the clockwise direction + no more than 1 backward loop -lvl 3: lvl0 + no more than 1 round-trip for each size of round-trips -lvl 4: lvl1 + no more than 1 round-trip for each size of round-trips -lvl 5: lvl2 + no more than 1 round-trip for each size of round-trips I will try to make another Quora with more detail, my goal for lvl 2 to 5 is to list all the possible path constraints create (lvl 0 and 1, there is infinites numbers of path, but we can still calcule the average number step it take, for lvl0 it's done thanks to the mathematician)

[@alikaperdue]

I missed 24153. Same as you. I played with symmetry on my hands too. I do the grey code count to efficiently count to 1024 on my fingers The result is that my hand will have displayed all combinations of raised and lowered fingers by changing only one finger at a time. When I was going for speed, I noticed that there are some ways to move my hand that are much more difficult. Almost like certain kinds of symmetry are easier than others. Much of it had to do with my digit dexterity limitations. But also, I wondered if it might be something in my brain. Anyhow, I missed the same symmetry as you. Why? Is some symmetry easier for us to notice than others? I'm curious.

[@philippenachtergal6077]

27:00 Hum. Imagine the same problem but with say 5 variables. You can expand the principle of the solution for 3 variables to 5 variables without much problem except that there are now 32 groupings (if you include "None") like the ones shown here. What I'm not sure of is this: how many dimensions do you need to show a single diagram like the one on the bottom right if there are 5 variables or M variables instead of 3 ? What if the sets don't have to be represented as circles/spheres/N-dimension spheres ? And does it change if you specify that you cannot have two disjointed regions of your N-space that represent the same intersection of sets ? With 4 variables, I can add a 4th (non-circle) figure to the 2d diagram and still cover all possible intersections but I cannot add a fifth (I think).

[@hakonanthun3058]

For those wondering, the Danish letter says: To decide the number of ways, in which the numbers 1, 2, 3, 4 ..., n can be put in order such that, the difference the difference between adjacent numbers is everywhere different from 1. (This is to say, that for example the number 3 is to be neither immediately to the right of or to the left of the numbers 2 or 4, 7 neither immediately to the right of or to the left of the numbers 6 or 8 etc. - For n = 4 there is only two possible solutions to be had, namely 2413 and the reverse 3142). The grammar is archaic and lovely, kinda shakespearean

[@Kapomafioso]

4:22 wow that looks like an amazing piano exercise!

[@brandonlewis2599]

Your finger fidget rhythm is awesome!

[@NotSomeJustinWithoutAMoustache]

I'm so confused by k. Is k always just n-1 like what was indicated in 17:47? Is k always less than n or are there cases where k and n can be equal? What is the term for k? I don't even know what k is supposed to be.

[@AnotherRoof]

At that timestamp, k is a number between 0 and n. We have n cards, and we wish to choose k of them, so we can choose 0 or 1 or any number up to n. In analysing Hertzsprung's problem, n is the number of "fingers" and k is the number of "forbidden pairs". A forbidden pair is an instance of two adjacent entries being consecutive, like 12 or 54. So in the n=5 case, we could have 13524 as a valid solution, so k=0 as it contains no forbidden pairs. Whereas 51243 is a k=2 case as it contains 2 forbidden pairs, 12 and 43. Hope that helps -- stick with it! 🙂

[@NotSomeJustinWithoutAMoustache]

@@AnotherRoof Oh it's the number of forbidden pairs, thank you! Idk why I didn't get that

[@eriksteffahn6172]

I think the final formula is a bit wrong. For k = 0 the second sum is empty, so the formula doesn't actually count the case of no forbidden pairs (iterating over the number of parts of zero forbidden pairs doesn't really make sense, so it's not surprising that the formula fails here). An easy fix would be to start at k = 1 and just add n! to the total at the end.

[@AnotherRoof]

Actually when k=0 the whole thing just becomes n!, which *does* count the case of *at least 0* forbidden pairs. Remember, the formula for k counts the number of permutations containing at least k forbidden pairs, and the number of permutations containing at least 0 forbidden pairs is all n! of them. So the formula makes sense and is consistent with the k=0 case. Hope this helps!

[@eriksteffahn6172]

@@AnotherRoof I might be missing something obvious but isn't the formula for k = 0 just (-1)^0 * (n-0)! * sum_{r=1}^0 {...} = 1 * n! * 0 = 0? I get that it should be n! since it's supposed to count all permutations with at least 0 forbidden pairs, which is all of them. But since the n! is multiplied by an empty sum (which evaluates to 0) the whole thing just becomes 0, no? (I'm talking about the formula at 1:03:00 in case this wasn't already super obvious)

[@AnotherRoof]

@@eriksteffahn6172 Oh I see, yes -- I think you're right about that actually. I'm away for the weekend and don't have access to my notes -- I must have something about this but I can't see what the justification is right now (obviously we just set that second sum to 1 in the k=0 case so the whole thing becomes n! but I didn't justify that in the video).

[@markjreed]

Am I crazy or does that formula (copied from the blackboard at 1:03:00) not work? When I plug in n=3 I get an answer of -6: For k=0, the inner sum counts from 1 to 0 and is therefore 0, so the partial sum is 0. For k=1,r=1: the inner sum is 2*(2 choose 1)*(0 choose 0)=4. That's all the r's for k=1, so we multiply that by (-1)^k=-1 and (3-1)!=2 to get -8 so far. For k=2,r=1: the inner sum is 2*(1 choose 1)*(1 choose 0)=2, which is our partial inner sum. For k=2,r=2: the inner sum is 2^2*(1 choose 2)*(1 choose 1)=0, which means our total inner sum is still 2. We multiply that by (-1)^k=1 and (3-2)!=1, which is still 2, and add that to -8 to get -6. What am I missing?

[@AnotherRoof]

This is an error on my part. I'm about to add a pinned comment about this but I'll respond here as well! In my efforts to simplify the derivation to make it more video-friendly, I did make a mistake and that's that the k=0 value should yield n! where instead of actually gives 0 (as you correctly pointed out). In the n=3 case, you get 3! = 6 instead of 0 for the k=0 case, so your final answer was -6 when in fact you get -6+6=0 as the proper answer (which is correct as there are no solutions for n=3). My apologies!

[@markjreed]

​@@AnotherRoof Ah, OK. Well, good to know I'm not crazy. :) Yeah, 3 wasn't a great example; I only picked it because it has so few steps it's easy to show them all in a short comment. I was actually willing to accept that maybe it just produced nonsense negative answers where the real answer should be 0. But when I also got negative answers for 4, 5, and 6, I knew something was wrong either in the formula or my several attempts to replicate it.

[@markjreed]

@@AnotherRoof So I guess the way to notate that would be to pull the k=0 case out of the sigma expression and write it as n! + the sum for k=1 to n-1 of . . .

[@AnotherRoof]

@@markjreed Yep, which is what I put in my pinned comment! The original formula is neater in that regard but has a more complicated derivation.

[@ulfvinr9364]

Around the 55 minute mark, when you are talking about the 4(123)(65) case and the (65)4(123) case, is it because you are using (123) and (65) explicitly and solely, and you need 3 elements, that the 4 doesn't cause issues in that second case? I guess it would have to, because 6(54)(123) is functionally identical to (65)4(123), and (654)(123) only has 2 elements.

[@universallanguageproject]

Nice explanation, you make complex maths easy to understand. You're doing an awesome job.

[@PretzelBS]

I love it when you think you're a genius, then go to the oeis and discover you're problem has been torn to death

[@not_David]

19:20 10/10 explanation of the nCk formula

[@Ardub23]

The version of the five-finger problem that I came up with is a bit stronger: Touch the five fingertips of one hand to the five fingertips of the other, such that adjacent fingers on a hand don't touch adjacent fingers on the other hand, _and_ matching fingers don't touch each other (e.g. you can't touch thumb to thumb). A solution of this version is actually a double-solution of the five-finger problem-one solution for each hand. There are only two solutions to this problem: one is 24153 one the left hand, 31524 on the right; the other solution is the same but with the hands swapped. I've always thought that swapping which hand gets which order results in different hand shapes (notably, the middle finger is curled down in one version and extended in the other). But while writing this, I realized that it also depends on how you lay the hands against each other. It's comfortable to hold them palm-to-palm with about a 90° angle between the two hands, but you can turn them to form the angle the other way (i.e. swap which hand's thumb is close to the other hand's fingertips) to get the alternate hand-shape without swapping the ordering. You can't keep the fingers touching turning, though-they'll get tangled. This, naturally, leads us to wonder about the generalized problem of touching n m-fingered hands in k dimensions.

[@Scum42]

One of my favorite things about this video is your description of where you gave up when you tried this post-grad. You gave up during the most complex step (how many ways can a permutation contain at least k forbidden pairs) with the thought "this is getting ridiculous, there must be an easier way to solve this." Well, as the rest of this video shows, there really isn't. This was only solved by rolling up your sleeves and diving into that mess head first, keeping track of everything as best as you can along the way. This is a really great lesson on the fact that while striving for elegance and simplicity is usually a good idea, and can often lead you to the right answer, it isn't always possible. Sometimes a problem really is a mess but is solvable through pure perseverance. And as a consequence of that complexity, the final formula is messy as well.

[@nomukun1138]

That's hard work. I'm tired after watching this halfway through, but I can keep going. Feel the burn!

[@stanleydodds9]

My first thought on just seeing the problem as stated is to just use the inclusion exclusion principle. Include all permutations, exclude those with at least 1 pair of consecutive numbers, include those with at least 2 such pairs, exclude those with 3, etc. Usually when I'm doing this for combinatorics problems or probability problems, it's sufficient to just find an approximation by doing a few terms of the I-E, but I'm guessing that maybe there's some neat representation once you do all of the summations of choose functions, but I don't know yet.

[@EebstertheGreat]

Shockingly, when I was a kid, I had exactly the same thoughts with tapping my fingers and developed exactly the same fidget. I would also go methodically through every single combination, before moving on to other tapping patterns, maybe tapping out rhythms, and then my mind wandering elsewhere. I don't have autism and don't fidget that much anymore, so I don't really do it as an adult, but it was something I did all the time as a kid in lower and middle school. And I never told anyone about it, because it never even occurred to me as something to mention. I also explored all possible sequences for n=5, and I paid special attention to the ones where you could get stuck. With only n=5 fingers, you don't get stuck very often. I also looked at n < 5, noticing that you can get stuck in the cases n=3 and n=4 and would always get stuck when n=2. As the number of fingers increased, it seemed like you got stuck less and less often, but I couldn't rule out that n=5 was somehow unique. When I explored n > 5 by adding one or more fingers from my left hand, I wasn't trying to count all the possible ways to do it _correctly._ I was mostly interested in how often you got stuck if you tapped at random. I had no method except picking fingers arbitrarily, like a really slow Monte Carlo simulation. At other times, particularly with n=6, I would try to include every single possible combination, though I didn't count them. It seemed like there was some obvious pattern that ought to present itself. Certainly the more fingers you add, the more often you get stuck (which is hardly surprising), but I couldn't figure out any pattern beyond that, so at some point I dropped the question. I had almost forgotten about it until I saw this video.

[@Sinzari]

I play a lot of card games so I did a similar thing trying to mix up/shuffle a small deck of cards, picking them up one at a time so that no two cards are adjacent in order.

[@aashsyed1277]

29:36 i am scrolling. 1:03:09 actually it is n! Minus that formula because that formula only counts the number of forbidden pairs,amd we want the number of non- forbidden pairs.

[@simonwillover4175]

Wow this was amazing! I have never even thought like this!