How to calculate permutations. Lecture in Yandex
Some time ago, Igor Pak came to the Moscow office of Yandex - a scientist with many scientific works, a graduate of the Moscow State University and a Harvard graduate school. Now Igor works at the University of California. His lecture at Yandex was devoted to various classes of sequences and permutations. Including during the lecture, he presented the calculations that refute the Noonan and Seilberger hypothesis - one of the key ones in the field of permutations.
Under the cut - detailed text transcript and most of the slides.
')
I have a report about not the most standard things. Unfortunately, enumerative combinatorics is not studied very seriously - in Russia it is not included in the standard university program. In the first, introductory half of the report, I will cite famous classical questions from enumerated combinatorics. And in the second half will go more complex things of those that we have recently understood. If you stop me and ask questions - do not worry.
What are enumerated combinators in general? We usually study sequences of natural numbers. They are different. I wrote down half a dozen sequences from the Online Encyclopedia of Integer Sequences Encyclopedia. I will speak in Russian, but all the slides are in English.
Some sequences are more combinatorial, some less. For example, the number of finite groups, the very first sequence in this encyclopedia, is not very combinatorial. So it turns out that there are two groups of order 4. The next, simpler sequence is prime numbers. The number of partitions of an integer n, the sum of the items - we will see them later. The next sequence is the Fibonacci numbers. Then the number of involutions, the number of Catalan, the number of connected graphs.
The question is: is there a formula that describes the numbers in each sequence? This is a difficult question - it is related to the value of the formula. I will talk about different sequences and what formulas are. Then I will try to unify it, to tell the theory. We study sequences and try to understand the formulas for the numbers they contain.
I will start with a standard introduction. I myself will not determine anything - I'd rather quote from two authors. The first quote is Richard Stanley, to read it for a long time, but the meaning is this: he believes that the most interesting are explicit formulas when you can write that βsomething is the sum of something multiplied by somethingβ.
Herb Wilf says no, the formulas are irrelevant to whether this is a sum or a product, that they cannot be defined in such a way that the formula is actually an algorithm. For us, his idea is very important. A formula is a certain algorithm that counts the numbers in a sequence for a time polynomial in n.
But actually the older idea is to understand whether the formula is good or not. They look at formulas, on asymptotics. If we can figure out by formula what this number is, with an accuracy of plus or minus 3%, then this is a good formula. I have listed three standard definitions of what a formula is. All three will be very important to us, but the algorithmic approach will be most important.
Let's start with the asymptotics. This is a very old thing, known for all sequences. For example, the Fibonacci numbers grow in a very specific exponential way, the Catalan numbers also grow exponentially - there is a polynomial factor. We are talking about very old theorems. This is a theorem on the distribution of prime numbers, which is more than a hundred years old. For the number of partitions, there is also a remarkable asymptotic formula. It is not very easy to prove, but to understand the exponential term is a little easier.
For the number of involutions, a little bit of analysis is needed, not too complicated. But the formula for the number of groups of order <= n is very complex. To prove it, you need to know the classification of simple finite groups; this is not quite combinatorics, not combinatorics at all.
But the latter formula, on the contrary, is very simple. The number of graphs on n vertices is about 2 to the power (...) coefficient, n / 2. And its meaning is very simple: a random graph is connected with a high probability that tends to 1 when n tends to infinity.
These formulas are wonderful, but they are analytical formulas, not combinatorial ones. And they do not give us an understanding of how to calculate these numbers. And this is what we do. And in order to understand exactly what we are doing, I will start with a very standard classical example - Fibonacci numbers.
I will give one of their definitions. The Fibonacci number is the number of sequences of zeros and ones of length n minus 1, in which there are no two consecutive ones. For example, sequences of length 2, in which there are no two units in a row, will be exactly 3. Here they are: 00, 01, 10. Sequences of length 3, in which there are no two consecutive units, will be five.
Then there are three formulas. The first formula is the recurrence relation from us to the Fibonacci numbers, that the following is the sum of the two previous ones. The second formula writes Fibonacci numbers as the sum of the binomial coefficients. The third formula is quite clear: she writes them as the sum of two degrees β the golden ratio and its reverse.
Next question, which of these formulas is better? When I teach students, freshmen and second year students, I traditionally start with the first formula - I say that this definition, and we derive the third formula after some time and 30 minutes we prove.
But if you need to calculate the 117th Fibonacci number, then the third formula is quite useless. To calculate it, you need to very clearly know what exactly this golden section is - it must be calculated with a large number of signs. And this is again difficult. How will you do it? If you think this is not a good formula. The formula for the sum of binomial coefficients is excellent, but for calculations the first formula is better and simpler. You count one by one, and everything will work out.
It is already clear what the question is. Which formula is better is not quite obvious. In terms of aesthetics, maybe the third formula is better, and in terms of asymptotics, for sure. She immediately says what the Fibonacci number is asymptotic. But the first formula is better for calculations, and the second is more suitable for proving some theorems.
The number of unrest is a very old sequence. Take such a number of permutations that the element i always goes into some element that is not equal to i. If you have a permutation of length 2, there is always only one such permutation. A single permutation does not fit, {21} fits. When you have a permutation of length three, there are exactly two permutations, both cycles. The rest do not fit at all - they have a fixed point.
And in general, again, three formulas. The first is remarkable: this number is the closest integer to the number n! / E. Before us is a very simple formula. A simple, but asymptotic achievement is remarkable. The value of e is very difficult to calculate on a computer, and in order to clearly calculate the number of unrest of length 117, you need to know e with very high accuracy. The second formula explains the first. Roughly speaking, if you endure n! out, get n! multiply by the sum of the first k members of the Taylor series. On the one hand, this explains the first formula, and on the other hand, there are whole numbers - they can be easily counted.
In fact, the best formula for the calculations - the third. It gives a slightly unexpected recurrence relation, which is easiest to calculate and which explains absolutely nothing. Proving such a formula from the definition is not a very obvious exercise. It is not clear what to do with this (β1) to the power n. Such is the story. For the number of riots, it is clear that it is not entirely clear which formula is good and which is bad.
MΓ©nage numbers, french word. The task is as follows: an old-fashioned 19th-century dinner party is being arranged, n married couples are invited and they want to sit down with them, so that two conditions are fulfilled. The first condition is that men alternate with women. The second condition - spouses do not sit side by side. The task of the XIX century, maybe someone still collects such dinner parties. They say they do this at weddings.
How to count this number? If you have only two married couples, then they will not succeed. In order for spouses to sit together, they must be opposite each other - it means there will be no alternation. The sequence starts from zero when there are two married couples. But when we have three married couples, there are already quite a few such arrangements. Here is one of them. Suppose we have couples 1A, 2B, and 3C. A, B and C will be planted in order, and 1, 2 and 3 will be planted in a more complicated way. It can be seen that 3 sits between A and B and is not the spouse of neither A nor B.
This problem can be solved. From a historical point of view, there are two solutions. The first is complex, long and recurrent - historically it was received earlier, in 1891. The second solution is an explicit formula for the sum of binomial coefficients, factorials, factors, etc. When this ratio was obtained, no one was particularly pleased. It was believed that this is not a very necessary formula, although according to it it is easy to calculate everything. But as soon as Tushard in 1934 received a formula in the form of a variable sum of binomial coefficients, everyone thought that the problem had been solved. Although from a computational point of view, the second formula is much better.
I cite very classic examples from periodic combinatorics. How do we work with this? Now we are trying to improve our understanding of what an explicit formula is. The standard way is to take a generating function. This can be done in two different ways. The easiest is to simply take the sum of such a series and treat it as a formal function of t.
The question is whether there is any formula for this function. Often there is no good formula for a sequence, but for a function. Here is an example where for the Fibonacci numbers we have a very good formula - a very rational one for the generating function. But for the Catalan numbers the number of triangulations of n + 2-gon is taken. They were invented and studied by Euler in St. Petersburg in the 1750s. The generating function in this case will be not rational, but algebraic.
Let's look at other examples - say the number of involutions. Involution - a permutation, which is equal to one in the square. This means that it consists of cycles of length either 1 or 2. For the number of such involutions, there is no good formula that would allow to present it as the sum of binomial coefficients. However, there is a very good recurrence ratio. It is clear how to prove this?
Take the last element n. It is either a fixed point - then the number of permutations is 1 less, - or it is in transposition with some other element. There are n-1 ways to select such an element, and n-2 elements remain, with which you need to do something after that. From the definition we get such a simple recurrence relation. It has a great generating function that can be written explicitly. Note that this is an exponential generating function. We take t n > a n / n! - as if looking at the generating function for probabilities.
And there is a good formula e t + t 2/2 .
Here is a new way to look at the explicit formula. For the number of partitions n, there are several ways to present n as the sum of the items. For example, 4 = 3 + 1 = 2 + 2, and so on - there are a total of five ways to write 4 as a sum of terms. But the generating function is also wonderful. This, too, was invented by Euler, in 1738. An endless piece is what it will be. Before us is not such a good function, as we have seen before. If we have an infinite work, it is not very clear what to do with it. This is a fairly complex function.
- Tell for the graphs.
- For connected graphs on n vertices, there is a recurrent relation, but it is quadratic and its coefficients will be binomial. There is a quadratic relation for graphs, but I do not remember it by heart. You can calculate it pretty quickly, but it is not included in this topic.
Theory. We want to classify as many sequences as possible. Take a few classes. The first class is rational sequences. They are rational, if their generating function is rational, that is, is the ratio of two polynomials. In fact, this is completely equivalent to a simple recurrent relation to the given numbers, which summarizes the Fibonacci numbers. Here is the simplest thing you can think of. Surprisingly, there are quite a few sequences that satisfy these recurrence relations. But the sequences are simpler than rational functions - quite a few. All rational sequences have a very simple asymptotics, they are very easy to learn, everything is known about them.
The next level is algebraic. These are algebraic sequences that generalize the formula A (t) = 1 - β (1 - 4t) / 2t .
Suppose our generating function satisfies a certain algebraic equation with poly-mial coefficients. There are also quite a few such sequences: the Catalan numbers have such a sequence, the Motzkin number, and many others. But it turns out that this is not the largest class. We will study a larger class - the binomial sums. We take the sums, many binomial coefficients. I write - to summarize over all the vectors on the lattice, but in fact, where alpha and beta are some linear functions. If some function becomes negative in the binomial coefficient, then we assume that it is 0. It is interesting only when these numbers are finite. And there are quite a few such cases.
In this example, this is the case. Before us is the sum of some binomial coefficients. Here - from 0 to n / 2, but you can also release, do more, just the binomial coefficient will disappear, become zero.
As a result, we have a lot of different sequences, binomial sums. They include the number of unrest, and the number of seating at the table. All this can be understood from the point of view of such binomial coefficients. There are a lot of factorials from above, from below too - everything can be understood. This is a large class, but we are interested in an even larger class: P-recursive sequences. They can be defined in two ways. The clearest way is when there is a recursive relation to these numbers, when the coefficients are not constants, as in the rational case, but polynomials depending on n. If you remember, this complex and not very accurately written recurrence relation invented by Lucas is typical. But there are such relationships for many other sequences.
A typical example is n! .. It is by definition (n - 1)! * n.
Another example is the Catalan numbers. You remember that this is some kind of relation between two binomial coefficients. A certain rational function will turn out, which depends on n. This means that it can be written as a recurrent relation, which should be zero.
This is not a very complicated theorem. It means that the generating function satisfies such an ordinary differential equation with polynomial coefficients. Here is another way to understand how the sequences are arranged. For us, P-recursive sequences will be the most important class. It includes the following theorems, which are written below and consist in the fact that all previous classes lie inside it. Speech about the largest class. For algebraic sequences, this is not entirely obvious, but to prove this for the others is a little easier.
Of course, this class does not include all the examples. Let's say primes are not included here - for them there is no polynomial relation. Similarly, there is no polynomial relation for the number of connected graphs. With them - a more complex example, which does not apply here. It is bad that there are such examples when the number of partitions is not included here, but it is remarkable that the P-recursive sequences can be simply calculated by definition for polynomial time. What is written here will be important to us. We have a class of sequences, all of which can be counted.
Before we start counting them, I will give some result. It consists in the fact that in this class everything is already good from the point of view of asymptotics. If you have a P-recursive sequence, then the asymptotic behavior is already very good: there is a constant, n !, some degrees, Ξ» n n Ξ± (log n) Ξ² . Everything works fine, but, unfortunately, this theorem is not proven. Some consider it a theorem, but it is her only in special cases. However, for us, in principle, such a special case is just that - if there is a non-negative P-recursive integer sequence that does not grow higher than the exponent, then its behavior is very simple: Ξ» n n Ξ± (log n) Ξ² . She has a good and simple asymptotics. This class is very large and includes many different combinatorial sequences that we want to study. P-recursive sequences are the most important class for us.
There is another more general class about which very little is known. We are talking about sequences in which the generating function satisfies an algebraic differential equation. If we take a certain number of derivatives of this generating function, then all together they will satisfy a certain polynomial equation. This is a more general class. Unfortunately, there are quite a few results about its asymptotics. Here is one example. Take alternating permutations, which begin with a certain number, and then go more-less, more-less. For example, there are exactly two such permutations of length 3 - 1, 3, 2 and 2, 3, 1. There are five permutations of length 4, and so on.
For the number of such permutations, there is a rather complex recurrence relation. It can be rewritten as an equation that is not an ordinary differential, but an algebraic differential: 2A '= A 2 + 1. In this form, it is solved - the generating function can be written explicitly: tan (t) + sec (t). , , , . , , , β n- . , .
, β , . , , , , . 150 , , , t n 2 , t n 3 , β 150 . , . , . , - . .
4. , . . . , .
β ?
β . , n .
β . , , ?
β . , , , , .
n! * t n , . , , defined, n! , . , .
β , , ?
β . , .
? . ?
β β ?
β , , , . , n β 2 n/2, β , . , β , . . β , . .
, , , . , , n, ? - , , labeled unlabeled. , . ? : e n β . , . , , . β .
. . . β -. «». , , , 0-1-, . , (5674123) (321) β .
, (4321), 4. (321) β . , , , .
, . , , . β , Ο avoids Ο.
. , - : Β«, Β».
, . , , 0-1- . β , , . , . A simple example. , β (12). 7, ? One , (12), , . : (7654321).
, . .
. , (123), 3. , : , , . , 1915 β . 3, , . , (213), . , , , 3: . . 4, 4, 4 β . .
, , . . , . , , , , , .
, , . . , 2, β , , , . , . , . , , , (1342). , , .
β , , . , - , , .
, , : , , , -, .
, , . . , , , , . 31 80 , .
31 β . - , , . , . ? . , 80 . .
, , - , , . , , β . 90- , . , , : β 1990 . - , , , . , 4, (1324), , , -. .
31 , 4. , , , . - - . -, . -, ? .
? . , F F', , 2, , . : . .
2. , , F F'. , ? , , , . , ?
, . , β F F' «» «». - .
, , , . β , . , .
, k , . , . , , - . β , . , .
, . , , , . . β . , -. , - .
, , , . 2.
, = NP. : , , .
NP? , , NP. , , .
βP. , . . , = βP = NP β . , βP β , . , . , , β . . β .
, . , n- . imput size n log (n) bits, n log (n) . , n, input. , P β βP EXP β βEXP. , input unary, not in binary. Computation Complexity.
, . EXP β βEXP, β 31 β , , , , n. , , defined, AD, 1 , β Computation Complexity. , . - , - β .
, , , , n β , .
1982 : - , ? ? - 31 80 β , . , , Computation Complexity , , , .
, . , , - . , 1. . β - . β 0, β 1 . , , . . , , .
- . , r 0 (n)a n + r 1 (n)a n-1 . . , , .
. . 0, 1, 0,0, 0,1, 1,0 1,1, 0,0,0, 0,0,1 0,1,0, .
. : , . , . , 80 80, .
, 88. , - , 1010, . , , :
, , β , , . , , . , , , , , .
β . . 88 1010. , β¦ 1 ? . , , -, , , β , . , . , , , 2 n . , 1 + Ξ΅ n - Ξ΅, , - . .
. . , -, ADE. , . . , , , K! + K n.
. , n 2 . , , β . ! + , , , , . , .
? ? , . , , Wang tiles. 11. , . Wang tiles, . : , , ? , , .
, , . . , , . . - , , .
.
. : , 1. , , ? , , , . , , , 2, . , , -? , .
, , , . , . , , β . 31 . , , .
, , , -.
, , , . , .
Actually, everything. Thanks to all.
Under the cut - detailed text transcript and most of the slides.
')
I have a report about not the most standard things. Unfortunately, enumerative combinatorics is not studied very seriously - in Russia it is not included in the standard university program. In the first, introductory half of the report, I will cite famous classical questions from enumerated combinatorics. And in the second half will go more complex things of those that we have recently understood. If you stop me and ask questions - do not worry.
What are enumerated combinators in general? We usually study sequences of natural numbers. They are different. I wrote down half a dozen sequences from the Online Encyclopedia of Integer Sequences Encyclopedia. I will speak in Russian, but all the slides are in English.
Some sequences are more combinatorial, some less. For example, the number of finite groups, the very first sequence in this encyclopedia, is not very combinatorial. So it turns out that there are two groups of order 4. The next, simpler sequence is prime numbers. The number of partitions of an integer n, the sum of the items - we will see them later. The next sequence is the Fibonacci numbers. Then the number of involutions, the number of Catalan, the number of connected graphs.
The question is: is there a formula that describes the numbers in each sequence? This is a difficult question - it is related to the value of the formula. I will talk about different sequences and what formulas are. Then I will try to unify it, to tell the theory. We study sequences and try to understand the formulas for the numbers they contain.
I will start with a standard introduction. I myself will not determine anything - I'd rather quote from two authors. The first quote is Richard Stanley, to read it for a long time, but the meaning is this: he believes that the most interesting are explicit formulas when you can write that βsomething is the sum of something multiplied by somethingβ.
Herb Wilf says no, the formulas are irrelevant to whether this is a sum or a product, that they cannot be defined in such a way that the formula is actually an algorithm. For us, his idea is very important. A formula is a certain algorithm that counts the numbers in a sequence for a time polynomial in n.
But actually the older idea is to understand whether the formula is good or not. They look at formulas, on asymptotics. If we can figure out by formula what this number is, with an accuracy of plus or minus 3%, then this is a good formula. I have listed three standard definitions of what a formula is. All three will be very important to us, but the algorithmic approach will be most important.
Let's start with the asymptotics. This is a very old thing, known for all sequences. For example, the Fibonacci numbers grow in a very specific exponential way, the Catalan numbers also grow exponentially - there is a polynomial factor. We are talking about very old theorems. This is a theorem on the distribution of prime numbers, which is more than a hundred years old. For the number of partitions, there is also a remarkable asymptotic formula. It is not very easy to prove, but to understand the exponential term is a little easier.
For the number of involutions, a little bit of analysis is needed, not too complicated. But the formula for the number of groups of order <= n is very complex. To prove it, you need to know the classification of simple finite groups; this is not quite combinatorics, not combinatorics at all.
But the latter formula, on the contrary, is very simple. The number of graphs on n vertices is about 2 to the power (...) coefficient, n / 2. And its meaning is very simple: a random graph is connected with a high probability that tends to 1 when n tends to infinity.
These formulas are wonderful, but they are analytical formulas, not combinatorial ones. And they do not give us an understanding of how to calculate these numbers. And this is what we do. And in order to understand exactly what we are doing, I will start with a very standard classical example - Fibonacci numbers.
I will give one of their definitions. The Fibonacci number is the number of sequences of zeros and ones of length n minus 1, in which there are no two consecutive ones. For example, sequences of length 2, in which there are no two units in a row, will be exactly 3. Here they are: 00, 01, 10. Sequences of length 3, in which there are no two consecutive units, will be five.
Then there are three formulas. The first formula is the recurrence relation from us to the Fibonacci numbers, that the following is the sum of the two previous ones. The second formula writes Fibonacci numbers as the sum of the binomial coefficients. The third formula is quite clear: she writes them as the sum of two degrees β the golden ratio and its reverse.
Next question, which of these formulas is better? When I teach students, freshmen and second year students, I traditionally start with the first formula - I say that this definition, and we derive the third formula after some time and 30 minutes we prove.
But if you need to calculate the 117th Fibonacci number, then the third formula is quite useless. To calculate it, you need to very clearly know what exactly this golden section is - it must be calculated with a large number of signs. And this is again difficult. How will you do it? If you think this is not a good formula. The formula for the sum of binomial coefficients is excellent, but for calculations the first formula is better and simpler. You count one by one, and everything will work out.
It is already clear what the question is. Which formula is better is not quite obvious. In terms of aesthetics, maybe the third formula is better, and in terms of asymptotics, for sure. She immediately says what the Fibonacci number is asymptotic. But the first formula is better for calculations, and the second is more suitable for proving some theorems.
The number of unrest is a very old sequence. Take such a number of permutations that the element i always goes into some element that is not equal to i. If you have a permutation of length 2, there is always only one such permutation. A single permutation does not fit, {21} fits. When you have a permutation of length three, there are exactly two permutations, both cycles. The rest do not fit at all - they have a fixed point.
And in general, again, three formulas. The first is remarkable: this number is the closest integer to the number n! / E. Before us is a very simple formula. A simple, but asymptotic achievement is remarkable. The value of e is very difficult to calculate on a computer, and in order to clearly calculate the number of unrest of length 117, you need to know e with very high accuracy. The second formula explains the first. Roughly speaking, if you endure n! out, get n! multiply by the sum of the first k members of the Taylor series. On the one hand, this explains the first formula, and on the other hand, there are whole numbers - they can be easily counted.
In fact, the best formula for the calculations - the third. It gives a slightly unexpected recurrence relation, which is easiest to calculate and which explains absolutely nothing. Proving such a formula from the definition is not a very obvious exercise. It is not clear what to do with this (β1) to the power n. Such is the story. For the number of riots, it is clear that it is not entirely clear which formula is good and which is bad.
MΓ©nage numbers, french word. The task is as follows: an old-fashioned 19th-century dinner party is being arranged, n married couples are invited and they want to sit down with them, so that two conditions are fulfilled. The first condition is that men alternate with women. The second condition - spouses do not sit side by side. The task of the XIX century, maybe someone still collects such dinner parties. They say they do this at weddings.
How to count this number? If you have only two married couples, then they will not succeed. In order for spouses to sit together, they must be opposite each other - it means there will be no alternation. The sequence starts from zero when there are two married couples. But when we have three married couples, there are already quite a few such arrangements. Here is one of them. Suppose we have couples 1A, 2B, and 3C. A, B and C will be planted in order, and 1, 2 and 3 will be planted in a more complicated way. It can be seen that 3 sits between A and B and is not the spouse of neither A nor B.
This problem can be solved. From a historical point of view, there are two solutions. The first is complex, long and recurrent - historically it was received earlier, in 1891. The second solution is an explicit formula for the sum of binomial coefficients, factorials, factors, etc. When this ratio was obtained, no one was particularly pleased. It was believed that this is not a very necessary formula, although according to it it is easy to calculate everything. But as soon as Tushard in 1934 received a formula in the form of a variable sum of binomial coefficients, everyone thought that the problem had been solved. Although from a computational point of view, the second formula is much better.
I cite very classic examples from periodic combinatorics. How do we work with this? Now we are trying to improve our understanding of what an explicit formula is. The standard way is to take a generating function. This can be done in two different ways. The easiest is to simply take the sum of such a series and treat it as a formal function of t.
The question is whether there is any formula for this function. Often there is no good formula for a sequence, but for a function. Here is an example where for the Fibonacci numbers we have a very good formula - a very rational one for the generating function. But for the Catalan numbers the number of triangulations of n + 2-gon is taken. They were invented and studied by Euler in St. Petersburg in the 1750s. The generating function in this case will be not rational, but algebraic.
Let's look at other examples - say the number of involutions. Involution - a permutation, which is equal to one in the square. This means that it consists of cycles of length either 1 or 2. For the number of such involutions, there is no good formula that would allow to present it as the sum of binomial coefficients. However, there is a very good recurrence ratio. It is clear how to prove this?
Take the last element n. It is either a fixed point - then the number of permutations is 1 less, - or it is in transposition with some other element. There are n-1 ways to select such an element, and n-2 elements remain, with which you need to do something after that. From the definition we get such a simple recurrence relation. It has a great generating function that can be written explicitly. Note that this is an exponential generating function. We take t n > a n / n! - as if looking at the generating function for probabilities.
And there is a good formula e t + t 2/2 .
Here is a new way to look at the explicit formula. For the number of partitions n, there are several ways to present n as the sum of the items. For example, 4 = 3 + 1 = 2 + 2, and so on - there are a total of five ways to write 4 as a sum of terms. But the generating function is also wonderful. This, too, was invented by Euler, in 1738. An endless piece is what it will be. Before us is not such a good function, as we have seen before. If we have an infinite work, it is not very clear what to do with it. This is a fairly complex function.
- Tell for the graphs.
- For connected graphs on n vertices, there is a recurrent relation, but it is quadratic and its coefficients will be binomial. There is a quadratic relation for graphs, but I do not remember it by heart. You can calculate it pretty quickly, but it is not included in this topic.
Theory. We want to classify as many sequences as possible. Take a few classes. The first class is rational sequences. They are rational, if their generating function is rational, that is, is the ratio of two polynomials. In fact, this is completely equivalent to a simple recurrent relation to the given numbers, which summarizes the Fibonacci numbers. Here is the simplest thing you can think of. Surprisingly, there are quite a few sequences that satisfy these recurrence relations. But the sequences are simpler than rational functions - quite a few. All rational sequences have a very simple asymptotics, they are very easy to learn, everything is known about them.
The next level is algebraic. These are algebraic sequences that generalize the formula A (t) = 1 - β (1 - 4t) / 2t .
Suppose our generating function satisfies a certain algebraic equation with poly-mial coefficients. There are also quite a few such sequences: the Catalan numbers have such a sequence, the Motzkin number, and many others. But it turns out that this is not the largest class. We will study a larger class - the binomial sums. We take the sums, many binomial coefficients. I write - to summarize over all the vectors on the lattice, but in fact, where alpha and beta are some linear functions. If some function becomes negative in the binomial coefficient, then we assume that it is 0. It is interesting only when these numbers are finite. And there are quite a few such cases.
In this example, this is the case. Before us is the sum of some binomial coefficients. Here - from 0 to n / 2, but you can also release, do more, just the binomial coefficient will disappear, become zero.
As a result, we have a lot of different sequences, binomial sums. They include the number of unrest, and the number of seating at the table. All this can be understood from the point of view of such binomial coefficients. There are a lot of factorials from above, from below too - everything can be understood. This is a large class, but we are interested in an even larger class: P-recursive sequences. They can be defined in two ways. The clearest way is when there is a recursive relation to these numbers, when the coefficients are not constants, as in the rational case, but polynomials depending on n. If you remember, this complex and not very accurately written recurrence relation invented by Lucas is typical. But there are such relationships for many other sequences.
A typical example is n! .. It is by definition (n - 1)! * n.
Another example is the Catalan numbers. You remember that this is some kind of relation between two binomial coefficients. A certain rational function will turn out, which depends on n. This means that it can be written as a recurrent relation, which should be zero.
This is not a very complicated theorem. It means that the generating function satisfies such an ordinary differential equation with polynomial coefficients. Here is another way to understand how the sequences are arranged. For us, P-recursive sequences will be the most important class. It includes the following theorems, which are written below and consist in the fact that all previous classes lie inside it. Speech about the largest class. For algebraic sequences, this is not entirely obvious, but to prove this for the others is a little easier.
Of course, this class does not include all the examples. Let's say primes are not included here - for them there is no polynomial relation. Similarly, there is no polynomial relation for the number of connected graphs. With them - a more complex example, which does not apply here. It is bad that there are such examples when the number of partitions is not included here, but it is remarkable that the P-recursive sequences can be simply calculated by definition for polynomial time. What is written here will be important to us. We have a class of sequences, all of which can be counted.
Before we start counting them, I will give some result. It consists in the fact that in this class everything is already good from the point of view of asymptotics. If you have a P-recursive sequence, then the asymptotic behavior is already very good: there is a constant, n !, some degrees, Ξ» n n Ξ± (log n) Ξ² . Everything works fine, but, unfortunately, this theorem is not proven. Some consider it a theorem, but it is her only in special cases. However, for us, in principle, such a special case is just that - if there is a non-negative P-recursive integer sequence that does not grow higher than the exponent, then its behavior is very simple: Ξ» n n Ξ± (log n) Ξ² . She has a good and simple asymptotics. This class is very large and includes many different combinatorial sequences that we want to study. P-recursive sequences are the most important class for us.
There is another more general class about which very little is known. We are talking about sequences in which the generating function satisfies an algebraic differential equation. If we take a certain number of derivatives of this generating function, then all together they will satisfy a certain polynomial equation. This is a more general class. Unfortunately, there are quite a few results about its asymptotics. Here is one example. Take alternating permutations, which begin with a certain number, and then go more-less, more-less. For example, there are exactly two such permutations of length 3 - 1, 3, 2 and 2, 3, 1. There are five permutations of length 4, and so on.
For the number of such permutations, there is a rather complex recurrence relation. It can be rewritten as an equation that is not an ordinary differential, but an algebraic differential: 2A '= A 2 + 1. In this form, it is solved - the generating function can be written explicitly: tan (t) + sec (t). , , , . , , , β n- . , .
, β , . , , , , . 150 , , , t n 2 , t n 3 , β 150 . , . , . , - . .
4. , . . . , .
β ?
β . , n .
β . , , ?
β . , , , , .
n! * t n , . , , defined, n! , . , .
β , , ?
β . , .
? . ?
β β ?
β , , , . , n β 2 n/2, β , . , β , . . β , . .
, , , . , , n, ? - , , labeled unlabeled. , . ? : e n β . , . , , . β .
. . . β -. «». , , , 0-1-, . , (5674123) (321) β .
, (4321), 4. (321) β . , , , .
, . , , . β , Ο avoids Ο.
. , - : Β«, Β».
, . , , 0-1- . β , , . , . A simple example. , β (12). 7, ? One , (12), , . : (7654321).
, . .
. , (123), 3. , : , , . , 1915 β . 3, , . , (213), . , , , 3: . . 4, 4, 4 β . .
, , . . , . , , , , , .
, , . . , 2, β , , , . , . , . , , , (1342). , , .
β , , . , - , , .
, , : , , , -, .
, , . . , , , , . 31 80 , .
31 β . - , , . , . ? . , 80 . .
, , - , , . , , β . 90- , . , , : β 1990 . - , , , . , 4, (1324), , , -. .
31 , 4. , , , . - - . -, . -, ? .
? . , F F', , 2, , . : . .
2. , , F F'. , ? , , , . , ?
, . , β F F' «» «». - .
, , , . β , . , .
, k , . , . , , - . β , . , .
, . , , , . . β . , -. , - .
, , , . 2.
, = NP. : , , .
NP? , , NP. , , .
βP. , . . , = βP = NP β . , βP β , . , . , , β . . β .
, . , n- . imput size n log (n) bits, n log (n) . , n, input. , P β βP EXP β βEXP. , input unary, not in binary. Computation Complexity.
, . EXP β βEXP, β 31 β , , , , n. , , defined, AD, 1 , β Computation Complexity. , . - , - β .
, , , , n β , .
1982 : - , ? ? - 31 80 β , . , , Computation Complexity , , , .
, . , , - . , 1. . β - . β 0, β 1 . , , . . , , .
- . , r 0 (n)a n + r 1 (n)a n-1 . . , , .
. . 0, 1, 0,0, 0,1, 1,0 1,1, 0,0,0, 0,0,1 0,1,0, .
. : , . , . , 80 80, .
, 88. , - , 1010, . , , :
, , β , , . , , . , , , , , .
β . . 88 1010. , β¦ 1 ? . , , -, , , β , . , . , , , 2 n . , 1 + Ξ΅ n - Ξ΅, , - . .
. . , -, ADE. , . . , , , K! + K n.
. , n 2 . , , β . ! + , , , , . , .
? ? , . , , Wang tiles. 11. , . Wang tiles, . : , , ? , , .
, , . . , , . . - , , .
.
. : , 1. , , ? , , , . , , , 2, . , , -? , .
, , , . , . , , β . 31 . , , .
, , , -.
, , , . , .
Actually, everything. Thanks to all.
Source: https://habr.com/ru/post/311480/
All Articles