. + x_n-1)^[xi]n,
and to obtain the condensed form we have to evaluate the co-axial minors
of the invertebrate determinant--
| 0 1 1 ... 1 |
| 1 0 1 ... 1 |
| 1 1 0 ... 1 |
| . . . ... . |
| 1 1 1 ... 0 |
The minors of the 1st, 2nd, 3rd ... nth orders have respectively the
values
0
-1
+2
...
(-)^(n-1)(n - 1),
therefore the generating function is
1
--------------------------------------------------------------------------------------;
1 - [Sigma]x1x2 - 2[Sigma]x1x2x3 - ... - s[Sigma]x1x2...x_s+1 - ... - (n - 1)x1x2...xn
or writing
(x - x1)(x - x2)...(x - xn) = x^n - a1x^(n-1) + a2x^(n-2) - ...,
this is
1
-------------------------------------
1 - a2 - 2a3 - 3a4 - ... - (n - 1)a_n
Again, consider the general problem of "derangements." We have to find
the number of permutations such that exactly _m_ of the letters are in
places they originally occupied. We have the particular redundant
product
(ax1 + x2 + ... + xn)^[xi]^1 (x1 + ax2 + ... + xn)^[xi]^2 ...
(x1 + x2 + ... + ax_n)^[xi]n,
in which the sought number is the coefficient of
a^m x1^[xi]^1 x2^[xi]^2...xn^[xi]n. The true generating function is
derived from the determinant
| a 1 1 1 . . . |
| 1 a 1 1 . . . |
| 1 1 a 1 . . . |
| 1 1 1 a . . . |
| . . . . |
| . . . . |
and has the form
1
------------------------------------------------------------------------------------------.
1 - a[Sigma]x1 + (a - 1)(a + 1)[Sigma]x1x2 - ... + (-)^n(a - 1)^(n-1)(a + n - 1)x1x2... xn
It is clear that a large class of problems in permutations can be solved
in a similar manner, viz. by giving special values to the elements of
the determinant of the matrix. The redundant product leads uniquely to
the real generating function, but the latter has generally more than one
representation as a redundant product, in the cases in which it is
representable at all. For the existence of a redundant form, the
coefficients of x1, x2, ... x1x2 ... in the denominator of the real
generating function must satisfy 2^n - n^2 + n - 2 conditions, and
assuming this to be the case, a redundant form can be constructed which
involves n - 1 undetermined quantities. We are thus able to pass from
any parti
|