Catalan Numbers - Numberphile

แชร์
ฝัง
  • เผยแพร่เมื่อ 13 ม.ค. 2025

ความคิดเห็น • 530

  • @numberphile
    @numberphile  11 หลายเดือนก่อน +48

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

    • @NekoAlosama
      @NekoAlosama 11 หลายเดือนก่อน +3

      haven't you uploaded this video before?

    • @LucenProject
      @LucenProject 11 หลายเดือนก่อน

      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
      @huecan5748 11 หลายเดือนก่อน +4

      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
      @MichaelSandbox 11 หลายเดือนก่อน +1

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

    • @Unlimit-729
      @Unlimit-729 6 หลายเดือนก่อน

      What???
      Try typing it into calculator:
      ( 100000 - sqrt(9999600000) )/2 and you will get catalan numbers

  • @stanimir5F
    @stanimir5F 11 หลายเดือนก่อน +1050

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

    • @numberphile
      @numberphile  11 หลายเดือนก่อน +149

      Cheers. She does seem to like them. :)

    • @HappyMathDad
      @HappyMathDad 11 หลายเดือนก่อน +29

      Just a tiny bit.

    • @alleycatsphinx
      @alleycatsphinx 11 หลายเดือนก่อน

      have you seen the paper from Wildburger?@@numberphile

    • @chammy2812
      @chammy2812 11 หลายเดือนก่อน +32

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

    • @monkeybusiness673
      @monkeybusiness673 11 หลายเดือนก่อน +5

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

  • @EaglePicking
    @EaglePicking 11 หลายเดือนก่อน +911

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

    • @JeremyForTheWin
      @JeremyForTheWin 11 หลายเดือนก่อน +24

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

    • @arikwolf3777
      @arikwolf3777 11 หลายเดือนก่อน +2

      I seconded.

    • @zhezburger
      @zhezburger 11 หลายเดือนก่อน +12

      I want a 1+ hour talk about Catalan numbers.

    • @thomasanderson9383
      @thomasanderson9383 11 หลายเดือนก่อน +2

      Me too !!

    • @liz4v
      @liz4v 11 หลายเดือนก่อน +6

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

  • @meiliyinhua7486
    @meiliyinhua7486 11 หลายเดือนก่อน +327

    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
      @mo284 11 หลายเดือนก่อน +43

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

    • @meiliyinhua7486
      @meiliyinhua7486 11 หลายเดือนก่อน +23

      @@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
      @taljones4844 11 หลายเดือนก่อน +5

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

    • @sethhu20
      @sethhu20 11 หลายเดือนก่อน +12

      pov: your code have 12 nested parenthesis and curly brackets

    • @noa_1104
      @noa_1104 11 หลายเดือนก่อน +5

      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.
    @N.I.R.A.T.I.A.S. 11 หลายเดือนก่อน +241

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

    • @sdffhsdghhn
      @sdffhsdghhn 2 หลายเดือนก่อน +1

      "enthusiasm"

    • @MttGaming904
      @MttGaming904 15 วันที่ผ่านมา

      @@sdffhsdghhn "enthusiasum"

  • @wildndetroit
    @wildndetroit 11 หลายเดือนก่อน +388

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

    • @marksusskind1260
      @marksusskind1260 11 หลายเดือนก่อน +6

      I got that right-- now

    • @MeltedMask
      @MeltedMask 11 หลายเดือนก่อน

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

    • @Jacquobite
      @Jacquobite 11 หลายเดือนก่อน +20

      Yeah two pitfalls for one word.

    • @deltalima6703
      @deltalima6703 11 หลายเดือนก่อน +4

      Now for the aussie accent....

    • @Ggdivhjkjl
      @Ggdivhjkjl 11 หลายเดือนก่อน +2

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

  • @axillv1736
    @axillv1736 11 หลายเดือนก่อน +50

    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!

  • @stpacctsgn
    @stpacctsgn 11 หลายเดือนก่อน +55

    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.

  • @gervasiosantos3563
    @gervasiosantos3563 11 หลายเดือนก่อน +71

    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
      @JohnnieMartynov 11 หลายเดือนก่อน

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

    • @therealax6
      @therealax6 11 หลายเดือนก่อน +2

      @@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
      @JohnnieMartynov 11 หลายเดือนก่อน

      @@therealax6 OK, I will try it. 🙂

    • @siquod
      @siquod 5 หลายเดือนก่อน

      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?

  • @TheFireHawkDelta
    @TheFireHawkDelta 11 หลายเดือนก่อน +126

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

    • @queueeeee9000
      @queueeeee9000 11 หลายเดือนก่อน +8

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

    • @ArawnOfAnnwn
      @ArawnOfAnnwn 11 หลายเดือนก่อน +1

      @@queueeeee9000 The Fine Structure Constant too!

    • @temporarytemporary-fh2df
      @temporarytemporary-fh2df 8 หลายเดือนก่อน

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

    • @siquod
      @siquod 5 หลายเดือนก่อน

      @@ArawnOfAnnwn Where outside of QED?

  • @thargy
    @thargy 11 หลายเดือนก่อน +80

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

    • @pawezielinski2781
      @pawezielinski2781 11 หลายเดือนก่อน

      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
      @Fucisko 11 หลายเดือนก่อน

      @@pawezielinski2781 bruh

    • @scottdebrestian9875
      @scottdebrestian9875 11 หลายเดือนก่อน +4

      @@pawezielinski2781 That's the Numberphile way!

    • @teliph3U
      @teliph3U 11 หลายเดือนก่อน +7

      @@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
      @lonestarr1490 11 หลายเดือนก่อน +2

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

  • @eminence_
    @eminence_ 11 หลายเดือนก่อน +45

    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
      @numberphile  11 หลายเดือนก่อน +11

      Ha ha

    • @AroundTheBlockAgain
      @AroundTheBlockAgain 8 หลายเดือนก่อน +3

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

  • @ErhanTezcan
    @ErhanTezcan 11 หลายเดือนก่อน +24

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

  • @nafizbasaran1907
    @nafizbasaran1907 11 หลายเดือนก่อน +11

    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
    @landonthompson-tschimperle3964 11 หลายเดือนก่อน +7

    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!

  • @ahabkapitany
    @ahabkapitany 11 หลายเดือนก่อน +21

    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
      @mortgageapprovals8933 11 หลายเดือนก่อน +1

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

    • @junj1023
      @junj1023 4 หลายเดือนก่อน

      @@mortgageapprovals8933 And what about the probability density function of the Normal Distribution? (3b1b has a video about this)

  • @imakarsh
    @imakarsh 5 หลายเดือนก่อน +2

    🎯 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

  • @coulie27
    @coulie27 11 หลายเดือนก่อน +77

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

  • @KaedennYT
    @KaedennYT 11 หลายเดือนก่อน +1

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

  • @walternullifidian
    @walternullifidian 8 หลายเดือนก่อน +2

    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.

    • @oz_jones
      @oz_jones 5 หลายเดือนก่อน +1

      Nice!

  • @bananatassium7009
    @bananatassium7009 11 หลายเดือนก่อน +2

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

  • @gerryn2
    @gerryn2 11 หลายเดือนก่อน +11

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

  • @devnol
    @devnol 11 หลายเดือนก่อน +37

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

  • @d_roy_
    @d_roy_ 11 หลายเดือนก่อน

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

  • @nienke7713
    @nienke7713 11 หลายเดือนก่อน

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

  • @boredgrass
    @boredgrass 11 หลายเดือนก่อน

    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.

  • @HappyMathDad
    @HappyMathDad 11 หลายเดือนก่อน +4

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

  • @Kebabrulle4869
    @Kebabrulle4869 11 หลายเดือนก่อน +14

    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!

  • @St_M_
    @St_M_ 11 หลายเดือนก่อน

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

  • @Bregylais
    @Bregylais 11 หลายเดือนก่อน +1

    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
      @tristanridley1601 11 หลายเดือนก่อน +1

      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.

  • @hantuchblau
    @hantuchblau 11 หลายเดือนก่อน +2

    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.

  • @ConManAU
    @ConManAU 11 หลายเดือนก่อน +1

    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.

  • @Art1factlol
    @Art1factlol 9 หลายเดือนก่อน +2

    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👏

  • @drocpdp
    @drocpdp 2 หลายเดือนก่อน

    This explanation really helps bridge the gap between the formula and the conceptual idea!!! Thanks.

  • @emanuellandeholm5657
    @emanuellandeholm5657 11 หลายเดือนก่อน +1

    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)

  • @markjreed
    @markjreed 11 หลายเดือนก่อน +4

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

  • @3Max
    @3Max 11 หลายเดือนก่อน

    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!

  • @NickEllis-nr6ot
    @NickEllis-nr6ot 11 หลายเดือนก่อน +5

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

  • @lillyfiorino8636
    @lillyfiorino8636 11 หลายเดือนก่อน +2

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

  • @daboffey
    @daboffey 11 หลายเดือนก่อน

    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.

  • @TECHNIXCAFE
    @TECHNIXCAFE 11 หลายเดือนก่อน +5

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

  • @dmitry7132
    @dmitry7132 11 หลายเดือนก่อน +7

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

    • @KDBA
      @KDBA 11 หลายเดือนก่อน +2

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

  • @mplsmike4023
    @mplsmike4023 11 หลายเดือนก่อน +3

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

  • @ACLozMusik
    @ACLozMusik 11 หลายเดือนก่อน

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

  • @unvergebeneid
    @unvergebeneid 11 หลายเดือนก่อน +1

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

  • @yash1152
    @yash1152 11 หลายเดือนก่อน

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

  • @TemplerOO7
    @TemplerOO7 11 หลายเดือนก่อน

    Wow I was blown away by her enthusiasm, contagious!

  • @charlesmrader
    @charlesmrader 11 หลายเดือนก่อน +6

    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.

  • @mytube001
    @mytube001 11 หลายเดือนก่อน +7

    Love it! Old school Numberphile!

  • @M4DA.
    @M4DA. 11 หลายเดือนก่อน +8

    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
      @quatrevingtneuf 11 หลายเดือนก่อน +4

      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
      @Farull 11 หลายเดือนก่อน +2

      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.
      @M4DA. 11 หลายเดือนก่อน +3

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

  • @xyz.ijk.
    @xyz.ijk. 11 หลายเดือนก่อน +1

    Her abstract relations aptitude is off the charts.

  • @ilghiz
    @ilghiz 11 หลายเดือนก่อน +4

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

  • @Escviitash
    @Escviitash 11 หลายเดือนก่อน +2

    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.

  • @Doubting_Thomas1
    @Doubting_Thomas1 10 หลายเดือนก่อน +1

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

  • @Aezwozere
    @Aezwozere 11 หลายเดือนก่อน +3

    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.

  • @someonewithaguitar
    @someonewithaguitar 11 หลายเดือนก่อน

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

  • @mikeymad
    @mikeymad 11 หลายเดือนก่อน

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

  • @don5oan
    @don5oan 11 หลายเดือนก่อน +2

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

  • @platypi_otbs
    @platypi_otbs 11 หลายเดือนก่อน +1

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

  • @alonvinkler
    @alonvinkler 11 หลายเดือนก่อน +2

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

  • @PBGidi
    @PBGidi 11 หลายเดือนก่อน +3

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

  • @MasterHigure
    @MasterHigure 11 หลายเดือนก่อน +10

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

  • @AroundTheBlockAgain
    @AroundTheBlockAgain 8 หลายเดือนก่อน

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

  • @11th_Moon
    @11th_Moon 2 หลายเดือนก่อน

    I want to say 1000 thanks - best explanation of the Catatln number!

  • @zdlax
    @zdlax 11 หลายเดือนก่อน +1

    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.

  • @LittlePunnkk
    @LittlePunnkk 11 หลายเดือนก่อน +30

    "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
      @rennleitung_7 11 หลายเดือนก่อน +1

      @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
      @DarklordZagarna 9 หลายเดือนก่อน

      @@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
      @rennleitung_7 9 หลายเดือนก่อน

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

  • @Meskarune
    @Meskarune 10 หลายเดือนก่อน +1

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

  • @brandondegraaf
    @brandondegraaf 11 หลายเดือนก่อน

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

  • @msolec2000
    @msolec2000 11 หลายเดือนก่อน

    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.

  • @Kaepsele337
    @Kaepsele337 11 หลายเดือนก่อน +1

    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.

  • @TimJSwan
    @TimJSwan 11 หลายเดือนก่อน

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

  • @TheElectra5000
    @TheElectra5000 11 หลายเดือนก่อน +1

    Friend: "oh, look at this view!! Isn't it gorgeous?"
    Sophie: "yeah, that's nice. Have I told you about Pascal's Triangle?"

  • @DB-ei6wr
    @DB-ei6wr 11 หลายเดือนก่อน +3

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

  • @diffusegd
    @diffusegd 11 หลายเดือนก่อน +1

    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

  • @stephenweigel
    @stephenweigel 11 หลายเดือนก่อน

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

  • @peterhemmings2929
    @peterhemmings2929 11 หลายเดือนก่อน +2

    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.

    • @Stereomoo
      @Stereomoo 11 หลายเดือนก่อน +4

      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)

    • @peterhemmings2929
      @peterhemmings2929 11 หลายเดือนก่อน +1

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

  • @name12321
    @name12321 11 หลายเดือนก่อน +1

    I love how she explains it

  • @JianJiaHe
    @JianJiaHe 8 หลายเดือนก่อน

    9:30 There was an error here, there were 2n+1 possible rearrangements, so it should be divided by 2n+1, not n+1.

  • @traviswilliams3034
    @traviswilliams3034 11 หลายเดือนก่อน +7

    Me, drunk on TH-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."

  • @pudicio
    @pudicio 11 หลายเดือนก่อน

    Now I want to see an episode with Sophie and Cliff Stoll together. I think the galaxy would explode

  • @MateHegyhati
    @MateHegyhati 11 หลายเดือนก่อน

    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.

  • @chrisd561
    @chrisd561 11 หลายเดือนก่อน

    Best video in a while. Love the enthusiasm!!

  • @AntoshaPushkin
    @AntoshaPushkin 11 หลายเดือนก่อน +1

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

  • @camicus-3249
    @camicus-3249 11 หลายเดือนก่อน

    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
      @andrybak 11 หลายเดือนก่อน

      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.

  • @gary5407
    @gary5407 11 หลายเดือนก่อน

    At 2:40 the 3rd row is incorrect - two are duplicated (and two others are missing).

  • @AnotherRoof
    @AnotherRoof 11 หลายเดือนก่อน +7

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

    • @rgfella
      @rgfella 11 หลายเดือนก่อน +2

      Ayyy cool seeing you here :D

    • @mojacodes
      @mojacodes 11 หลายเดือนก่อน

      yo, whatcha doin here

  • @sarahchellew8244
    @sarahchellew8244 11 หลายเดือนก่อน +2

    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

  • @Dudleymiddleton
    @Dudleymiddleton 11 หลายเดือนก่อน +1

    Geometric maths is always fascinating! Thinking outside the polygon!

  • @bejoscha
    @bejoscha 11 หลายเดือนก่อน

    I liked the math, but I really particularly liked the enthusiasm in the presentation.

  • @JTheoryScience
    @JTheoryScience 11 หลายเดือนก่อน

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

  • @mavericktron2966
    @mavericktron2966 11 หลายเดือนก่อน

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

  • @stumbling
    @stumbling 11 หลายเดือนก่อน

    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.

  • @Bronzescorpion
    @Bronzescorpion 11 หลายเดือนก่อน

    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.

  • @ginsengaddict
    @ginsengaddict 11 หลายเดือนก่อน

    0:40 - There are 20, actually. You can draw the N in reverse, so you have an additional 6 ways using "|/|" shaped lines.

  • @samsibbens8164
    @samsibbens8164 11 หลายเดือนก่อน

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

  • @JacksonBockus
    @JacksonBockus 11 หลายเดือนก่อน

    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 )

  • @MathematicsOne
    @MathematicsOne 10 หลายเดือนก่อน +1

    Phenomenal video as always!

  • @GordonWrigley
    @GordonWrigley 11 หลายเดือนก่อน +6

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

  • @shrihanaleti4510
    @shrihanaleti4510 11 หลายเดือนก่อน +1

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

  • @tohaomg
    @tohaomg 11 หลายเดือนก่อน +1

    It was a surprise for me, that those numbers were not named after the land of Catalonia, but after a person with such last name

    • @gregweatherup9596
      @gregweatherup9596 11 หลายเดือนก่อน +1

      I’ll raise you an extra step- I was expecting the video to be about an alternative numeral system (set of symbols) from ancient Catalonia. 😮