0:50

This time we're going to talk about that same object, but we're going to look at

Â it as a word. So it's a sequence of M label sets that

Â have N objects in total. There are also M to the N words, and so

Â it's a sequence of sets. Now these are really two different ways

Â of looking at the same object. Because if you take the string and you

Â take every occurrence of the letter I as being the Ith set in the sequence.

Â So for example one in this string appears in position seven and that's the only

Â place it appears so that corresponds to the set seven Two appears in one, three,

Â and eight. So that corresponds to the set, one,

Â three, and eight. there's no three.

Â four appears in position two and four and five in positions five, six, and nine.

Â You can see a direct correspondence between strings and sequences of sets.

Â We refer the sequences of sets as words. so that's the correspondence again just

Â what I just described. so what's the difference between strings

Â and words? there's no difference, it's only the

Â point of view. last time when we talked about strings,

Â we were concerned about sequences of characters in relation to one another in

Â the sequence, like how many sequences of zeros in a row are there or is does a

Â pattern occur. for this lecture in words, we're more

Â concerned with the sets of indices and not so much in the the sequence, and

Â there's applications where that point of view it the one that, that we want to

Â push. so another way to look at the same thing

Â is the, the balls and urn model, which is classical in, in commonotoric.

Â so if we have n labeled balls and we throw them into m urns you can think of

Â when ball i, goes into urn j, that means j character in the string is the i

Â character in this string is j. Hm, so when five goes into earn one, and

Â we just write a one in the string. so this balls in, and, and we don't,

Â balls and earn sequences is simply corresponds to strings.

Â and we don't care about the the order in which the balls are in the urns, they're

Â sets of indices. Though balls and urns sequences are

Â equivalent to both strings of words and so, sometimes, we use that model, for

Â describing these objects. Its more like words in terms of its a

Â sequence of sets of objects. so how many words are there?

Â or if you throw in Bolst and Merns, how many configurations are there?

Â Well, you can tell by the language that I'm using that this is going to be very

Â simply described with the symbolic method.

Â so we'll call the combinatorial class a w sub n since we have a sequence on m urns.

Â so and then the size function is just the total number objects.

Â and so the generating function is straight forward from the definition.

Â and so we've got all those examples that I just talked about.

Â But the key thing is that the combinatorial construction says that a

Â word on M letters is a sequence of M urns the sequence of sets.

Â and so the generating function, the, the set of objects is e to the z, sequence of

Â size M is that to the nth power. So the generating function is e to the m

Â z. Coefficient of z to the n in that in

Â times n factorial is m to the n. So that's the basic construction and

Â counting, for words. and again using the standard paradigm, we

Â can build of this same construction. to study variations, and there's many and

Â important applications of variations. but again, just to summarize, a string

Â is, we think of as unlabeled objects that are just a sequence.

Â we use OGF and our enumeration is, it's a sequence of M different unlabeled

Â objects. So the generating functions, 1 over 1

Â minus e and the end, that's what we talked about last time.

Â And we use that to study algorithms like string searching algorithms where as a

Â word is labeled objects, it's exponential-generating functions.

Â It's sets of objects, but you can also write it as a string the generating, the

Â construction is a sequence of sets of objects, size M.

Â and we get the same count, and we use that to study hashing algorithms, and

Â more generally, occupancy problems in combinatorics.

Â but we can do variations. again, just as for permutations, to get

Â results for problems and applications problems using the, the same symbolic

Â method that we use for the basic problem. And these are two very famous variations,

Â and again, if you want to see many more details about these, go to part one of

Â the course. So a birthday sequence is a word where no

Â letter appears twice. we throw the balls in the urns and we

Â never get two balls in an urn. a coupon collector sequence is a word

Â where every letter appears at least once. so birthday sequence is about if you have

Â a room with n people in it. And you want, and there's 365 different

Â birthdays. what's the chance that no two people have

Â the same birthday? coupon collector sequence is how many

Â things do you have to see before you get everything in the collection?

Â And there's many, many applications of both of these.

Â And they're classic in commonotorics. So let's look at a simple modification of

Â that basic construction to study the problem of how many birthday sequences

Â are there. so that's our words where no set has more

Â than one element and, and again, it's easy to define the class and, and the

Â generating functions, and the construction is simply a birthday

Â sequence with alpha to M letters, is a sequence, of length M, of either empty

Â urns or urns with one ball in them. So that means the EGF of birthday

Â sequences, is just one plus Z to the N. And a counting sequence is, coefficient

Â of N factorial. And N factorial times coefficient is Z to

Â the N in that, which is m times m plus, minus 1 and so forth.

Â And then if you want to get the probability that a random words of

Â birthday sequence, you divide by that m to the n and so forth.

Â So that's again, just a simple example of modifying the basic construction to be

Â able to quickly get a generating function for such sequences.

Â Or, a, the other, another example is coupon collectors, at the other end of

Â the spectrum. So, that's a string that uses all the

Â letters in the alphabet. So, it's a sequence of sets.

Â None of them are empty, so by now you can practically write down this construction

Â yourself. A birthday sequence is a sequence of

Â length and of set, that are all of 5 bigger than 0.

Â The transfer theorem immediately gives a generating function equation, so a set of

Â size, greater than zero, is E to the Z minus one.

Â Subtract off the first term the set of zero and then sequence of m of those is

Â either the z minus 1 to the n. So that's a generating function that

Â describes the the, for the coupon collector sequences, exponential

Â generating function. and so here's some other related

Â combinatorial classes. so another name for coupon collector

Â sequence is an m surject, surjection. That's an m word with no empty set.

Â if we take off the constraint on m and you just say it's a word that's an m

Â sur-, surjection for some m So that is, there's some value of N that

Â uh,[COUGH] it's a sequence of sets, none of which are empty, for some size of the

Â sequence. So these are examples of surjections.

Â so how many sur, surjections are there of length N?

Â So this one's all 1s. This one's all 1s and 2s.

Â and then the rest of them are 1s, 2s, and 3s.

Â but from analytic combinatorics, it's easy to write down the construction for

Â this. for M-surjections, we had sequence of

Â length M and we got that generating function.

Â For surjections in general we take out the constraint on m so that means a seq-

Â the set greater than 0 is e to z minus 1. Sequence of those is 1 over 1 minus that.

Â So it's 1 over 2 minus e to the z. That's the generating function for

Â surjections. Now to extract an estimate for the

Â coefficient of z to the M and N. Again it's best done with complex

Â asymptotics that we'll talk about in the second part of this course.

Â Turns out to be about N factorial over 2 log 2 of the n plus 1.

Â Again, a very simple modification to the basic construction but it leads us to a

Â generating function equation that we can later analyze.

Â And by the way, the analysis at the other end is going to have come from similar

Â general transfer theorems. so, this is the, types of variations that

Â we, see on words. So, we start with the basic construction,

Â and, so maybe we generalize it to talk about coupon collectors, where we insist

Â that all the letter counts are bigger than a certain amount.

Â or my birthday where there, all the letter counts are less than a certain

Â amount. and these things are relevant in the

Â analysis of of computer algorithms and many other applications.

Â or you can do the constraint really in any way that, you know, you want the

Â occupancies to all be odd or all be even or prime numbers, whatever you want.

Â leads to a generating function equation. and then we talked about surjections,

Â though again starting with a basic thing we get a galaxy of related constructions,

Â that the constructions are quite simple and they lead to generating functions of

Â all different character. and that's a introduction to the analytic

Â commonatorics of words and strings, and how to use the symbolic method to get

Â exponential generating functions for a variety of commonatorial classes.

Â