[SOUND] The program which we are going to discuss next. Will illustrate a connection of combinatorics to algebra or maybe to number theory. It is called the merry-go-round problem. Let's start with the following question which we have already discussed today. Suppose that you have a train with let's say with p carriages. And you have n different colors. And you want to paint each carriage using one of the n colors. And the question is in how many ways can you do this, how many different colored trains are you going to get? In how many ways Can we Paint a train If we can paint each carriage in one of n colors? Well if you look at this problem closely, you see that this is exactly the word problem. So, each train, well, if you paint say, suppose you have pink, blue, and yellow. And you can paint different carriages in different colors or maybe on repetitions can occur. So for the first carriage there are n possibilities. For the second one there also n possibilities and so on. So the answer is the total number of different car trains is n to the power of P. Okay so here was the supplementary problem and now comes the merry-go-round problem. So the question is as follows. Suppose that For some reason, we suppose that, p is prime. And now we have not trains but merry-go-rounds, also consisting of p carriages. And again, you're allowed to Color each of the carriages Using one of the n colors. Let's say this is pink. And let's say these two guys are blue. In how many ways Can we Paint each carriage Of a merry-go-round Again using n colors? So what's the difference with the previous problem? The difference is that the merry-go-round can rotate. And if two different merry-go-rounds can be brought one to another by rotation this coloring is considered to be the same. Say if we paint this carriage pink, these two yellow, and these two blue this is the same as this merry go round shown on this picture. So how many possibilities are there to do this and what's the difference with the previous problem? Our first guess is that you can split a merry-go-round in some place and get a crane out of it. So if we split this merry go round in this place and then we will count, well lets say clockwise, we'll get a train. So we'll get a train consisting of pink, yellow, yellow, blue, blue carriages. So we will get exactly the train which is on this figure here upstairs. And each merry go round can be split in one of p places. So there are p possibilities to get a train out of a merry-go-round. So the first guess, A very naive one, is as follows. That we can Get p trains from each merry go round. So, the answer will be then the number of trains divided by p, divided by the number of trains obtained from each merry-go-round. The answer is then n to the power of p divided by p. [MUSIC]