Which you have learned in discrete
mathematics.

A number of these formulas that will
result, you will have, in theory,

have gone through in discrete mathematics.

But anyway, so I have it here all
contained for what we need.

I have it all contained here in this set
of notes.

There's a second
tab, which I'll explain to

you after in, I think,
structure number three.

Anyway, the very first structure,
which we've already discussed,

that structure is subsets of a set.

You have a set of items.

Now, generally, it's unordered in that you
can't put positions, relate, associate

positions where they're stored,
as it were, to the elements of the set.

Of course, in computer science,
that's exactly what we do.

Because everything, by
definition, anything stored

in computer memory is
associated with an address.

And those addresses are sequentially
numbered.

So that's why we call it RAM, random
access memory, that we could address them.

Anyway, whatever.

And we can access them based on their
position.

So let's consider a set of elements,
E0 through EN minus 1.

Again, because in computer
science, the indices are 0

to N minus 1 for an array
or a set that has N elements.

OK?

N is the cardinality of the set,
and that's the vertical bars on line 8.

That's a standard notation in discrete
mathematics and set theory.

All right.

So now, how could we encode what... we may
have talked about this before,

but this is just to get us a running
start.

We discussed this when we discussed
diagonalization, Cantor's diagonalization

arguments, to show that the
power set of the natural numbers

is... or the power set of the
natural numbers is not countable.

Anyway, so again, you have this bit
vector.

You have the indices
0 through N minus 1

representing the elements
E0 through EN minus 1.

And then you'll have a 1 in the
corresponding position on line 11 to

indicate that there is an element in the
set.

And then there will be a 0 if it's not in
the set.

So in the subset of these elements E0
through EN minus 1, the drawing,

the diagram indicates that E0 is there,
E1 is there, and EN minus 1 is there.

OK?

So that is indicated on line 14.

In other words, those elements.

Good.

Now, how do we count the set?

And so as we mentioned last time,
we count the set by asking ourselves,

well, how many such bit strings of 0s,
1s are there?

But we could readily note that ignoring
how we got them into the set, ignoring how

we got them into the set, they now look
like a binary number.

In other words, consider the binary digits
1, 1, 0, 0, 0, 1, right?

So you can... that is a
binary number, and there are

algorithms to convert that
back into a natural number, right?

So then the question
is, how many natural

numbers are there
that can fill up n digits?

And those are the numbers from all 0s to
all 1s.

And all n 1s is 2 to the n minus 1,
and all 0s is 0.

So... and it's every number in between,
because it's all 0s and... every possible

combination, a listing sequence of 0s and
1s would fit into that array.

So it's all numbers from 0 to n minus 1.

So that... therefore, in total,
there are 2 to the n such subsets.

And this is... we call all such subsets
the power set.

So therefore, the power set of a set is 2
to the power of n.

So on line 5, in summary, in J5,
for structure 1, the subsets of a set,

how many are there?

There are 2 to the n, right?

So that we... that we know before.

That we've done that before.

Just so... maybe up in the notes,
I'll emphasize that.

So 1, 1, 0, 0, 0, 1, and then it's base 2.

And in general, of course, we have 0s.

In other words, whatever
number of... if you

have all 0s, and then
you have possibly all 1s.

I'll fill this in a little later,
just to make it a little...

easier to relate to.

The question... I just want to show you,
of course.

So while this we know, this is equal to 2
to the power of n minus 1.

The sub 2 means base 2.

All right?

And then here, that, of course,
is equal to 0.

We should put it here, just a little
closer.

And that's that.

And this would be equal to 1, 2,
4, 8, 16, 32.

I think it would be
49, for example.

Well, that's if there were no dot,
dot, dots.

If the word dot, dot, dots is equal to
whatever it's equal to.

Anyway, so you have these base 2s.

Fine.

All right, so that's the subset.

Now, moving on to our second structure,
different structure.

That we already discussed in the previous
note, lecture note.

Structure number 2 will be relations.

Relationships.

Relationships or relations.

Also known as relationships.

All right, relations.

Actually, you could either way.

Relationships or relations.

From a set S1 to a set S2.

So, let's imagine set S1 has elements A1
through AM.

And set S2 has elements B1 through BN.

And we're mapping, which
means that we're telling the

elements of A1 where they
are allowed to go to in the Bs.

We tell the A's, where are you allowed,
where do you have access to?

Where are you allowed to go to in the Bs?

In the case of a relationship,
anything goes.

Which means that a single A could go to
one B.

A single A could go to
more... It has the option to...

You could set it up so that it could go to
more than one B.

A single A could go to no Bs.

So, it has all possibilities.

A little note I have here
on the right in column F,

which is that eventually
this will become a graph.

Because, in essence, a graph is a
graphical representation of a relation.

And if you think about
it, the only difference is

the default in terms of
how we present the graphs.

Normally, when we draw
graphs, we think the graph

as being a relation of the
elements to themselves.

Because the vertices is... you only have
one set.

We'll mention this in a second because
this is one of our structures.

But the point is, normally, in a graph,
you're mapping the set of nodes,

the set of vertices, which in essence is
the set of elements, to itself.

Whereas here, we're mapping one set to
another set.

The only thing is, the other set could be
the same set.

So, it's really the same thing.

And, in addition, graphs can be
considered...

You can consider a graph when you're
mapping a set to a different set.

That happens to be called bipartite,
which I have here on line 32.

So, the fact is that graphs and relations
really are the same thing.

The only difference is the convention of
where you start.

In the case of relationships, you start
with going from one set to another set.

In the case of a graph, you start from one
set going to the same set.

In the case of graph, you could have one
set going to a different set.

That's called bipartite.

And in the case of a relation, you can
have that the B's are identical to the A's.

So it's just a question of convention.

But the truth is that a
graph, as they say on line 27,

a graph is a graphical
representation of a relation.

Anyway, we'll play on
that in a second when we

count the number of
graphs, which is very useful.

So how many are there?

So the point is that what is the maximum
possible relation?

In other words, what is the relation?

It's a single relation that has lots of
pieces to it.

What's the relation that where every A
goes to every possible B, right?

Any single A goes to every B, because
that's the most.

You can't have A going to somebody not on
the S2 list, right?

And you can't talk about someone not in
the S1 list.

So it has to be that the A's go to the
B's, and the most it could go to is N B's.

A given A sub I can
only go to, at most, all

the N's, all the B's,
which is N B's, right?

So that graphical
relationship can be described

mathematically as
the Cartesian product.

The Cartesian product is exactly that
relationship where every A is related to

every B, goes to every B, every
possibility.

Maybe I should add here one more.

Because I'd like to also give you,
besides specific numbers, 1 and M and N,

I'd also like to emphasize that it's the
generic case as well.

The general case.

So A, I, B, J, all the way up to A,
M, B, N.

Ah, yeah.

One little note about the drawing,
which is the following.

A note about the drawing.

Where should I put it?

It's not about graphs, per se.

A note about the drawing.

Note.

A note.

A note.

A note.

For diagramming purposes.

I think I said elsewhere,
but I want to say this

right away, because I don't
give the wrong impression.

For diagramming purposes, the two sets
appear of the same length, meaning size,

but mathematically that's not the case.

Mathematically, of course, they are of any
size.

This is indicated by the fact that the
cardinality of S1 equals M, Mary,

the variable M as in Mary, and S2 is equal
to N, Nancy.

The variable that begins as in the first
letter in Nancy.

So M and N.

And the fact is that M does not have to
equal to M.

They could, but they don't have to.

With possibly M not equal to N.

In fact, most probably with.

It doesn't have to be, but statistically,
they're not.

So in general, usually they're not the
same.

Anyway, I just want to point that out.

Okay, now.

So how many are there?

So we just said the Cartesian product is
the maximum possible single relation.

It's one relation.

It has many pieces to it.

Because it has an edge from A1 to B1.

It has an edge relation from
A1 to B... It has a connection.

A connection from A1 to B1, A1 to B2,
A1 to BI, BJ, A1 to BN, AM to B1,

B2, BJ, BN, right?

So in fact, the cardinality of the
Cartesian product on line 39...

So the cardinality of S1
Cartesian product S2 equals the

cardinality of S1 times the
cardinality of S2, which is M times N.

Now, an arbitrary relation from S1 to S2
will not have every connection.

It will have some of the connections.

So it will be a subset of S1 Cartesian
product S2, okay?

It's a subset.

Because the Cartesian product has every
possible connection.

A random relation, arbitrary
relation on these sets

from S1 to S2 will have
some of those connections.

So some is a subset of all, right?

It will be a subset of S1, S2.

S1, S2, maybe I'll just put a little extra
description.

One sec.

Has all possible connections from S1 to
S2.

And a random subset, arbitrary subset,
has some possible connections.

Some of the possible connections.

One sec.

One sec.

One sec.

Something got deleted by accident.

Here we go.

And some is a subset of all.

Therefore, an arbitrary relation is a
subset of... an arbitrary relation is a

subset of the Cartesian product,
S1 times S2.

Since R is one subset,
then all relations are

all subsets, and that is
known as the power set.

So the power set of S1
times S2 is the set of all

relations based on structure
number one that we just did.

All subsets is 2 to the power of n,
where n is the number of elements.

Here, the number of elements isn't n,
it's m times n.

So therefore, the power set of the
Cartesian product, S1 times S2,

is 2 to the power of the cardinality of S1
times S2.

And that's therefore equal to 2 to the
power of m times n.

Okay?

So that is the case.

So that is what we wrote on line 24 in
summary, that the number of relation or

relationships from set S1 to set S2 is 2
to the power of m times n.

Good.

Good.

Just a little note about graphs,
which is what I'm leaning into on line 46.

In sets, the relation with the most number
of connections to Cartesian product,

and in its corresponding graph, the graph
with all possible edges is called complete.

Complete.

The notation would be...

Now, so again, we use two sets.

Right?

We're using two sets.

So if your graph has two sets,
then the notation is... Okay.

So let me write this way.

Complete.

Noted by the letter K for complete.

I know that sounds funny, but that's
actually what they did.

Now, whether they meant it as a joke or
they didn't want you to get confused,

complete is spelled with a C.

Now, it could be that in
other languages, maybe

in German, the C is very
often replaced by a K.

I don't know if that's where it came from.

It could be they just wanted...

They just wanted you not to get... But
not to get confused with other usages of C.

Notice the first letter should have been
C, not K.

But the fact is that the notation is with
a K.

In discrete mathematics and in graph
theory, they use a K.

All right?

Anyway, so KMN if it's two sets and K
sub-N if it's over one set.

So when we say a complete graph,
we're really meaning the Cartesian product.

Okay.

A little note here.

A little note here about graphs.

Anyway, from discrete math.

Okay.

Leading into structure number three.

Structure number three is directed graphs.

And that dovetails relations
because as we just said on line 27,

a graph actually is a graphical
representation of a relation.

All right.

Directed graphs over a set S.

Now, the default is that there's only one
set that you're over.

The relationship is only over one set.

That set is V.

A graph G is V, the set of vertices,
and E, the set of edges.

So a little note here.

V is the set of vertices.

Also known as... AKA means
also known as the set of nodes.

And E is the set of edges.

And that is also known as arcs.

Historically, node and arc was slightly
different than vertex and edge.

Today, it's all the same.

All right.

So let's assume that... Let
me open that here, actually.

Okay.

Also known as... N... Let's
assume N just with no particular N.

Let's assume N is the set of vertices,
the size.

So then what is E?

E is a subset of V times V.

Right?

And that...

And that dovetails exactly
what we said above on line 43,

that R, its cousin, the
relation, is the set of S1 and S2.

So here, you know, cross-reference line 43
above.

Right?

And as we said, here, S1 equals S2 equals
V.

Okay.

You could have had that above also.

Right?

So that's why E is a subset.

E, we called it R above.

Now we call it E.

E is a subset of V times V, just like R is
a subset of S1 times S2.

Okay?

All right.

Fine.

As I mentioned above, as we just said.

Now... Okay.

So this is the part I mentioned a second
ago.

I'll just... I mentioned it.

I have it in the notes here.

That the issue of S1SV is an issue of
convention.

Because, in other words, the fact is...

Give me one second.

Okay, fine.

Now I just wanted to
edit the notes so that

you realize we just
said that a second ago.

And I want to know where to cut it.

Here.

Okay, so as I just said a second ago,
the convention with graphs is over one,

the same set, whereas the... That's
what I wrote on the paragraph on line 57.

Whereas the convention in relations,
the default on graphs is one set,

which means the same set, the
relationships over the same set.

Whereas the default in relations is two
sets.

Okay, fine.

But you could set the two to be the same.

All right.

Therefore, line 63.

Therefore, we can use structure number two
that we just said.

Structure number two being relations.

And there are two to the power of MN.

To count the number of directed graphs
over V.

Where N equals the size of V.

Because now M equals N and S1 equals S2.

Right?

Then the number of directed graphs over a
single set V.

Capital V in our notation.

Is the power set of S1 times S2 equals two
to the power of MN.

But S1 equals S2 equals the size of V.

Is V.

So it's really the power set of V times V.

Which is... So it's equal
to two to the power.

Because E on line 54.

E is a subset of V times V.

So it's two to the power of the Cartesian
product of V with V.

And here M and N equals the same.

So it's two to the power of M squared.

That's it.

So relation is two to the power of MN.

Because this S1 and S2 could be arbitrary
size sets.

And M and N don't have to be the same.

In the case of the relationship called
directed graphs, that's the same.

So M equals N.

So it's two to the power of N squared.

Alright?

So now just consider a relatively small
vertex set with just ten nodes and vertices.

The number of different directed graphs
over the set V.

It only has ten elements.

It's two to the power of N squared or two
to the power of ten to the power of two.

Which is two to the one power.

One hundred.

Two to the power of one hundred.

Wow.

That's large.

I believe this is larger
than the scientific

claim number of
molecules in the universe.

It is.

Anyway, so that's unbelievably large.

And we're even dealing with just a small
number of elements, right?

We're only dealing with ten.

I gave an example here.

Ten elements.

Ten numbers.

And the number of different graphs is two
to the power of one hundred.

Of directed graphs.

All right.

Maybe I'll add...

I really should add a structure here.

Which is...

I will leave for homework.

Maybe not.

Maybe I'll give you the answer.

I'll think about that.

But anyway, I will leave for homework to
calculate the number of undirected graphs.

All right.

Anyway.

So we... Because we
did directed graphs.

What about undirected graphs?

Fine.

Let's continue on.

Partial mapping.

Now this is a very interesting one.

For reasons that I have a second tab.

And I mentioned this to you earlier when
we discussed this.

Maybe it was last class.

About the very interesting consideration.

Is a partial computation considered more
aligned with deterministic?

Or is it more aligned with the
non-deterministic?

So this is in the previous class notes.

And I mentioned...

I mentioned there that if you take the
mathematical model of mappings,

one could argue that a
partial mapping should

be aligned with
non-deterministic computation.

But if you deal with the realistic
assumption, not like the theory

assumption, but if you deal with the
realistic assumption that your actual,

you know, physical computer, when given a
partial map will cause an error or crash.

The point is that that's a predictable
response.

So that dividing by zero will always give
you error.

Error.

Error.

Error on the calculator.

Or in your code.

Right?

It always will.

So that fact that's predictable and it
will only be one response, that particular

error, So then you could argue that that's
deterministic.

So it has a little bit of both.

So some people say it's... pardon the pun.

It's partially deterministic.

Anyway, that's what we mentioned in the
last notes.

So the question is, how many partial maps
are there?

So again, it's the same sort of... it's a
relation, it's a mapping.

But here the a sub i, first of all,
so there's an inherent restriction,

which is that it could go to at most one
element...

at most one element of the second set.

So a1 could go to b1.

It could go to b2, but then it can't go to
b1.

So... but it has an extra independent
decision that it may not go at all.

And that's where the issue is about being
partial.

what we call undefined.

Okay?

So that's what I say here on lines 83
through 85.

In a partial mapping,
each element a sub i has

independently n possible
choices to choose from.

Right?

Each of the b sub j.

b1, you know, through...
each of the a sub i has up

to b sub j elements to go
through... or n elements.

It could go to any of those, but it could
only go to at most one.

Okay?

But in addition, each element has the
right not to go at all.

And that's why we call partial or
undefined.

Okay?

And we can only make one of these choices
for each element a sub i.

Let's draw this.

So let's... let's lay out the elements.

Lay out the elements a1 through a m.

So the... the boxes here are just for
drawing purposes.

They're... they're holders.

They're seats.

Okay.

So a1 could go to... how many... how many
choices does a1 have?

So a1 could go to b1, b2, bj, bn.

That's n choices provided to you by set b.

But in addition, it could also go to one
more choice, n plus 1.

What is that choice?

It decides not to go at all.

So a1 makes... has n plus 1 choices.

And if it goes... which b does go to plus
1, it decides not to go at all.

A2 is independent.

That's why I write on line 83 that each
element does this choice independently.

A2 has an independent choice.

It also could go to any
of the elements of the

b's, but it also could
decide not to go at all.

Right?

A2.

Same... same with a1, a sub i,
or a m.

All these elements,
each of them... each of the

a's independently
could go to any of the b's.

Two a's could go to 1b.

That's okay.

But... but 1a can't go to 2b's,
but 2a's could go to 1b.

But they... each of the a's may decide to
not go at all.

So that's n plus 1, n plus 1, n plus 1.

Since in basic probability
theory and basic analysis of

algorithms, independent
choices are multiplied together.

Independent choices are multiplied
together.

So that's what you learned in discrete
math.

So therefore it's n plus 1 times n plus 1
times, times, times, times, n plus 1.

And there are m such elements.

So m elements have to make choices.

So it's n nancy plus 1 to the power m.

And that's what I have here on line 74 in
summary.

All right.

Now, something I mentioned in a previous
class.

So just would like to go quickly through
with you.

I'll show it to you.

As mentioned in a previous class,
the face plate of a scientific calculator

has a number of button combinations that
yield partial functions.

So you should... the reason I said that,
and I'm saying it now, is that you,

in fact, when you take calculus and you
take other courses dealing with partial

functions, you walk away thinking that
something's wrong with a partial function,

right?

Slightly broken.

The fact is, it's a way of... it's a part
of daily life.

The point is that the calculator,
scientific calculator, has 10... 10...

I'm up to 10 different key combinations
that are, in fact, partial functions.

So here I give you... that was... I was
hoping you would do that for homework.

I give you the answer here in the second
tab, which I'll email you.

1 divided by x cannot be divided by 0.

Square root cannot have a minus 1.

Logarithm and ln, although
it's similar purpose, one's

base... well, base 2 or
base 10 or whatever base.

The other is base e.

So log is typically, traditionally,
a natural number base.

It doesn't have to be, but it was
typically a natural number...

Well, okay, let's ignore that.

The point is ln is base e.

Just to remind you, it's a real number
base.

It doesn't have to be, but typically...

No, it's the calculators will... I believe
will do real number base, but typically,

a natural number base.

All right, fine.

Okay, let's just say it again.

Typically, a natural number base.

All right, fine.

Anyway, you could test
it whether your computer

allows for real number
bases when using log.

Anyway, whatever it is.

Division.

I couldn't get the... I couldn't find an
icon that has the other dot below.

Anyway, this is division.

Division.

Well...

Let's assume it's division.

You know what?

I was trying to give you what it looks
like on the...

Let's do another way of writing division.

Anyway.

Okay, I wasn't sure which icon you're used
to.

Anyway, what we mean here is division.

All right.

X to the power of Y.

Now, this is a very interesting one.

A number of calculators will actually give
you values for all values of X and Y.

This is technically wrong.

This is a fascinating little point.

X to the power of Y is actually a partial
function, believe it or not.

The reason is that what do you do when X
equals Y equals zero?

So there are computers in Excel,
but I don't know if all calculators have

this built in, where they will define zero
to the power of zero to be equal to one.

But this is not true.

So the issue, and I have it below in line
15, the issue is the following.

There are two... there are two... there
are two... what you call it?

There are two rules,
heuristics or rules, that

contradict each other
when dealing with...

Okay, maybe I'll read it back here.

When dealing with zero to the power of
zero.

The first rule, line 16, zero raised to
any power equals zero.

But then you know
another rule on line 17,

any number raised to
power of zero equals one.

So what do you do with zero to the power
of zero?

You now have a clash of these two rules.

And this is considered
such a big contradiction,

mathematicians
give it a special name.

It's called indeterminate.

Impossible to know.

Meaning there's an error, there's a
contradiction.

Now computer theory needed to define zero
to the power of zero as equal to one in

order for certain mathematical recursions
to work.

So Martin Davis, the
modern founder of computer

theory, chose rule number
two over rule number one.

Meaning in rule number two here,
any number raised to the power of zero,

even if the base is zero, so zero to the
power of zero is one.

So that's a convention that's equal to
one.

The fact is it's a partial function.

Then you have your, you have g, h, and
i, the different trigonometric functions.

So that are, those don't, those are also
partial functions.

And then finally factorial, because
technically not defined by negative values.

All right.

Anyway, so you could go through and test
it yourself.

And that's a total of 10 different
combinations on your calculator faceplate,

where in fact, it's not, it's not,
it's not, what you call it?

It's not, it's not considered,
it's, it's, it's a partial function.

Okay, fine.

All right.

So that's what I wanted to mention
regarding that.

All right, next in our math structures.

So we did partial.

So for m, from set one
equal to m, Mary, and set two

equal to n, size equal to n,
Nancy, n plus one to the m.

What about if you're total?

So if you're total, it's the same story as
you see on line 114, the same layout,

same story.

But here, the independent choices are not
n plus one, but n.

Each one has to make exactly one choice.

Now, exactly one choice.

Oh, I say that.

Okay.

But please note, this is a, something that
students sometimes get confused with.

They forget.

Please note that they all, that, that
all a sub i can go to the same b sub j.

Okay.

The, the exactly one is a quantitative
issue, not a qualitative issue.

Exactly one is not the same as uniquely
one.

Next structure.

Uh, so the next structure or two
structures?

Next structure.

All right.

So please remind ourselves, exactly one is
not the same.

Exactly one is a quantitative issue.

It's purely a quantitative issue.

How many can it go to?

It can only go to one choice.

But which choice?

But which choice?

That's up to you.

Quantitatively.

Quantitatively.

It's purely a quantitative issue.

Uniquely one is also qualitative.

Okay?

All right.

Okay.

I'll leave it like this.

All right.

So now, so again, A1.

Who can A1 go to?

It can go to B1, B2, B sub j, B sub j,
B sub n.

It can go to any of these.

So they're n choices.

Now, whoever A1 goes to, A2 independently
also has the same choices.

It could go to the same place.

Everybody could go to a, uh, to the same
number.

In fact, there's a term, if they all do,
uh, just as a terminology.

Okay?

So there's a name.

So for example,

uh, f of x equals five.

Everybody goes to five.

That's a total function.

And that's sometimes called, oh,
it's called a constant function.

Sorry.

Uh, it's called a fixed point of a
constant function.

Whatever.

Uh, it's called a constant function.

For example, f of x equals five.

All right.

Anyway, so A1 has n choices.

A2 has n choices because A2 is
independent.

A sub i has n choices.

A sub n has n choices.

And again, uh, in, in, uh,
as we said before, uh, the

choices, independent
choices are multiplied together.

Uh, so the number of total mappings from a
set, uh, uh, S1 of size M, Mary,

to a set S2 of size N, Nancy, equals N to
the power of M.

And that's what we have here on line 101,
as opposed to the partial functions,

which is N plus one to the M, the extra
choice being not going at all.

All right.

Now comes the uniqueness.

So the fancy name is injective mappings.

Uh, the fact is it's also known as a
permutation.

I should mention that here.

Permutation, permute.

All right.

So injective mappings, and I'll put in
parentheses, uh, also known as permutations.

So believe it or not, cause I know you're
taught that they're different.

If you look in the early 19th,
in math books from the early 1900s,

they say this openly, injective mapping,
which is a fancy name for permutations.

Anyway, here it goes.

You can all that fact, but we're going to
mention it.

We're going to mention it a little but
later, but here it goes.

Injective mappings.

First of all, are total.

Um, based on the pigeonhole principal.

And if you don't know
what that is looking,

up, you're supposed to
know from discrete math.

Based on the pigeonhole
principle of the uniqueness

property of one to one
also known as one to one.

Injective mappings are also known as one
to one functions.

So the uniqueness property that every
element must go to a different element

requires that m is less than or equal to
n.

It must be the case.

All right, fine.

All right, in a one-to-one
mapping, each element a sub

i has to uniquely choose
one of the remaining b sub j.

So the analogy I usually give is the
following.

Imagine a caterer... a waiter comes by at
a party.

And the caterer put a hundred different
little cakes, right?

A little different shaped cakes.

Each one different, so it looks really
fancy.

A hundred different shaped cakes.

Now, whoever the waiter quote-unquote
bumps into first has a hundred choices of

different small little cakes to choose
from.

Right?

And the person takes one.

Now, the second person doesn't have a
hundred choices anymore.

The second person has 99 choices.

The third person has 98, 97...

So because of uniqueness, there were a
hundred different shaped cakes.

So the one that each person takes is no
longer available to the next person,

the next people.

So that's the issue here.

So A1 is the... let's say without loss of
generality, let A1 make the first choice.

It's irrelevant who makes the first
choice.

Somebody has to make the first choice.

We'll call it A1.

Anyway, A1 makes the first choice.

And how many choices are there?

Well, A1 could go to any of the Bs.

So that's N choices.

But that means that one choice is gone
because of the uniqueness.

No two A's are allowed to go choose the
same B.

So A2 has N minus 1.

AI has N minus I plus 1.

And finally, if you follow through,
A sub M has N minus M plus 1 choices.

But given the fact that the
number of choices are different,

the actual ability to make
the choices are independent.

A1 makes its choice independent...

A2 makes its choice of the N minus 1
independent of who A1 goes to.

So the fact is you, once again,
multiply them together.

And that means the following.

Yeah.

So therefore...

One second.

Therefore, the number of
total mappings would be N

times N minus 1 times
times times N minus N plus 1.

Now, this formula on 139 actually is true.

Please understand that.

We could have stopped right here.

The only thing is, it's not so easy to
read or analyze algebraically.

What exactly is that?

So mathematicians noticed that this is
sort of like a broken factorial function,

right?

N times N minus 10 minus 9 times 8,
7, 6.

It's missing 5, 4, 3, 2, 1.

Okay?

So what they do is they play this trick.

Well, let's multiply this by N minus M
factorial divided by N minus M factorial.

Now, mathematically,
that's like multiplying by 1,

so we haven't changed
the original formula, right?

But that is the missing piece.

So the numerator now is complete,
and the numerator becomes N factorial,

and then we take along this denominator,
which is N minus M factorial.

So that's the formula here on lines 142,
143, highlighted here in column I.

That's the formula that you will find in
discrete mathematics.

You won't find the formula on line 139,
but it is correct.

It just doesn't... it's not as neatly
packaged.

Also a little hard to analyze.

Anyway, so that's the formula we use.

N factorial divided by N minus M
factorial.

Okay.

Now, the point that
I said above here on

line 122, this is also
known as permutations.

So as I say here, this is also a number of
ways to permute a subset of a set.

Okay.

So just to remind you a
little difference that we need

to discuss, because I
could have put this separate.

I could have said this structure is set...
put the structure separate.

When I send you the notes, I'll decide.

Anyway, this is a
cousin, but the fact is that

there's a cousin to
permutations called combinations.

And a combination is a permutation sort
of... well, it's sort of similar.

The point is, in order to permute a
subset, you have to first choose.

In other words, let's imagine it's the
letters A through P. Okay.

That was the original set.

And I asked you to permute five of them.

And you choose A, B, C, D, E.

Okay.

So again, you're permuting... where am I
right at?

You're permuting a subset.

Here we go.

This is also the number of ways to permute
a subset of a set.

Okay.

To permute a subset of a set.

All right.

So now... But permuting
requires choosing first.

First, you got it... so here.

A one-to-one mapping could be considered a
two-step process.

First, you select, or what they call
choose, M of the N elements in S2.

Okay.

In other words, you're permuting elements
from S2.

You choose them via the access points in
A.

So A's purpose is not to count.

A's purpose is to choose which of the B
we're going to permute.

So first, you choose M of the N elements
in set S2.

Which in mathematics is the combination
choose NM.

And then, for each of these, you then...

You then, what you're called?

Each of these, you then...

You then, what?

You then permute.

You permute the M elements you just chose.

The M elements of the B's you just chose.

So in summary, what we have is that permuting
is the number of combinations times.

Because we also do that.

And we do that.

And is multiplied.

When you and in logic, it's in
probability.

And is multiplied.

So you'll have here the original choose.

But now we multiply that by M factorial.

And that's where we get this formula.

N factorial divided by N minus M
factorial.

Now the question is, what is this number?

So factorial...

Just to remind you of something we will
discuss in a different class to prove it.

Because there's an interesting comment
here.

In the proof, there's an interesting point
that arises.

But we're going to prove that N factorial,
in fact, is greater or equal to 2 to the N.

So it's yet another exponential formula.

In fact, it's bigger than that.

Right?

Yeah.

Okay.

Fine.

What did I just do?

Something went wrong.

Give me one second.

Okay.

All right.

So that's how many injected
mappings, which is cousin

to permutation, which is
a cousin to combination.

All right.

Right.

Now, the next structure is called the
subjective mapping.

You also know it as the onto function.

Let me just get a drop of water.

One second.

Okay.

Thank you.

All right.

Now, admittedly, the onto function in and
of itself may not so readily appear in our

discussions, but the fact is that it's the
fundamental component of something that we

are all going to discuss a lot,
which is the notion of a partition.

So we'll see how that's connected to each
other in a moment.

The formula is not a straightforward
formula.

All of the above were straightforward
formulas.

And the way we counted them are similar.

The onto, though, cannot
be counted, no one knows

how to count it in a similar
straightforward fashion.

It's a rather involved proof, which I
summarize here.

First of all, our original principle,
what's the definition of onto?

Onto says that every element of the second
set is reached,

is connected to.

You reached it from A.

You have to make sure that
someone goes to B1, someone

goes to B2, someone
goes to Bn, but it's also total.

So every A has got to go.

Now, the fact is in
order to reach it, it must

be the case that you
have as many As as Bs.

M has got to be greater or equal to N.

If M were less, the only
way that every B would

be reached is if an A
goes to more than one B.

But the fact is, it's total.

So no A sub I can go to more than one B
sub J.

But they're all reached.

So therefore, M is greater or equal to N.

Anyway, fine.

Okay.

As I said a second ago, no one knows how
to directly calculate this.

So they just don't.

So they do it not by calculating what is
onto, they calculate what is not onto.

So total equals onto plus non-onto,
right?

And we know from a structure five above
that total is N to the power of M.

So now we're going to
have to subtract from the

number of total functions,
the non-onto functions.

All right.

Okay, how do you do that?

So I'll give you a little taste of what
it's about.

And that has to do with something called
the inclusion-exclusion principle,

which you should have learnt in discrete
mathematics.

I'll give you a simple example here.

And then I'll just quickly go through that
proof with you so you can get the formula.

Once we write the formula,
what it says could be

readily interpreted, but
it's not a simple formula.

Anyway, here we go.

So let's imagine the following story,
just to give you a simple scenario where

the inclusion-exclusion principle will
apply.

So let's imagine the following.

The math major society,
the students who are math

majors, connect with the
computer science major society.

The students who are currently computer
science majors.

And they decide to have an end of semester
party.

Okay, they're going to have a pizza party
at the end of the semester.

Beautiful.

The rule is that no teachers, no one else
is invited.

Only the students.

So then all the math majors and all the
computer science majors get together at

this wonderful party at the end of the
semester.

Great.

Now, let's imagine there are 50 math majors
and there are 50 computer science majors.

And everybody attends.

Everybody attends this amazing party.

And the question is, oh, it's an amazing
party.

They're going to prove theorems and
they're going to do coding together.

I don't know.

Just imagine what geeky parties
may... No, it doesn't have to be.

I'm sure math majors and computer science
majors are fun-loving people too.

So I'm sure it's a nice party.

Anyway, irrelevant about the... whatever,
not important.

So 50 math majors, 50 computer science
majors, and everybody attends.

So if you approach this quickly and I ask
you how many people were at the party,

you weren't there, but you were doing a
calculation, right?

You're a reporter for the Queens College
newspaper.

And you want to say, wow, that amazing
party.

Everybody attended.

How many people attended?

So you know there are 50 math, 50
computer science, 50 plus 50 equals 100.

But that's not exactly true or not
necessarily true.

The reason is because
one student can be both

a math major and a
computer science major.

There's nothing in the rule books that say
you can't.

Right?

And so, in fact, it used to be,
I once attended a graduation of my niece.

She went to Barnard.

Is it possible the same thing happens in
Columbia?

I don't know.

There's a whole shtick.

There's a whole game to try to get as many
majors as possible.

So you'll have math, computer science,
gym.

Math, computer science, gym, and French.

Okay.

The thing is that in their brochure where
they write the names of the graduates,

if you are a math and computer science
major, they will not list you with the

math majors, nor will they list you with
the computer science majors.

They will list you with the math-computer
science major.

And if you're math,
computer science, and gym,

they will list you with
neither of the three.

They'll list you as the math, computer
science, gym major.

And then if you are also
through French, then you are

not in the math, computer
science, gym, or French majors.

You are a math, computer science,
gym, French major.

And I think they make this game students
have amongst themselves because they

wanted to graduate to be the only student
in the class and the only major, right?

Anyway, so I actually read one.

I read one of their public... their
brochure of the day of graduation.

That's what they do.

Anyway, the inclusion-exclusion principle.

So you can't say that there are 100,
not necessarily.

Maybe there were.

But if there's duplication between the two
sets, it's a little bit less.

So the best you could say is between 50
and 100.

Anyway, the
inclusion-exclusion principle

for two sets is a plus
b minus a intersect b.

For three sets, it's a plus b plus c minus
intersect b minus a intersect c minus b

intersect c plus a intersect b intersect
c.

Anyway, this numerics, if you count the
structures that are presented on the left,

it turns out to be Pascal's triangle.

And it's not by accident, perhaps, that
Pascal's triangle also are... whatever.

It has to do with combinatorics.

There are a lot of applications to
Pascal's triangle and discrete mathematics.

I would have taught you this.

Hopefully most books have it.

You can look it up in Rosen's discrete
math book.

Anyway, we need to apply all this to count
the number of non-onto.

Because remember, we don't know how to do
onto.

So we do non-onto and then we're going to
subtract it from total.

All right.

I give a whole discussion here, if you want
to figure out how the whole story works.

You have forced agents, free will agents,
in the sense, some of the AIs must go.

In other words, N, Nancy, of the M,
Mary AIs, must.

That's what I mean, forced.

They must go to the BI, to B1 through BN.

Because you must make sure that every BI
is reached.

But there's still a number of other
elements left over if M is greater than N.

Right?

As we said here, a line... well,
now it's line 172.

M is greater or equal to N.

So, you have a lot of extra.

Where they go to at that point,
they're free agents.

They can go any B you want.

They must go because it's the total.

All right.

So, it turns out, and this comes from
discrete mathematics, so here's the formula.

It's equal, non onto, and therefore you
subtract it.

So, the total number of... and here it is.

So, the total number of...

more easily.

One second.

I'm curious if I can do it this way.

One?

That doesn't work.

Yeah, I thought so.

A little tricky.

Yeah.

I have... I may be able to... Okay,
it's not worth it.

Anyway, N to the power of M, minus the
summation of I equals 1 to N minus 1,

of minus 1 to the power of I plus 1.

Choose I from N, and then times N minus I
to the M.

That's all.

Anyway, that's the number of onto...
that's the true number of onto functions.

Every discrete math book has that.

That's a... that's a really heavy to-do
function.

But I give you the story to explain where
every piece comes from.

All right?

Okay.

Anyway, that's the story.

You can read up on it.

Why is this important?

It's important because of the related
cousin.

Partitions.

What's the definition of a partition?

And CARP has four different problems in
his CARP 21 related to partitions,

in some manner, related to partitions.

Partitions are as follows.

The rules of a partition, lines 247 to
251, as defined in discrete math.

One... So the point of a
partition is the following.

You take a set P, your partition.

So we're going to partition a set S.

And what we do is that we break it up into
smaller, non-intersecting subsets.

So let's say K subsets.

So first of all, each such S sub i,
it has to be non-empty.

Don't tell me there's a piece of the
partition and there's nothing in it.

Don't pack the elements
of my house, if you're a

mover, and tell me that
one of the boxes is empty.

All right?

There.

Each S sub i must be a subset of S.

Every box purchased, every box that I'm
going to use, that the movers must use,

or I'm going to pay the movers,
has to be used.

Oh, I'm sorry.

Hmm.

Give me one second.

That's...

Yeah, something got pushed over.

Give me one second.

One second.

It got out of order here.

Okay, here we go.

I don't know how that happened,
but anyway.

The orders are a little... we're a little
bit off, let me say.

All right.

Each S sub i is non-empty.

Every box purchased is being used.

S sub i must be a subset of S.

No extraneous elements crept in.

And also, you can't have duplicates.

If it's a true set.

But that's not because of a partition.

That's not because of a partition.

That's because of a definition of a set.

So, if S is unordered.

All right, well.

Anyway, the definition of a mathematical
definition assumes that S is unordered.

All right.

Fine.

The union of all the elements is the
original S.

Give me a second.

One second.

Right.

Which means all original elements have
been packed.

Every element must go somewhere.

And finally, no two boxes...

No two boxes have...

What?

No two boxes have the same elements.

Mutually distraught.

All right.

Now, a slight distinction here between a K
partition and a regular partition.

And I will repeat this when we do Karp's
paper, and it's actually quite important.

It's a minor point, but it's an important
minor point.

But mathematicians give this distinction.

The question is the following.

When you pack my elements, you're the
movers, and you pack my elements.

You're making a partition of my elements
by packing them into boxes.

The items I own that I want to move,
and you've got to pack.

Now, who decided that there are only K
boxes?

Did I buy... I'm the
person who's moving.

Did I buy, ahead of time, K boxes?

And I tell the movers, listen,
I have K boxes.

You've got to use them all.

But you only
can... But that's it.

I'm not going to pay you for more than K
boxes.

You only have K boxes.

Use them well.

So that's...

If I decided ahead of time, if the number
of boxes was fixed ahead of time,

each piece of the partition is actually a
subset.

Right?

The S sub i are subsets.

Together, the subsets make the partition.

If it's fixed ahead of time, someone said
you've got to use K.

Then that is called a K partition.

If no initial restriction is placed,

on the number of boxes.

Afterwards, we find out it's K.

But the movers had the right.

I said I'll pay for any number of boxes
you need.

Just don't sell me empty boxes.

But you can put in whatever you want.

I don't care.

So if that's the case, obviously it's a
trust.

Because they can put one
sock in a box and charge

me for boxes and make
a lot of money on boxes.

But anyway, assuming there's a trust here.

But if no initial
restriction is placed on the

number of boxes,
that's just called partition.

All right.

Anyway, here we go.

So there's a fascinating connection between
structure eight and structure seven.

Structure seven being onto
also known as subjective

mappings, which is this
crazy formula over here.

It takes a second to load up in lines 242.

And there's a fascinating connection
between partitions and onto.

Between K partitions and onto mappings.

So using this analogy of a box,
it comes out the following.

What's an onto mapping?

An onto mapping is such...

So let's imagine A1, A2, A3 in the example
I give on line 274.

Let's imagine A1, A2, A3, A4 go to B1.

A5, A6, and A7 go to B2.

A8, A9 go to B3.

A10 goes to B4.

Okay?

So that's one here on the left on lines
275 through 278.

That's one such partition.

One such partition.

Now try a different one.

A1 through A4 go to B4.

A5 through A7 go to B3.

A8, A9 go to B2.

And A10 go to B1.

So the groupings of the elements chosen
are the same.

But they are labeled by a different box.

Box 1 through box 4 in the first one.

But now box 4 through box 1 in the second.

So from an onto function perspective,
from a subjective mapping perspective,

these are different.

In terms of onto, these are different.

But in terms of partitions, they are the
same.

Since the order of the boxes do not
matter, only which elements are with which

elements are packed, which are packed with
which elements.

So...

Something's happened funny here.

Oh, right.

So in both of the... In our example, in
both cases, right, the left and the right,

the same elements are with the same
elements.

Right?

Just which box they're in looks different.

But not... The
elements are the same.

Anyway, mathematically,
that comes out to meaning the

difference between combination
and partition and permutation.

So the conclusion is...

Conclusion is that partition of MN is all
the onto functions divided by N factorial.

All right.

Just a little extra, a little tidbit.

The bell number is the number of
partitions for a given size.

The above, the above
is for K partitions,

so you have to sum
it up for all possible K.

Okay?

Therefore, that's the bell number.

Okay.

So that's a really...

That's important.

So that's a really, really involved
exponential formula.

Okay, you divide by N factorial.

That's an incredibly big number.

And if you want to look up the bell number
online, you'll see the growth of how many

partitions there are, even for
small... for sets of a small size.

All right?

We can look it up later.

Anyway, last one.

Okay, we can conclude this.

The last one is called a bijection,
also known as a one-to-one correspondence.

And the importance of this is that it
allows for an inverse mapping.

All right?

So let me just
copy this... here.

All right.

Maybe I should...
Okay, whatever.

Fine.

Now, the discrete
math books say that its

total functions are
injective and surjective.

But the fact is that here, bijective,
and I give you the reasoning, M equals N.

So that... It turns
out that you could...

You don't need this crazy formula in order
to figure out the number of bijections.

Otherwise, you would have to set...

You know, it's the
definition of injective and

surjective, but that's
the two formulas above.

It turns out that you could
do slightly different by

plugging in the bijective
constraint that M equals N.

So the result is that the
number of injective mappings

is N factorial divided
by N minus N factorial.

And that's equal to N equals M.

So one... Zero factorial is one.

It's the end of the class.

Okay.

Give me two seconds.

Let me land.

So therefore, the result is N factorial.

Anyway, I have a comment here which you
should read, which is...

What is the notion of an inverse?

A short little comment.

Read it.

Maybe I'll repeat it next time.

Anyway, it's the end of class.

If you didn't have... I'll
send you these notes.

If you didn't have a chance, kindly text
the word present, and we will continue.

Oh, I believe, but double check.

I believe Monday is President's Day or
something like that.

So I think we don't have...
The school is closed on Monday.

Is that true?

I believe so.

Let me check our calendar, which I have
written here offline.

What day is that?

The 16th.

Yes.

College is closed the 16th and possibly
the 17th.

You'll have to double check, but I believe
so.

So I believe our next class is a week from
today.

Okay?

Anyway, check your calendars.

All right.

If you didn't have a chance, kindly text
that you're present.

And...

Right?

And otherwise...

All right.

Thank you all.

Fun all right.

No?

Thanks all.

dich