MathDB

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}

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

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.

A4