So we have discussed how to count the number of Tuples,
and now we can move on to
our second standard combinatorial setting, permutations.
We will count how many permutations are there.
Consider the following general problem.
Suppose we have a set of n symbols and we would
like to count how many different sequences of length k are there,
consisting of these n symbols but with additional restriction,
we are now not allowing to use the same symbol twice.
Tuples of length k without repetitions of letters are called k-permutations.
And this is what we are going to compute in this problem,
the number of k permutations are going to compute in this problem.
And let's make the following useful observation,
if n is less than k,
if the number of symbols in our disposition is less than
the length of sequence they are trying to construct and we
are not allowed to repeat letters.
Then the answer is simple,
there are just no permutations as there are just not
enough different letters to construct the sequence of
length k. So in this case the answer is zero,
and this case is simple.
So, let's further on assume that k is at
most n. Let's consider this case, on trivial case.
Let's proceed to solution to our problem.
Here we see our sequence we denote the symbol by
star so lets numerate them from one to k.
And we will apply the rule of product,
we will solve this problem using the rule of product.
The first symbol we can pick in n ways.
What about the second symbol? How many choices do we have there?
And note that we can place there anything
except the symbol we already placed in the first position.
So there are n minus one options for the second symbol.
The symbol in the first position might be any symbol,
but for any symbol in the first position
there are n minus one possibilities for the second symbol.
So there are n possibilities.
For the first symbol, for each of them,
there are n minus one possibilities for the second symbol.
So in total, we have n times n minus
one possibilities to pick the first and the second symbol.
And now we can proceed in the same way.
Consider the first symbol,
we can pick the first two symbols by n times n minus one ways.
And for the third symbol,
whatever the first and the second symbols are,
for the first symbol we have n minus one options,
all symbols except the symbol in
the first position and the symbol in the second position.
So there are n minus two possibilities for
all ways to pick the first and the second symbol.
So for the first three symbols,
we have n times n minus one times n minus two possibilities, and so on.
For each next symbol, we have one less option.
And in the end,
so for the last symbol we will have n minus k plus one options.
So this might require a moment of reflection,
why it's n minus k plus one and not n minus k?
One easy way to observe it is to look at- so
let's see if near the first symbol we have one number above and one number below,
one and n. For the second symbol its the same,
we have two numbers two and minus one.
Know that for each symbol, for the first,
for the second, for the third, and so on,
the sum of these numbers is n plus one.
And when we move to the right,
the first number increases,
the second number decreases.
So then, the sum of these numbers always stay to be equal to n plus one.
So in the end it's also should be equal to n plus one.
So which would be minus k plus one below there.
So that's the easy way to observe that this is in minus k plus one.
There are n minus k plus one options there,
for the last symbol.
So in total, we have to multiply all of
these options and so we have n times n minus 1, and so on,
times n minus k plus one k-permutations of symbols of
length n. So this is not a very nice looking formula.
There is a convenient notation to make it look more simple and more short.
A convenient notation is n factorial. N factorial is just a product
of numbers from one to n. One times two, and so on, times n.
And in this notation, the number of k-permutations of n symbols looks nicer.
It has notes that we have product of- The answer to
our problem was the product of all numbers.
We multiply n by n minus one,
by n minus two, and so on,
but we stop on n minus k plus one.
So we can write it as n factorial divided by n minus k factorial.
So we consider n factorial,
and we divide it by all multipliers we do not want in our product.
So the answer in these terms is n factorial divided by n minus k factorial.
One important observation to make,
what if n minus k is equal to zero? This is possible.
So what if n is equal to k?
Then this formula we have,
it looks like we try to divide by zero,
n minus k is zero so we are trying to divide something,
this is time to divide by zero.
No it's not, it's not time to divide by zero factorial.
And you haven't said what it is yet.
And the standard convention here to make this formula true only also for the this case,
the standard convention is to save a zero factorial, is one.
So this what we will agree upon and then
this formula works also for the case of n equals k. And we are done,
the answer to his problem is n factorial divided by n minus k factorial.
So, now let's consider the following specific example.
So we have n books, n different books,
and we would like to place them on the shelf in some order.
So how many different orders we can do it?
We can think of each book as a symbol.
And now what we need to do,
we need to count how many sequences of n symbols do we have.
And again, as is in the previous problem,
we are not allowed to repeat the symbol twice.
We cannot place the same book in two places simultaneously on the bookshelf.
So we need to count n-permutations of n symbols, and these are called just permutations.
If we have n permutations of n symbols,
then we can just omit the prefix n there and talk about just permutations.
this is various standard objects in Combinatorics.
And by the previous result we have n factorial of them.
We could show in our previous problem shows that there are n factorial of
such permutations and so there are n factorial ways to place n books on the shelf.
There are n factorials orders to place n books on the shelf.
And recall, if you have seen our first course, "What is a Proof?",
recall that we have used this formula when discussing magic squares.
In this week, we have started the discussion of Combinatorics.
This field is important and will be important for us.
It is important for Probability Theory.
It will be important for estimation of running time of
algorithms and it is also important in mathematics in general.
And we have already discussed
two standard settings in Combinatorics, tuples and permutations.
We have discussed how we can
compute how many tuples are there of certain lengths over certain alphabet,
and how many permutations are there of certain lengths over certain alphabet.
And these two settings already
help us in many settings.
We also have discussed recursive counting,
it is also useful especially if you are trying to compute something.
Not to produce a formula,
but to compute something by an algorithm,
recursive counting is very useful there.
But we still do not know everything we need.
For example, if we would like to count what
are our chances to get two aces in the card game if you have six card hand.
We still do not know how to do it,
and we will discuss this later on.
Alexander S. KulikovVisiting Professor
Vladimir PodolskiiAssociate Professor
