Solving Polynomial Equations 11
Wild Egg Maths
4.25K subscribers
The Catalan and Fuss-Catalan numbers have close parallels. We have seen that with our attempt to solve the general cubic equation with a power series approach, rather than with the traditional approach of radicals, we are led to a somewhat interesting array of natural numbers that have the Catalan and Fuss-Catalan numbers down the 0th column and across the 0th row.
So obviously we should learn more about these sequences to try to understand our array of coefficients. To do that we will inspect entries of the Online Encyclopedia of Integer Sequences, and have a good look at some nice web pages created by Robert Dickau, at robertdickau.com/fusscatalan.html .
00:02
hello everyone i'm norman wahlberger
00:04
and thank you for joining me in this
00:06
adventure
00:07
as we explore some research level
00:09
mathematics
00:10
related to solving polynomial equations
00:15
so we've been looking at a cubic
00:16
equation we've found that a certain
00:18
array of natural numbers
00:22
seems to crop up from this novel power
00:25
series orientation that we've adopted
00:28
and currently we're trying to get our
00:31
heads around
00:33
the meaning of these numbers
00:36
appearing in this array so the numbers
00:39
start
00:40
out by being defined in terms of these
00:43
sub multinomial coefficients which are
00:45
quotients of factorial so here's sort of
00:47
the
00:48
the official definition and then here
00:50
are what we end up getting
00:52
once we convert things into natural
00:54
numbers so we want to explain this array
00:57
in particular we would like to explain
00:59
it combinatorially and in a uniform way
01:03
now what we currently know is that the
01:04
first
01:06
column are the catalan numbers
01:09
and we also know that the first row is
01:11
another sequence not quite as
01:13
famous as the catalan numbers but also
01:15
pretty well known
01:16
that's called the fuse catalan numbers
01:18
or faf foose
01:20
catalan numbers and we found both of
01:22
those sequences in
01:24
neil sloane's online encyclopedia of
01:26
integer sequences
01:27
where we also managed to find the second
01:30
column and the second row and also the
01:33
third
01:33
column but it appeared that
01:37
further columns and were not in there
01:42
so what we would like to do is to find a
01:45
uniform
01:46
interpretation of these things to
01:47
combine our understanding
01:49
sort of of the vertical story with sort
01:52
of a catalan story
01:53
and this horizontal story sort of the
01:55
fuse catalan story
01:56
to explain the array generally
02:00
so a good comprehensive reference for
02:03
this
02:04
very rich area of covenant works is the
02:08
beautiful work of richard stanley who is
02:10
a key figure
02:11
in in modern mathematics sort of a god
02:14
of combinatorics
02:16
his volumes in numerative combinatorics
02:18
two volumes
02:20
um has a lot of information about the
02:23
catalan story
02:24
and related things so so at some point
02:26
we'll want to touch base with this
02:28
although
02:28
maybe we need to learn a little bit more
02:30
before we're in the position to do that
02:33
so today what i want to do is i want to
02:36
stare at these
02:38
at these numbers and try to frame
02:41
a possible extension of
02:44
the the catalan and the foose catalan
02:47
story
02:48
that perhaps might go uh some ways
02:51
towards explaining this array
02:53
so great great little project
03:00
so a starting reference for this is
03:03
my famous math problem 8 lecture
03:06
which is on the problem of euler's
03:08
triangulation of a polygon
03:10
and this is historically where the
03:12
catalan numbers
03:13
first appeared so maybe they should be
03:15
called euler numbers but if we named
03:17
everything
03:18
after oil or that deserved to be then
03:20
pretty well everything would be called
03:21
oil or something rather and it'd be very
03:23
confusing okay so euler asked the
03:25
question how do you
03:28
count the number of triangulations of a
03:30
polygon
03:31
so if you have just a triangle there's
03:32
only one way of triangulating it if you
03:34
have a square or a rectangle
03:36
you have two ways of triangulating it
03:40
here are the five ways of triangulating
03:42
a pentagon
03:44
so the third catalan number is five and
03:46
here are the 14
03:47
different ways of triangulating a
03:50
hexagon
03:52
so there's some triangulations like this
03:55
are sort of emerging from a vertex
03:57
like six of those and then there's some
03:59
that sort of have some
04:00
ends in them there's six of those and
04:03
then there's these sort of two special
04:05
ones where there's sort of some interior
04:06
triangles
04:08
with triangles on the outside
04:11
so this is the start of the catalan
04:14
story and it's
04:16
a primary kind of uh you know intuition
04:20
or connection with with geometry
04:22
now if we skip forward to modern times
04:26
i've shown you already the online
04:27
encyclopedia of integer sequences and
04:29
here
04:30
is a triple zero one zero eight i think
04:32
i may have said five zero eight last
04:34
time okay
04:35
it's one zero eight that's the catalan
04:37
numbers one one two five
04:38
fourteen forty two one thirty two four
04:40
twenty nine fourteen 1430
04:42
4862 etc and there's
04:45
dozens and dozens of interpretations
04:49
unfortunately if you scroll down these
04:52
interpretations and you look for sort of
04:54
the euler interpretation which is
04:56
actually the first one
04:58
um you know it's perhaps it's somewhere
05:01
down here but
05:02
it's not let's say prominently visible
05:05
so if you're
05:06
involved in the online encyclopedia can
05:08
you please sort of prominently at the
05:09
top
05:11
mention euler's decomposition of a
05:14
polygon this is a primary
05:17
interpretation of these things it really
05:19
should be very near the top of the list
05:22
okay so but in any case this is a very
05:24
very rich story in fact it's almost
05:26
too rich there's just too many different
05:28
ways of thinking about
05:29
the catalan numbers perhaps now if we go
05:32
to a
05:33
double zero 1764 we
05:36
come to numbers which um we might call
05:39
the
05:39
fuse catalan numbers or fafus catalan
05:42
numbers
05:42
this is the first row of rra 113 12
05:47
55 273 1428 7752 etc and there's still
05:52
quite a few
05:53
interpretations of that as we've seen
05:56
already
05:58
okay so one strategy would be to sort of
06:00
you know
06:01
go through these different
06:03
accommodations and
06:05
you know study these entries
06:07
considerably and then
06:08
find some sort of commonality between
06:11
the catalan
06:12
story and the foos catalan story
06:15
and once having done that we might then
06:17
also connect with the other
06:21
rows and columns that we've already
06:24
found
06:25
that were on our array and also in the
06:27
online encyclopedia for example
06:29
2054 and
06:33
nine two two but
06:36
i'm going to actually employ a a
06:38
different
06:39
resource due to robert dickow
06:43
there's just some web pages that he's
06:45
put together
06:46
um which are very attractive and they
06:49
are a really nice resource
06:51
for us to understand uh the first
06:53
catalan numbers
06:54
along with the catalan numbers okay so
06:57
let's have a look at his pages
06:59
for the catalan numbers because it's
07:02
very nice just to
07:03
scroll through and and to sort of see uh
07:05
you know
07:06
what the ver some of the various
07:07
interpretations are
07:09
so here is the formula uh 2n
07:13
choose n maybe make this a bit bigger if
07:15
i can
07:17
okay 2n choose n
07:20
over n plus 1 that's the definition
07:24
and then here are these subdivisions
07:27
of of a pentagon for example the five
07:30
subdivisions into triangles
07:32
and there's sort of a corresponding sort
07:34
of tree-like structures that might be
07:36
associated
07:37
to to that then if we scroll down
07:40
further we see
07:41
you know the the oil or subdivision
07:43
prominently
07:44
that i've already showed you in my video
07:46
but we also
07:47
see um seven sides there are 42 ways
07:51
those the 42 ways of
07:53
subdividing a septagon and then the
07:56
132 ways of subdividing um an
08:00
eighth gone and then there are various
08:02
other
08:03
uh interpretations there's
08:04
interpretations of catalan numbers in
08:06
terms of um sort of decomposing a
08:09
staircase pattern into
08:10
into rectangles of different kinds
08:13
and there's then interpretations of
08:17
number of ways of
08:18
arranging brackets of some combined
08:22
multiplication of a number of
08:24
terms and then there's also some tree
08:27
diagrams
08:28
and some interpretations in terms of
08:32
paths along a grid okay in this case
08:35
where you're
08:35
you're going horizontally and you can
08:38
always go either
08:39
up to the right or or down to the right
08:43
and you're going from here to here so
08:45
these will say the
08:46
five ways of doing that
08:49
if you have to ultimately go from here
08:51
to here and if you want to go from here
08:52
to here well then there's uh
08:55
14 waves etc and then there's some
08:58
further
09:00
some further diagram
09:03
okay great so those are the catalan
09:05
numbers that we're somewhat familiar
09:07
with now let's have a look at these fuse
09:09
catalan numbers which we have perhaps
09:11
less
09:11
experience with and i really love
09:14
robert's um introduction here he he
09:17
outlines some of the
09:19
the prominent ways okay so
09:22
as as you've seen catalan numbers have
09:24
many interpretation and combinatorics
09:26
including
09:27
number of ways of parentheses can be
09:29
placed in a sequence of n numbers to be
09:30
multiplied two at a time
09:32
the number of binary planar binary trees
09:35
with n plus
09:36
one leaves the number of paths of length
09:39
two n through an n by n grid that does
09:41
not cross above the main diagonal
09:44
number of non-crossing partitions of the
09:46
set one
09:47
through n and the number of ways of a
09:49
polygon with n plus two sides can be
09:51
sliced into
09:52
n triangles that's euler's
09:56
euler's original problem okay so those
09:59
are the catalan numbers and now the
10:01
generalization of the catalan numbers
10:03
uses triples instead of pairs
10:06
for example the number of ways to place
10:08
parentheses in
10:09
sequence of two n plus one numbers to be
10:11
multiplied three at a time
10:13
the number of planar ternary trees with
10:15
two n plus one leaves
10:17
the number of paths of length 3n through
10:19
a 2n by n
10:20
grid that do not cross above the main
10:22
diagonal the number of non-crossing
10:24
partitions of the set
10:26
1 through 2n that contains only subsets
10:28
of
10:29
even lengths and the number of ways a
10:32
polygon with
10:33
two n plus two sides can be sliced into
10:36
n
10:36
quadrilaterals uh this is such a
10:40
beautiful succinct uh explanation which
10:45
shows the parallels between the catalan
10:47
numbers and the foos catalan numbers
10:49
this is exactly what we want right we
10:51
that's what we want we want to
10:53
understand some uniform picture that
10:55
goes beyond the fuse
10:56
catalan numbers and the catalan numbers
10:58
and combines them okay so this is great
11:01
so now let's just see what some of the
11:02
pictures that we have here also
11:05
so first of all here's the formula for
11:06
the foust catalan numbers
11:08
3n choose n over 2n plus 1.
11:13
and if we go back up to the online
11:15
encyclopedia very briefly so that's that
11:17
first row 1 1
11:18
3 12 55 etc you see that the formula is
11:21
the same
11:22
3n choose n divided by 2n
11:25
plus 1. so we're talking about the same
11:28
thing here
11:29
okay and um okay
11:33
then he lists some interpretation so
11:35
there's
11:36
some diagram in terms of planar ternary
11:39
trees
11:39
certain paths that go from one
11:43
end of a rectangle to another in terms
11:46
of
11:46
number of ways of parenthesizing five
11:50
numbers as triples
11:52
something involving planar ternary trees
11:56
and
12:00
yes ways of combining things where
12:02
you're
12:03
not performing a binary operation but a
12:05
ternary operation
12:07
okay this is kind of a mathematics less
12:09
familiar to us because we're very binary
12:11
oriented but
12:12
hey it's uh it's interesting ternary
12:15
trees
12:16
um some more paths um some other things
12:21
um and here 12 ways to slice an
12:24
octagon into quadrilaterals
12:29
okay so this is the analog of the euler
12:32
thing
12:33
where we're looking at an octagon we're
12:35
slicing it into quadrilaterals
12:37
okay there's two slices there's a
12:39
quadrilateral up there
12:40
there's another quadrilateral here it's
12:42
got one two
12:44
three four vertices and then there's
12:46
another one down here
12:49
and there are 12 ways of
12:53
of doing that corresponding to
12:58
the 12 that's appearing here in
13:01
the sequence
13:06
okay and then there's some some some
13:07
more and more pictures so this is a
13:09
great resource um
13:12
55 ways to slice a decagon into
13:14
quadrilaterals here we see them all
13:16
right 55 is the one that's following 12
13:18
in the sequence
13:20
ways of slicing a decagon that's 10
13:22
sides into
13:23
quadrilaterals each of these is a little
13:25
quadrilateral
13:29
okay so thank you very much robert for
13:31
that now let's go back here and people
13:33
let's let's think
13:34
so what we want to do we want to
13:36
understand
13:37
um a generalization of the catalan story
13:40
and
13:41
the foos catalan numbers
13:45
that will explain our array so what is
13:48
the simplest thing that we could do
13:50
okay you'd be amazed at how many times
13:53
in mathematics
13:55
the simplest thing is often the thing
13:58
that works best
14:00
i know you don't think that you think oh
14:01
it's all very complicated
14:03
the complexity is often because well
14:06
you're looking at a situation which is
14:08
very rich okay
14:10
but it's sometimes also because you're
14:13
not quite looking at things in the right
14:15
way
14:16
so when we do look at things in the
14:17
right way we've broken it down into
14:19
simple things
14:20
then often the next step is just the
14:23
obvious one
14:25
and i claim that there's now an obvious
14:27
thing to do here
14:28
there's an obvious way of
14:32
extending the catalan story and the fuse
14:34
catalan story
14:35
and since we think of the catalan story
14:39
primarily or maybe historically first in
14:42
terms of euler's problem
14:44
this is this last one here the number of
14:46
ways a polygon with n plus two sides can
14:48
be sliced into n triangles
14:51
the corresponding foos catalan condition
14:54
would be this last one here
14:55
the number of ways a polygon with two n
14:57
plus two sides can be sliced into n
14:59
quadrilaterals so we're talking about
15:02
creating a polygon
15:03
from n triangles in the one case and in
15:07
the other case
15:08
creating a polygon with n quadrilaterals
15:12
how could we mesh those together
15:16
i know you already know the answer right
15:18
we ask
15:20
how can we create a polygon
15:23
using a certain number of triangles and
15:27
a certain number of quadrilaterals not
15:30
just triangles not just quadrilaterals
15:33
but
15:34
triangles and quadrilaterals
15:40
so if we go back to our original array
15:44
after the first column first row do you
15:47
remember what that next entry in
15:49
the sort of the 1 1 position is it was a
15:53
five
15:55
a five and what would that five
15:59
correspond to
16:00
it would correspond to the number of
16:02
ways of taking a pentagon
16:04
there's a pentagon and subdividing it
16:07
into
16:08
one triangle and one quadrilateral
16:12
i hope you can all see if there's five
16:14
ways of doing that right you've got
16:15
there's a pentagon
16:16
you're going to take a line that a
16:18
diagonal like this a diagonal like this
16:20
is going to slice it
16:21
into a triangle on this side and a
16:24
quadrilateral on this side
16:26
and such a such a diagonal there's
16:29
exactly five of them
16:31
so that interpretation at least matches
16:35
with one
16:36
entry which is in our array the simplest
16:39
entry which is not in the first row and
16:41
first column
16:42
so now we have a potential candidate for
16:45
understanding our array
16:47
very exciting but obviously we have a
16:49
lot of work to do
16:50
to check whether this might actually
16:54
work