Today, we're going to talk about words and
mappings.
This is an appropriate area in which to
finish our study because it ties together
many of the things we've talked about
before.
Again, this is the, the last of, of the
second half of the class.
And what we're talking about today mostly
labeled objects, so we'll be working
exponential generating functions.
And again, as I've been saying each week
there's many more examples in the book
than we're able to do in lecture.
But we'll consider some techniques from
analytic combinatorics in applications to
the analysis of algorithms.
So to start out, I'm going to talk about
what we mean by what is a word in a
combinatorial sense.
And to do that, let's just review a few of
the related combinatorial objects that
we've looked at.
So, for example, we've looked at again,
how many binary strings are within bits,
seems we talked about this almost every
lecture.
So a string is a sequence of 0 bits and 1
bits.
And with the symbolic method using
ordinary generating functions we show that
it's 2 to the N.
Now that can extend to how many strings
drawn from an M character alphabet.
Then in that case it's a sequence of one
of the M characters which is 1 over 1
minus Mz.
So again, that gives us N to the N.
It's the number of strings drawn from the
N character alphabet that has N
characters.
So, how's that related to words?
Well, we'll get there.
Let's look at labelled objects now.
And let's say how many sets labelled sets
are there of size N.
So there's exactly one labelled set of
size 2, the one that's got 2 objects in
it.
And actually of any size N there's only
one labelled set.
This is just a little bit of a review of
what we mean by labeled objects as we
don't consider the order significant so
there's only one set and we label all the
objects.
Now, if you want to take ordered pairs of
label sets of N objects, so then what do
you get?
Well for 2 objects you can have a 1 and
then a 2, or a 2 and then a 1 or you can
have an empty set in 2 objects or 2
objects in an empty set.
So the, in this case, the ordering of the
sets is significant and then the labeled
objects can fall in the sets in these
different ways.
And so, there's 8 different ordered pairs
or labeled sets of, of N objects and so
then, you can see the answers to the end.
And that's the same as the number of
bitstrings and we'll see how that
relationships comes through in just a
minute.
So what about instead of pairs, what if we
have a sequence of M sets, how many
sequences of length M of labeled sets of N
objects are there?
And I, we use the word, urns, to talk
about a set as a thing that can hold
labeled objects.
So thinking of it that way, a classic, or
a classical way to think of it is of balls
and urns.
So, really what we are talking about is
the number of different ways to throw in
balls into two urns.
So, if there's one ball, it can go, if
there's two urns, one ball can go into
either one of them.
If there's two balls it can either, both
can go in the first or both can go in the
second.
Or they can go in the two orders.
The labels on the balls are significant
but not the order of the labels within the
urn.
We put them in the order they went in but
that order is not significant.
And again, there's 8 ways to throw three
balls into two urns.
So that's a balls-and-urns way of looking
at really the same combinatorial
structure.
So again, 2 to the N.
So now, let's look at how we get at these
counting results from the symbolic method.
And this is just a review of what we
talked about in, in Lecture 5.
If we have combinatorial classes of
labeled objects then we have these basic
operations that we can perform on the
classes that disjoint copies or taking
ordered pairs relabeling in all ways and
then the corresponding operations on the
exponential generating function give us a
symbolic transfer from the construction
right to the generating function.
And for labeled objects, we extend that to
the sequences of length k or sequences of
any length giving those transformations of
the generating function or for sets where
we divide by k factorial.
So, a set of objects from a class, the
generating function for that is e to the
generating function of the class and also
the cycles.
So these are the basic operations that we
use for labeled objects.
And so, these are the ones that we're
going to use now to look at balls and urns
problems or words.
So, combinatorially, we're going to define
a word to be a sequence of M urns that
have N objects and it's the number of ways
to throw N balls into M urns.
It's a number of it's, it's a
configuration of throwing N balls into M
urns.
So, I want to know how many different
words there are then we use generating
functions.
It's parameterized by M so that'd the
number of urns in the sequence.
So, the generating function is the sum of
all possible objects that's configurations
the way the balls fall.
It's either the object size over W
factorial and then as usual, that collects
it together to get us the, a number of
ways we can get balls into M urns.
So, and again, we have all these different
ways of looking at it.
So, so this 9 balls into 5 urns and maybe
this one way it could come out that
corresponds to a sequence of 5 subsets of
9 things or it could just write out the
subset.
Those are all different ways of
representing the same combinatorial
object.
But in terms of the symbolic method, to
find out this generating function or how
many different ways there are to do this
it's simple.
It's a sequence of length M of a set of
objects.
So and it's, it's nothing more than that.
So that means immediately, the generated
function equation is e to the z to the Mth
power, or e to the Mz.
And so, our number of different
configurations is N factorial times the
coefficient of z to the N in that, which
is just M to the N.
Now, that M to the N, again, that's,
that's the same as the number of strings
from an alphabet of length N with M
characters in it.
And, and indeed, there's the 1 to 1
correspondence between words and strings.
So a string, as we talked about last time,
is a sequence of N characters drawn from
an M character alphabet.
And since for each of the N characters in
the string, there's M different
possibilities, there's M to the N
different strings.
A word is a sequence of label sets with a
total of N objects and there's M to the N
words.
So, what's the correspondence?
Well, the correspondence is, is quite
simple.
What we do is we take a look at the second
set, for example, corresponds to the
positions in the string where the second
character happens.
It's as simple as that.
There's no 3, so the third set is empty.
The 1 is in position 7 so the first set
has 7 in it.
And the 5s are at positions 5, 6, and 9.
And the 4s are position 2 and 4.
So, it's just a 1 to 1 correspondence
where the word tells us the position in
the string where the character happens.
That is for in the word, if you look at
the case set for every i in the word, the
ith character in the string is, is k or
vice-versa.
If you look at the string, if the ith
character in the string is k, then you put
i into the k set in the word.
So, the word is just the indices where the
letter appears in the string.
That's the correspondent.
So it's very familiar, we, we're, we
worked with strings before and now we're
going to be working with words and we have
this one to one correspondence so this is
just another way to look at it for binary
strings.
So looking at the 8 binary strings as
words first one says that all three
characters are zeros, and there's no ones.
And the last one says there's no zeros,
and all three characters are one and so
forth.
So what's the difference?
That there's no difference, it's only the
point of view.
Last lecture, when we were looking at
strings, we were concerned about the
sequence of characters and about the
relationships between one and the next in
the sequence, looking for patterns in the
string, and so forth.
This time we're interested in applications
where the sets of indices are important,
where it matters how many zeros there are,
how many ones there are, and so forth.
But really it's the same object.
In strings, we were using OGFs to
enumerate words we're going to use EGFs so
that's not a difference in point of view
and a difference in technique that we use
to analyze variations.
So again, here's just a, a summary for
strings, which we considered last time.
We considered them as unlabeled objects,
we used OGF to enumerate them.
A typical string is just a sequence of
characters.
So, the OGF is 1 over 1 minus Mz if
there's N characters, those M to the N of
them.
For words we consider them as labeled
objects, and used an EGF.
And we had all these different
representations.
And now, when we're doing sequence for
doing star product or re, relabel and all,
all possible ways and our number of
different words is e to the Mz but we get
the same result out.
So, we're going to be focusing on a balls
and urns kind of representation in this
lecture.
Now, that's a brief introduction to what
is a word, combinatorially.