prior knowledge
You may need to know some generating function basics. You should be able to read it and learn it if you can't understand it.
One needs to know at least the most basic forms of transclosure:\(1 + x + x^2 + x^3\dots = \frac{1}{1 - x}\) cap (a poem)\(1 + ax + (ax)^2 + (ax)^3\dots = \frac{1}{1 - ax}\)。
stipulated (time, amount, quality etc)
\(F\) denotes the function that\(f\) Denote a generating function (a polynomial with infinite terms?) .
\([x^i]f\) denote a polynomial\(f\) (used form a nominal expression)\(x^i\) The coefficients of the
function (math.)\(\to\) Ordinary generating function closed form
If there is a function like this
\(G(i)\) What is it? It's long for\(i\) The number of legal replacement rings for the
- Legitimate substitution ring: there is only one substitution ring and it is composed of the substitution ring from the\(1\) Ascending to\(n\) retrace one's steps\(n\) Descending to\(1\) The two chains that make up the
If we ask\(F(n)\) long as\(n\) of the sequence is satisfied:
- consists of a legal substitution ring (in this case the\(mn\to mx, mx\to mn\) (the two chains of which are composed)
- Each permutation ring is a continuous segment of intervals on the sequence.
in that case\(F(n) = \sum\limits_{i = 1}^{n}F(n - i)G(i), F(0) = 1\)。
Then write the generating function\(g = \sum\limits_{i = 0}G(i)x^i = x + \sum\limits_{i = 2}2^{i - 2}x^i = x + x^2\sum\limits_{i = 0}(2x)^i = x + x^2\frac{1}{1 - 2x} = \frac{x^2 + x(1 - 2x)}{1 - 2x} = \frac{x - x^2}{1 - 2x}\)。
Then consider a legal permutation equivalent to a number of legal substitution rings stitched together, with\(f = \sum\limits_{i = 0}^{n} g^i\), i.e., the enumeration is stitched together from several permutation rings. Then\(f = \frac{1}{1 - g} = \frac{1 - 2x}{1 - 3x + x^2}\)。
Ordinary generating function closed form\(\to\) recursive equation
Here we need to ask for\([x^n]f\) That is the answer, so how do you find it here?
We consider setting\(f = a_0 + a_1x + a_2x^2 +\dots\)(which actually has\(a_i = G(i)\)）
insofar as\(f\)，\(f = \frac{1 - 2x}{1 - 3x + x^2}\) equivalence\((1 - 3x + x^2)f = (1 - 2x) = t\)The left side of the\(=a_0 + (-3a_0 + a_1)x + (a_2 + -3a_1 + a_0)x^2 + \dots\), so we're actually getting information about\(a\) The system of equations of the
there are\(a_0 = 1, -3a_0 + a_1 = -2\)，
It was also found that for\(i\ge 2\)Yes\([x^i](1 - 2x) = 0\)and\([x^i]\ ((1 - 3x + x^2)f) = 1(a_ix^i) + (-3x)(a_{i - 1}x^{i - 1}) + x^2(a_{i - 2}x^{i - 2}) = (a_i -3a_{i - 1} + a_{i - 2})x^i = [x^i](1 - 2x) = 0\)。
And so we actually get a description of the\(F(i)\) The recursive form of, in this problem\(F(0) = F(1) = 1, F(i) = 3F(i - 1) - F(i - 2)(i\ge 2)\)
summarize
For infinite series\(f = \frac{c}{d}\)(of which\(c, d\) (is it an integer?) , which can be obtained as\(cf = d\)set up\(f = a_0 + a_1x + a_2x^2\dots\)For the larger\([x_n]f\) is the same recursive and can be solved for by solving the equation, the larger definition is\(\ge c, d\) The highest number of times in the\(\ge len(c)\) It is obvious that the requirement\(\ge len(d)\)Because it's only now that they're all\(= 0\)。
Up to this point, we have reviewed (learned) the way to invert recursive equations by closed form of ordinary generating functions in certain cases. There was also a slight review of the way functions are reduced to ordinary generating functions.