Professor Tait's Problem of Arrangement

116 Views Asked by At

Professor Tait's Problem of Arrangement asks for the number of ways of a set of $[n]$ things, subject to the conditions that the first is not to be in the last or first place, the second not in the first or second place, the third not in the second or third place, and so on.

Here is a link that gives a recurrence relation for such permutations,however I don't understand the page 384 of this article,how exactly a determinant can be transformable to the two others?

enter image description here enter image description here

enter image description here enter image description here enter image description here enter image description here

But I even don't know how even we can sum these two determinants,I really don't understand what does that mean and how the first determinant is transformable to these two next.

1

There are 1 best solutions below

0
On

Determinants are numbers, so the sum of two determinants, even of different sizes, would be fine. That's not actually what is going on here, however. The key passage for understanding this appears near the bottom of page 383:

Further, let any determinant-form with dots and asterisks stand for the number of terms in such a determinant;

By this Muir means the number of non-zero terms in the Leibniz formula for the determinant, which may be computed recursively using the cofactor expansion (Laplace formula). So each determinant in Muir's article actually represents a non-negative integer—the number of non-zero terms that would result if the determinant were fully expanded. The dots in Muir's determinants represent zero elements and the asterisks represent non-zero elements.

Recall that the Leibniz and Laplace formulas involve powers of $-1$. In Muir's prescription, we are being asked to ignore the sign, and indeed, any aspect of the value of a term apart from whether it is zero or not. An equivalent procedure would be to replace all Muir's dots by zeros, all his asterisks by ones, and to compute the permanent rather than the determinant. The permanent is defined by a Leibniz expansion similar to that of the determinant except that the powers of $-1$ are absent. I suspect that Muir himself may have formulated things this way in a later article, as he is credited with introducing the permanent in its modern definition. I have not seen the later article to confirm this, however.

Let's follow the permanent prescription in an example. The number of permutations of the set $\{1,2,3\}$ satisfying your conditions would be $$ \operatorname{perm}\begin{bmatrix}0 & 1 & 0\\ 0 & 0 & 1\\ 1 & 0 & 0\end{bmatrix}=0\cdot0\cdot0+1\cdot1\cdot1+0\cdot0\cdot0+1\cdot0\cdot0+0\cdot1\cdot0+0\cdot0\cdot1=1, $$ where we have multiplied elements on the three forward diagonals and on the three backward diagonals and summed all six terms.

Let's do the same thing for the set $\{1,2,3,4,5\}$, this time using the Laplace formula: $$\begin{aligned} &\operatorname{perm}\begin{bmatrix}0 & 1 & 1 & 1& 0\\ 0 & 0 & 1 & 1 & 1\\ 1 & 0 & 0 & 1 & 1\\ 1 & 1 & 0 & 0 & 1\\ 1 & 1 & 1 & 0 & 0\end{bmatrix}\\ &\quad=\operatorname{perm}\begin{bmatrix}1 & 1 & 1& 0\\ 0 & 1 & 1 & 1\\ 1 & 0 & 0 & 1\\ 1 & 1 & 0 & 0\end{bmatrix}+\operatorname{perm}\begin{bmatrix}1 & 1 & 1& 0\\ 0 & 1 & 1 & 1\\ 0 & 0 & 1 & 1\\ 1 & 1 & 0 & 0\end{bmatrix}+\operatorname{perm}\begin{bmatrix}1 & 1 & 1& 0\\ 0 & 1 & 1 & 1\\ 0 & 0 & 1 & 1\\ 1 & 0 & 0 & 1\end{bmatrix}\\ &\quad=\operatorname{perm}\begin{bmatrix}1 & 1 & 1\\ 0 & 0 & 1\\ 1 & 0 & 0\end{bmatrix}+\operatorname{perm}\begin{bmatrix}1 & 1 & 0\\ 1 & 1 & 1\\ 1 & 0 & 0\end{bmatrix}+\operatorname{perm}\begin{bmatrix}1 & 1 & 0\\ 1 & 1 & 1\\ 0 & 0 & 1\end{bmatrix}\\ &\quad\quad+\operatorname{perm}\begin{bmatrix}1 & 1 & 1\\ 0 & 1 & 1\\ 1 & 0 & 0\end{bmatrix}+\operatorname{perm}\begin{bmatrix}1 & 1 & 0\\ 1 & 1 & 1\\ 0 & 1 & 1\end{bmatrix}\\ &\quad\quad+\operatorname{perm}\begin{bmatrix}1 & 1 & 1\\ 0 & 1 & 1\\ 0 & 0 & 1\end{bmatrix}+\operatorname{perm}\begin{bmatrix}1 & 1& 0\\ 1 & 1 & 1\\ 0 & 1 & 1\end{bmatrix}\\ &\quad=1+1+2+2+3+1+3\\ &\quad=13, \end{aligned} $$ where we have expanded on the first column of the $5\times5$ matrix and each of the resulting $4\times4$ matrices, and have used the method of the previous example on the $3\times3$ matrices.