1986 Putnam A4

A *transversal* of an $n\times n$ matrix $A$ consists of $n$
entries of $A$, no two in the same row or column. Let $f(n)$ be the
number of $n \times n$ matrices $A$ satisfying the following two
conditions:

(a) Each entry $\alpha_{i,j}$ of $A$ is in the set
$\{-1,0,1\}$.

(b) The sum of the $n$ entries of a transversal is the same for
all transversals of $A$.

An example of such a matrix $A$ is

$$

A = \left( \begin{array}{ccc} -1 & 0 & -1 \\ 0 & 1 & 0 \\ 0 & 1 & 0

\end{array}

\right).

$$

Determine with proof a formula for $f(n)$ of the form

$$

f(n) = a_1 b_1^n + a_2 b_2^n + a_3 b_3^n + a_4,

$$

where the $a_i$'s and $b_i$'s are rational numbers.

$n\times n$ 矩阵 $A$ 的*横截面* 由 $n$ 组成

$A$ 的条目，不能有两个在同一行或同一列。设 $f(n)$ 为

满足以下两个条件的 $n \times n$ 矩阵 $A$ 的数量

条件：

(a) $A$ 的每个条目 $\alpha_{i,j}$ 都在集合中

$\{-1,0,1\}$。

(b) 横截面的 $n$ 个条目的总和是相同的
$A$ 的所有横线。

这种矩阵 $A$ 的一个例子是

$$

A = \left( \begin{array}{ccc} -1 & 0 & -1 \\ 0 & 1 & 0 \\ 0 & 1 & 0

\结束{数组}

\右)。

$$

通过证明确定 $f(n)$ 形式的公式

$$

f(n) = a_1 b_1^n + a_2 b_2^n + a_3 b_3^n + a_4,

$$

其中 $a_i$ 和 $b_i$ 是有理数。