Catalan Numbers - Numberphile

Featuring Sophie Maclean. See brilliant.org/numberphile for Brilliant and 20% off their premium service & 30-day trial (episode sponsor). More links & stuff in full description below ↓↓↓
Sophie Maclean is based at Kings College, London: sophiethemathmo.wordpress.com
More Sophie on Numberphile: bit.ly/Sophie_Numberphile
Pascal's Triangle: • Pascal's Triangle - Nu...
Patreon: / numberphile
Numberphile is supported by Jane Street. Learn more about them (and exciting career opportunities) at: bit.ly/numberphile-janestreet
We're also supported by the Simons Laufer Mathematical Sciences Institute (formerly MSRI): bit.ly/MSRINumberphile
Our thanks also to the Simons Foundation: www.simonsfoundation.org
NUMBERPHILE
Website: www.numberphile.com/
Numberphile on Facebook: / numberphile
Numberphile tweets: / numberphile
Subscribe: bit.ly/Numberphile_Sub
Video by James Hennessy, Pete McPartlan, and Brady Haran
Numberphile T-Shirts and Merch: teespring.com/stores/numberphile
Brady's videos subreddit: / bradyharan
Brady's latest videos across all channels: www.bradyharanblog.com/
Sign up for (occasional) emails: eepurl.com/YdjL9

[@numberphile]

See brilliant.org/numberphile for Brilliant and 20% off their premium service & 30-day trial (episode sponsor)

[@NekoAlosama]

haven't you uploaded this video before?

[@LucenProject]

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?

[@huecan5748]

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.

[@MichaelSandbox]

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

[@stanimir5F]

Sophie's enthusiasm about the Catalan's number and after that about Pascal's triangle makes the whole episode so fun! :)

[@numberphile]

Cheers. She does seem to like them. :)

[@HappyMathDad]

Just a tiny bit.

[@alleycatsphinx]

have you seen the paper from Wildburger?@@numberphile

[@chammy2812]

Listening to people discuss what they are truly passionate about is maybe the best thing in the world

[@monkeybusiness673]

Yeah, I always love when people here absolutely geek out on something they find cool.

[@AdelaeR]

I never thought I would say this, but here it goes: "I want a Pascal's triangle talk".

[@JeremyForTheWin]

technically you haven't said it yet, if that makes you feel any better

[@arikwolf3777]

I seconded.

[@zhezburger]

I want a 1+ hour talk about Catalan numbers.

[@thomasanderson9383]

Me too !!

[@liz4v]

I'd love to hear more about Pascal's triangle! Every exploration of it feels so superficial.

[@meiliyinhua7486]

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]

That's... Actually really helpful. Thank you kind stranger :-)

[@meiliyinhua7486]

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

[@taljones4844]

Oh that's why it felt familiar, thanks for mentioning!

[@sethhu20]

pov: your code have 12 nested parenthesis and curly brackets

[@noa_1104]

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

[@N.I.R.A.T.I.A.S.]

Sophie's contributions to this channel are starting to become addictive, partly for the content but mostly for her enthusiasm.

[@wildndetroit]

Lol when she said, " I gotta get this right" 🤣 Deeeck words.

[@marksusskind1260]

I got that right-- now

[@MeltedMask]

Can't pronounce /dɛik/ Try to avoid /dɪk/ land into /dɪːk/

[@Jacquobite]

Yeah two pitfalls for one word.

[@deltalima6703]

Now for the aussie accent....

[@Ggdivhjkjl]

​@@deltalima6703We can say that easily. It uses the FLEECE vowel.

[@TheFireHawkDelta]

Pascal's triangle is the ninja behind the curtain of mathematics. It's everywhere, always jumping in the surprise me.

[@queueeeee9000]

Pascals triangle and PI always show up in the most interesting places

[@ArawnOfAnnwn]

@@queueeeee9000 The Fine Structure Constant too!

[@temporarytemporary-fh2df]

Yeah when i was fiddling with cryptographic systems vandermonde identities appeared to me everywhere and powers of 11 are merely pascal rows with retains.

[@stpacctsgn]

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.

[@eminence_]

Would have been funny to end it with cameraman slowly walking out the door and we could still faintly hear Sophie talking with enthusiasm

[@numberphile]

Ha ha

[@AroundTheBlockAgain]

As if we would ever leave in the middle of a Sophie Explanation :P

[@ErhanTezcan]

There is a book called "Catalan Numbers" by Richard P. Stanley that lists 200+ different sets that give the Catalan numbers, mind-blowing...

[@gervasiosantos3563]

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]

How to compute Catalan numbers by a program? These formulas on wiki are not too friendly. 😊

[@therealax6]

@@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?

[@JohnnieMartynov]

@@therealax6 OK, I will try it. 🙂

[@axillv1736]

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!

[@ahabkapitany]

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.

[@mortgageapprovals8933]

if something involves a period or a rotation it makes sense for pi to show up

[@futurepath]

The paper change interlude was much longer than the actual paper change this time! Lol 😂

[@Art1factlol]

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👏

[@coulie27]

Combinatorics for the win! Great video, brilliant presentation and enthusiasm from Sophie. 😀

[@devnol]

Every time I hear something shows up in pascal's triangle my immediate response is just "motherfu-". It feels like absolute magic

[@thargy]

I love Sophie’s passion, and I love that she is willing to share it!

[@pawezielinski2781]

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.

[@Fucisko]

@@pawezielinski2781 bruh

[@scottdebrestian9875]

@@pawezielinski2781 That's the Numberphile way!

[@teliph3U]

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

[@lonestarr1490]

​@@pawezielinski2781 You do know how chalk is produced, don't you?

[@nafizbasaran3639]

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

[@landonthompson-tschimperle3964]

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!

[@ilghiz]

*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 🙃

[@gerryn2]

The greatest talk on Catalan numbers I never though I would watch. The enthusiasm makes the show.

[@Kebabrulle4869]

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!

[@M4DA.]

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 :)

[@quatrevingtneuf]

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

[@Farull]

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.

[@M4DA.]

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

[@hantuchblau]

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.

[@soranuareane]

Any video starring Sophie is an instant gem. She's such a wonderful explainer.

[@markjreed]

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

[@d_roy_]

Her enthusiasm about the Pascal's Triangle's relation made this episode SO MUCH better!

[@SumNutOnU2b]

Her energy is just so contagious! I can't get enough.

[@HappyMathDad]

Such a nice thing to see a bright young woman like her. so excited about mathematics. Thank you so much!!!

[@NickEllis-nr6ot]

Make more videos Sophie Maclean. Love your topics and energy!

[@ConManAU]

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.

[@St_M_]

I just love this level of enthusiasm when geeking out over math explanations and seemingly weird interconnections!

[@TemplerOO7]

Wow I was blown away by her enthusiasm, contagious!

[@walterfristoe4643]

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.

[@bananatassium7009]

man, i love sophie, its so rare to see people like her that are close to my age and so passionate about maths :)

[@PBGidi]

I adore Sophie’s energy !! 💜💜💜💜

[@don5oan]

Would love to see more from her. Great pace and amazing at taking our hands through the conclusion 🎉 Bravo 👏

[@TimJSwan]

I used to catalan numbers to iterate through all possible algorithms. Nice to see you guys making a video on them!

[@boredgrass]

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.

[@TECHNIXCAFE]

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! 🚀

[@emanuellandeholm5657]

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)

[@mytube001]

Love it! Old school Numberphile!

[@Bregylais]

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.

[@tristanridley1601]

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.

[@alonvinkler]

Please more things like this! this video was one of the most interesting Numberphile videos!

[@stephenweigel]

This is such a great way to visualize these fantastic numbers!

[@Kaepsele337]

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.

[@lillyfiorino8636]

ERROR: The third row graphic of 5th order binary trees at 13:15 has a repeat of only 2 symmetries.

[@LittlePunnkk]

"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

[@rennleitung_7]

@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]

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

[@rennleitung_7]

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

[@chrisd561]

Best video in a while. Love the enthusiasm!!

[@zdlax]

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.

[@charlesmrader]

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.

[@nienke7713]

I'll happily listen to her talk for an hour about something she's passionate about like this.

[@mikeymad]

"This is where it becomes cool" --- indeed. The excitement showed is encaptivating. I was all in. - Cheers.

[@3Max]

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!

[@mplsmike4023]

Sophie going all goofy at the end is the best thing I’ll see all day.

[@MathematicsOne]

Phenomenal video as always!

[@unvergebeneid]

I could sit here and listen for an hour to Sophie talking about Catalan numbers

[@msolec2000]

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.

[@someonewithaguitar]

These constructive set equivalence proofs are what I loved about theoretical computer science class.

[@idolgin776]

This is a really cool pattern to explore. Great job!

[@futurepath]

Love the enthusiasm!

[@dmitry7132]

Catalan Numbers me, a language nerd: "is it about numerals in the Catalan language?" 😂

[@KDBA]

Yeah my initial reaction to the video thumbnail was "I didn't know they used a different numbering system in Catalonia".

[@name12321]

I love how she explains it

[@CorrectHorseBatteryStaple472]

Such infectious enthusiasm!

[@AroundTheBlockAgain]

I'm gonna be drawing lines through pentagons today, thank you Sophie!

[@daboffey]

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.

[@DB-ei6wr]

Sophie is an awesome, awesome nerd. More of her, please.

[@xyz.ijk.]

Her abstract relations aptitude is off the charts.

[@1Osama9]

I love the explanation and the energy! I also want a pascal triangle talk. Next numberphile video?

[@ACLozMusik]

Sophie`s level of enthusiam at the conclusion on Pascal Triangle is like Liverpool just scored a goal

[@JTheoryScience]

Symmetry seems important here for computer science. Thank you Sophie, you are great!

[@OneTrueBadShoe]

Sophie Maclean may be my new favorite presenter. Very cool.

[@AntoshaPushkin]

I wish everybody that one special person who looks at them like Sophie looks at catalan numbers and pascal triangle

[@xeiroe_gaming]

i really enjoy sophie and her attitude. more of her and prof tony

[@keopsequinox1624]

So cool, thank you for yet another great video

[@Aezwozere]

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.

[@yash1152]

6:08 to 6:36 for anyone who didnt understand it, this alternate name may help. its Depth First Traversal/search (aka DFS)

[@Dudleymiddleton]

Geometric maths is always fascinating! Thinking outside the polygon!

[@benjaminlehmann]

That was great! Thanks. Love learning.

[@JacksonBockus]

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 )

[@ronny332]

That was intense, thank you very much! 🙂

[@MCLooyverse]

Woah! I just learned about Catalan numbers yesterday, as I had punched "1, 1, 2, 5" into OEIS. I was thinking about associativity, and how many associations there are for N terms (that is, how many ways are there to parenthesize N terms added together)

[@jansenart0]

I've been spoiled by Busy Beavers moving Trees of Graham's Numbers.

[@Nebukanezzer]

Look up the fast growing hierarchy. Stuff gets big.

[@camicus-3249]

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

[@andrybak]

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.

[@Adamreir]

The enthusiasm 👏👏

[@MateHegyhati]

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.

[@AnotherRoof]

Lovely video! Another topic to scratch off my video list 😅

[@crusatyr1452]

Ayyy cool seeing you here :D

[@proloycodes]

yo, whatcha doin here

[@GordonWrigley]

I'm a lil shocked you didn't show how Dyck numbers and binary trees relate to parenthesis in basic math equations.

[@Bronzescorpion]

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.

[@itechflagstaff]

Thank you. Brilliant video👍👍

[@AbcDef-jh7rw]

What a fantadtic presentation.

[@Doubting_Thomas1]

For your binary trees of order 5: 9&12 are equivalent, and 10&11 are equivalent

[@malaysahitya3710]

Great explanation 👏

[@marmite6621]

sophie is so interesting thank you sophie!

[@Escviitash]

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.

[@Meskarune]

Watching videos like this for fun is why my friends call me a nerd 😅

[@shrihanaleti4510]

I was just searching this up yesterday and it appeared in my recommended.

[@brandondegraaf]

Coincidentally, connecting the points at 5:37 creates Voronoi diagrams, which means the sliced hexagons are Delaunay triangulations.

[@samsibbens8164]

At 8:30 this is quite similar to LFSRs (linear-feedback shift registers) in old videogames for pseudo-random number generation