PolynomialEquations17
Wild Egg Maths
4.44K subscribers
Generating functions are a crucial tool in combinatorics to analyse sequences, and they form an algebraic bridge to power series in analysis, avoiding questions of convergence. We have a look at Chapter 7 of the classic text Concrete Mathematics: A Foundation for Computer Science by R. Graham, D. Knuth and O. Patashnik, which introduces generating functions in a pleasant fashion by looking at the problem of decomposing a 2 x n rectangle into 1 x 2 dominoes.
We will see that the kind of combinatorial algebra that they introduce to study this problem relates directly to our investigation of BiTri numbers and subdivisions of a polygon. In fact Exercise 22 and Problem 50 of that Chapter directly addresses the kind of geometrical/ algebraic problem we are interested in!
00:01
hello everyone i'm norman wahlberger and
00:03
thank you for joining me on this
00:04
adventure
00:05
towards solving general polynomial
00:07
equations
00:10
today i want to look at a beautiful text
00:14
by graham knuth and padishnik called
00:18
concrete mathematics a foundation for
00:20
computer science
00:21
and i want to go over particularly
00:23
chapter seven of this text which
00:26
talks about generating functions and
00:28
where i'm aiming to
00:30
show you two remarkable and intriguing
00:33
exercises or problems at the end of that
00:35
chapter exercise 22 and problem 50.
00:38
and i think these exercises
00:41
are going to have very direct bearing on
00:43
our investigation
00:45
of the combinatorics of the by tri
00:49
array and actually going further okay so
00:53
when we're doing exploration we should
00:56
balance
00:58
working ourselves on things together
01:02
with
01:03
reading existing material trying to make
01:06
contact with what other people have done
01:09
previously
01:10
okay so it's very rare to be able to
01:13
discover really new things
01:15
uh well even even under any
01:17
circumstances but especially at the
01:19
beginning so
01:20
you have to expect that when you're
01:21
starting to investigate something that
01:23
most of what you're going to be learning
01:24
is already known by someone now that's
01:27
not to say that you can't um
01:29
start experimenting to begin with i
01:32
think it's
01:32
it's nice to discover things yourself
01:36
it gives you a stronger sense of
01:39
understanding okay
01:40
but you do also want to make
01:44
contact with the existing materials
01:47
and find out other you know interesting
01:50
points of view
01:50
and and techniques or tricks or
01:54
or you know entire new theories that
01:56
that bear down on whatever you're
01:57
interested in
01:59
now we have to do this in a kind of a
02:01
balanced way so we can't get too
02:03
sidetracked not if we want to go off and
02:04
spend two years
02:06
doing something else but making contact
02:08
with other things is really great
02:10
and this particular book concrete
02:12
mathematics the foundation for computer
02:14
science
02:14
is in my view clearly one of the say top
02:18
five mathematics texts of
02:20
20th century mathematics it's it's a
02:22
it's a powerhouse
02:24
it's based on lectures by donald knuth
02:28
that he gave over many years on concrete
02:30
mathematics and it
02:31
embodies an approach to mathematics very
02:33
computationally
02:35
oriented which i have a lot of sympathy
02:37
with but aside from that it's just
02:38
really interesting it's full of
02:40
highly original and intriguing
02:43
mathematics and we're going to be
02:46
looking at the chapter 7 which is
02:48
all on generating functions so
02:51
if you have a sequence say a0 a1
02:54
a2 a3 etc then
02:57
associated to that is an algebraic
03:00
object called a generating function
03:02
where you just create a polynomial
03:05
that's
03:06
ongoing of an ongoing polynomial that
03:09
has those sequence elements as
03:12
coefficients
03:13
so for example f of x equals a0 plus a1
03:16
x
03:16
plus a2 x squared plus a3 x cubed etc
03:20
so we starting with this perhaps
03:23
combinatorial
03:24
sequence coming from somewhere and we're
03:27
creating this
03:27
ultimately an algebraic object
03:31
now how should we interpret this thing
03:32
because uh you know there's
03:34
seemingly an unbounded number of
03:37
operations here
03:39
so in classical calculus texts
03:43
these kinds of things are also discussed
03:45
in the context
03:46
of functions of power series and
03:49
in in analysis we think of these things
03:52
as being
03:53
rules that take real numbers as input
03:56
and
03:57
output real numbers according to these
03:59
instructions for adding and multiplying
04:01
and so on you have to do them an
04:02
infinite amount of times
04:04
i definitely do not want you to think
04:06
about things that way all right
04:07
i want you to think about this as an
04:09
algebraic object which is
04:10
something like a polynomial it's not a
04:12
function okay it's called a function but
04:14
i don't want you to think about it as a
04:15
function
04:16
i want you to think of it as like a
04:17
closed line an algebraic closed line on
04:20
which we're hanging our particular
04:21
sequence
04:23
now this is very natural for us of
04:25
course because
04:26
in fact we've sort of started with the
04:28
generating function approach when we
04:30
had this polynomial equation that we
04:33
wanted to solve and we
04:34
generated a a power series or
04:38
maybe a rational power series
04:41
by looking at uh solutions of it sort of
04:43
sequentially
04:44
and then we were led by studying that
04:47
thing a little bit more
04:48
carefully to to realize that there was a
04:49
combinatorial aspect
04:51
um to the the coefficients that appear
04:54
okay
04:54
and we got this by tri ray so we sort of
04:57
went from the algebra
04:58
to the combinatorics but
05:01
combinatorialists
05:02
like to go from the combinatorical
05:05
information the sequences themselves
05:07
to the generating function so the online
05:10
encyclopedia for example is full of this
05:12
kind of thing that you
05:13
you you have one of these um sequences
05:16
and then
05:16
naturally you want to associate to it
05:18
the ordinary generating function and see
05:20
if you can say something about that
05:21
so we're going to have a look at chapter
05:23
seven of this book
05:25
which treats uh this
05:28
subject gives you an introduction to uh
05:31
generating functions
05:32
and if you're interested in this general
05:34
direction and you want to explore this
05:36
you know i think it'd be time well spent
05:38
to look carefully at chapter seven
05:41
we're not going to be able to go through
05:42
all of it because that would take us too
05:43
much time but we'll have a quick look at
05:45
this general structure of the chapter
05:47
and especially uh looking at a few
05:49
interesting examples that will give us
05:52
really
05:52
interesting ideas especially when we get
05:55
to exercise 22 and problem
05:57
- okay so we're not going to go
06:01
through this entire chapter i want to
06:02
give you a rough idea so
06:03
let's start first paragraph the most
06:05
powerful way to deal with sequences of
06:08
numbers as far as anybody knows
06:09
is to manipulate infinite series that
06:12
generate
06:13
those sequences we've learned a lot of
06:15
sequences and we've seen a few
06:16
generating functions
06:17
now we're ready to explore generating
06:19
functions in depth and to see how
06:20
remarkably useful they are
06:24
okay and this first example is quite
06:26
interesting that's what we'll have a
06:27
look at mostly
06:28
so domino theory and change so the the
06:31
basic
06:32
thing here is to ask how many ways are
06:35
there to completely cover a two by end
06:37
rectangle with two by one dominoes so
06:40
you have a strip
06:42
too high and across and you want to see
06:45
how many ways you can
06:47
fill that with standard dominoes which
06:49
are
06:50
two by one and we assume that dominoes
06:52
are identical and you can put them
06:54
either
06:54
vertical horizontal and so for example
06:57
for a
06:58
2 3 rectangle there's this way here
07:01
where you have
07:02
three uh sort of stacked uh vertically
07:06
beside each other and then here there's
07:07
one vertical and two horizontal and that
07:09
can be either on the left or on the
07:10
right so
07:11
there's t uh three equals three ways of
07:14
tiling a two by three rectangle
07:16
and they'd like to have a closed form
07:18
for t sub n
07:20
where n is a natural number in general
07:23
okay so
07:27
let's um let's scroll down here
07:31
okay so there's uh some counting they
07:34
find some some values for a t
07:36
sub n and i'm we're not going to go
07:38
through it okay but what i want to
07:41
to particularly have a look at is
07:44
is right here to boldly go where no
07:47
tiling has gone before okay
07:49
so here's another way to figure out what
07:52
t n is this new way is based on a bold
07:54
idea
07:55
let's consider the sum of all possible 2
07:57
by n tilings for all
07:58
n greater than or equal to 0 and column
08:00
t so they're introducing an idea here
08:02
which i think is really
08:04
a beautiful idea and i think it probably
08:07
hasn't been taken up
08:08
as as much as it as could have been
08:12
and um i think this this particular idea
08:14
is going to actually be
08:16
essential for us to understand this
08:19
um this rational
08:24
rational power series approach to uh
08:27
solving general polynomial equations so
08:30
what they're proposing is that
08:31
we create some kind of algebraic
08:35
sum out of these combinatorial objects
08:37
so we think of all possible ways of
08:40
tiling not just a given two by n
08:43
rectangle but say like all of them
08:45
starting with say the empty
08:48
rectangle which has sort of zero uh
08:51
width
08:52
which is just denoted by this sort of i
08:55
and then
08:55
the the case n equals one is here that's
08:58
just a
08:59
single vertical tile and then n equals
09:02
two there's three of them and then you
09:04
know uh
09:08
n equals two so there's two of them and
09:09
then there's three uh
09:12
for uh with three tiles and so on and
09:15
they're proposing to create
09:16
this ongoing object which is
09:20
uh it's like a polynomial or like a
09:22
series but the
09:23
elements themselves are actually these
09:25
configurations okay and this thing
09:27
goes on in some fashion uh it goes on
09:30
indefinitely but
09:31
they're not going to worry too much
09:32
about you know the
09:34
the logical interpretation of what this
09:36
infinite sum refers to
09:38
and this whole thing is called t okay
09:41
the terms of the sum stand for tilings
09:43
which are combinatorial objects
09:44
we won't be fussy about what's
09:46
considered legal when infinitely many
09:48
tilings are added together
09:50
all right so they claim everything can
09:51
be made rigorous and
09:53
at some point we'll have to think about
09:54
that
09:56
okay so what they're going to do is
09:58
they're going to
10:00
do some arithmetic with this thing and
10:04
for that they introduce a kind of a a
10:06
multiplication
10:07
you can multiply tiles or tilings
10:10
together by just
10:12
physically com combining them with just
10:15
juxtaposition
10:16
okay so for example uh if you
10:20
you take this single vertical tile and
10:22
you take this
10:23
double tile here of horizontal things
10:25
and you you multiply them then you get
10:27
this new tiling which is the
10:29
obvious combination where you put them
10:30
together and they note that this
10:32
multiplication is not commutative okay
10:35
see the order of multiplication counts
10:38
and then they propose to do some domino
10:40
arithmetic with this to in
10:42
to manipulate the infinite sum so here
10:45
is uh you know the original t
10:48
object that we're thinking about and
10:50
then they're saying okay look
10:51
this this sum can be subdivided
10:55
into three lots first of all the the
10:59
the null tiling which is sort of acting
11:02
like the identity when you
11:03
consider what it does to this
11:05
multiplication
11:06
and then you have all the tiles that
11:08
start with a single vertical tile
11:11
and and how many of those are there
11:15
well there's one of those for every
11:16
element in t
11:18
in others if you given any tiling
11:20
constituent of t
11:22
you can create a new tiling by sticking
11:25
a
11:26
vertical domino to the left in other
11:28
words by multiplying on the left by
11:31
a single domino so that's what this
11:35
summand here represents all the times
11:38
that essentially start with a single
11:40
vertical one
11:41
and these ones here are the
11:45
the remaining ones they're the ones that
11:47
start with two horizontal tiles one on
11:49
top of each other
11:50
and we can think about that as being
11:53
this particular tile multiplied again by
11:56
the entire
11:58
sum t so we get this intriguing equation
12:01
that t
12:02
equals this sort of single thing which
12:05
is almost like an i
12:06
i plus vertical domino times t
12:10
plus stack of two horizontal dominoes
12:13
times t
12:15
now this is i think really intriguing
12:16
because it's a kind of an algebra
12:18
right but it's not really an algebra
12:20
with variables like you're familiar with
12:23
it's an algebra with combinatorial
12:25
objects
12:26
for which the fundamental operation is
12:29
itself
12:30
a combinatorial in this case almost a
12:32
geometrical combination
12:34
okay this juxtaposition of two tilings
12:39
okay so then they they rewrite this
12:42
thing here like this
12:43
as one minus vertical
12:47
tile minus two horizontal tiles times t
12:50
equals identity and then there they go
12:53
on to
12:54
to manipulate this to sort of to solve
12:56
for t so so formally t
12:58
is like some kind of quotient of uh an i
13:01
uh divided by an i minus vertical tile
13:04
minus
13:06
two horizontal tiles
13:10
great okay and then they uh then they
13:14
introduce associated generating
13:17
functions okay so
13:18
with generating functions we actually
13:20
have variables playing the role so for
13:22
example one over one minus z that's
13:24
one plus z plus z squared plus z cubed
13:27
okay that's the sort of standard
13:29
the most simplest uh sort of generating
13:31
function essentially
13:32
and they're saying well we can sort of
13:34
think about what we've got here as some
13:36
kind of version of this
13:37
except instead of having z we have this
13:40
sum of of these two
13:42
individual tilings so this would suggest
13:44
that we're taking some sum
13:46
of um of powers of these of this binary
13:49
combination of these two particular
13:51
tilings
13:52
it's all happening in a kind of a
13:54
combinatorial algebra
13:56
where the actual objects are tilings
13:59
okay
13:59
so without worrying about the details
14:02
then they
14:03
do various things and then they you know
14:05
they get
14:06
certain formulas which is all very nice
14:08
and it's
14:10
well worth thinking about but
14:13
i think this is the really the main idea
14:16
that i want
14:17
to um to extract here is that
14:20
when we're working in this generating
14:22
function world taking this purely
14:24
sort of algebraic slash combinatorial
14:26
approach it's possible to
14:28
to follow to follow
14:32
concrete mathematics here and and think
14:34
about
14:35
creating an algebra with essentially
14:38
combinatorial objects
14:41
okay so that's there's a much more in
14:44
this chapter i'll just
14:45
quickly give you a you know quickly
14:48
scroll through it
14:49
so if you were a graduate student
14:50
sitting beside me here i say you know
14:52
this is all really good stuff you should
14:54
read all of this spend a couple of weeks
14:56
going through this chapter and figuring
14:58
out
14:58
uh what they're talking about and
15:00
absorbing the various techniques that
15:02
they have for
15:03
fiddling around and working with
15:05
generating functions
15:06
okay because the problem that we're
15:08
dealing with is very much in that spirit
15:10
so we want to have some
15:12
facility with the standard techniques so
15:14
this is a great thing to do
15:15
okay absolutely and you can
15:19
get a sense of some chapter on basic
15:20
maneuvers various
15:22
operations you can do with generally
15:24
generating functions in general you can
15:25
differentiate them you can shift them
15:27
you can multiply them and then we have
15:29
some
15:30
standard you know standard manipulations
15:33
you can integrate them
15:34
sort of term by term it's all algebraic
15:36
it's it may look like it's analysis that
15:39
you're differentiating and integrating
15:40
but you're not really it's just a purely
15:42
formal
15:43
kind of of algebra just like i do in my
15:46
algebraic calculus if
15:48
you've watched any of those videos okay
15:50
and then here are some
15:52
some simple sequences for example and
15:55
and their corresponding generating
15:57
functions with some closed forms for
15:59
them
16:00
okay so this is a powerful way of of
16:03
encapsulating very efficiently
16:06
interesting sequences
16:07
and manipulating them
16:11
okay so uh then we have some recurrence
16:14
relations
16:15
uh okay maybe
16:18
too much about that all
16:22
good stuff i want to now head towards
16:25
again there's lots more material
16:26
okay but i want to hit convolutions
16:31
uh some dyke paths here which we'll have
16:34
to talk about at some point
16:36
also very important for us um
16:39
oh and actually here are m uh here are
16:42
the basically
16:42
these let's look here see there's foos
16:44
catalan numbers
16:46
um these are kind of
16:50
generalization of the foos catalan
16:51
numbers that we've been considering
16:53
we've been considering the case when
16:54
m is three okay so we've been looking at
16:56
uh something like this that what we're
16:58
calling the fuse
16:59
numbers is really something like this
17:01
where m is equal to three
17:03
three n choose n and uh over
17:06
two n plus one okay but you can actually
17:09
generalize this you can replace the
17:11
the three with an m and you still get
17:13
interesting sequences and
17:14
studied originally by by foose
17:18
in any case yes we're just having a look
17:21
at what
17:22
all kinds of interesting things that
17:23
they're doing and then there's a
17:26
variant on the generating functions that
17:27
we've been talking about called
17:28
exponential generating functions
17:30
where you basically introduce also
17:32
factorials
17:34
in the denominators and they have a
17:36
somewhat
17:37
somewhat somewhat parallel but it's has
17:40
a different kind of character and
17:42
sometimes exponential generating
17:43
functions are
17:44
more useful
17:47
okay dirichlet generating functions okay
17:50
now we come to
17:52
what i think is quite interesting so the
17:54
exercises at the end of the chapter
17:57
all right and no doubt many interesting
17:59
things to think about here so if you
18:01
were a graduate student i would also ask
18:02
you to
18:03
do some of these things you know have a
18:05
go see if you can
18:06
figure it and figure them out but i'm
18:09
particularly keen on showing you
18:13
question or exercise 22 there it is
18:16
right there
18:17
okay 22. make it a little bit bigger so
18:21
you can see for sure
18:22
all right let p be the sum of all ways
18:25
to triangulate polygons so this is the
18:28
same kind of thing as
18:30
they were talking about with dominoes
18:31
but now we're considering triangulations
18:33
of
18:34
polygons so there's a kind of an
18:36
identity
18:37
sort of null triangulation the
18:39
triangulation of the triangle of which
18:41
there's only one
18:42
the two of them for for a square the
18:45
five of them for a pentagon and so on
18:47
and they're proposing to put all of
18:49
these together
18:50
okay that's the same kind of thing we're
18:52
taking combinatorial or if you like
18:53
geometrical objects
18:55
and stringing them together to form some
18:58
kind of
18:59
combinatorial algebraic object
19:03
okay define a multiplication operator or
19:06
operation
19:07
a triangle b on triangulated polygons a
19:11
and b so that the equation p equals this
19:14
identity plus
19:15
p triangle p is valid
19:18
so you have to come up with a suitable
19:22
multiplication on triangulated polygons
19:27
and then finally replace each triangle
19:30
by z and what does this tell you about
19:32
the number of ways to decompose an n
19:34
gone into triangles
19:35
so this is of course the catalan story
19:37
right but it's a
19:38
another way of thinking about the
19:40
catalan story involving this
19:42
combinatorial algebra of these sort of
19:44
ongoing
19:46
ongoing slew of um of triangulated
19:50
polygons so this is a quite an
19:53
intriguing thing and i think we want to
19:54
think about
19:55
this now in the same spirit
19:58
if we go a little bit further
20:02
bonus problems here we get to bonus
20:04
problem number 50.
20:06
it's continuing exercise 22
20:09
consider the sum of all ways to
20:11
decompose
20:12
polygons into polygons
20:16
so not just triangles not just
20:18
quadrilaterals not just
20:20
you know small ones but arbitrary
20:24
polygons so you can use pentagons
20:25
hexagons
20:26
dodecagons 37 gons whatever it is okay
20:30
to just decompose polygons
20:33
but again the orientation matters just
20:36
as it does for the catalan
20:37
story now they ask
20:40
find a symbolic equation for this sum
20:43
and use it to find a generating function
20:45
for the number of ways to draw in
20:47
non-intersecting diagonals inside a
20:49
convex and gone
20:50
give a closed form for the generating
20:52
function as a function of z
20:53
you need not find a closed form for the
20:56
coefficients
20:58
all right so this is a great thing for
20:59
for us to think about because
21:01
uh this is making obvious contact with
21:04
the
21:04
kind of bi-tri array that we've been
21:07
investigating
21:08
and also the natural extension that we
21:10
can
21:11
you know clearly see is ahead of us
21:13
where we move not just from triangles
21:15
and quadrilaterals but
21:16
to include higher degree polygons in the
21:20
decomposition
21:22
okay and so these two exercises are
21:24
suggesting that there is a kind of
21:25
combinatorial algebraic
21:27
approach to at least getting some
21:29
information from these kinds of things
21:32
and my guess is that it's exactly this
21:35
approach
21:38
coming from concrete mathematics that's
21:40
going to
21:41
play an interesting role for us in
21:44
illuminating
21:45
what's going on in our approach to
21:48
solving
21:49
general polynomial equations