@@LucenProject Yes; different languages use different letter/group of letters to sound associations. In my language, we pronounce the letters just as their associated sound. For example, we pronounce 'a' like the 'a' in "father".
BTW that XY interpretations restrictions are easily recognized as brackets (). There are always an equal number of open and close brackets, but there can never appear more close brackets than open ones that have already appeared in the sequence
@@mo284 Glad you find it helpful! I had first encountered these from something in algebra called a "magma", where this "Dycke language" of parentheses proves useful due to the lack of associativity
Very interesting. Feels like there could be more to learn from this. Definitely makes the relationship to the binary trees obvious- that’s just the same structure of nested brackets
The method used in the Binary Trees in order to transform the problem is actually called Pre-Order Transversal of a Binary Tree. It's a way of unwrapping the binary tree, there's also In-Order and Post-Order. If you have a Binary Search Tree (that is, the binary tree is sorted in some way), then these different ways to transverse the tree give you a different meaningful result! So cool!
The binary trees shown for C_5=14 contain two duplicates (corresponding to Dyck words XXXYYXYY & XYXXYYXY) in the thumbnail (3rd row) and at 2:40 (3rd row) & 11:20 (far right). Missing are those corresponding to Dyck words XXXYXYYY & XYXYXXYY.
I have been obsessed with Catalan numbers since 2013 when a professor showed how they related to binary trees. Seeing someone share this very particular obsession so strongly warmed my heart ❤
@@JohnnieMartynov The values in Pascal's triangle are really easy to compute, so you should be able to get away with calculating the two relevant columns and subtracting them off, couldn't you?
Yeah when i was fiddling with cryptographic systems vandermonde identities appeared to me everywhere and powers of 11 are merely pascal rows with retains.
Could also care about the environment... Why is Sophie writing this on this light brown paper and not on the blackboard? The environment suffers because it already has markers that are perfect to use on the board.
@@pawezielinski2781 right, not writing on a paper will save the world. It's not flying, not driving by car, not going on a wild shopping spree for stuff that you will throw away a month later, it is paper folks. It does not matter that thousand or millions will watch this, this paper needs to be saved. For the environment.
Thank you for the great explanation. As a contribution, ratio of two consecutive Catalan Numbers C(n)/C(n+1) converges to 1/4 when n grows since it equals to (n+1)(n+2) / (2n+1)(2n+2).
I want to thank your channel! Years ago when I was in high school I started watching your videos .I was terrible at math but your videos were so accessible and interesting that it helped inspire me to study more. I am now pursuing my master's degree in mathematics and I want to thank you!
What really blows my mind in math is when seemingly random, distant concepts turn out to be connected. Like Pascal's triangle at the end, or how pi shows up at ridiculous places.
🎯 Key points for quick navigation: 00:00 *🔄 Key takeaway is the puzzle about splitting a hexagon into four triangles with diagonals, resulting in 14 ways.* 02:36 *🌲 There are 14 binary trees of order five and a pattern of 1, 1, 2, 5, 14 emerges.* 04:35 *🎯 The number of de words with four X's and four Y's is 14, following the pattern of 1, 1, 2, 5, 14.* 07:14 *📝 Formula for Catalan numbers is given as 1 / (n + 1&t=434) * 2n choose n, explained with de words and cycles.* 11:20 *🧮 Catalan numbers appear in Pascal's triangle column through subtraction, with examples leading to the sequence up to 30.* Made with HARPA AI
A couple of years ago, while I was laid up recuperating from a heart attack, I had a friend bring me a calculator so that I could play with numbers. After a good while I discovered two completely different methods for determining the numbers in the diagonals of Pascal's Triangle. I'm not a mathematician, but I enjoy playing with numbers occasionally.
There is one more, indeed the most important step that needs to be included: Encouraging and supportive science education that fosters a joyful curiosity and a kind disposition to share.
I actually "discovered" these myself a while ago. I had a project where I needed a Python program to enumerate all the binary trees of a given size (even though I didn't know that's what I was doing). I saw the sequence 1, 2, 5, 14, 42 and thought "huh, interesting", and looked it up on the OEIS. To my surprise it was one of the longest entries there!
I am convinced that the academical field of mathematicians was brought into existence by puzzle-geeks, who loved puzzling so much, they found puzzles so obscure so that no-one of the rest of us even understands the puzzle any longer and then convinced the rest of us that it is crucial for the well-being of humanity that we pay them for locking themselves into a small chamber to solve said puzzle. Chapeau, puzzle-geeks, chapeau.
You're not wrong, except it turns out they really are making modern society work. Every time we come up with a real world puzzle and hand it over they reply "aw this one's easy. Just a variant of [obscure maths puzzle]." And then they hand us the answer through some sort of magic.
I remember encountering Catalan numbers in university where they were presented as the number of ways to write balanced sets of brackets (essentially the Dyck words but with “(“ and “)” instead of “x” and “y”), but also as the number of ways to fill a 2xn grid of squares with the numbers 1 to n so that the numbers are increasing both left-to-right and top-to-bottom.
Catalan numbers crop up in some surprising places in computer science, such as range minimum queries. In a list of numbers, repeatedly find the smallest number in some range. You can do it, after linear time preprocessing, in constant time per query?! Part of the trick is to precompute cartesian trees for logarithmically-sized blocks, which is fast enough because the catalan number and the log cancel out.
10:10 -- "and this is where it becomes cool" - it was already so cool when I saw those three equivalences, but now I knew it was going to get way cooler!
Catalan numbers are basically scaled central binomial coefficients. Binomial coefficients can be computed efficiently using a simple iteration rather than the usual n choose k = n-1 choose k-1 + n-1 choose k double recursion. This is what the programming language Python does behind the scenes. Fun fact: You can easily extend the Catalan numbers to C using the Gamma function rather than factorial. Catalan(z) = 1/(z+1) Gamma(2 z + 2) / Gamma(z + 1). The +2 and +1 come from the annoying definition of Gamma(n) as (n-1)! for natural n. def choose(N, k): def _choose_iterative(N, k): numerator = N denominator = k while k > 1: N -= 1 k -= 1 numerator *= N denominator *= k return numerator // denominator # guaranteed to be a whole number # preconditions and range reduction before jumping into the iteration assert isinstance(N, int) assert isinstance(k, int) if N N: return 0 elif k + k > N: # reflection formula k = N - k return _choose_iterative(N, k)
I think Dyck words are a lot easier to understand if you use brackets; balancing brackets is much more intuitive than counting Xs and Ys with this weird abstract "Y's can't exceed X's'" rule. :)
Another way to show the number of Dyck words of length 2n is comb(2n, n) - comb(2n, n - 1) is to consider a modified Pascal's triangle. In this modified triangle, the numbers are still the sum of the two above them, but the boundary changes (see below). Any path descending to a number within Pascal's triangle can be thought of as a word (not necessarily a Dyck word) where one descends diagonally left for an X and diagonally right for a Y. The Dyck condition would hold if the path never went to the right of the centre column and also ended on the central column. This can be realised by modifying the triangle so that the left diagonal is still all 1s but the column directly to the right of the central column is all 0s (so no path can go through them). If we take the triangle and move it one number to the right (so the apex is at (0, 1) instead of (0, 0), then negate all entries, the additive property still holds. Now adding this translated and negated triangle to the original triangle will form the required modified Pascal's triangle. The result follows immediately.
Wow, your explanation of Catalan Numbers in this video is absolutely fantastic! 👏 As a competitive programmer, I stumbled upon these gems a few months ago, and they've become an indispensable tool in my problem-solving arsenal. We use Catalan Numbers for various challenges, such as 1) Finding possible Binary Search Trees. 2) Generating Parenthesis Combinations. 3) Determining Triangulations on an N-gon. 4) Calculating possible paths in a matrix. 5) Dividing a circle into n chords. 6) Handling Dyck Words. 7) Navigating through Lattice Paths. Your breakdown has not only enhanced my understanding but also reinforced the significance of Catalan Numbers. Thanks for such a clear and insightful presentation! 🚀
About one minute into the video, when I saw 1 1 2 5 14 I went immediately to the "On-Line Encyclopedia of Integer Sequences". Anyone interested in combinatorics should know about this resource. The Catalan number sequence entry begins by noting that in all the tens of thousands of integer sequences it lists, the Catalan number sequence has the most entries.
The equivalence proof starting in 5:09 between pentagrams and trees is somehow sketchy and not very precise. If i take any graph created from joining fields in a pentagon i can choose any of the three blue nodes and say "this is the root" and uncoil it in such a way that that this one will be the actual root (topmost node). You can even make different binary trees choosing the same root. That doesn't show the 1 : 1 corespondance. At 5:40 you can even see that 4 of 5 are isomorhpic (ignoring chirality) and somehow each produces different binary tree. Unless the uncoiling procedure is more strictly defined than in here, this proof is not enough to say that those sequences are equal. Beside that, absolutely great video :)
seems to me like the implicit assumption behind the uncoiling process shown is that the blue node adjacent to the unmarked side of the pentagon is always taken to be the root; not sure if this is sufficient or if you also need to add that the four pink nodes stay in order
The outer nodes must stay in the same order as they were on the polygon, and you have to order them in the same way for all polygons. Otherwise rotations could all make the same tree.
@@Farull @quatrevingtneuf Ok that makes sense but it is not really stated in the video how the unrolling procedure works and why it leads to 1 : 1 corespondance. Thanks for explanation
*A filming tip* if you don't mind: Filming from the left side of a person drawing with their right hand would be better, so that the drawing hand doesn't cover the picture 🙃
2:38 The picture is not correct as it only shows 12 different configuration ( in row 3 the two middle is the same and the two outer is the same ) The two missing configurations are pretty similar two the first two in row 1 with the exception that the shortest stem connects to the middle stem instead of the outer stem. So there are 14 configurations but not the 14 shown in this picture.
Great video, I love the enthusiasm! By the way, at 2:40, it looks like pattern numbers 10 and 11 (reading from left to right) are exactly the same as each other, as are numbers 9 and 12. I tried working these out myself, and I was wondering why I ended up with two patterns that I couldn't find in that picture. I guess 11 should have been a new unique pattern and 12 should have been its mirrored image but pattern 10 was accidentally copied into pattern 11 and then that was mirrored for pattern 12.
I think using ( and ) rather than x and y is the better representation of Dyck words. It's just more obvious to people what the restriction means. And the tree-to-word translation is that they are both different ways to count the number of ways to associate n successive applications of a binary operator. I am particularly fond personally of the recursive formula for the Catalan numbers, that each Catalan number is the convolution of all the Catalan numbers that come before it. I still remember the first time I proved it. Spelled out, the recursive formula yields C1 = C0 C2 = C0 C1 + C1 C0 C3 = C0 C2 + C1 C1 + C2 C0 C4 = C0 C3 + C1 C2 + C2 C1 + C3 C0 . . .
"Dyck is pronounced with a long *i* sound in the middle" This somehow reminds me of the "it's a bent finger" incident in the Egyptian fraction video lol
@nabilzogby4537 Your explanation is unlikely to be true. There are more vowels in heaven and earth than are dreamt of in your letters. The use of the letter y to represent a certain sound differs widely from Flanders and the lower Rhein area to Berlin and Munich, the place of Dycks family. Also the use of "CK" mostly indicates a short vowel. Unless you talk with a descendant of Walther von Dyck you will not know for sure, how it should be pronounced.
@DarklordZagarna That is your thesis. But where is the proof. There are Ypern and Schloss Dyck as well, but that proofs nothing even though there was some fighting too. This problem is the same as the set Windsor, tiny and city. There is no strict rule that says what an I sounds like. Windsor is a name and you say it like the owner of the name wishes to. Fortunately it doesn't matter until you meet a family member.
I came across Catalan numbers quite by accident when i was trying to calculate/simulate the distribution of "betting game lengths". Start with X>=1 and each game you bet 1. Each game has probably p of winning, with some payoff. I was interested in simulating how long could you bet on this game before you went bankrupt. Before too long i was deep into Wikipedia reading about Dyck words and binary tree traversal. Fun stuff for sure.
I love the Catalan. I couldn't keep it under a quarter hour. We need more videos about all the cool things that go into Catalan numbers and how they are related. There is all sorts of things. Literally hundreds.
It's funny. During my PhD, I tried to count all the possible ways to find all the parametrizations of Feynman diagrams. If you know how to do that, then the relation to binary trees is straight forward, so I wanted to figure out all the binary trees with n leaves and get different ways to look at that. It was crucial to find the best possible parametrization and I was hoping that a different way to look at them would give some insight why some works and others don't. In the end it was a mostly futile attempt and I was stuck with trial and error, but I did actually find all the different representations that are given in this video (and one more, basically the number of ways to stretch a simplex into an n dimensional cube) and the formula, but I did not know they were called Catalan numbers :D It would have been very nice to know the name. Also, I definitely want a Pascals triangle talk.
Heres some more connections with Probability theory, specifically random matrices and free probability Consider a probability distribution with density 1/2π √(4-x^2). The moments of the distribution are 0,1,0,1,0,2,0,5,0,14,... Which means all the even moments are the catalan numbers. Compare to how the normal distribution has even moments as a double factorial (n-1)!!. Note that (n-1)!! Is the number of ways you can partition n points into n/2 pairs. Similarly, the catalan numbers are the number of ways you can partition n into non-crossing partitions. Consider a large random matrix (specifically a Gaussian ensemble). Its eigenvalues form a nice distribution. This distribution happens to be the semicircle distribution, which means the moments of the eigenvalues are the catalan nunbers. Those of you who have seen the central limit theorem will know that the sample average of iid scalar random variables converges in distribution to a normal. One way to prove this is to show the moments converge. It turns out if we consider independent random matrices (more specifically, freely independent random matrices) which are all distributed the same, it turns out sample average converges in distribution... ... To a semicircle. The moments converge to the catalan numbers. The proof is via using non-crossing partitions. The analogue of the central limit for random matrices is the semicircle distribution. You can read more about this in "Topics in random matrix theory" Tao and "Free probability and random matrices" Speicher, Mingo
The ratio between successive numbers seemed to be about 3, maybe growing towards 4. By playing around in Python, I found the exact ratio between them is (4n+2)/(n+2) which does indeed asymptotically approach 4, but can't see why that should be.
Might help to write the combinatorics as factorials. nCr = n!/(r!(n-r)!), here we have 1/(n+1) * 2n choose n = 1/(n+1) * (2n)! / (n!n!) = (2n)! / (n!(n+1)!) Substituting in n+1, it'll be (2n+2)! / ((n+1)!(n+2)!) So if you divide those out you get the ratio between consecutive terms, (2n+2)(2n+1) / ((n+1)(n+2)) And from there, (2n+2)/(n+1) = 2, so it's (4n+2)/(n+2)
Are you smiling at your screen now, like a kid? Don't worry, you are not alone 😀 I'll bookmark this to send to people when asked how can math be fun and exciting. Thank you for making it.
Me, drunk on UA-cam at 2 am. Sees thumbnail of hexagons and numbers. "Oooh. A video on Catan numbers?" Me, as the hexagon question is proposed. "What does Settlers of Catan have to do with the Catalan numbers." Me, probably 75% of the way through the video. "I can't read."
Something similar came up in a calculator for solving the Countdown numbers game, just a sort of odd version. If you want to come up with every possible equation, you always need one more number than operator. If done in RPN, it looks the same: NNO
In Dyck words, replace Xs with opening parenthesis and Ys with closing parenthesis. You'd get all valid pairings of N pairs of parentheses which are correctly matched. Conversion to Reverse Polish Notation is natural, of course.
The brilliant circle seemed so easy that I hesitated for a moment, because surely it couldn't be. It is pretty common knowledge that increasing the radius drastically affects the area, which of course is evident, since the radius gets squared. Even without calculating the first orange ring is a good deal greater than the first blue ring, likewise for the second orange and second blue ring. If it continues indefinitely the innermost areas are close to zero and can in no way make up for the difference in the beginning. So unless something weird is going on because of infinity, the orange area should be the greatest.
Brilliant Explanation! But why are at 2:40 when buliding the 14 binary trees row 3 ... why is tree 1 not equal to tree 4 and tree 2 not equal to tree 3 ... maybe it's just me and I'm missing something. Thanks for an answer !! :-)
I noticed a similar pattern when considering plastic bags that can be placed in any configuration; i.e. bags side by side or one inside another. To get the Catalan numbers, each bag would need to be uniquely identifiable. At least, I think this gives the Catalan numbers but I'm not totally sure.
See brilliant.org/numberphile for Brilliant and 20% off their premium service & 30-day trial (episode sponsor)
haven't you uploaded this video before?
2:57 The "Long I sound" sounds like a long E sound to me. Is it a difference in the sound-letter associations since I'm American?
I'm sorry, but the binary tree of order 5 is wrong. In the third row, the 2 outer are the same, and the 2 inner are the same.
@@LucenProject Yes; different languages use different letter/group of letters to sound associations. In my language, we pronounce the letters just as their associated sound. For example, we pronounce 'a' like the 'a' in "father".
What???
Try typing it into calculator:
( 100000 - sqrt(9999600000) )/2 and you will get catalan numbers
Sophie's enthusiasm about the Catalan's number and after that about Pascal's triangle makes the whole episode so fun! :)
Cheers. She does seem to like them. :)
Just a tiny bit.
have you seen the paper from Wildburger?@@numberphile
Listening to people discuss what they are truly passionate about is maybe the best thing in the world
Yeah, I always love when people here absolutely geek out on something they find cool.
I never thought I would say this, but here it goes: "I want a Pascal's triangle talk".
technically you haven't said it yet, if that makes you feel any better
I seconded.
I want a 1+ hour talk about Catalan numbers.
Me too !!
I'd love to hear more about Pascal's triangle! Every exploration of it feels so superficial.
BTW that XY interpretations restrictions are easily recognized as brackets (). There are always an equal number of open and close brackets, but there can never appear more close brackets than open ones that have already appeared in the sequence
That's... Actually really helpful. Thank you kind stranger :-)
@@mo284 Glad you find it helpful! I had first encountered these from something in algebra called a "magma", where this "Dycke language" of parentheses proves useful due to the lack of associativity
Oh that's why it felt familiar, thanks for mentioning!
pov: your code have 12 nested parenthesis and curly brackets
Very interesting. Feels like there could be more to learn from this. Definitely makes the relationship to the binary trees obvious- that’s just the same structure of nested brackets
Sophie's contributions to this channel are starting to become addictive, partly for the content but mostly for her enthusiasm.
"enthusiasm"
@@sdffhsdghhn "enthusiasum"
Lol when she said, " I gotta get this right" 🤣 Deeeck words.
I got that right-- now
Can't pronounce /dɛik/
Try to avoid /dɪk/
land into /dɪːk/
Yeah two pitfalls for one word.
Now for the aussie accent....
@@deltalima6703We can say that easily. It uses the FLEECE vowel.
The method used in the Binary Trees in order to transform the problem is actually called Pre-Order Transversal of a Binary Tree. It's a way of unwrapping the binary tree, there's also In-Order and Post-Order. If you have a Binary Search Tree (that is, the binary tree is sorted in some way), then these different ways to transverse the tree give you a different meaningful result! So cool!
The binary trees shown for C_5=14 contain two duplicates (corresponding to Dyck words XXXYYXYY & XYXXYYXY) in the thumbnail (3rd row) and at 2:40 (3rd row) & 11:20 (far right). Missing are those corresponding to Dyck words XXXYXYYY & XYXYXXYY.
I have been obsessed with Catalan numbers since 2013 when a professor showed how they related to binary trees. Seeing someone share this very particular obsession so strongly warmed my heart ❤
How to compute Catalan numbers by a program? These formulas on wiki are not too friendly. 😊
@@JohnnieMartynov The values in Pascal's triangle are really easy to compute, so you should be able to get away with calculating the two relevant columns and subtracting them off, couldn't you?
@@therealax6 OK, I will try it. 🙂
So did you know that the sum of all Catalan numbers is a primitive sixth root of unity, similar to how the sum of all natural numbers is -1/12?
Pascal's triangle is the ninja behind the curtain of mathematics. It's everywhere, always jumping in the surprise me.
Pascals triangle and PI always show up in the most interesting places
@@queueeeee9000 The Fine Structure Constant too!
Yeah when i was fiddling with cryptographic systems vandermonde identities appeared to me everywhere and powers of 11 are merely pascal rows with retains.
@@ArawnOfAnnwn Where outside of QED?
Would have been funny to end it with cameraman slowly walking out the door and we could still faintly hear Sophie talking with enthusiasm
Ha ha
As if we would ever leave in the middle of a Sophie Explanation :P
I love Sophie’s passion, and I love that she is willing to share it!
Could also care about the environment... Why is Sophie writing this on this light brown paper and not on the blackboard? The environment suffers because it already has markers that are perfect to use on the board.
@@pawezielinski2781 bruh
@@pawezielinski2781 That's the Numberphile way!
@@pawezielinski2781 right, not writing on a paper will save the world. It's not flying, not driving by car, not going on a wild shopping spree for stuff that you will throw away a month later, it is paper folks. It does not matter that thousand or millions will watch this, this paper needs to be saved. For the environment.
@@pawezielinski2781 You do know how chalk is produced, don't you?
There is a book called "Catalan Numbers" by Richard P. Stanley that lists 200+ different sets that give the Catalan numbers, mind-blowing...
Thank you for the great explanation. As a contribution, ratio of two consecutive Catalan Numbers C(n)/C(n+1) converges to 1/4 when n grows since it equals to (n+1)(n+2) / (2n+1)(2n+2).
I want to thank your channel! Years ago when I was in high school I started watching your videos .I was terrible at math but your videos were so accessible and interesting that it helped inspire me to study more. I am now pursuing my master's degree in mathematics and I want to thank you!
What really blows my mind in math is when seemingly random, distant concepts turn out to be connected. Like Pascal's triangle at the end, or how pi shows up at ridiculous places.
if something involves a period or a rotation it makes sense for pi to show up
@@mortgageapprovals8933 And what about the probability density function of the Normal Distribution? (3b1b has a video about this)
🎯 Key points for quick navigation:
00:00 *🔄 Key takeaway is the puzzle about splitting a hexagon into four triangles with diagonals, resulting in 14 ways.*
02:36 *🌲 There are 14 binary trees of order five and a pattern of 1, 1, 2, 5, 14 emerges.*
04:35 *🎯 The number of de words with four X's and four Y's is 14, following the pattern of 1, 1, 2, 5, 14.*
07:14 *📝 Formula for Catalan numbers is given as 1 / (n + 1&t=434) * 2n choose n, explained with de words and cycles.*
11:20 *🧮 Catalan numbers appear in Pascal's triangle column through subtraction, with examples leading to the sequence up to 30.*
Made with HARPA AI
Combinatorics for the win! Great video, brilliant presentation and enthusiasm from Sophie. 😀
Any video starring Sophie is an instant gem. She's such a wonderful explainer.
A couple of years ago, while I was laid up recuperating from a heart attack, I had a friend bring me a calculator so that I could play with numbers. After a good while I discovered two completely different methods for determining the numbers in the diagonals of Pascal's Triangle. I'm not a mathematician, but I enjoy playing with numbers occasionally.
Nice!
man, i love sophie, its so rare to see people like her that are close to my age and so passionate about maths :)
The greatest talk on Catalan numbers I never though I would watch. The enthusiasm makes the show.
Every time I hear something shows up in pascal's triangle my immediate response is just "motherfu-". It feels like absolute magic
Her enthusiasm about the Pascal's Triangle's relation made this episode SO MUCH better!
I'll happily listen to her talk for an hour about something she's passionate about like this.
There is one more, indeed the most important step that needs to be included: Encouraging and supportive science education that fosters a joyful curiosity and a kind disposition to share.
Such a nice thing to see a bright young woman like her. so excited about mathematics. Thank you so much!!!
I actually "discovered" these myself a while ago. I had a project where I needed a Python program to enumerate all the binary trees of a given size (even though I didn't know that's what I was doing). I saw the sequence 1, 2, 5, 14, 42 and thought "huh, interesting", and looked it up on the OEIS. To my surprise it was one of the longest entries there!
I am convinced that the academical field of mathematicians was brought into existence by puzzle-geeks, who loved puzzling so much, they found puzzles so obscure so that no-one of the rest of us even understands the puzzle any longer and then convinced the rest of us that it is crucial for the well-being of humanity that we pay them for locking themselves into a small chamber to solve said puzzle. Chapeau, puzzle-geeks, chapeau.
You're not wrong, except it turns out they really are making modern society work. Every time we come up with a real world puzzle and hand it over they reply "aw this one's easy. Just a variant of [obscure maths puzzle]." And then they hand us the answer through some sort of magic.
I just love this level of enthusiasm when geeking out over math explanations and seemingly weird interconnections!
I remember encountering Catalan numbers in university where they were presented as the number of ways to write balanced sets of brackets (essentially the Dyck words but with “(“ and “)” instead of “x” and “y”), but also as the number of ways to fill a 2xn grid of squares with the numbers 1 to n so that the numbers are increasing both left-to-right and top-to-bottom.
Catalan numbers crop up in some surprising places in computer science, such as range minimum queries. In a list of numbers, repeatedly find the smallest number in some range.
You can do it, after linear time preprocessing, in constant time per query?! Part of the trick is to precompute cartesian trees for logarithmically-sized blocks, which is fast enough because the catalan number and the log cancel out.
This explanation really helps bridge the gap between the formula and the conceptual idea!!! Thanks.
Found the video trying to learn about the catalan chess opening but stayed all the way thru. Well done! This was very interesting and fun👏
10:10 -- "and this is where it becomes cool" - it was already so cool when I saw those three equivalences, but now I knew it was going to get way cooler!
Catalan numbers are basically scaled central binomial coefficients. Binomial coefficients can be computed efficiently using a simple iteration rather than the usual n choose k = n-1 choose k-1 + n-1 choose k double recursion. This is what the programming language Python does behind the scenes.
Fun fact: You can easily extend the Catalan numbers to C using the Gamma function rather than factorial. Catalan(z) = 1/(z+1) Gamma(2 z + 2) / Gamma(z + 1). The +2 and +1 come from the annoying definition of Gamma(n) as (n-1)! for natural n.
def choose(N, k):
def _choose_iterative(N, k):
numerator = N
denominator = k
while k > 1:
N -= 1
k -= 1
numerator *= N
denominator *= k
return numerator // denominator # guaranteed to be a whole number
# preconditions and range reduction before jumping into the iteration
assert isinstance(N, int)
assert isinstance(k, int)
if N N:
return 0
elif k + k > N: # reflection formula
k = N - k
return _choose_iterative(N, k)
Make more videos Sophie Maclean. Love your topics and energy!
I think Dyck words are a lot easier to understand if you use brackets; balancing brackets is much more intuitive than counting Xs and Ys with this weird abstract "Y's can't exceed X's'" rule. :)
ERROR: The third row graphic of 5th order binary trees at 13:15 has a repeat of only 2 symmetries.
Another way to show the number of Dyck words of length 2n is comb(2n, n) - comb(2n, n - 1) is to consider a modified Pascal's triangle.
In this modified triangle, the numbers are still the sum of the two above them, but the boundary changes (see below).
Any path descending to a number within Pascal's triangle can be thought of as a word (not necessarily a Dyck word) where one descends diagonally left for an X and diagonally right for a Y. The Dyck condition would hold if the path never went to the right of the centre column and also ended on the central column.
This can be realised by modifying the triangle so that the left diagonal is still all 1s but the column directly to the right of the central column is all 0s (so no path can go through them).
If we take the triangle and move it one number to the right (so the apex is at (0, 1) instead of (0, 0), then negate all entries, the additive property still holds. Now adding this translated and negated triangle to the original triangle will form the required modified Pascal's triangle.
The result follows immediately.
Wow, your explanation of Catalan Numbers in this video is absolutely fantastic! 👏 As a competitive programmer, I stumbled upon these gems a few months ago, and they've become an indispensable tool in my problem-solving arsenal. We use Catalan Numbers for various
challenges, such as
1) Finding possible Binary Search Trees.
2) Generating Parenthesis Combinations.
3) Determining Triangulations on an N-gon.
4) Calculating possible paths in a matrix.
5) Dividing a circle into n chords.
6) Handling Dyck Words.
7) Navigating through Lattice Paths.
Your breakdown has not only enhanced my understanding but also reinforced the significance of Catalan Numbers. Thanks for such a clear and insightful presentation! 🚀
Sophie going all goofy at the end is the best thing I’ll see all day.
Sophie`s level of enthusiam at the conclusion on Pascal Triangle is like Liverpool just scored a goal
Catalan Numbers
me, a language nerd: "is it about numerals in the Catalan language?" 😂
Yeah my initial reaction to the video thumbnail was "I didn't know they used a different numbering system in Catalonia".
I could sit here and listen for an hour to Sophie talking about Catalan numbers
6:08 to 6:36 for anyone who didnt understand it, this alternate name may help.
its Depth First Traversal/search (aka DFS)
Wow I was blown away by her enthusiasm, contagious!
About one minute into the video, when I saw 1 1 2 5 14 I went immediately to the "On-Line Encyclopedia of Integer Sequences". Anyone interested in combinatorics should know about this resource. The Catalan number sequence entry begins by noting that in all the tens of thousands of integer sequences it lists, the Catalan number sequence has the most entries.
Love it! Old school Numberphile!
The equivalence proof starting in 5:09 between pentagrams and trees is somehow sketchy and not very precise. If i take any graph created from joining fields in a pentagon i can choose any of the three blue nodes and say "this is the root" and uncoil it in such a way that that this one will be the actual root (topmost node). You can even make different binary trees choosing the same root. That doesn't show the 1 : 1 corespondance. At 5:40 you can even see that 4 of 5 are isomorhpic (ignoring chirality) and somehow each produces different binary tree. Unless the uncoiling procedure is more strictly defined than in here, this proof is not enough to say that those sequences are equal.
Beside that, absolutely great video :)
seems to me like the implicit assumption behind the uncoiling process shown is that the blue node adjacent to the unmarked side of the pentagon is always taken to be the root; not sure if this is sufficient or if you also need to add that the four pink nodes stay in order
The outer nodes must stay in the same order as they were on the polygon, and you have to order them in the same way for all polygons. Otherwise rotations could all make the same tree.
@@Farull @quatrevingtneuf Ok that makes sense but it is not really stated in the video how the unrolling procedure works and why it leads to 1 : 1 corespondance. Thanks for explanation
Her abstract relations aptitude is off the charts.
*A filming tip* if you don't mind:
Filming from the left side of a person drawing with their right hand would be better, so that the drawing hand doesn't cover the picture 🙃
2:38 The picture is not correct as it only shows 12 different configuration ( in row 3 the two middle is the same and the two outer is the same )
The two missing configurations are pretty similar two the first two in row 1 with the exception that the shortest stem connects to the middle stem instead of the outer stem.
So there are 14 configurations but not the 14 shown in this picture.
For your binary trees of order 5: 9&12 are equivalent, and 10&11 are equivalent
These constructive set equivalence proofs are what I loved about theoretical computer science class.
Great video, I love the enthusiasm!
By the way, at 2:40, it looks like pattern numbers 10 and 11 (reading from left to right) are exactly the same as each other, as are numbers 9 and 12.
I tried working these out myself, and I was wondering why I ended up with two patterns that I couldn't find in that picture.
I guess 11 should have been a new unique pattern and 12 should have been its mirrored image but pattern 10 was accidentally copied into pattern 11 and then that was mirrored for pattern 12.
"This is where it becomes cool" --- indeed. The excitement showed is encaptivating. I was all in. - Cheers.
Sophie Maclean may be my new favorite presenter. Very cool.
Would love to see more from her. Great pace and amazing at taking our hands through the conclusion 🎉 Bravo 👏
Please more things like this! this video was one of the most interesting Numberphile videos!
I'm gonna be drawing lines through pentagons today, thank you Sophie!
I adore Sophie’s energy !! 💜💜💜💜
I think using ( and ) rather than x and y is the better representation of Dyck words. It's just more obvious to people what the restriction means. And the tree-to-word translation is that they are both different ways to count the number of ways to associate n successive applications of a binary operator.
I am particularly fond personally of the recursive formula for the Catalan numbers, that each Catalan number is the convolution of all the Catalan numbers that come before it. I still remember the first time I proved it.
Spelled out, the recursive formula yields
C1 = C0
C2 = C0 C1 + C1 C0
C3 = C0 C2 + C1 C1 + C2 C0
C4 = C0 C3 + C1 C2 + C2 C1 + C3 C0
.
.
.
I want to say 1000 thanks - best explanation of the Catatln number!
Coincidentally, connecting the points at 5:37 creates Voronoi diagrams, which means the sliced hexagons are Delaunay triangulations.
"Dyck is pronounced with a long *i* sound in the middle"
This somehow reminds me of the "it's a bent finger" incident in the Egyptian fraction video lol
@nabilzogby4537 Your explanation is unlikely to be true. There are more vowels in heaven and earth than are dreamt of in your letters. The use of the letter y to represent a certain sound differs widely from Flanders and the lower Rhein area to Berlin and Munich, the place of Dycks family. Also the use of "CK" mostly indicates a short vowel. Unless you talk with a descendant of Walther von Dyck you will not know for sure, how it should be pronounced.
@@rennleitung_7It's the same vowel as the one in the name of the Dyle River, which was briefly of some importance in the early part of World War II.
@DarklordZagarna That is your thesis. But where is the proof. There are Ypern and Schloss Dyck as well, but that proofs nothing even though there was some fighting too. This problem is the same as the set Windsor, tiny and city. There is no strict rule that says what an I sounds like. Windsor is a name and you say it like the owner of the name wishes to. Fortunately it doesn't matter until you meet a family member.
I came across Catalan numbers quite by accident when i was trying to calculate/simulate the distribution of "betting game lengths". Start with X>=1 and each game you bet 1. Each game has probably p of winning, with some payoff. I was interested in simulating how long could you bet on this game before you went bankrupt. Before too long i was deep into Wikipedia reading about Dyck words and binary tree traversal. Fun stuff for sure.
I love the Catalan. I couldn't keep it under a quarter hour. We need more videos about all the cool things that go into Catalan numbers and how they are related. There is all sorts of things. Literally hundreds.
Watching videos like this for fun is why my friends call me a nerd 😅
It's funny. During my PhD, I tried to count all the possible ways to find all the parametrizations of Feynman diagrams. If you know how to do that, then the relation to binary trees is straight forward, so I wanted to figure out all the binary trees with n leaves and get different ways to look at that. It was crucial to find the best possible parametrization and I was hoping that a different way to look at them would give some insight why some works and others don't. In the end it was a mostly futile attempt and I was stuck with trial and error, but I did actually find all the different representations that are given in this video (and one more, basically the number of ways to stretch a simplex into an n dimensional cube) and the formula, but I did not know they were called Catalan numbers :D It would have been very nice to know the name.
Also, I definitely want a Pascals triangle talk.
I used to catalan numbers to iterate through all possible algorithms. Nice to see you guys making a video on them!
Sophie is an awesome, awesome nerd. More of her, please.
Friend: "oh, look at this view!! Isn't it gorgeous?"
Sophie: "yeah, that's nice. Have I told you about Pascal's Triangle?"
Heres some more connections with Probability theory, specifically random matrices and free probability
Consider a probability distribution with density 1/2π √(4-x^2).
The moments of the distribution are 0,1,0,1,0,2,0,5,0,14,...
Which means all the even moments are the catalan numbers.
Compare to how the normal distribution has even moments as a double factorial (n-1)!!.
Note that (n-1)!! Is the number of ways you can partition n points into n/2 pairs. Similarly, the catalan numbers are the number of ways you can partition n into non-crossing partitions.
Consider a large random matrix (specifically a Gaussian ensemble). Its eigenvalues form a nice distribution. This distribution happens to be the semicircle distribution, which means the moments of the eigenvalues are the catalan nunbers.
Those of you who have seen the central limit theorem will know that the sample average of iid scalar random variables converges in distribution to a normal. One way to prove this is to show the moments converge. It turns out if we consider independent random matrices (more specifically, freely independent random matrices) which are all distributed the same, it turns out sample average converges in distribution...
... To a semicircle. The moments converge to the catalan numbers. The proof is via using non-crossing partitions.
The analogue of the central limit for random matrices is the semicircle distribution. You can read more about this in "Topics in random matrix theory" Tao and "Free probability and random matrices" Speicher, Mingo
This is such a great way to visualize these fantastic numbers!
I love how she explains it
The ratio between successive numbers seemed to be about 3, maybe growing towards 4. By playing around in Python, I found the exact ratio between them is (4n+2)/(n+2) which does indeed asymptotically approach 4, but can't see why that should be.
Might help to write the combinatorics as factorials. nCr = n!/(r!(n-r)!), here we have
1/(n+1) * 2n choose n
= 1/(n+1) * (2n)! / (n!n!)
= (2n)! / (n!(n+1)!)
Substituting in n+1, it'll be
(2n+2)! / ((n+1)!(n+2)!)
So if you divide those out you get the ratio between consecutive terms, (2n+2)(2n+1) / ((n+1)(n+2))
And from there, (2n+2)/(n+1) = 2, so it's (4n+2)/(n+2)
@@Stereomoo thanks buddy, a win for diving straight into the algebra, and a loss for my approach of trying to just magically visualise why it was true
9:30 There was an error here, there were 2n+1 possible rearrangements, so it should be divided by 2n+1, not n+1.
Now I want to see an episode with Sophie and Cliff Stoll together. I think the galaxy would explode
Are you smiling at your screen now, like a kid? Don't worry, you are not alone 😀
I'll bookmark this to send to people when asked how can math be fun and exciting. Thank you for making it.
Best video in a while. Love the enthusiasm!!
Me, drunk on UA-cam at 2 am. Sees thumbnail of hexagons and numbers. "Oooh. A video on Catan numbers?"
Me, as the hexagon question is proposed. "What does Settlers of Catan have to do with the Catalan numbers."
Me, probably 75% of the way through the video. "I can't read."
Something similar came up in a calculator for solving the Countdown numbers game, just a sort of odd version.
If you want to come up with every possible equation, you always need one more number than operator. If done in RPN, it looks the same:
NNO
In Dyck words, replace Xs with opening parenthesis and Ys with closing parenthesis. You'd get all valid pairings of N pairs of parentheses which are correctly matched.
Conversion to Reverse Polish Notation is natural, of course.
I wish everybody that one special person who looks at them like Sophie looks at catalan numbers and pascal triangle
At 2:40 the 3rd row is incorrect - two are duplicated (and two others are missing).
Lovely video! Another topic to scratch off my video list 😅
Ayyy cool seeing you here :D
yo, whatcha doin here
I liked the math, but I really particularly liked the enthusiasm in the presentation.
Geometric maths is always fascinating! Thinking outside the polygon!
Symmetry seems important here for computer science. Thank you Sophie, you are great!
0:40 - There are 20, actually. You can draw the N in reverse, so you have an additional 6 ways using "|/|" shaped lines.
There's an error in the image thumbnail and at 2.40 . There are 2x two of the same binary tree on the second row
The brilliant circle seemed so easy that I hesitated for a moment, because surely it couldn't be.
It is pretty common knowledge that increasing the radius drastically affects the area, which of course is evident, since the radius gets squared.
Even without calculating the first orange ring is a good deal greater than the first blue ring, likewise for the second orange and second blue ring.
If it continues indefinitely the innermost areas are close to zero and can in no way make up for the difference in the beginning. So unless something weird is going on because of infinity, the orange area should be the greatest.
Brilliant Explanation! But why are at 2:40 when buliding the 14 binary trees row 3 ... why is tree 1 not equal to tree 4 and tree 2 not equal to tree 3 ... maybe it's just me and I'm missing something. Thanks for an answer !! :-)
At 8:30 this is quite similar to LFSRs (linear-feedback shift registers) in old videogames for pseudo-random number generation
I noticed a similar pattern when considering plastic bags that can be placed in any configuration; i.e. bags side by side or one inside another. To get the Catalan numbers, each bag would need to be uniquely identifiable. At least, I think this gives the Catalan numbers but I'm not totally sure.
Phenomenal video as always!
Dyck words seem to have the same rules as validating strings of parentheses (or brackets if you're a royal subject), with X being ( and Y being )
I was just searching this up yesterday and it appeared in my recommended.
I love the explanation and the energy! I also want a pascal triangle talk. Next numberphile video?
I'm a lil shocked you didn't show how Dyck numbers and binary trees relate to parenthesis in basic math equations.